Change search
ReferencesLink to record
Permanent link

Direct link
Upright Stiff: subproblem updating in the FW method for traffic assignment
Blekinge Institute of Technology, School of Computing.
2014 (English)In: EURO Journal on Transportation and Logistics, ISSN 2192-4384 , Vol. 3, no 3, 205-225 p.Article 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 , 2014. Vol. 3, no 3, 205-225 p.
Keyword [en]
Traffic assignment, Frank–Wolfe method, Subproblem updating
National Category
Mathematics Computer Science
URN: urn:nbn:se:bth-6544DOI: 10.1007/s13676-013-0031-3Local ID: diva2:834062
Available from: 2014-11-20 Created: 2014-11-19 Last updated: 2015-06-30Bibliographically approved

Open Access in DiVA

fulltext(384 kB)20 downloads
File information
File name FULLTEXT01.pdfFile size 384 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Holmgren, Johan
By organisation
School of Computing
MathematicsComputer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 20 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: 29 hits
ReferencesLink to record
Permanent link

Direct link