Understanding and Improving Traffic with Unknown Demands
Project Goal
This project studies how traffic flows behave under uncertain or unknown demand and how
equilibria can be improved systematically via algorithmic methods and data-driven control
strategies.
The focus is on Wardrop equilibria in networks with affine edge costs:
we analyze structural properties of equilibria under varying demand, develop
parametric algorithms that compute entire equilibrium paths, and study when
strategic information disclosure by a central coordinator improves total system performance.
Interactive Visualization
The figure below is locally scroll-controlled: scrolling directly over the figure reveals
successive stages of a demand and equilibrium analysis without scrolling the text below.
Main Results
A core contribution of the project is a sharper understanding of how traffic equilibria
react to changing demand. The dependence is typically not smooth: active routes and support
structures can change at critical demand values. Identifying these breakpoints algorithmically
is essential when planning for demand intervals instead of a single operating point.
To address this, the project develops parametric homotopy methods that compute complete
equilibrium paths as demand varies. This turns equilibrium computation into a structured
continuation problem: rather than recomputing from scratch for each scenario, one follows
the solution across regime changes and obtains explicit threshold information.
These ideas were further extended to richer cost models and minimum-cost-flow settings with
convex or piecewise quadratic costs. This enables controlled approximations with explicit
error guarantees on realistic instances, making large-scale sensitivity studies computationally
feasible while preserving mathematical reliability.
On the complexity side, the project clarifies fundamental limits in atomic splittable
congestion models by proving PPAD-completeness in full generality, while still providing
structured path-following algorithms based on weighted block Laplacians for tractable regimes.
This combination of positive algorithms and tight hardness results gives a realistic map of
what can be computed efficiently under demand uncertainty.
Methodological Contribution
Overall, the project combines structural equilibrium analysis, parametric algorithm design,
and complexity theory into one coherent framework. For mobility and infrastructure planning,
this provides a practical basis to quantify robust operating ranges, detect critical load
transitions early, and evaluate interventions under fluctuating demand.
References
- Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians (Max Klimm and Philipp Warode)
SIAM Journal on Computing, 54:1241–1293, 2025.
@article{KlimmWarode2025,
author = {Max Klimm and Philipp Warode},
title = {Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians},
journal = {SIAM Journal on Computing},
year = {2025},
volume = {54},
issue = {5},
pages = {1241--1293},
doi = {10.1137/20M1361523},
}
We settle the complexity of computing an equilibrium in atomic splittable congestion games with player-specific affine cost functions $l_{e,i}(x) = a_{e,i} x + b_{e,i}$ as we show that the computation is PPAD-complete. To prove that the problem is contained in PPAD, we develop a homotopy method that traces an equilibrium for varying flow demands of the players. A key technique for this method is to describe the evolution of the equilibrium locally by a novel block Laplacian matrix where each entry of the Laplacian is a Laplacian again. Using the properties of this matrix allows to recompute efficiently the Laplacian after the support of the equilibrium changes by matrix pivot operations. These insights give rise to a path following formulation for computing an equilibrium where states correspond to supports that are feasible for some demands and neighboring supports are feasible for increased or decreased flow demands. A closer investigation of the block Laplacian system further allows to orient the states giving rise to unique predecessor and successor states thus putting the problem into PPAD. For the PPAD-hardness, we reduce from computing an approximate equilibrium of a bimatrix win-lose game. As a byproduct of our reduction we further show that computing a multi-class Wardrop equilibrium with class-dependent affine cost functions is PPAD-complete as well. As another byproduct of our PPAD-completeness proof, we obtain an algorithm that computes a continuum of equilibria parametrized by the players' flow demand. For player-specific costs, the continuum may involve several increases and decreases of the demand and yields an algorithm that runs in polynomial space. For games with player-independent costs, only demand increases are necessary yielding an algorithm computing all equilibria as a function of the flow demand that runs in time polynomial in the output.
- Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs (Max Klimm and Philipp Warode)
Mathematics of Operations Research, 47(1):812–846, 2022.
@article{KlimmWarode2021,
author = {Max Klimm and Philipp Warode},
doi = {10.1287/moor.2021.1151},
journal = {Mathematics of Operations Research},
number = {1},
pages = {812--846},
title = {Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs},
volume = {47},
year = {2022},
}
We develop algorithms solving parametric flow problems with separable, continuous, piecewise quadratic, and strictly convex cost functions. The parameter to be considered is a common multiplier on the demand of all nodes. Our algorithms compute a family of flows that are each feasible for the respective demand and minimize the costs among the feasible flows for that demand. For single commodity networks with homogenous cost functions, our algorithm requires one matrix multiplication for the initialization, a rank 1 update for each nondegenerate step and the solution of a convex quadratic program for each degenerate step. For nonhomogeneous cost functions, the initialization requires the solution of a convex quadratic program instead. For multi-commodity networks, both the initialization and every step of the algorithm require the solution of a convex program. As each step is mirrored by a breakpoint in the output this yields output-polynomial algorithms in every case.
- Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs (Per Joachims, Max Klimm, and Philipp Warode)
Preprint, 2021.
@techreport{JoachimsKlimmWarode2021,
arxiv = {2203.13146},
author = {Per Joachims and Max Klimm and Philipp Warode},
title = {Approximate Parametric Computation of Minimum-Cost Flows with Convex Costs},
year = {2021},
}
This paper studies a variant of the minimum-cost flow problem in a graph with convex cost functions, where the demands at the vertices are functions depending on a one-dimensional parameter $\lambda$. We devise two algorithmic approaches for the approximate computation of parametric solutions for this problem. The first approach transforms an instance of the parametric problem into an instance with piecewise quadratic cost functions by interpolating the marginal cost functions. The new instance can be solved exactly with an algorithm we developed in prior work. In the second approach, we compute a fixed number of non-parametric solutions and interpolate the resulting flows yielding an approximate solution for the original, parametric problem. For both methods we formulate explicit bounds on the step sizes used in the respective interpolations that guarantee relative and absolute error margins. Finally, we test our approaches on real-world traffic and gas instances in an empirical study.
- Computing all Wardrop Equilibria parametrized by the Flow Demand (Max Klimm and Philipp Warode)
SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms, pp. 917–934.
@inproceedings{KlimmWarode2019,
author = {Max Klimm and Philipp Warode},
booktitle = {SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms},
doi = {10.1137/1.9781611975482.56},
pages = {917--934},
title = {Computing all {Wardrop} Equilibria parametrized by the Flow Demand},
year = {2019},
}
We develop an algorithm that computes for a given undirected or directed network with flow-dependent piece-wise linear edge cost functions all Wardrop equilibria as a function of the flow demand. Our algorithm is based on Katzenelson's homotopy method for electrical networks. The algorithm uses a bijection between vertex potentials and flow excess vectors that is piecewise linear in the potential space and where each linear segment can be interpreted as an augmenting flow in a residual network. The algorithm iteratively increases the excess of one or more vertex pairs until the bijection reaches a point of non-differentiability. Then, the next linear region is chosen in a simplex-like pivot step and the algorithm proceeds. We first show that this algorithm correctly computes all Wardrop equilibria in undirected single-commodity networks along the chosen path of excess vectors. We then adapt our algorithm to also work for discontinuous cost functions which allows to model directed edges and/or edge capacities. Our algorithm is output-polynomial in non-degenerate instances where the solution curve never hits a point where the cost function of more than one edge becomes non-differentiable. For degenerate instances we still obtain an output-polynomial algorithm computing the linear segments of the bijection by a convex program. The latter technique also allows to handle multiple commodities.
