Abstract In this paper, the minimum fleet size problem is investigated: Find the minimum number of vehicles to serve a set of trips of a given timetable for a transportation system. First, we present an algorithm for the basic problem requiring only linear-time after suitably sorting input data. This improves a quadratic-time greedy algorithm developed in [Su95]. Our algorithm was implemented and tested with real-life data indicating a good performance. Generated diagrams on vehicle standing times are shown to be useful for various tasks. Second, Min-Max-results for the minimum fleet size problem are discussed. We argue that Dilworth’s chain decomposition theorem works only if unrestricted deadheading, i.e., adding non-profit ‘empty’ trips, is permitted and thus its application to the case of railway or airline passenger traffic is misleading. To remedy this lack, we consider a particular network flow model for the no deadheading case, formulate a Min-Max-result, and discuss its implications- along with efficient algorithms-for vehicle as well as trip and deadhead trip scheduling.
Improving Vehicle Scheduling Support by Efficient Algorithms
Operations Research Proceedings 1996 ; 9 ; 307-312
Operations Research Proceedings ; 1996 , 9
1997-01-01
6 pages
Article/Chapter (Book)
Electronic Resource
English
Efficient Algorithms for Overhaul Task Scheduling
British Library Conference Proceedings | 2000
|Vehicle efficient scheduling system and scheduling method
European Patent Office | 2020
|Online-Algorithms for Reactive Transport Vehicle Scheduling
British Library Conference Proceedings | 2002
|Models and Algorithms for Single-Depot Vehicle Scheduling
British Library Online Contents | 2001
|Models and Algorithms for Single-Depot Vehicle Scheduling
Online Contents | 2001
|