Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
How does data quality in a network affect heuristic solutions?
Dalarna University, School of Technology and Business Studies, Statistics.
Dalarna University, School of Technology and Business Studies, Information Systems.ORCID iD: 0000-0003-4871-833X
Dalarna University, School of Technology and Business Studies, Computer Engineering.ORCID iD: 0000-0003-1015-8015
2014 (English)Report (Other academic)
Abstract [en]

To have good data quality with high complexity is often seen to be important. Intuition says that the higher accuracy and complexity the data have the better the analytic solutions becomes if it is possible to handle the increasing computing time. However, for most of the practical computational problems, high complexity data means that computational times become too long or that heuristics used to solve the problem have difficulties to reach good solutions. This is even further stressed when the size of the combinatorial problem increases. Consequently, we often need a simplified data to deal with complex combinatorial problems. In this study we stress the question of how the complexity and accuracy in a network affect the quality of the heuristic solutions for different sizes of the combinatorial problem. We evaluate this question by applying the commonly used

p-median model, which is used to find optimal locations in a network of p supply points that serve n demand points. To evaluate this, we vary both the accuracy (the number of nodes) of the network and the size of the combinatorial problem (p).

The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 supply points we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000 (which is aggregated from the 1.5 million nodes). To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited

improvement in the optimal solutions when the accuracy in the road network increase and the combinatorial problem (low

p) is simple. When the combinatorial problem is complex (large p) the improvements of increasing the accuracy in the road network are much larger. The results also show that choice of the best accuracy of the network depends on the complexity of the combinatorial (varying p) problem.

Place, publisher, year, edition, pages
Borlänge: Högskolan Dalarna, 2014. , 19 p.
Series
Working papers in transport, tourism, information technology and microdata analysis, ISSN 1650-5581 ; 2014:08
Keyword [en]
complex networks, p-median model, simulated annealing heuristics
National Category
Other Social Sciences not elsewhere specified
Research subject
Complex Systems – Microdata Analysis
Identifiers
URN: urn:nbn:se:du-14054OAI: oai:DiVA.org:du-14054DiVA: diva2:714722
Available from: 2014-04-29 Created: 2014-04-29 Last updated: 2015-12-16Bibliographically approved

Open Access in DiVA

How does data quality in a network affect heuristic solutions?(762 kB)83 downloads
File information
File name FULLTEXT01.pdfFile size 762 kBChecksum SHA-512
0dc60a54a3cf389a4425f61e75281e45dae03025c8e1079cc37826469fb9ff9f47e88255405daa377e0a5d64ef8f1eb9eb54455414d522906e9d80c43011471a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Han, MengjieHåkansson, JohanRebreyend, Pascal
By organisation
StatisticsInformation SystemsComputer Engineering
Other Social Sciences not elsewhere specified

Search outside of DiVA

GoogleGoogle Scholar
Total: 83 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 906 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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