Scheduling and Routing of Truck Drivers Considering Regulations on Drivers’ Working Hours

In many countries, truck drivers are obliged by law to take a break or a rest regularly. In the European Union, for example, this is governed by Regulation (EC) No. 561/2006. It states that, after 4.5 hours of driving a truck, it is prohibited to continue driving until a 45-minute break is taken. After accumulating a driving time of 9 hours, a rest of 11 hours is mandatory. These are only two rules of a considerably longer list of break rules set out in this regulation, and it is only one of many regulations there are worldwide. Such breaks and rests have to be planned into the work schedules of the drivers. In general, the task of a dispatcher is to find routes and schedules for the truck drivers such that every customer is served in time. With the regulations on drivers’ working hours, both the routing and the scheduling parts of the task become more challenging.

In this thesis, we study several optimization problems that arise in the context of drivers’ working hours. One is known as the truck driver scheduling problem. Here, a sequence of customers is given, and the task is to find a schedule for a driver such that every customer is visited within one of the customer’s time windows and the applicable break rules are complied with. ... mehrDepending on the regarded break rules, we get different variants of the truck driver scheduling problem. Little is known about the complexity of the individual problem variants. One of the two focal points of this thesis is to present polynomial-time algorithms for different variants of the problem, for which polynomial-time algorithms are not yet known. With this, we can falsify the NP-hardness conjecture of Xu et al. (2003) for an important special case of their considered problem variant.

But this thesis is not only about scheduling, it is also about routing. This constitutes the second focal point of this thesis. We present an integrated approach for the vehicle routing and truck driver scheduling problem. Here, a route refers to the order in which the customers are visited. However, the meaning of route is twofold. In another studied problem, the truck driver scheduling and routing problem, it means the sequence of road segments that the driver takes to drive from one customer to the other. In this problem, we take into account that, before taking a break, truck drivers need to head for a rest area or at least a spot where their vehicle can be parked. We even consider the time-dependent scenario in which driving times on road segments vary over the day due to rush hours. Both an exact approach and a heuristic for this problem are presented, and both are evaluated on a recent road network instance of Germany. It turns out that the heuristic is at least two orders of magnitude faster but still hardly worse than the exact approach.

Our main motivation is the application in practice. It is our aim – and this is especially true for the second focal point – to provide helpful algorithms that may find their way into software products for dispatchers, like the described approach for the vehicle routing and truck driver scheduling problem is already integrated into the vehicle route planning tools of a commercial provider of logistics optimization software.