Many problems in the real world have dynamic nature and can be modeled as dynamic combinatorial optimization problems. However, research on dynamic optimization focuses on continuous optimization problems, and rarely targets combinatorial problems. One of the applications in dynamic combinatorial problems that has received a growing interest during the last decades is the on-line or dynamic transportation systems. A typical problem of this domain is the Dynamic Vehicle Routing Problems (DVRPs). In this latter, the dynamism can be attributed to several factors (weather condition, new customer order, cancellation of old demand, vehicle broken down, etc.). In such application, information on the problem is not completely known a priori, but instead is revealed to the decision maker progressively with time. Consequently, solutions for different instances have to be found as time proceeds, concurrently with managing the incoming information. Such problems call for a methodology to track their optimal solutions through time. In this thesis, dynamic vehicle routing problem is addressed and developing general methodologies called metaheuristics to tackle this problem is investigated. Their ability to adapt to the changing environment and their robustness are discussed. Experimental results demonstrate that the methods are effective on this problem and hence have a great potential for other dynamic combinatorial problems.
Directeurs : Laetitia Jourdan, Professeur, Université Lille 1 El-Ghazali Talbi, Professeur, Université Lille 1 Rapporteurs : Van-Dat Cung, Professeur, INP Grenoble Pascal Bouvry, Professeur, Université du Luxembourg Geir Hasle, Directeur de recherche, SINTEF Applied Mathematics (Norvège) Membres : Gille Goncalves, Professeur, Université d'Artois Dominique Feillet, Professeur, Ecole des Mines de Saint-Etienne Gabriel Luque, Maître de Conférences, Université de Málaga (Espagne)
Thèse de l'équipe Dolphin soutenue le 2 décembre 2011