Change search
ReferencesLink to record
Permanent link

Direct link
Upright Stiff: subproblem updating in the FW method for traffic assignment
Blekinge Tekniska Högskola. (datavetenskap och kommunikation)
KTH, School of Architecture and the Built Environment (ABE), Transport Science, Transport and Location Analysis.
2013 (English)In: EURO Journal on Transportation and Logistics, ISSN 2192-4376Article in journal (Refereed) Published
Abstract [en]

We present improvements of the Frank–Wolfe (FW) method for static vehicular traffic and telecom routing. The FW method has been the dominating method for these problem types, but due to its slow asymptotic convergence it has been considered dead by methods oriented researchers. However, the recent introduction of conjugate FW methods has shown that it is still viable, and in fact the winner on multi-core computers. In this paper, we show how to speed up the FW iterations, by updating the subproblems in the FW method, instead of solving them from scratch. The subproblem updating is achieved by viewing the subproblems as network flow problems with a threaded representation of the shortest path trees. In addition, we introduce a new technique, thread following, implying that a single traversal of the thread is enough to find a new shortest path tree. Our computational tests show that very few nodes in practice are visited more than once when searching for improving arcs. Moreover, we update also the all-or-nothing solutions of the subproblems, resulting in significantly reduced loading times. For a set of standard test problems, we observe speedups in the region of 25–50 % for the subproblem updating FW method, compared to the traditional non-updating version. We typically achieve higher speedups for more difficult problems and converged solutions.

Place, publisher, year, edition, pages
Springer Berlin/Heidelberg, 2013.
Keyword [en]
Traffic assignment, Frank–Wolfe method, Subproblem updating
National Category
Transport Systems and Logistics
URN: urn:nbn:se:kth:diva-129950DOI: 10.1007/s13676-013-0031-3OAI: diva2:653749

QC 20140120

Available from: 2013-10-05 Created: 2013-10-05 Last updated: 2014-06-02Bibliographically approved

Open Access in DiVA

Upright(1086 kB)118 downloads
File information
File name FULLTEXT01.pdfFile size 1086 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lindberg, Per Olov
By organisation
Transport and Location Analysis
In the same journal
EURO Journal on Transportation and Logistics
Transport Systems and Logistics

Search outside of DiVA

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

Altmetric score

Total: 88 hits
ReferencesLink to record
Permanent link

Direct link