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
2014 (Engelska)Rapport (Övrigt vetenskapligt)
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
Borlänge: Högskolan Dalarna, 2014.
Serie
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2014:10
Nyckelord [en]
p-median problem, simulated annealing, jack-knife, discrete optimization, extreme value theory
Nationell ämneskategori
Sannolikhetsteori och statistik Datavetenskap (datalogi)
Forskningsämne
Komplexa system - mikrodataanalys
Identifikatorer
URN: urn:nbn:se:du-14135OAI: oai:DiVA.org:du-14135DiVA, id: diva2:719712
Forskningsfinansiär
Handelns utvecklingsrådTillgänglig från: 2014-05-26 Skapad: 2014-05-26 Senast uppdaterad: 2018-01-11Bibliografiskt granskad

Open Access i DiVA

On statistical bounds of heuristic solutions(2017 kB)171 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 2017 kBChecksumma SHA-512
624a6ff1cfb697ed80e215ed6d90ae74e795224de9276cca54acb3a97e2ad5863a312616bb7def973a5afec97a291ab62032ace6cb4c1d9ea6cd6fc575a91202
Typ fulltextMimetyp application/pdf

Personposter BETA

Carling, KennethMeng, Xiangli

Sök vidare i DiVA

Av författaren/redaktören
Carling, KennethMeng, Xiangli
Av organisationen
Statistik
Sannolikhetsteori och statistikDatavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 171 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 879 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