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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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


    Contributors:

    Published in:

    Publication date :

    1982-05-03


    Size :

    13 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    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