ECCO 2024
Abstract Submission

40. A complete algorithm for the truck driver scheduling problem?

Invited abstract in session FC-2: Logistics, stream Logistics.

Friday, 13:30 - 15:00
Room: M228

Authors (first author is the speaker)

1. Niels De Walsche
2. Greet Vanden Berghe
Computer Science, KU Leuven
3. Pieter Smet
Computer Science, KU Leuven

Abstract

In recent years, there has been an increased focus on employee wellbeing.
This is especially relevant for truck drivers, who are often on the road for long periods of time.
In an effort to ensure safe and sustainable working conditions for such drivers, the EU introduced a set of hours-of-service regulations, adherence to which results in a problem known as the truck driver scheduling problem [1].
It is crucial for companies to ensure that their drivers are compliant with these regulations, as non-compliance can lead to fines and other penalties.
When this scheduling problem is combined with the vehicle routing problem, it becomes the Vehicle Routing and Truck Driver Scheduling Problem (VRTDSP). Here the goal is to find routes for the trucks and feasible schedules for the drivers that minimize the number of drivers used and the total distance traveled.
Our proposed truck driver scheduling algorithm is based on the multilabel method introduced by Goel [1].
We have made several improvements compared to the original method, such as a better labeling strategy that finds more feasible schedules and a more effective pruning strategy that reduces the number of schedules that must be checked for feasibility.
The algorithm has been tested on the VRTDSP instances introduced by Goel [1] and is able to deliver results that are better than the current state-of-the-art heuristic algorithm for the problem.
However, although our algorithm is able to deliver improved results, it is not yet clear if it is complete.
Due to the intersection of personnel scheduling and vehicle routing, the problem not only becomes very computationally challenging but also unintuitive for human planners.
While we have not yet found any counterexamples, this makes it very difficult to determine whether the algorithm is overlooking/failing to find any potential feasible solutions.
With this talk we want to invite experienced and theoretical perspectives to help determine if the algorithm is complete or to find holes in the method.

1. Goel, A.: Vehicle scheduling and routing with drivers' working hours. Transportation Science 43(1), 17-26 (2009)

Keywords

Status: accepted

Back to the list of papers