End-to-end differentiable network traffic simulation with dynamic route choice

摘要

Optimization using network traffic models requires computing gradients of objective functions with respect to model parameters. However, derivation of such gradients has often been considered difficult or impractical due to their complexity and size. Conventional approaches rely on numerical differentiation or derivative-free methods that do not scale well with the parameter dimension, or on adjoint methods that require manual derivation for each specific model. This study proposes a novel end-to-end differentiable network traffic flow simulator based on automatic differentiation (AD), employing the Link Transmission Model (LTM) and a Dynamic User Optimum (DUO) route choice model. The LTM operates on continuous aggregate state variables through piecewise-linear min/max operations, which admit subgradients almost everywhere and thus require no smooth relaxation for AD. The DUO is also suitable for AD: although the shortest path search is itself discrete, the resulting diverge ratios at each node are continuous functions of per-destination vehicle counts and are thus differentiable. In order to demonstrate the capability of the proposed model, we solved a dynamic congestion toll optimization problem on the Chicago-Sketch dataset with approximately 2500 links, 1 million vehicles, a 3-hour duration, and 15000 decision variables. The proposed model successfully derived a high-quality solution in 3000 iterations, taking about 40 minutes. The simulator, implemented in Python and JAX, is released as open-source software named UNsim (https://github.com/toruseo/UNsim).