Solving the anticipatory route guidance generation problem using a generalization of secant methods

Route guidance refers to information provided to travelers in an attempt to facilitate their decisions relative to departure time, travel mode and route. We are specifically interested in consistent anticipatory route guidance, in which real-time traffic measurements are used to make short-term predictions, involving complex simulation tools, of future traffic conditions. These predictions are the basis of the guidance information that is provided to users. By consistent, we mean that the anticipated traffic conditions used to generate the guidance must be similar to the traffic conditions that the travelers are going to experience on the network. The problem is tricky because, contrarily to weather forecast where the real system under consideration is not affected by information provision, the very fact of providing travel information may modify the future traffic conditions and, therefore, invalidate the prediction that has been used to generate it. Bottom (2000) has proposed a general fixed point formulation of this problem with the following characteristics. First, as guidance generation involves considerable amounts of computation, this fixed point problem must be solved quickly and accurately enough for the results to be timely delivered to drivers. Secondly the unavailability of analytical forms for the objective function and the presence of noise due to the use of simulation tools prevent from using classical algorithms. We propose in this paper an adaptation of the generalized secant method (cf. the related presentation “A generalization of secant methods for solving nonlinear systems of equations”) in order to handle the intrinsic characteristics of the consistent anticipatory route guidance generation, especially the very high dimension associated with real problems. We present then a number of simulation experiments based on two simulation tools in order to compare the performances of the diverse algorithms. The first is a simple simulator implementing the framework of the route guidance generation on a small network, which is used to illustrate the properties of this problem and the behavior of the algorithms. Then, we present a large-scale case study of size 124575 using DynaMIT, a simulation-based real-time Dynamic Traffic Assignment system designed to compute and disseminate anticipatory route guidance. These results point out the real-time potential of the method as its ability to handle large scale problem.