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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahuja, R.K., Magnanti, T.L., and Orlin, J.B., L.: Network Flows. Prentice Hall, NJ, 1993.
Bartlett, T.E.: “An algorithm for the minimum number of transport units to maintain a fixed schedule” Bartlett, T.E. and Charnes, A.: “Part II: Generalizations and Analysis”. Nav. Res. Log.Q., 4,139–149 and 207–220, 1957.
Ford, L.R. and Fulkerson, D.R.: Flows in Networks. Princeton U.P., Princeton, NJ, 1962.
Mellouli, T. and Suhl, L.: “Supporting Planning and Operation Time Control in Transportation Systems”. Symposium on Operations Research (SOR’96). Braunschweig, Germany, 1996.
Suhl, L.: Computer-Aided Scheduling: An Airline Perspective. Gabler - DUV, Wiesbaden, 1995.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mellouli, T. (1997). Improving Vehicle Scheduling Support by Efficient Algorithms. In: Operations Research Proceedings 1996. Operations Research Proceedings, vol 1996. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-60744-8_55
Download citation
DOI: https://doi.org/10.1007/978-3-642-60744-8_55
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62630-5
Online ISBN: 978-3-642-60744-8
eBook Packages: Springer Book Archive