The truck driver Sscheduling problem under the european Community social legislation
Le problème d’ordonnancement des chauffeurs de camions dans le cadre de la législation sociale de la Communauté européenne
Résumé
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 thesis starts with an introduction, which presents an overview of the problem and the different approaches that have been proposed in the literature to solve it. This literature review follows two lines, problems related with the Truck Driver Scheduling Problem (TDSP) and the combined Vehicle Routing and Truck Driver Scheduling Problem (VRTDSP). 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. This problem is the subject of chapter 2: a linear model and a label setting algorithm are proposed and tested on a new set of instances. 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. On this problem different contributions are made: the first is a linear model which extends the model from chapter 2, and three versions of a label setting algorithm. 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.
Cette thèse porte sur la modélisation et la résolution de différents problèmes d'ordonnancement en intégrant les contraintes légales qui portent sur les temps de conduite et les temps de travail des chauffeurs de camion. Ces problèmes demandent, entre autre, une coordination entre des activités de livraisons, qui se définissent par une date de début et une durée au niveau des clients (qui possèdent des contraintes horaires de passage), et des opérations de transport, qui se définissent par une date de début, une date de fin. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation ont été proposées afin d’obtenir des solutions de bonne qualité dans des temps raisonnables. La thèse commence par une introduction qui présente d’une façon générale le problème et des différentes approches qui ont été proposées dans la littérature pour le résoudre. Cette revue de la littérature suit deux axes, les problèmes liés au Truck Driver Scheduling Problem (TDSP) et le Vehicle Routing and Truck Driver Scheduling Problem (VRTDSP). Les méthodes de résolution sont développées par ordre de complexité, en commençant par des modèles utilisant un nombre restreint de points de décision et en terminant par des modèles qui prennent en compte des hypothèses de preemption. Le premier problème est un problème d'ordonnancement/transport de type Truck and Driver dans lequel les pauses des chauffeurs ne sont planifiés qu'au niveau des clients ce qui impose que les temps de transport de dépassent pas 4h30. Il s'agit d'une modélisation parfaitement adaptée aux transports régionaux ou nationaux dans lesquels les distances entre deux clients ne dépassent pas 4h30. Il faut noter que le retour du camion au dépôt n'est pas modélisé dans l'évaluation de la tournée. Ce problème fait l'objet du chapitre 2 : une modélisation linéaire et un algorithme de programmation dynamique sont proposés et testés sur un nouveau jeu d'instances.Le dernier problème traité concerne la résolution du Truck and Driver, dans lequel les pauses de chauffeurs peuvent être planifié à tout moment, que ce soit chez le client ou au milieu d’une activité (conduit ou service). Ce problème est plus complet car il modélise des cas plus généraux dont en particulier les transports grande distance entre les clients. Sur ce problème différentes contributions sont réalisées : la première concerne la proposition d'un modèle linéaire qui étend le modèle du chapitre 2 et trois versions d’un modèle de programmation dynamique.Cette thèse présente différentes méthodes de solutions pour le problème TDSP tout en considérant les règles hebdomadaires de l’European Community Social Legislation, étendant dans ce sens toutes les contributions précédentes dans la littérature. En particulier, la règle du travail de nuit qui a été simplifiée ou rejetée dans le passé. En outre, un nouveau point de référence avec des solutions optimales détaillées est fourni. L’efficacité des méthodes proposées et les implications des différentes règles, en particulier la contrainte du travail de nuit, sont discutées.
Origine : Version validée par le jury (STAR)