du.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On statistical bounds of heuristic solutions to location problems
Högskolan Dalarna, Akademin Industri och samhälle, Statistik.ORCID-id: 0000-0003-2317-9157
Högskolan Dalarna, Akademin Industri och samhälle, Statistik.ORCID-id: 0000-0003-2970-9622
2016 (Engelska)Ingår i: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 31, nr 4, s. 1518-1549Artikel i tidskrift (Refereegranskat) Published
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.

Ort, förlag, år, upplaga, sidor
2016. Vol. 31, nr 4, s. 1518-1549
Nyckelord [en]
p-median problem;simulated annealing; jack-knife; discrete optimization; extreme value theory
Nationell ämneskategori
Sannolikhetsteori och statistik
Forskningsämne
Komplexa system - mikrodataanalys, Allmänt Mikrodataaanalys - metod
Identifikatorer
URN: urn:nbn:se:du-16828DOI: 10.1007/s10878-015-9839-0ISI: 000373574300012OAI: oai:DiVA.org:du-16828DiVA, id: diva2:787256
Tillgänglig från: 2015-02-09 Skapad: 2015-02-09 Senast uppdaterad: 2017-12-04Bibliografiskt granskad
Ingår i avhandling
1. Optimization heuristic solutions, how good can they be?: With empirical applications in location problems
Öppna denna publikation i ny flik eller fönster >>Optimization heuristic solutions, how good can they be?: With empirical applications in location problems
2015 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Combinatorial optimization problems, are one of the most important types of problems in operational research. Heuristic and metaheuristics algorithms are widely applied to find a good solution. However, a common problem is that these algorithms do not guarantee that the solution will coincide with the optimum and, hence, many solutions to real world OR-problems are afflicted with an uncertainty about the quality of the solution. The main aim of this thesis is to investigate the usability of statistical bounds to evaluate the quality of heuristic solutions applied to large combinatorial problems. The contributions of this thesis are both methodological and empirical. From a methodological point of view, the usefulness of statistical bounds on p-median problems is thoroughly investigated. The statistical bounds have good performance in providing informative quality assessment under appropriate parameter settings. Also, they outperform the commonly used Lagrangian bounds. It is demonstrated that the statistical bounds are shown to be comparable with the deterministic bounds in quadratic assignment problems. As to empirical research, environment pollution has become a worldwide problem, and transportation can cause a great amount of pollution. A new method for calculating and comparing the CO2-emissions of online and brick-and-mortar retailing is proposed. It leads to the conclusion that online retailing has significantly lesser CO2-emissions. Another problem is that the Swedish regional division is under revision and the border effect to public service accessibility is concerned of both residents and politicians. After analysis, it is shown that borders hinder the optimal location of public services and consequently the highest achievable economic and social utility may not be attained.

Abstract [sv]

Kombinatoriska optimeringsproblem, är en av de viktigaste typerna av problem i operationsanalys (OR). Heuristiska och metaheuristiska algoritmer tillämpas allmänt för att hitta lösningar med hög kvalitet. Ett vanligt problem är dock att dessa algoritmer inte garanterar optimala lösningar och sålunda kan det finnas osäkerhet i kvaliteten på lösningar på tillämpade operationsanalytiska problem. Huvudsyftet med denna avhandling är att undersöka användbarheten av statistiska konfidensintervall för att utvärdera kvaliteten på heuristiska lösningar då de tillämpas på stora kombinatoriska optimeringsproblem. Bidragen från denna avhandling är både metodologiska och empiriska. Ur metodologisk synvinkel har nyttan av statistiska konfidensintervall för ett lokaliseringsproblem (p-median problemet) undersökts. Statistiska konfidensintervall fungerar väl för att tillhandahålla information om lösningens kvalitet vid rätt implementering av problemen. Statistiska konfidensintervall överträffar även intervallen som erhålls vid den vanligen använda Lagrange-relaxation. I avhandlingen visas även på att metoden med statistiska konfidensintervall är fungerar väl jämfört med många andra deterministiska intervall i ett mer komplexa optimeringsproblem som det kvadratiska tilldelningsproblemet. P-median problemet och de statistiska konfidensintervallen har implementerats empiriskt för att beräkna och jämföra e-handelns och traditionell handels CO2-utsläpp från transporter, vilken visar att ehandel medför betydligt mindre CO2-utsläpp. Ett annat lokaliseringsproblem som analyserats empiriskt är hur förändringar av den regionala administrativa indelningen av Sverige, vilket är en aktuell och pågående samhällsdiskussion, påverkar medborgarnas tillgänglighet till offentlig service. Analysen visar att regionala administrativa iv gränserna lett till en suboptimal placering av offentliga tjänster. Därmed finns en risk att den samhällsekonomiska nyttan av dessa tjänster är suboptimerad.

Ort, förlag, år, upplaga, sidor
Borlänge: Dalarna University, 2015. s. 200
Serie
Dalarna Doctoral Dissertations in Microdata Analysis ; 2
Nationell ämneskategori
Beräkningsmatematik
Forskningsämne
Komplexa system - mikrodataanalys
Identifikatorer
urn:nbn:se:du-17353 (URN)978-91-89020-94-8 (ISBN)
Disputation
2015-04-23, Clas Ohlson, Borlänge, 10:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2015-05-07 Skapad: 2015-05-06 Senast uppdaterad: 2019-06-17Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Carling, KennethMeng, Xiangli

Sök vidare i DiVA

Av författaren/redaktören
Carling, KennethMeng, Xiangli
Av organisationen
Statistik
I samma tidskrift
Journal of combinatorial optimization
Sannolikhetsteori och statistik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 659 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf