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

Sarang Kulkarni, Mohan Krishnamoorthy, Abhiram Ranade, Andreas T. Ernst and Rahul Patil

Transportation Research Part B: Methodological, 2018, vol. 118, issue C, 457-487

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.

Keywords: Bus scheduling; Multi-depot; Vehicle scheduling; Column generation; Inventory formulation; Dantzig–Wolfe decomposition (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261518301115
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:118:y:2018:i:c:p:457-487

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2018.11.007

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().