Real-time multi-depot vehicle type rescheduling problem

Pablo C. Guedes and Denis Borenstein

Transportation Research Part B: Methodological, 2018, vol. 108, issue C, 217-234

Abstract: The multiple-depot vehicle type rescheduling problem (MDVTRSP) is a dynamic extension of the classic multiple-depot vehicle scheduling problem (MDVSP), where a heterogeneous fleet is considered. The MDVTRSP consists of finding a new schedule given that a severe disruption occurred in previously scheduled trips very quickly, simultaneously minimizing the transportation costs and the deviations from the original plan. Although several mathematical formulations and solution methods have been developed for the robust MDVTRSP, the real time MDVTRSP is still unexplored. In this paper, we introduce a formulation of the problem and develop a heuristic solution method, employing time-space network, truncated column generation, and preprocessing procedures. The solution method has been implemented in several algorithm variants, combining different developed preprocessing methods. Computational experiments on randomly generated instances were performed to evaluate the performance of the developed algorithms. The best solutions concerning efficiency and efficacy were obtained by the variants considering state space reductions to accelerate the convergence process of the column generation. Solutions were obtained very quickly (in less than 150 seconds for large instances, considering up to 2500 trips, eight depots, and one breakdown. The developed heuristics also presented a good behavior for several simultaneous disruptions, solving the problem with a little increase (less than 8.5%, on average) in the required CPU time. A case study using data from a real-life small instance in Brazil also demonstrated the efficiency and efficacy of the approach when compared with manual planning strategies.

Keywords: Vehicle rescheduling; Heterogeneous fleet; Multi-depot; Column generation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S019126151730797X
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:108:y:2018:i:c:p:217-234

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.2017.12.012

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 ().