Faculté des sciences de base SB, Section de mathématiques, Institut de mathématiques IMA (Laboratoire transport et mobilité TRANSP-OR)

New algorithmic methods for real-time transportation problems

Crittin, Frank ; Bierlaire, Michel (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2003 ; no 2877.

Ajouter à la liste personnelle
    Summary
    Two of the most basic problems encountered in numerical optimization are least-squares problems and systems of nonlinear equations. The use of more and more complex simulation tools on high performance computers requires solving problems involving an increasingly large number of variables. The main thrust of this thesis the design of new algorithmic methods for solving large-scale instances of these two problems. Although they are relevant in many different applications, we concentrate specifically on real applications encountered in the context of Intelligent Transportation Systems to illustrate their performances. First we propose a new approach for the estimation and prediction of OriginDestination tables. This problem is usually solved using a Kalman filter approach, which refers to both formulation and resolution algorithm. We prefer to consider a explicit least-squares formulation. It offers convenient and flexible algorithms especially designed to solve largescale problems. Numerical results provide evidence that this approach requires significantly less computation effort than the Kalman filter algorithm. Moreover it allows to consider larger problems, likely to occur in real applications. Second a new class of quasi-Newton methods for solving systems of nonlinear equations is presented. The main idea is to generalize classical methods by building a model using more than two previous iterates. We use a least-squares approach to calibrate this model, as exact interpolation requires a fixed number of iterates, and may be numerically problematic. Based on classical assumptions we give a proof of local convergence of this class of methods. Computational comparisons with standard quasi-Newton methods highlight substantial improvements in terms of robustness and number of function evaluations. We derive from this class of methods a matrix-free algorithm designed to solve large-scale systems of nonlinear equations without assuming any particular structure on the problems. We have successfully tried out the method on problems with up to one million variables. Computational experiments on standard problems show that this algorithm outperforms classical large-scale quasi-Newton methods in terms of efficiency and robustness. Moreover, its numerical performances are similar to Newton-Krylov methods, currently considered as the best to solve large-scale systems of equations. In addition, we provide numerical evidence of the superiority of our method for solving noisy systems of nonlinear equations. This method is then applied to the consistent anticipatory route guidance generation. 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 and of use to drivers. Secondly the unavailability of a closed-form objective function and the presence of noise due to the use of simulation tools prevent from using classical algorithms. A number of simulation experiments based on two system software including DynaMIT a state-of-the-art, real-time computer system for traffic estimation and prediction, developed at the Intelligent Transportation Systems Program of the Massachusetts Institute of Technology (MIT), have been run. These numerical results underline the good behavior of our large-scale method compared to classical fixed point methods for solving the consistent anticipatory route guidance problem. We close with some comments about future promising directions of research.
    Résumé
    La résolution de moindres carrés et de systèmes d'équations non-linéaires font parties des problèmes fondamentaux que l'on rencontre en optimisation numérique. De part les progrès constants réalisés en informatique favorisant l'utilisation d'outils de simulation de plus en plus complexes, la taille de ces problèmes ne cesse d'augmenter. L'objectif principal de cette thèse est la conception de nouvelles méthodes algorithmiques pour la résolution de ce type de problèmes de grande taille. Bien qu'ils apparaissent dans de nombreux domaines, cette dissertation se concentre sur l'application de nos méthodes à des outils de gestion dynamique du trafic routier. Une nouvelle approche pour l'estimation et la prédiction de tables OrigineDestination est proposée. En général ce problème se résout avec la méthode des filtres de Kalman, qui fait référence aussi bien à la formulation qu'à l'algorithme de résolution. Nous préférons ici une formulation en termes de moindres carrés. Elle permet l'utilisation d'algorithmes efficaces pour la résolution de problèmes de grande taille. Les résultats numériques mettent en évidence l'amélioration flagrante en termes de temps de calculs de cette approche par rapport à l'algorithme des filtres de Kalman. De plus, cette méthode permet de considérer des problèmes de plus grandes dimensions susceptibles de se présenter dans les applications réelles. Une nouvelle classe de méthodes pour la résolution de systèmes d'équations non linéaires est présentée dans cette thèse. L'idée principale est la généralisation des méthodes sécantes, en construisant un modèle basé sur plus de deux itérés. Nous proposons une approche basée sur les moindres carrés pour la calibration du modèle, contrairement aux méthodes traditionnelles qui utilisent l'interpolation. Sous des hypothèses classiques, la convergence locale de cette classe de méthodes est démontrée. Les résultats numériques obtenus par ces algorithmes comparés aux méthodes quasi-Newton illustrent une amélioration significative des performances aussi bien du point de vue de l'efficacité que de la robustesse. A partir de cette nouvelle classe de méthodes, nous développons un algorithme pour la résolution de systèmes d'équations de grande taille qui ne recourt pas à la construction explicite de matrices et qui n'impose aucune structure particulière au problème. En pratique cet algorithme nous a permis de traiter des problèmes comptant un million de variables. Les résultats numériques obtenus sur des problèmes standards montrent clairement que cette méthode est supérieure aux méthodes quasi-Newton classiques en termes d'efficacité et de robustesse. Ces performances peuvent même être comparées avec les méthodes de type Newton-Krylov actuellement considérées comme les meilleures pour la résolution de systèmes d'équations de grande taille. De plus, la qualité de notre algorithme appliqué à des problèmes pour lesquels l'évaluation de la fonction objectif est bruitée est mis en évidence. Cette méthode est ensuite appliquée au problème de génération d'information routière cohérente. Nous nous intéressons en particulier à la génération en temps réel d'information, basée sur la prédiction de l'état futur du réseau routier. Dans ce cas, il faut tenir compte de la réaction des conducteurs à cette information. En effet, contrairement aux informations météorologiques, la diffusion d'informations sur le trafic influence celui-ci, affectant les prédictions. Le concept de cohérence entre l'information produite et les prédictions effectuées appréhende ce problème. La génération d'information routière cohérente peut être formulée comme un problème de point fixe avec les caractéristiques suivantes. Premièrement, comme la génération de l'information se base sur des simulations de l'état futur du réseau qui nécessitent beaucoup de temps de calcul, le problème de point fixe doit être résolu rapidement afin de pouvoir disséminer ces informations à temps. Deuxièmement, l'utilisation de modèles comportementaux afin de simuler la réaction des usagers empêche l'application de méthodes classiques souvent sensibles à la présence de bruit dans la fonction objectif. Les tests numériques sont effectués grâce à deux programmes. L'un d'entre eux est DynaMIT, un système de prédiction de trafic et de génération d'information en temps réel développé au Intelligent Transportation Systems (ITS) Program du Massachusetts Institute of Technology (MIT). Ces résultats numériques mettent en évidence l'excellent comportement de notre méthode comparé aux méthodes de résolutions conventionnelles. La thèse se termine par l'identification de directions prometteuses qui s'inscrivent dans le prolongement des recherches présentées.