Upright Stiff : subproblem updating in the FW method for traffic assignment

• 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.

Ämnesord

TEKNIK OCH TEKNOLOGIER  -- Samhällsbyggnadsteknik -- Transportteknik och logistik (hsv//swe)

ENGINEERING AND TECHNOLOGY  -- Civil Engineering -- Transport Systems and Logistics (hsv//eng)

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Traffic assignment

Frank–Wolfe method

Subproblem updating

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)