du.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Statistical bound of genetic solutions to quadratic assignment problems
Högskolan Dalarna, Akademin Industri och samhälle, Statistik.ORCID-id: 0000-0003-2970-9622
2015 (engelsk)Rapport (Annet vitenskapelig)
Abstract [en]

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones. 

sted, utgiver, år, opplag, sider
Borlänge: Högskolan Dalarna, 2015. , s. 20
Serie
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2015:02
Emneord [en]
quadratic assignment problem, genetic algorithm, Jack-knife, discrete optimization, extreme value theory
HSV kategori
Forskningsprogram
Komplexa system - mikrodataanalys
Identifikatorer
URN: urn:nbn:se:du-17034OAI: oai:DiVA.org:du-17034DiVA, id: diva2:791806
Tilgjengelig fra: 2015-03-02 Laget: 2015-03-02 Sist oppdatert: 2018-01-11bibliografisk kontrollert
Inngår i avhandling
1. Optimization heuristic solutions, how good can they be?: With empirical applications in location problems
Åpne denne publikasjonen i ny fane eller vindu >>Optimization heuristic solutions, how good can they be?: With empirical applications in location problems
2015 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Borlänge: Dalarna University, 2015. s. 200
Serie
Dalarna Doctoral Dissertations in Microdata Analysis ; 2
HSV kategori
Forskningsprogram
Komplexa system - mikrodataanalys
Identifikatorer
urn:nbn:se:du-17353 (URN)978-91-89020-94-8 (ISBN)
Disputas
2015-04-23, Clas Ohlson, Borlänge, 10:00 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2015-05-07 Laget: 2015-05-06 Sist oppdatert: 2019-06-17bibliografisk kontrollert

Open Access i DiVA

fulltext(1131 kB)103 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 1131 kBChecksum SHA-512
341773ef8c0f627c7b0022a61bf427f66ac9298f46cb666afb836d6049bd4098d27abbf2c94b6a412c74641a322823e6ffa6fcac98cfe51ce19f6ca2d5b605ba
Type fulltextMimetype application/pdf

Personposter BETA

Meng, Xiangli

Søk i DiVA

Av forfatter/redaktør
Meng, Xiangli
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 103 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

urn-nbn

Altmetric

urn-nbn
Totalt: 935 treff
RefereraExporteraLink to record
Permanent link

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