A column generation approach for the driver scheduling problem with staff cars
Shyam Sundar Govindaraja Perumal  1, 2@  , Jesper Larsen  1@  , Richard Lusby  1@  , Morten Riis  2@  , Tue Christensen  2@  
1 : Technical University of Denmark

Given a set of timetabled bus trips, transport companies are faced with the challenge of finding feasible driver schedule that covers all trips and abides by various labor union regulations. The regulations are concerned with providing sufficient breaks for the drivers during the day. Practical limitations in city networks enforce drivers to travel by cars between bus stops to have breaks. Transport companies have a limited number of cars, known as staff cars, which have to be returned to its depot at the end of the day. The simultaneous scheduling of drivers and staff cars is known as the driver scheduling problem with staff cars (DSPSC). It is estimated that the DSPSC accounts for 60% of a company's operational expense, and a column generation approach is proposed that attempts to minimize operational expense. The column generation method 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 method is tested on eight real-life instances from seven Northern European companies. A comparison with a state-of-the-art mixed integer programming solver and an adaptive large neighborhood search heuristic indicate that the column generation method provides improved solutions for six instances and the average improvement is 1.45%.

Online user: 1 RSS Feed