How to Decide Upon Stopping a Heuristic Algorithm in Facility-Location Problems?

详细信息    查看全文

• 作者：Xiangli Meng (20)
  Kenneth Carling (20)
  
• 关键词：p ; median problem ; Simulated Annealing ; discrete optimization ; extreme value theory
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8182
• 期：1
• 页码：280-283
• 全文大小：199 KB
• 参考文献：1. Beasley, J.E.: OR library: Distributing test problems by electronic mail. Journal of Operational Research Society, 41聽41(11), 1067鈥?072 (1990)
  2. Chiyoshi, F.Y., Galv茫o, R.D.: A statistical analysis of simulated annealing applied to the p-median problem. Annals of Operations Research聽96, 61鈥?4 (2000) CrossRef
  3. Dannenbring, D.G.: Procedures for estimating optimal solution values for large combinatorial problems. Management Science聽23(12), 1273鈥?283 (1977) CrossRef
  4. Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research聽12(3), 450鈥?59 (1964) CrossRef
  5. Hakimi, S.L.: Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems. Operations Research聽13(3), 462鈥?75 (1965) CrossRef
  6. Kotz, S., Nadarajah, S.: Extreme value distributions, theory and applications. Imperial College Press (2000)
  7. Levanova, T., Loresh, M.A.: Algorithm of ant system and simulated annealing for the p-median problem. Automation and Remote Control聽65, 431鈥?38 (2004) CrossRef
  8. Quenouille, M.H.: Notes on bias in estimation. Biometrika聽43, 353鈥?60 (1956)
  9. Robson, D.S., Whitlock, J.H.: Estimation of a truncation point. Biometrika聽51, 33鈥?9 (1964)
  10. Wilson, A.D., King, R.E., Wilson, J.R.: Case study on statistically estimating minimum makespan for flow line scheduling problems. European Journal of Operational Research聽155, 439鈥?54 (2004) CrossRef
  11. Zhigljavsky, A., Hamilton, E.: Stopping rules in k-adaptive global random search algorithms. Journal of Global Optimization聽48(1), 87鈥?7 (2010) CrossRef
  
• 作者单位：Xiangli Meng (20)
  Kenneth Carling (20)
  
  20. School of Technology and Business Studies, Dalarna university, SE-791 88, Falun, Sweden
  
• ISSN：1611-3349

文摘

Solutions to combinatorial optimization, such as p-median problems of locating facilities, frequently rely on heuristics to minimize the objective function. The minimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. However, pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. In this paper we compare the methods proposed previous literate of estimating minimum, and propose some thought of it.