From Optimization to Prediction: Transformer-Based Path-Flow Estimation to the Traffic Assignment Problem

Technical Summary: From Optimization to Prediction: Transformer-Based Path-Flow Estimation to the Traffic Assignment Problem

1. Problem Statement

The Traffic Assignment Problem (TAP) is a cornerstone of transportation planning, aimed at determining how traffic flows distribute across a network based on travel demand between Origin-Destination (OD) pairs. Traditionally, this is solved using mathematical optimization to reach User Equilibrium (UE), where no driver can reduce their travel time by unilaterally changing routes.

However, traditional optimization methods (e.g., Frank-Wolfe, Gradient methods) face two critical bottlenecks:

• Computational Complexity: The complexity grows non-linearly with the number of OD pairs and feasible paths, making large-scale network analysis prohibitively slow.
• Lack of Flexibility: Any change in demand (e.g., a new policy) or network topology (e.g., a road closure) requires the entire optimization process to be recalculated from scratch, preventing real-time "what-if" analysis.

2. Methodology

The authors propose a shift from optimization to prediction by employing a deep learning approach. Instead of solving an iterative mathematical program, they train a model to directly predict the optimal path-flow distribution.

Key Architectural Features:

• Transformer-Based Encoder-Decoder: Unlike previous Graph Neural Network (GNN) approaches that rely on local message passing (limiting their ability to capture long-range dependencies), this model uses global self-attention. This allows the model to capture intricate correlations between distant OD pairs across the entire network.
• Path-Level Formulation: Most existing ML models predict link flows. This model predicts path flows directly. This aligns with the game-theoretic nature of UE (where travelers choose paths) and ensures that OD-level flow conservation is implicitly satisfied by the model's design.
• Input Representation: The model takes a normalized input tensor containing graph information (link length, capacity), free-flow travel times, OD demand matrices, and encoded feasible path information.
• Multi-Head Attention: The Encoder processes the network/demand context, while the Decoder uses that context to generate the predicted path-flow distribution.

3. Key Contributions

1. Novel Architecture: The first TAP framework to utilize a Transformer-based sequence learning architecture integrating both encoder and decoder global attention.
2. Path-Based Learning: By learning in the path-flow space, the model inherently preserves flow conservation and capacity constraints without needing explicit post-processing or iterative enforcement.
3. Robustness to Perturbations: The model is designed to handle "joint supply-demand perturbations," meaning it can function even when both the demand data (OD matrix) and the network structure (links) are incomplete or changing.
4. Scalability: It provides a high-speed surrogate for traditional solvers, enabling rapid scenario testing.

4. Experimental Results

The model was tested on synthetic (Manhattan-like) and real-world urban networks (Sioux Falls, Eastern Massachusetts, and Anaheim).

• Speed: The Transformer model is orders of magnitude faster than traditional solvers. For the EMA network, it was ~5,000 times faster than Gurobi; for the Anaheim network, it was >20,000 times faster.
• Accuracy:
  • In the Manhattan-like network with 30% missing OD data, the Path Flow MAPE was only 5.50%.
  • In multi-class scenarios (cars and trucks), it achieved high accuracy, with truck path flow MAPE at 1.55%.
• Generalization:
  • Topology Changes: The model successfully predicted flows even when links were randomly removed (Scenario 2) or when the entire network topology was modified (Scenario 3) without requiring retraining.
  • Missing Data: It demonstrated robust performance under simultaneous missing link and missing demand scenarios.
• Comparison: Compared to a Multi-Layer Perceptron (MLP), the Transformer performed significantly better because the MLP lacks the structural ability to model the interdependencies between different OD pairs.

5. Significance

This research represents a paradigm shift in transportation modeling. By treating traffic assignment as a sequence learning problem rather than a pure optimization problem, the authors provide a tool that is:

• Practical for Real-Time Use: The near-instantaneous inference allows for real-time traffic management.
• Essential for Policy-Making: The ability to perform rapid "what-if" analyses (e.g., "What happens if we close this bridge and demand increases by 10%?") makes it a powerful decision-support tool for urban planners.
• Resilient: Its ability to handle incomplete data makes it highly applicable to real-world sensor networks where data is often noisy or missing.