![](/images/graphics-bg.png)
Solving a Large-Scale Multi-Depot Vehicle Scheduling Problem in Urban Bus Systems
Joint Authors
Zhirui, Ye
Xu, Xiaomei
Li, Jin
Wang, Chao
Source
Mathematical Problems in Engineering
Issue
Vol. 2018, Issue 2018 (31 Dec. 2018), pp.1-13, 13 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2018-08-23
Country of Publication
Egypt
No. of Pages
13
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Xu, Xiaomei& Zhirui, Ye& Li, Jin& Wang, Chao. 2018. Solving a Large-Scale Multi-Depot Vehicle Scheduling Problem in Urban Bus Systems. Mathematical Problems in Engineering،Vol. 2018, no. 2018, pp.1-13.
https://search.emarefa.net/detail/BIM-1207718
Modern Language Association (MLA)
Xu, Xiaomei…[et al.]. Solving a Large-Scale Multi-Depot Vehicle Scheduling Problem in Urban Bus Systems. Mathematical Problems in Engineering No. 2018 (2018), pp.1-13.
https://search.emarefa.net/detail/BIM-1207718
American Medical Association (AMA)
Xu, Xiaomei& Zhirui, Ye& Li, Jin& Wang, Chao. Solving a Large-Scale Multi-Depot Vehicle Scheduling Problem in Urban Bus Systems. Mathematical Problems in Engineering. 2018. Vol. 2018, no. 2018, pp.1-13.
https://search.emarefa.net/detail/BIM-1207718
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1207718