The lack of uniqueness constitutes a serious concern for any analysis that relies on class-specific traffic assignment results, such as understanding the impact of a transport policy on the welfare of travelers from different income groups, sometimes known the vertical equity analysis.  Entropy maximization is a standard approach to consistently selecting a unique class-specific solution for multi-class traffic assignment.

Here, we show the conventional maximum entropy formulation fails to strictly observe the multi-class bi-criteria user equilibrium condition, because a class-specific solution matching the total equilibrium link flow may violate the equilibrium condition. We propose to fix the problem by requiring the class-specific solution, in addition to matching the total equilibrium link flow, also match the objective function value at the equilibrium.  This leads to a new formulation that is solved using an exact algorithm based on dualizing the hard, equilibrium-related constraints.

Our numerical experiments highlight the superior stability of the maximum entropy solution, in that it is affected by a perturbation in inputs much less than an untreated benchmark multi-class assignment solution.  In addition to instability, the benchmark solution also exhibits varying degrees of arbitrariness, potentially rendering it unsuitable for assessing distributional effects across different groups, a capability crucial in applications concerning vertical equity and environmental justice. The proposed formulation and algorithm offer a practical remedy for these shortcomings.

This is the third paper completed by the first author, Qianni Wang, who officially joined my group last year.

The paper was currently under review at Transportation Research Part B.  You may download a preprint here, or read the abstract below.

Abstract: Entropy maximization is a standard approach to consistently selecting a unique class-specific solution for multi-class traffic assignment. Here, we show the conventional maximum entropy formulation fails to strictly observe the multi-class bi-criteria user equilibrium condition, because a class-specific solution matching the total equilibrium link flow may violate the equilibrium condition. We propose to fix the problem by requiring the class-specific solution, in addition to matching the total equilibrium link flow, also match the objective function value at the equilibrium. This leads to a new formulation that is solved using an exact algorithm based on dualizing the hard, equilibrium-related constraints. Our numerical experiments highlight the superior stability of the maximum entropy solution, in that it is affected by a perturbation in inputs much less than an untreated benchmark multi-class assignment solution. In addition to instability, the benchmark solution also exhibits varying degrees of arbitrariness, potentially rendering it unsuitable for assessing distributional effects across different groups, a capability crucial in applications concerning vertical equity and environmental justice. The proposed formulation and algorithm offer a practical remedy for these shortcomings.

The traffic assignment problem (TAP) aims to find the distribution of agents—travelers, goods or data—in a network according to certain rules that govern how the agents make choices and move in the network. This problem lies at the heart of numerous applications, ranging from infrastructure planning to travel demand management. In these applications, it is often important to differentiate the agents according to the governing rules.  The trade-off between two attributes by agents with heterogeneous preferences is ubiquitous in route choice, traffic assignment, congestion games and beyond, and it leads to the bi-criteria traffic assignment (BiTA) problem concerned herein.  In this study, we develop a novel  algorithm to solve a continuous version of the BiTA problem. See Abstract for details.

This is a joint work with my former visiting PhD student and  Postdoc Jun Xie (currently Associate Professor at Southwest Jiaotong University, Chengdu, China) and Qianni Wang, an MS student currently at Northwestern University. The paper is currently under revision at Operations Research; a preprint can be downloaded here.

Abstract: This paper studies the continuous bi-criteria traffic assignment (C-BiTA) problem, which 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 (OD) pair using a 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 OD pairs, confirmed the consistent and significant computational advantage of the SBA algorithm over the Frank-Wolfe (FW) algorithm, the widely-held benchmark for C-BiTA. In most cases, SBA offers a speedup of an order of magnitude.  We also uncovered evidence suggesting the discretization-based approach—or the standard multi-class formulation—-is likely to produce far more used paths per OD 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 multi-criteria assignment models on large networks.