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
Confidence in heuristic solutions?
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 frequently rely on heuristics to minimize an objective function. The optimum is sought iteratively and pre-setting the number of iterations dominates in operations research applications, which implies that the quality of the solution cannot be ascertained. Deterministic bounds offer a mean of ascertaining the quality, but such bounds are available for only a limited number of heuristics and the length of the interval may be difficult to control in an application. A small, almost dormant, branch of the literature suggests using statistical principles to derive statistical bounds for the optimum. We discuss alternative approaches to derive statistical bounds. We also assess their performance by testing them on 40 test p-median problems on facility location, taken from Beasley’s OR-library, for which the optimum is known. We consider three popular heuristics for solving such location problems; simulated annealing, vertex substitution, and Lagrangian relaxation where only the last offers deterministic bounds. Moreover, we illustrate statistical bounds in the location of 71 regional delivery points of the Swedish Post. We find statistical bounds reliable and much more efficient than deterministic bounds provided that the heuristic solutions are sampled close to the optimum. Statistical bounds are also found computationally affordable.

Ort, förlag, år, upplaga, sidor
Borlänge: Högskolan Dalarna, 2014. , s. 26
Serie
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2014:12
Nationell ämneskategori
Ekonomisk geografi Sannolikhetsteori och statistik
Forskningsämne
Komplexa system - mikrodataanalys
Identifikatorer
URN: urn:nbn:se:du-14457OAI: oai:DiVA.org:du-14457DiVA, id: diva2:727755
Tillgänglig från: 2014-06-23 Skapad: 2014-06-23 Senast uppdaterad: 2015-05-07Bibliografiskt granskad

Open Access i DiVA

Confidence in heuristic solutions(1068 kB)171 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1068 kBChecksumma SHA-512
8db36920f35f9d76dd5b02ef6043c7d0ae0b03920f56718855978c2794a4100bba81e4f366c989ae0477344243584a8af61e573022a6a781db6a93c5c04978b9
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
Ekonomisk geografiSannolikhetsteori och statistik

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: 903 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