Scheduling truck drivers with interdependent routes under European Union regulations

When transporting goods, truck drivers may have to perform load transfers between two vehicles at cross-dock or transfer locations. These transfers create interdependencies between the routes of different truck drivers and require careful temporal synchronization. The situation becomes even more complicated when driver schedules must comply with customer time windows, working periods and regulatory resting requirements. Although the scheduling of hours of service for truck drivers is a well-known problem, existing algorithms cannot cope with interdependent routes. We introduce the Truck Driver Scheduling Problem with Interdependent Routes to successfully accommodate this real-world characteristic. This paper proposes a mathematical model and a label propagation algorithm to solve this new problem under the regulations of the European Union. Experiments indicate that the algorithm can quickly schedule a large number of interdependent routes and outperforms a mathematical programming approach. The algorithm produces valid schedules for multiple drivers and thus becomes a foundation for future vehicle routing algorithms that address interdependent routes and hours of service regulations.