Efficient Gradient Estimation of Traffic Assignment Models with Iterative Backpropagation

Abstract

Traffic assignment (TA) optimization is at the heart of many transportation planning and operation problems. For a reasonably sized network with high-dimensional decision variables, TA optimization quickly becomes intractable due to high computation time and a large number of function evaluations. Generally, TA models have cyclic dependencies among their components and hence, have no closed-form gradients, which is crucial for high dimensional optimization. This paper proposes an efficient TA gradient estimation technique called Iterative Backpropagation (IB) to solve this problem. IB exploits the iterative TA solution algorithms and generates the TA gradients while the TA model converges. IB neither requires solving any system of equations nor any additional functional evaluations irrespective of the problem dimension. In our experiments, IB gradients match the finite-difference gradients at machine precision. IB gradients are usable with any state-of-the-art gradient-based optimization algorithms and can be extended to a wide range of TA optimization problems.