This thesis is about models and solution methods for different routing and scheduling problems, which consider legal constraints related to the driving and working time of the truck drivers.  These kind of problems require, among other things, coordination between delivery activities, which are defined by a starting date, the service duration at customers (who have time windows), and transport operations, which are defined by starting and finishing dates.

In order to solve this models, different optimization methods were proposed to achieve good quality solutions in a reasonable running times.  The solution methods are developed in order of complexity, starting with models using a restricted number of decision points and ending with models that can handle pre-emption assumptions.  The first problem is a Truck Driver Scheduling problem in which breaks and daily rests are only scheduled at the customer locations, which means that transport times between customers must not exceed 4.5 hours.  This model is perfectly suited to regional or national transport where distance between two customers does not exceed 4.5h.  The second problem addressed concerns to the solution of the Truck Driver Scheduling problem, in which breaks can be scheduled at any point of time, whether at customer locations or in the middle of an activity (driving or service).  This problem is more complete because it models more general cases including in particular long distance transports between customers. 

This thesis presents different solutions methods for the TDSP problem while considering all the weekly rules from the European Community Social Legislation, extending in this sense all previous contributions in the literature.  In particular, the night working rule that has been whether simplified or discarded in the past.   In addition, a new benchmark with detail optimal solutions is provided.  The efficiency of the proposed methods and the implications of the different rules in particular the night working constraint are discussed.

Jury :

Caroline Prodhon, MCF Hdr, Université de Troyes
Ammar Oulamara, Professeur au LORIA
Pierre Castagna, Professeur à l'IUT de Nantes
Thierry Garaix, MCF EMSE (co-directeur de thèse)
Philippe Lacomme, MCF HdR (co-directeur de thèse)
Nikolay Tchernev, Professeur (co-directeur de thèse);