Solving a Large-Scale Multi-Depot Vehicle Scheduling Problem in Urban Bus Systems

Xiaomei Xu, Zhirui Ye, Jin Li and Chao Wang

Mathematical Problems in Engineering, 2018, vol. 2018, 1-13

Abstract:

This study proposes an improved model and algorithm for the large-scale multi-depot vehicle scheduling problem (MDVSP) with departure-duration restrictions. In this study, the time-space network is applied to model the large-scale MDVSP. Considering that crews usually change shifts in the depot, departure-duration restrictions are added to the classic set-partitioning model to ensure that buses return to the depot when crews reach their working time limits. By embedding a preliminary exploring tactic to the shortest path faster algorithm (SPFA), researchers developed an improved large neighborhood search (LNS) algorithm to solve large-scale instances of MDVSP with departure-duration restrictions. The proposed methodology is applied to a real-life case in China and several test instances. The results show that the improved LNS algorithm can achieve very good performance in computational efficiency without deteriorating solution quality, which is important for large-scale systems. More specifically, the total cost of the improved LNS algorithm is approximately equal to branch-and-price, but the computational time is much shorter in the case study. For test instances with different number of timetabled trips (500, 1000, 1500, and 2000), the Quality Gap ( QG ) is very small, approximately 0.35%, 0.38%, 0.63%, and 0.93%, while the Efficiency Ratio ( ER ) reaches up to 2.89, 2.98, 3.65, and 3.79, respectively.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2018/4868906.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2018/4868906.xml (text/xml)

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:hin:jnlmpe:4868906

DOI: 10.1155/2018/4868906

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().