Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach
In practice, vehicle scheduling is planned on a variable timetable so that the departure times of trips can be shifted in tolerable ranges, rather than on a fixed timetable, to decrease the required fleet size. This paper investigates the vehicle scheduling problem on a variable timetable with the c...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Journal of Advanced Transportation |
| Online Access: | http://dx.doi.org/10.1155/2019/2781590 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849415266787655680 |
|---|---|
| author | Zekang Lan Shiwei He Rui Song Sijia Hao |
| author_facet | Zekang Lan Shiwei He Rui Song Sijia Hao |
| author_sort | Zekang Lan |
| collection | DOAJ |
| description | In practice, vehicle scheduling is planned on a variable timetable so that the departure times of trips can be shifted in tolerable ranges, rather than on a fixed timetable, to decrease the required fleet size. This paper investigates the vehicle scheduling problem on a variable timetable with the constraint that each vehicle can perform limited trips. Since the connection-based model is difficult to solve by optimization software for a medium-scale or large-scale instance, a designed path-based model is developed. A Benders-and-Price algorithm by combining the Benders decomposition and column generation is proposed to solve the LP-relaxation of the path-based model, and a bespoke Branch-and-Price is used to obtain the integer solution. Numerical experiments indicate that a variable timetable approach can reduce the required fleet size with a tolerable timetable deviation in comparison with a fixed timetable approach. Moreover, the proposed algorithm is greatly superior to GUROBI in terms of computational efficiency and guarantees the quality of the solution. |
| format | Article |
| id | doaj-art-5746388ebd8f45ea82e5c7595448fd64 |
| institution | Kabale University |
| issn | 0197-6729 2042-3195 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Advanced Transportation |
| spelling | doaj-art-5746388ebd8f45ea82e5c7595448fd642025-08-20T03:33:35ZengWileyJournal of Advanced Transportation0197-67292042-31952019-01-01201910.1155/2019/27815902781590Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price ApproachZekang Lan0Shiwei He1Rui Song2Sijia Hao3Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Ministry of Transport, Beijing Jiaotong University, Beijing, ChinaKey Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Ministry of Transport, Beijing Jiaotong University, Beijing, ChinaKey Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Ministry of Transport, Beijing Jiaotong University, Beijing, ChinaKey Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Ministry of Transport, Beijing Jiaotong University, Beijing, ChinaIn practice, vehicle scheduling is planned on a variable timetable so that the departure times of trips can be shifted in tolerable ranges, rather than on a fixed timetable, to decrease the required fleet size. This paper investigates the vehicle scheduling problem on a variable timetable with the constraint that each vehicle can perform limited trips. Since the connection-based model is difficult to solve by optimization software for a medium-scale or large-scale instance, a designed path-based model is developed. A Benders-and-Price algorithm by combining the Benders decomposition and column generation is proposed to solve the LP-relaxation of the path-based model, and a bespoke Branch-and-Price is used to obtain the integer solution. Numerical experiments indicate that a variable timetable approach can reduce the required fleet size with a tolerable timetable deviation in comparison with a fixed timetable approach. Moreover, the proposed algorithm is greatly superior to GUROBI in terms of computational efficiency and guarantees the quality of the solution.http://dx.doi.org/10.1155/2019/2781590 |
| spellingShingle | Zekang Lan Shiwei He Rui Song Sijia Hao Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach Journal of Advanced Transportation |
| title | Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach |
| title_full | Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach |
| title_fullStr | Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach |
| title_full_unstemmed | Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach |
| title_short | Optimizing Vehicle Scheduling Based on Variable Timetable by Benders-and-Price Approach |
| title_sort | optimizing vehicle scheduling based on variable timetable by benders and price approach |
| url | http://dx.doi.org/10.1155/2019/2781590 |
| work_keys_str_mv | AT zekanglan optimizingvehicleschedulingbasedonvariabletimetablebybendersandpriceapproach AT shiweihe optimizingvehicleschedulingbasedonvariabletimetablebybendersandpriceapproach AT ruisong optimizingvehicleschedulingbasedonvariabletimetablebybendersandpriceapproach AT sijiahao optimizingvehicleschedulingbasedonvariabletimetablebybendersandpriceapproach |