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

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Improving Vehicle Scheduling Support by Efficient Algorithms


    Contributors:


    Publication date :

    1997-01-01


    Size :

    6 pages





    Type of media :

    Article/Chapter (Book)


    Type of material :

    Electronic Resource


    Language :

    English




    Efficient Algorithms for Overhaul Task Scheduling

    Niznik, T. / International Federation of Operational Research Societies | British Library Conference Proceedings | 2000


    Vehicle efficient scheduling system and scheduling method

    LUO CHONGCAI / PANG XIAOKUN / LIAO MINGHUI et al. | European Patent Office | 2020

    Free access

    Online-Algorithms for Reactive Transport Vehicle Scheduling

    Gaikwad, M. A. / Arajpure, V. G. | British Library Conference Proceedings | 2002


    Models and Algorithms for Single-Depot Vehicle Scheduling

    Freling, R. / Wagelmans, A. P. M. / Paixao, J. M. P. | British Library Online Contents | 2001


    Models and Algorithms for Single-Depot Vehicle Scheduling

    Freling, Richard | Online Contents | 2001