Derivativefree Algorithms for the Estimation of Dynamic OD Matrix Structure Using Traffic Counts

Abstract

Dynamic Traffic Assignment (DTA) has recently received a considerable attention as an effective tool for real-time traffic management. Moreover, recent research has extended the use of DTA to the prediction of traffic conditions in the near future. However, in order to provide reliable simulation results, it is crucial to provide correct Origin-Destination (OD) matrix estimations, since travel demand is an essential input to the DTA model. Acquiring complete data sets for simulations through direct surveys can often be very expensive and sometimes even impossible to obtain. In this paper we therefore concentrate on the problem of correcting a given O-D matrix using traffic counts while preserving its structure in terms of generation, attraction and temporal profile.

Our goal is to develop an automatic procedure for the estimation of dynamic O-D flows for urban networks. The DTA model is used to relate the demand flows with observed network usage through non-linear relation. In particular, when the network is congested its sensitivity to small changes in the O-D flows is proved to be very high. Therefore, small errors in O-D matrix may result in large errors in the estimated queue lengths and travel times. The required accuracy of demand flows is difficult to achieve as numerous local minima in the objective function are present. In addition, two types of errors introduce noise in the objective function and can lead to the wrong solution: errors originating from traffic counts and errors originating from the model. They should also be considered in the attempt to extract the information of O-D flows from the assignment procedure and information contained in observations.

We treat our calibration task as an optimization problem. As this task is computationally very burdensome, we look for and explore the possibility of using derivative-free algorithms. While iterating to the solution, they conduct the limited number of function evaluations with respect to explicit computation of gradients and hessians. These stochastic search algorithms pursuit the solution by randomly choosing new points in a direction that depends on the objective function value of previous iterations. Our goal is to implement these algorithms in a way that their convergence to adequately accurate solutions is accomplished in a reasonable computation time. Three derivative-free optimization algorithms are tested. The first one is the Simultaneous Perturbation Stochastic Approximation (SPSA) (Spall, 1992; Spall, 1998), which has been extensively used in the literature for the estimation of O-D flows (Balakrishna & Koutsopoulos, 2008; Frederix et al., 2011; Cipriani et al., 2013). The second algorithm is the Nelder-Mead’s Simplex Algorithm (Nelder & Mead, 1965) and the third one is the Covariance Matrix Adaptation – Evolution Strategy (CMA-ES) (Hansen, 2011), which so far have not been used in the literature in this context. The comparison of

these three algorithms provides interesting insight of the estimation of dynamic demand flows.

The algorithms are used in different environments to explore their use in the O-D estimation problem. A first set of tests is conducted on simple toy networks with gradually increasing network complexity based on the combination of route choice and congestion. Results demonstrate the ability of all three algorithms to converge back to a known solution with respect to flows although with different characteristics with respect to their ability of representing correct traffic regimes. In scenarios where demand is set to values that do not produce congestion all algorithms show similar performance, since there is a linear relation between demand and link flows. In presence congestion SPSA and CMA-ES are able to converge to the solution for most of the test cases, whereas Nelder-Mead algorithm has difficulties in finding precise solution on some tests. Problems in convergence occur depending on the type of traffic information used: when flow counts are regarded as link exit flows there is no information about what happens along the link. In a second set of tests, a real-world network is used: the City of Turin network, which has a good coverage with traffic counts. This is used to explore the application of stochastic optimization algorithms in large-scale congested network and to emphasize practical issues.

TRE (Traffic Realtime Equilibrium) (Gentile et al., 2007; Gentile, 2008) model is used as a test bed for simulation and optimization. It is a model for Dynamic Traffic Assignment that consists of two components: route choice model and dynamic network loading model with realistic representation of traffic phenomena, such as congestion, queues and spillback. The objective function chosen for the optimization process measures deviations between estimated and revealed network usage, in our case traffic flows. As far as demand flows are concerned, we do not estimate single O-D pairs but rather estimate the structure of the matrix in terms of generation, attraction and temporal profile. For the tests with toy networks we assume that we know the solution and, additionally to objective function minimization, we track the progression of algorithms in terms of convergence and evolution of unknown parameters (i.e. the variables that define the demand structure). In the case of the real-world large-scale network, we take previous estimation of the O-D matrices and conduct perturbation of these matrices in order to identify correct demand flows. Additionally, sensitivity analysis is performed to depict the change in the objective function value for gradually changing parameter value to show expected oscillations due to congested network conditions. The results of the O-D matrix estimation are analysed and discussed.

The contribution of this paper is to prove the applicability of different optimization algorithms, other than SPSA, for the O-D matrix estimation and to provide their comparison. Moreover, we concentrate our investigation on the structure of the matrix rather on the single components. We demonstrate that Nelder-Mead and CMA-ES are valid alternatives with respect to SPSA, depending on the network to calibrate.

We show that Nelder-Mead can be the first choice for application in cases of small congestion. Despite the fact that CMA-ES is designed to work with high number of function evaluations per iteration, in this paper we show that even with small number it works well and can be used for calibration of large-scale urban networks. We also point out advantages and disadvantages of each algorithm and discuss their optimal settings for time-varying demand estimation.

References

Balakrishna, R. & Koutsopoulos. H.N. (2008). Incorporating Within-Day Transitions in the Simultaneous Off-line Estimation of Dynamic OriginDestination Flows without Assignment Matrices. 87th Annual Meeting of the Transportation Research Board, Washington, USA.

Cipriani, E., Gemma, A., & Nigro, M. (2013). A bi-level gradient approximation method for dynamic traffic demand estimation: sensitivity analysis and adaptive approach. Proceedings of the 16th International IEEE Conference on Intelligent Transportation Systems (ITSC 2013), The Hague, The Netherlands, 2013.

Frederix, R., Viti, F., Corthout, R., & Tampère, C.M.J. (2011). New Gradient Approximation Method for Dynamic Origin-Destination Matrix Estimation on Congested Networks. Transportation Research Record: Journal of the Transportation Research Board, Vol. 2263, 19–25.

Gentile G. (2008). The General Link Transmission Model for dynamic network loading and a comparison with the DUE algorithm. Proceedings of the 2nd International Symposium on Dynamic Traffic Assignment – DTA 2008, Leuven, Belgium.

Gentile G., Meschini L., & Papola N. (2007). Spillback congestion in dynamic traffic assignment: a macroscopic flow model with time-varying bottlenecks. Transportation Research Part B 41, 1114-1138.

Hansen, N. (2011). The CMA Evolution Strategy: A Tutorial. (https://www.lri.fr; date of visit: 06 May 2013), Laboratoire de Recherche en Informatique (LRI), Paris, France.

Nelder, J.A. & Mead, R. (1965). A simplex method for function minimization. The Computer Journal, Vol. 7, Issue 4, 308–313.

Spall, J.C. (1992). Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation. IEEE Transactions on Automatic Control, Vol. 37, No. 3, 332–341.

Spall, J.C. (1998). An Overview of the Simultaneous Perturbation Method for Efficient Optimization. Johns Hopkins APL Technical Digest, Vol. 19, No. 4, 482–492.