A new assignment algorithm for the vehicle scheduling problem

The multiple depot vehicle scheduling problem (MD-VSP) is NP-HARD and concerns the assignment of a set of time-tabled trips to vehicles stationed at different depots in order to minimize a given cost function, considering that each vehicle returns to its depot at the end of the duty. AP-VSP is a relaxation of MD-VSP in which a vehicle is not required to return to its own depot. Such a relaxation is used in heuristic and exact algorithms. We introduce a new shortest path based algorithm for AP-VSP and show that it dominates all other known methods, both in time complexity and average computational time.