Large-scale multiclass traffic assignment: leveraging the pareto frontier for discrete and continuous problems

Abstract

Modern urban transportation networks offer travelers unprecedentedly diversified travel options and personalized route guidance. For instance, apps like Google Maps and Waze can provide distance, toll charges, speed limits, and real-time traffic congestion information on different routes to travelers. Therefore, in real life, individual travelers may consider different criteria of travel options and make travel decisions in a way that is more customized to their own preferences. Meanwhile, travelers exhibit significant heterogeneity in preferences, such as different values of time (VOT) and risk preferences, influenced by their socio-economic status, trip purposes, or simply personal characteristics. Empirical studies revealed the limitations of homogeneous transport models and underscore the importance of accounting for travelers' heterogeneous preferences in transport models to facilitate a more disaggregate representation of individual choices. Traffic assignment (TA) is a fundamental tool for planning and managing urban and regional transportation networks. It aims to predict the spatial distribution of traffic flows on the network by analyzing and aggregating the route choices of numerous travelers. Integrating traveler preference heterogeneity into TA can relax the simplistic route choice assumption that all travelers select the shortest route, leading to the development of multiclass traffic assignment (MCTA) models. Compared to the standard TA models, the MCTA models can not only improve the prediction accuracy of network flows but also enable analyzing different travelers' responses to potential traffic planning projects and policies, supporting real-world applications from traditional ones like toll design to emerging challenges like evaluating the impacts of connected and autonomous vehicles. Nevertheless, incorporating preference heterogeneity into TA models also introduces many model and solution challenges, such as increased model complexity and solution inefficiency. This thesis focuses on the long-standing topic of transportation network equilibrium with heterogeneous users. The main contribution lies in the development of advanced discrete and continuous MCTA models and algorithms that skillfully leverage both supply-side (Pareto fron­tier of network paths) and demand-side (preference distribution of users) information, making the developed models and algorithms applicable to large-scale transportation networks. The thesis consists of four key studies: 1. Modeling user heterogeneity in congested transportation networks: A review of discrete and continuous approaches. MCTA models can be broadly classified into discrete and continuous, depending on whether heterogeneity is represented via finite classes or continuous distributions. This study reviews 108 studies (1979-2025) on the model developments, solution algorithms, and applications of discrete and continuous MCTA models. This review not only categorizes the literature along discrete and continuous paradigms but also identifies critical research gaps and emerging trends, particularly highlighting recent methodological breakthroughs that achieve single-class computational complexity for certain MCTA problems. 2. Discrete and continuous multiclass bi-criteria traffic assignment problems: A unified gradient projection algorithm. This study develops a unified path-based gradient projection algorithm that simultaneously addresses both discrete and continuous multiclass bi-criteria traffic assignment problems. The algorithm incorporates three specialized modules for column generation, equilibration, and convergence testing, each customized for the distinctive characteristics of discrete and continuous formulations. Numerical experiments demonstrate the algorithm's computational efficiency while showing the convergence relationship between discrete and continuous solutions as the number of user classes increases. 3. Discrete multiclass bi-criteria traffic assignment without class-specific variables: An alternative formulation and a subgradient projection algorithm. This study introduces an alternative formulation for the discrete MCTA problem that eliminates the need for class-specific variables through innovative exploitation of the order relationship between path preferences and traveler characteristics. This approach recognizes that high-VOT travelers prefer faster, more expensive routes while low-VOT travelers favor slower, cheaper alternatives. The resulting model maintains mathematical equivalence with conventional formulations while achieving dramatic reductions in variable counts, accompanied by a specialized subgradient projection algorithm that efficiently handles the non-differentiable convex objective function. 4. Continuous multiclass mean-risk traffic assignment problem: both criteria are flow-dependent. This study extends the continuous MCTA framework to address the challenging mean-risk traffic assignment problem with flow-dependent criteria. By introducing the novel concept of cumulative path costs and modeling risk-aversion through continuous distributions, we develop finite-dimensional complementarity conditions that avoid the curse of dimensionality. The accompanying computational framework combines path-based column generation with gradient projection methods, demonstrating superior performance in capturing nuanced risk-averse behaviors while maintaining computational tractability for large-scale networks. Collectively, this thesis contributes to the modeling and computation of transportation network equilibrium with heterogeneous users. It develops advanced mathematical models and solution algorithms for both the discrete and continuous MCTA problems, providing researchers and practitioners with enhanced analytical tools for capturing user heterogeneity in congested transportation systems. Ultimately, these tools can be applied to a wide range of applications to support the planning of innovative urban mobility solutions.