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

Holmgren, Johan; Lindberg, Per Olov · 2013 · OpenAlex-citations

DOI: 10.1007/s13676-013-0031-3

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the computational inefficiency of the Frank-Wolfe (FW) method for solving static vehicular traffic assignment problems, specifically focusing on reducing the time required per iteration. While the FW method has historically dominated this field, its slow asymptotic convergence led many researchers to deem it obsolete. However, recent advancements in Conjugate FW methods have revived its viability, particularly on multi-core systems. The authors argue that while previous improvements focused on reducing the number of iterations, significant speedups can be achieved by reducing the computational work within each iteration. The study introduces "Upright Stiff," a technique that updates subproblems rather than solving them from scratch, thereby accelerating the determination of shortest paths and the loading of all-or-nothing flows. The methodology treats the FW subproblems as network flow problems solved via linear programming techniques, utilizing a threaded representation of shortest path trees. The authors introduce a novel technique called "thread following," which allows for the identification of new shortest path trees through a single traversal of the thread, significantly reducing the overhead of scanning non-basic arcs to verify optimality. Additionally, the approach updates the all-or-nothing solutions directly, avoiding the computationally heavy origin-destination based loading typical of traditional codes. The algorithms were implemented in ANSI C and tested on standard traffic assignment networks, including Barcelona, Winnipeg, Chicago Sketch, and Chicago Regional. Performance was compared against a baseline Mitradjieva-Lindberg FW implementation using OD-based loading. The results demonstrate that subproblem updating yields speedups of 25% to 50% compared to traditional non-updating FW versions. The efficiency gains are more pronounced for difficult problems and converged solutions. Specifically, the "thread following" strategy generally outperformed the "first negative" pivot rule, except in extremely easy networks like Chicago Sketch where pivots were rare. When combined with Bi-Conjugate FW methods, the improvements were even more substantial, achieving speedups of 75% to 99% for high-accuracy requirements. For instance, on the Chicago Regional network, the updated Bi-Conjugate method reduced computation time by over 95% at a relative gap of $10^{-6}$ compared to the standard FW method. The significance of this work lies in revitalizing the FW method for large-scale traffic assignment. By drastically reducing the time per iteration, the proposed techniques make FW competitive with other state-of-the-art algorithms, especially when high precision is required. The findings suggest that integrating subproblem updating with Conjugate FW methods offers a powerful solution for modern traffic modeling, particularly given that several leading software packages already incorporate Conjugate FW approaches. This research provides a practical pathway to enhance the scalability and efficiency of traffic assignment tools without abandoning the established FW framework.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• perceptual countermeasures