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

Direct link
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
URN: urn:nbn:se:liu:diva-2573ISRN: LITH-MAT-EX--04/13--SEOAI: diva2:19908
Available from: 2004-11-05 Created: 2004-11-05

Open Access in DiVA

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

By organisation
Department of Mathematics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1773 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

Total: 870 hits
ReferencesLink to record
Permanent link

Direct link