In the last decade computers are integrated in the planning process of public transport. As a consequence, sufficient data for discrete optimization models are available for the optimization of international, national, and local public transport applications. For huge real-world instances various vehicle and crew scheduling models have been recently solved computing the round trips and assigning vehicles and crews to timetable trips. In contrast to these scheduling problems, the authors concentrate on activities in a depot. The problem of assigning trams to positions in a depot and to the scheduled round trips of the next day, considered in this paper, arises in the daily dispatching of local public transport companies. Given an incoming order of trams and an order in which trams of the different types are supposed to leave during the day, the objective is to find an assignment of incoming trams to siding positions and to forthcoming departures that minimizes the number of shunting movements. This TDP (tram dispatching problem) turns out to be a generalization of an NP-hard storage problem which arises in container shipment. In this paper, the authors concentrate on a subproblem of the TDP. The authors look for an assignment of already stored trams to the scheduled round trips with a minimum number of shunting movements. In section two of the paper, the authors give a mathematical formulation of the departure scheduling problem. In section three, the authors prove that this decision problem is NP-complete. In section four, the authors derive a dynamic program for this problem. Section five is concerned with computational results for random test data as well as for test data of four German transport companies. The computational results show that it is possible to solve real-world instances and random instances of relevant size for practical applications within acceptable time. All the practical instances are solved in less than 1 s. Finally, the authors conclude with applications of the results in the daily dispatching process.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Scheduling trams in the morning


    Beteiligte:
    Blasum, U. (Autor:in) / Bussieck, M.R. (Autor:in) / Hochstättler, W. (Autor:in) / Moll, C. (Autor:in) / Scheel, H.H. (Autor:in) / Winter, T. (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    1999


    Format / Umfang :

    12 Seiten, 5 Bilder, 3 Tabellen, 10 Quellen



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch




    Trams

    Buckley, Richard | Online Contents | 1996



    British trams

    Waller, Peter | SLUB | 2003


    Mansfield's trams

    Hurst, Tony | SLUB | 2002


    Old trams

    Turner, Keith K. | SLUB | 1985