Change search
ReferencesLink to record
Permanent link

Direct link
On statistical bounds of heuristic solutions to location problems
Dalarna University, School of Technology and Business Studies, Statistics.ORCID iD: 0000-0003-2317-9157
Dalarna University, School of Technology and Business Studies, Statistics.ORCID iD: 0000-0003-2970-9622
2014 (English)Report (Other academic)
Abstract [en]

Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region. 

Place, publisher, year, edition, pages
Borlänge: Högskolan Dalarna, 2014.
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2014:10
Keyword [en]
p-median problem, simulated annealing, jack-knife, discrete optimization, extreme value theory
National Category
Probability Theory and Statistics Computer Science
Research subject
Komplexa system - mikrodataanalys
URN: urn:nbn:se:du-14135OAI: diva2:719712
Swedish Retail and Wholesale Development Council
Available from: 2014-05-26 Created: 2014-05-26 Last updated: 2015-05-07Bibliographically approved

Open Access in DiVA

On statistical bounds of heuristic solutions(2017 kB)79 downloads
File information
File name FULLTEXT01.pdfFile size 2017 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Carling, KennethMeng, Xiangli
By organisation
Probability Theory and StatisticsComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 79 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 641 hits
ReferencesLink to record
Permanent link

Direct link