Tour Driver Scheduling

In this thesis we describe an algorithm for solving the Tour Driver Scheduling Problem (TDSP). A tour is a sequence of transportation tasks which can be executed by a driver. So the TDSP is in fact a crew scheduling problem in which transportation tasks have to be assigned to tours, such that costs are minimized while respecting a set of (legal) rules. Next to the more or less trivial constraints on the physical feasibility of a tour, constraints are imposed on the working and driving time. Furthermore, break and rest rules have to be respected. Finally, the tours have to return to their start location. The main objective of the TDSP is cost minimization, but the required computation time is an important factor which should be managed carefully. Also the quality of the tours and preferences of different tour types should be taken into account. The TDSP can be modelled as a set partitioning problem. Since the number of possible tours grows exponentially in the number of transportation tasks, complete enumeration of all possible tours will take a huge computation time. Therefore, column generation is used to solve the problem since this technique implicitly considers all possibilities and selects promising tours which could improve the current solution. A branch-and-price algorithm can be used in order to obtain an optimal solution of the problem. However, the computation speed is an important factor and therefore a heuristic approach seems better suited to our case. Therefore, we applied Lagrangian relaxation in combination with column generation. This means that we actually solve the Lagrangian relaxation, and finally use all generated tours to obtain a feasible solution to the overall problem. The column generation problem is solved with a two-stage approach. In the first stage one-day duties are generated by solving a set of shortest path problems. In the second stage tours are constructed by combining duties into feasible tours. Tours with negative reduced costs are added to the set of candidate tours. If no additional tours can be found, the resulting set partitioning problem is solved in order to obtain a feasible solution. The proposed method is tested on two real life problem instances. On the largest problem significant savings are achieved in the total amount of empty kilometres. Also the quality of the tours improved compared to the current schedule and the number of unscheduled tasks decreases. For the other problem the results are more or less comparable to the current schedule, but also for this problem the number of unscheduled tasks decreased.