Dial a ride problems consist of a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs, where each object requires to be moved from its source to destination vertex. We consider the multi-vehicle Dial a ride problem, with each vehicle having capacity k and its own depot-vertex, where the objective is to minimize the maximum completion time (makespan) of the vehicles. We study the "preemptive" version of the problem, where an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to destination. Our main results are an O(log^3 n)-approximation algorithm for preemptive multi-vehicle Dial a ride, and an improved O(log t)-approximation for its special case when there is no capacity constraint. We also show that the approximation ratios improve by a log-factor when the underlying metric is induced by a fixed-minor-free graph.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Minimum Makespan Multi-vehicle Dial-a-Ride


    Beteiligte:
    Goertz, Inge Li (Autor:in) / Nagarajan, Viswanath (Autor:in) / Ravi, R. (Autor:in)

    Erscheinungsdatum :

    2011


    Anmerkungen:

    22 pages, 1 figure. Preliminary version appeared in ESA 2009


    Medientyp :

    Preprint


    Format :

    Elektronische Ressource


    Sprache :

    Englisch




    Dial-A-Ride Vehicle Specification

    J. B. suomala | NTIS | 1971


    ELECTRIC VEHICLE DIAL-A-RIDE SYSTEM

    LIMMER STEFFEN | Europäisches Patentamt | 2024

    Freier Zugriff

    Dial-a-Ride

    Jørgensen, Rene Munk | BASE | 2003

    Freier Zugriff