Penalization and augmented Lagrangian for O-D demand matrix estimation from transit segment counts

ABSTRACT

In this paper we consider some penalized quadratic models to update Origin-Destination (O-D) matrices in transit networks from observed flows. These models look for the closest O-D matrix to an outdated one, which reproduces some observed segment flows. We demonstrate that the solution of these penalized models converges to the solution of the Spiess model when the penalty parameter increases to infinity. Another contribution is the introduction of an augmented Lagrangian model and its iterative solution by a dual ascent technique and the method of multipliers. This approach yields high-quality solutions with low CPU time and it is tested with two networks: the Winnipeg transit network, which has 23716 O-D pairs; and the transit network of the metropolitan area of the Valley of Mexico with more than 2 million of O-D pairs. For some instances, extracting the null coefficients from the old O-D matrix reduces the computational cost even further.

KEYWORDS:

• O-D matrix
• transit assignment
• penalization
• augmented Lagrangian
• conjugate gradient method

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. The Bolzano-Weierstrass theorem is a fundamental result about convergence in a n-dimensional Euclidean space ${\mathbb{R}}^n$. It states that each bounded sequence in ${\mathbb{R}}^n$ has a convergent subsequence.

Additional information

Funding

The authors want to acknowledge the financial support of CONACYT (National Council of Science and Technology in Mexico) through the scholarships for the first author, the support of Red de Matemáticas y Desarrollo (Network of Mathematics and Development-CONACYT, in Mexico) and Proyect 1948-Fronteras 2016-01. We acknowledge also the support from the Math Graduate program at the Autonomous Metropolitan University campus Iztapalapa in Mexico City.