Abstract We develop an O(N 2) heuristic to solve the single vehicle many-to-many Euclidean Dial-A-Ride problem. The heuristic is based on the Minimum Spanning Tree of the modes of the problem. The algorithm's worst case performance is four times the length of the optimal Dial-A-Ride tour. An analysis of the algorithm's average performance reveals that in terms of sizes of single-vehicle problems that are likely to be encountered in the real world (up to 100 nodes) and in terms of computational complexity, the O(N 2) heuristic performs equally well, or, in many cases, better than heuristics described earlier by Stein for the same problem. The performance of the heuristic exhibits statistical stability over a broad range of problem sizes.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Analysis of an O(N2) heuristic for the single vehicle many-to-many Euclidean dial-a-ride problem


    Beteiligte:

    Erschienen in:

    Erscheinungsdatum :

    03.05.1982


    Format / Umfang :

    13 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Tour Length of Many-To-One Dial-A-Ride Service

    National Research Council (U.S.) | British Library Conference Proceedings | 2005


    A tabu search heuristic for the static multi-vehicle dial-a-ride problem

    Cordeau, Jean-François / Laporte, Gilbert | Elsevier | 2002