A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem. (December 2018)

• Record Type: Journal Article
• Authors: Kulkarni, Sarang; Krishnamoorthy, Mohan; Ranade, Abhiram; Ernst, Andreas T.; Patil, Rahul
• Is Part Of: Transportation research. Volume 118(2018)
• Page Start: 457
• Page End: 487
• Publication Date: 2018-12
• Subjects: Bus scheduling -- Multi-depot -- Vehicle scheduling -- Column generation -- Inventory formulation -- Dantzig–Wolfe decomposition; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2018.11.007
• Languages: English
• ISSNs: 0191-2615

Abstract

Highlights: A new mathematical formulation is proposed to solve the multiple depot vehicle scheduling problem (MDVSP). A new decomposition of the formulation is proposed that can be solved using column generation. Column generation requires less time to solve the new decomposition than to solve the existing set partitioning formulation. Two new heuristics are proposed that use the new decomposition. The new heuristics perform better than the existing heuristics in terms of the solution quality and time. Abstract: 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.