Résumé
Rules on driving, working and breaks scheduling are crucial to enhance road safety and to respect drivers’ work conditions. Thus, adapting the vehicle routes that are commonly defined in routing optimization problems to integrate these rules leads us to the Truck Drive Scheduling Problem (TDSP) which purpose is to guarantee their compliance according to the European Union regulations. In this respect, we present the first Constraint Programming (CP) based approach for the TDSP which integrates rules regarding the driving, service, working time and breaks duration considering a one-week horizon time. Driving time concerns only the transportation time from one customer to another, service time as transportation and processing duration and working time encompass all activities within a day of work. Breaks between activities and night breaks must meet the law requirements. Therefore, the main idea of our CP-based algorithm is to schedule the arrival, starting, finishing and departure dates and define the breaks duration before and/or after the activities considering the EC regulation 561/2006 so that the completion time is minimized. Tests were performed in a set of 29 instances and results show that the majority is solved into optimality in less than one second and others present at most a 1% gap, which validates our algorithm effectiveness.