INGI - Thesis

Advanced modeling and search techniques for routing and scheduling problems by Charles THOMAS

Pour l’obtention du grade académique de Doctorat en sciences de l’ingénieur

This thesis presents the application of several constraint programming techniques to combinatorial problems. In particular, hybrid scheduling and routing problems such as Dial-A-Ride Problems (DARP) are explored. A variant of this problem, the Patient Transportation Problem (PTP) is formalized and resolved. Various approaches to model the PTP and DARP are studied, including a scheduling model and a classical successor model. The usage of sequence variables to model the routes of vehicles is investigated. Two different implementations of a sequence variable are presented as well as several global constraints used in conjunction with these variables to provide efficient propagation algorithms. Additionally, the use of an adaptive variant of the Large Neighborhood Search (LNS) is considered in a black-box context, without prior knowledge about the problem being solved. The approach studied uses a portfolio of different heuristics combined with a selection mechanism to adapt the heuristics used to the current problem during the search. Experimental results show the efficiency of the techniques proposed and hint at promising research directions in the domain of PTP-like problems, sequence variables and adaptive LNS.

Jury members :

• Prof. Pierre Schaus (UCLouvain), supervisor
• Prof. Charles Pecheur (UCLouvain), chairperson
• Prof. Yves Deville (UCLouvain), secretary
• Dr. Roger Kameugne (Université de Maroua, Cameroon)
• Dr. Vinasétan Ratheil Houndji (Université d’Abomey-Calavi, Bénin)
• Prof. Christian Artigues (Laboratory for Analysis and Architecture of Systems (LAAS-CNRS), France)

Pay attention :

The public defense of Charles Thomas scheduled for Wednesday 08 Februay at 02:00 p.m. will also take place in the form of a video conference