The defense will take place on Tuesday 9th June (morning) in the Heidi Lamarr building (Amphi Chappe), Insa-Lyon, Villeurbanne.

Title

Exact and anytime heuristic search for the Time Dependent Traveling Salesman Problem with Time Windows

Abstract

The Time Dependent (TD) Traveling Salesman Problem (TSP) is a generalization of the TSP which allows one to take traffic conditions into account when planning tours in an urban context: travel times between points to visit depend on departure times instead of being constant. The TD-TSPTW further generalizes this problem by adding Time Window constraints, i.e., constraints on visit times. Existing exact approaches such as Integer Linear Programming and Dynamic Programming usually do not scale well; heuristic approaches scale better but provide no guarantees on solution quality.

In this thesis, we introduce a new exact and anytime solving approach for the TD-TSPTW which aims at quickly providing approximate solutions and gradually improving them until proving optimality. We first show how to reduce the TD-TSPTW to the search for a best path in a state-transition graph. We provide an overview of existing search algorithms, with a focus on exact and anytime extensions of A*, and introduce a new one by hybridizing two of them. We show how to combine these exact and anytime search algorithms with local search – in order to faster find solutions of higher quality – and with bounding and time window constraint propagation – in order to filter the search space. Finally, we provide extensive experimental results to (i) validate our main design choices, (ii) compare our approach to state-of-the-art solving approaches on various TD benchmarks with different degrees of realism and different temporal granularities and (iii) compare TD solving approaches to recent TSPTW solvers on constant benchmarks. These experimental results show us that our approach offers a good compromise between the time needed to find good solutions and the time needed to find optimal solutions and prove their optimality for both TD and constant TSPTW instances.

Jury

• • • Cédric PRALET, Directeur de Recherche, ONERA – Rapporteur
    • Pierre SCHAUS, Professeur des Universités, UC Louvain – Rapporteur
    • Romain BILLOT, Professeur des Universités, IMT Atlantique – Examinateur
    • Christine SOLNON Professeure des Universités, INSA Lyon – Directrice de thèse
    • Jilles S. DIBANGOYE, Maître de Conférences HDR, University of Groningen – Co-directeur de thèse