An Efficient Algorithm for Continuous Bi-Criteria Traffic Assignment

The continuous bi-criteria traffic assignment (C-BiTA) problem aims to find the distribution of agents with heterogeneous preferences in a network. The agents can be seen as playing a congestion game, and their payoff is a linear combination of time and toll accumulated over the selected path. We rediscover a formulation that enables the development of a novel and highly efficient algorithm. The novelty of the algorithm lies in a decomposition scheme and a special potential function. Together, they reduce a complex assignment problem into a series of single boundary adjustment (SBA) operations, which simply shift flows between “adjacent” efficient paths connecting an origin-destination (O-D) pair by using a projected quasi-Newton method. The SBA algorithm is capable of producing highly detailed path-based solutions that hitherto are not widely available to C-BiTA. Our numerical experiments, which are performed on networks with up to forty thousand links and millions of O-D pairs, confirmed the consistent and significant computational advantage of the SBA algorithm over the Frank-Wolfe algorithm, the widely used benchmark for C-BiTA. In most cases, SBA offers a speed-up of an order of magnitude. We also uncover evidence suggesting the discretization-based approach—or the standard multiclass formulation—is likely to produce far more used paths per O-D pair than C-BiTA, a potential computational disadvantage. Equipped with the proposed algorithm, C-BiTA, as well as its variants and extensions, could become a viable tool for researchers and practitioners seeking to apply multicriteria assignment models on large networks.

Funding: J. Xie was supported by the National Natural Science Foundation of China [Grants 72371205 and 71971178]. J. Li was supported by the National Natural Science Foundation of China [Grant 72501242]. Y. Nie was supported by the United States National Science Foundation (CMMI #2225087).

Supplemental Review: The empirical results in this paper were replicated. The code, data, and files required to reproduce the results were reviewed and are available at https://doi.org/10.1287/opre.2024.0761.