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
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, p. 205-225Article 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, p. 205-225
Keywords [en]
Traffic assignment, Frank–Wolfe method, Subproblem updating
National Category
Mathematics Computer Sciences
Identifiers
URN: urn:nbn:se:bth-6544DOI: 10.1007/s13676-013-0031-3Local ID: oai:bth.se:forskinfo4A6037B7F785DEB1C1257D95006A7313OAI: oai:DiVA.org:bth-6544DiVA, id: diva2:834062
Available from: 2014-11-20 Created: 2014-11-19 Last updated: 2018-01-11Bibliographically approved

Open Access in DiVA

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

Other links

Publisher's full text

Authority records

Holmgren, Johan

Search in DiVA

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

Search outside of DiVA

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 154 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