On statistical bounds of heuristic solutions to location problems

Kenneth Carling and Xiangli Meng ()
Additional contact information
Kenneth Carling: Dalarna university
Xiangli Meng: Dalarna university

Journal of Combinatorial Optimization, 2016, vol. 31, issue 4, No 12, 1518-1549

Abstract: Abstract 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.

Keywords: $$p$$ p -Median problem; Simulated annealing; Jackknife; Discrete optimization; Extreme value theory (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9839-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:4:d:10.1007_s10878-015-9839-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9839-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().