A unified gradient projection algorithm for solving both discrete and continuous multiclass bi-criteria traffic assignment problems

Abstract

The multiclass bi-criteria traffic assignment (MBTA) problem considers travelers’ bi-criteria (time and toll) route choice behaviors and user heterogeneity. The MBTA models can be classified as discrete or continuous based on whether the value of time (VOT) is modeled as a discrete or continuous variable. While both models have been suggested in the literature, their connections and differences remain underexplored. This study compares the discrete MBTA (DMBTA) and continuous MBTA (CMBTA) models and proposes a unified path-based gradient projection (GP) algorithm framework to solve both models. In the unified framework, three modules, including column generation, decomposition and equilibration, and convergence criteria, are customized for discrete and continuous models, respectively. With appropriate algorithmic designs, both problems can be solved effectively by the path-based GP algorithm. Extensive numerical experiments show that the equilibrium flow of the DMBTA model will fluctuate when the number of classes is small, and it will converge to the equilibrium flow of the CMBTA model with the increase in the number of classes. Additionally, in all test networks, the CMBTA model requires CPU time comparable to the DMBTA model with five classes and maintains a working path set smaller than that of the DMBTA model with three classes, demonstrating that the CMBTA model can achieve a refined solution with modest computational time and memory requirements.