A time-space network approach for the integrated vehicle- and crew-scheduling problem with multiple depots

A time-space network approach for the integrated vehicle- and crew-scheduling problem with multiple depots

0.00 Avg rating0 Votes
Article ID: iaor20105880
Volume: 44
Issue: 3
Start Page Number: 367
End Page Number: 382
Publication Date: Aug 2010
Journal: Transportation Science
Authors: , , ,
Keywords: personnel & manpower planning, vehicle routing & scheduling
Abstract:

This paper discusses the integrated vehicle- and crew-scheduling problem in public transit with multiple depots. It is well known that the integration of both planning steps discloses additional flexibility that can lead to gains in efficiency, compared to sequential planning. We present a new modeling approach that is based on a time-space network representation of the underlying vehicle-scheduling problem. The integrated problem is solved with column generation in combination with Lagrangian relaxation. The column generation subproblem is modeled as a resource-constrained shortest-path problem based on a novel time-space network formulation. Feasible solutions are generated by a heuristic branch-and-price method that involves fixing service trips to depots. Numerical results show that our approach outperforms other methods from the literature for well-known test problems.

Reviews

Required fields are marked *. Your email address will not be published.