liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Efficient Updating Shortest Path Calculations for Traffic Assignment
Linköping University, Department of Mathematics.
2004 (English)Independent thesis Basic level (professional degree)Student thesis
Abstract [en]

Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world.

This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions.

These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.

Place, publisher, year, edition, pages
Matematiska institutionen , 2004.
Keyword [en]
Mathematical optimization, systems theory, Traffic Assignment, Frank-Wolfe Method, Shortest Path Problem, Network Simplex, Bucket Pricing, Conjugate Search Directions
Keyword [sv]
Optimeringslära, systemteori
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-2573ISRN: LITH-MAT-EX--04/13--SEOAI: oai:DiVA.org:liu-2573DiVA: diva2:19908
Uppsok
fysik/kemi/matematik
Available from: 2004-11-05 Created: 2004-11-05

Open Access in DiVA

fulltext(453 kB)2035 downloads
File information
File name FULLTEXT01.pdfFile size 453 kBChecksum MD5
997f18a40394b43757111b44ed87dc6ca9b5103cd6864eefce4186594b2d176a6b9e1d34
Type fulltextMimetype application/pdf

By organisation
Department of Mathematics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 2035 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: 890 hits
CiteExportLink to record
Permanent link

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