Latest revision as of 16:11, 12 February 2021

Abstract

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.

Document type: Article

Full document

Original document

The different versions of the original document can be found in:

• http://downloads.hindawi.com/journals/jat/2019/2781590.pdf under the license https://creativecommons.org/licenses/by

• http://dx.doi.org/10.1155/2019/2781590 under the license cc-by

• http://downloads.hindawi.com/journals/jat/2019/2781590.pdf,

http://downloads.hindawi.com/journals/jat/2019/2781590.xml,

http://dx.doi.org/10.1155/2019/2781590 under the license http://creativecommons.org/licenses/by/4.0

• http://dx.doi.org/10.1155/2019/2781590,

https://doaj.org/toc/0197-6729,

https://doaj.org/toc/2042-3195 under the license http://creativecommons.org/licenses/by/4.0/

• https://www.hindawi.com/journals/jat/2019/2781590,

http://downloads.hindawi.com/journals/jat/2019/2781590.pdf,

https://academic.microsoft.com/#/detail/2907074081