On statistical bounds of heuristic solutions to location problems

详细信息    查看全文

• 作者：Kenneth Carling ; Xiangli Meng
• 关键词：\(p\) ; Median problem ; Simulated annealing ; Jackknife ; Discrete optimization ; Extreme value theory
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：31
• 期：4
• 页码：1518-1549
• 全文大小：753 KB
• 参考文献：Akyüz MH, Öncan T, Altınel IK (2012) Efficient approximate solution methods for the multi-commodity capacitated multi-facility Weber problem. Comput Oper Res 39(2):225–237MathSciNet CrossRef MATH
  Beasley JE (1990) OR library: distributing test problems by electronic mail. J Oper Res Soc 41(11):1067–1072CrossRef
  Beasley JE (1993) Lagrangian heuristics for location problems. Eur J Oper Res 65:383–399CrossRef MATH
  Brandeau ML, Chiu SS (1993) Sequential location and allocation: worst case performance and statistical estimation. Locat Sci 1:289–298MATH
  Carling K, Han M, Håkansson J (2012) Does Euclidean distance work well when the \(p\) -median model is applied in rural areas? Ann Oper Res 201(1):83–97MathSciNet CrossRef MATH
  Carling K, Meng X (2014) Confidence in heuristic solutions? Working papers in transport, tourism, information technology and microdata analysis. http://​du.​diva-portal.​org/​smash/​record.​jsf?​pid=​diva2%3A727755&​dswid=​-6054
  Chiyoshi FY, Galvão RD (2000) A statistical analysis of simulated annealing applied to the p-median problem. Ann Oper Res 96:61–74CrossRef MATH
  Cureton EE (1968) Unbiased estimation of the standard deviation. Am Stat 22(1):22
  Dannenbring DG (1977) Procedures for estimating optimal solution values for large combinatorial problems. Manag Sci 23(12):1273–1283CrossRef MATH
  Daskin MS (1995) Network and discrete location: models, algorithms, and applications. Wiley, New YorkCrossRef MATH
  Derigs U (1985) Using confidence limits for the global optimum in combinatorial optimization. Oper Res 33(5):1024–1049MathSciNet CrossRef MATH
  Efron B (1979) Bootstrap methods: another look at the Jackknife. Ann Stat 7(1):1–26MathSciNet CrossRef MATH
  Golden BL, Alt FB (1979) Interval estimation of a global optimum for large combinatorial optimization. Oper Res 33(5):1024–1049MATH
  Hakimi SL (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper Res 12(3):450–459CrossRef MATH
  Hakimi SL (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper Res 13(3):462–475MathSciNet CrossRef MATH
  Handler GY, Mirchandani PB (1979) Location on networks: theorem and algorithms. MIT Press, CambridgeMATH
  Han M, Håkansson J, Rebreyend P (2013) How do different densities in a network affect the optimal location of service centers?. Working papers in transport, tourism, information technology and microdata analysis 2013:15
  Kotz S, Nadarajah S (2000) Extreme value distributions, theory and applications. Imperial College Press, LondonCrossRef MATH
  Levanova T, Loresh MA (2004) Algorithm of ant system and simulated annealing for the p-median problem. Autom Remote Control 65:431–438CrossRef MATH
  Luis M, Sahli S, Nagy G (2009) Region-rejection based heuristics for the capacitated multi-source Weber problem. Comput Oper Res 36:2007–2017CrossRef MATH
  McRobert KL (1971) A search model for evaluating combinatorially explosive problems. Oper Res 19:1331–1349CrossRef MATH
  Nydick RL, Weiss HJ (1988) A computational evaluation of optimal solution value estimation procedures. Comput Oper Res 5:427–440CrossRef MATH
  Quenouille MH (1956) Notes on bias in estimation. Biometrika 43:353–360MathSciNet CrossRef MATH
  Reese J (2006) Solution methods for the p-median problem: An annotated bibliography. Networks 48:125–142MathSciNet CrossRef MATH
  Robson DS, Whitlock JH (1964) Estimation of a truncation point. Biometrika 51:33–39MathSciNet CrossRef MATH
  Wilson AD, King RE, Wilson JR (2004) Case study on statistically estimating minimum makespan for flow line scheduling problems. Eur J Oper Res 155:439–454MathSciNet CrossRef MATH
  
• 作者单位：Kenneth Carling (1)
  Xiangli Meng (1)
  
  1. School of Technology and Business Studies, Dalarna university, 791 88, Falun, Sweden
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Combinatorial optimization problems such as locating facilities frequently rely on heuristics to minimize the objective function. The optimum is often sought iteratively; a criterion is therefore necessary to be able to decide when the procedure attains such an optimum. Pre-setting the number of iterations is dominant in OR applications, however, the fact that the quality of the solution cannot be ascertained by pre-setting the number of iterations makes it less preferable. A small and, almost dormant, branch of the literature suggests usage of statistical principles to estimate the minimum and its bounds as a tool to decide upon the stopping criteria and also to evaluate the quality of the solution. In the current work we have examined the functioning of statistical bounds obtained from four different estimators using simulated annealing. P-median test problems taken from Beasley’s OR-library were used for the sake of testing. Our findings show that the Weibull estimator and 2nd order Jackknife estimators are preferable and the requirement of sample size to be about 10. It should be noted that reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality; we have therefore provided a simple statistic for checking the quality. The work finally concludes with an illustration of applying statistical bounds to the problem of locating 70 post distribution centers in a region in Sweden.