A column generation approach for the driver scheduling problem with staff cars

In the public bus transport industry, it is estimated that the cost of a driver schedule accounts for approximately 60% of a transport company's operational expenses. Hence, it is important for transport companies to minimize the overall cost of driver schedule. A duty is defined as the work of a driver for a day and the driver scheduling problem (DSP) is concerned with finding an optimal set of driver duties to cover a set of timetabled bus trips. Numerous labor regulations and other practical conditions enforce drivers to travel within the city network to designated bus stops to start/end duty, to take a break or to takeover a bus from another driver. In this talk, we introduce the driver scheduling problem with staff cars (DSPSC), where staff cars can be utilized by the drivers to fulfill their travel activities. Staff cars should always be returned to the depot and the problem is restricted by the number of cars available at the depot.

A column generation framework is proposed that iterates between a master problem, a subproblem for generating driver variables and a subproblem for generating staff car variables. The subproblem related to the drivers is formulated as a resource constrained shortest path problem, which is solved by a dynamic programming approach. The proposed methodology is tested on eight real-life instances and the solutions are compared to a commercial heuristic that generates variables to be solved as a pure mixed integer programming model.

Registration to Remy Spliet, spliet@ese.eur.nl is required for availability of lunch.