A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem

The multiple depot vehicle scheduling problem (MDVSP) with a single vehicle type considers the assignment of timetabled trips to homogeneous vehicles that are stationed at different depots. The assignment of trips to a vehicle also provides a schedule for a vehicle. The objective is to minimise the total cost due to waiting and travelling empty while covering all the trips. In this paper, we propose a new formulation for the MDVSP (termed as the inventory formulation) that uses assignment arcs in a multi-commodity time-space network flow formulation. A general way to solve this multi-commodity network flow problem is to decompose the problem for each commodity (in this case, for each depot). However, we apply Dantzig–Wolfe decomposition to the inventory formulation by decomposing it for each trip. Column generation is used to solve the linear relaxation of the trip-based decomposition. Column generation requires less time to solve the new trip-based decomposition than the existing depot-based decompositions. To obtain a good-quality integer solution to the MDVSP, we propose a solution framework that solves the linear relaxation of the MDVSP iteratively. At each iteration, schedules for certain vehicles in the fleet are finalised. The iterations continue until all the trips receive an allocation. Three different heuristics are proposed based on the solution framework. The computational experiments suggest that the new heuristics provide better quality solutions than the existing heuristics. For instances with a large number of trips, the new heuristics provide solutions in less time than that required by the existing heuristics.