du.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On transforming a road network database to a graph for localization purpose
Dalarna University, School of Technology and Business Studies, Statistics.ORCID iD: 0000-0003-2970-9622
Dalarna University, School of Technology and Business Studies, Computer Engineering.ORCID iD: 0000-0003-1015-8015
2016 (English)In: International Journal of Web Services Research, ISSN 1545-7362, E-ISSN 1546-5004, Vol. 13, no 2, 46-55 p.Article in journal (Refereed) Published
Abstract [en]

The problems of finding best facility locations require complete and accurate road networks with the corresponding population data in a specific area. However the data obtained from road network databases usually do not fit in this usage. In this paper we propose a procedure of converting the road network database to a road graph which could be used for localization problems. Several challenging problems exist in the transformation process which are commonly met also in other data bases. The procedure of dealing with those challenges are proposed. The data come from the National road data base in Sweden. The graph derived is cleaned, and reduced to a suitable level for localization problems. The residential points are also processed in ordered to match the graph. The reduction of the graph is done maintaining the accuracy of distance measures in the network.

Place, publisher, year, edition, pages
2016. Vol. 13, no 2, 46-55 p.
Keyword [en]
road network, graph, population, GIS
National Category
Economic Geography
Research subject
Complex Systems – Microdata Analysis
Identifiers
URN: urn:nbn:se:du-17361DOI: 10.4018/IJWSR.2016040103ISI: 000384810100004OAI: oai:DiVA.org:du-17361DiVA: diva2:810572
Available from: 2015-05-07 Created: 2015-05-07 Last updated: 2016-11-03Bibliographically approved
In thesis
1. Optimization heuristic solutions, how good can they be?: With empirical applications in location problems
Open this publication in new window or tab >>Optimization heuristic solutions, how good can they be?: With empirical applications in location problems
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Borlänge: Högskolan Dalarna, 2015. 200 p.
Series
Dalarna Doctoral Dissertations, 2
National Category
Computational Mathematics
Research subject
Komplexa system - mikrodataanalys
Identifiers
urn:nbn:se:du-17353 (URN)978-91-89020-94-8 (ISBN)
Public defence
2015-04-23, Clas Ohlson, Borlänge, 10:00 (English)
Opponent
Available from: 2015-05-07 Created: 2015-05-06 Last updated: 2015-05-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Meng, XiangliRebreyend, Pascal
By organisation
StatisticsComputer Engineering
In the same journal
International Journal of Web Services Research
Economic Geography

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 562 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf