Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs {(si,ti)}mi=1, where each object requires to be moved from its source to destination vertex. In the multi-vehicle Dial-a-Ride problem, there are q vehicles each having capacity k and where each vehicle j ∈ [q] has its own depot-vertex rj ∈ V. A feasible schedule consists of a capacitated route for each vehicle (where vehicle j originates and ends at its depot rj) that together move all objects from their sources to destinations. The objective is to find a feasible schedule that minimizes the maximum completion time (i.e. makespan) of vehicles, where the completion time of vehicle j is the time when it returns to its depot rj at the end of its route. We consider the preemptive version of multi-vehicle Dial-a-Ride, where an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to destination. Approximation algorithms for the single vehicle Dial-a-Ride problem (q = 1) have been considered in [3,10]. Our main results are an O(log3n)-approximation algorithm for preemptive multi-vehicle Dial-a-Ride, and an improved O(logt)-approximation for its special case when there is no capacity constraint (here t ≤ n is the number of distinct depot-vertices). There is an Ω(log1/4n) hardness of approximation known [9] even for single vehicle capacitated preemptive Dial-a-Ride. We also obtain an improved constant factor approximation algorithm for the uncapacitated multi-vehicle problem on metrics induced by graphs excluding any fixed minor (eg. planar metrics). In this case, we obtain improved guarantees of O(log2 n) for capacitated multi-vehicle Dial-a-Ride, and O(1) for the uncapacitated problem.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Minimum Makespan Multi-vehicle Dial-a-Ride


    Beteiligte:
    Gørtz, Inge Li (Autor:in) / Nagarajan, Viswanath (Autor:in) / Ravi, R. (Autor:in)

    Erscheinungsdatum :

    2009-01-01


    Anmerkungen:

    Gørtz , I L , Nagarajan , V & Ravi , R 2009 , Minimum Makespan Multi-vehicle Dial-a-Ride . in Algorithms - ESA 2009 . Springer , Lecture Notes in Computer Science , no. Volume 5757/2009 , pp. 540-552 , 17th European Symposium on Algorithms , København , Denmark , 07/09/2009 . https://doi.org/10.1007/978-3-642-04128-0_48



    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Dial-A-Ride Vehicle Specification

    J. B. suomala | NTIS | 1971


    ELECTRIC VEHICLE DIAL-A-RIDE SYSTEM

    LIMMER STEFFEN | Europäisches Patentamt | 2023

    Freier Zugriff

    Dial-a-Ride Services

    Community Transport Association | British Library Conference Proceedings | 1993



    Planning Dial-a-Ride Services

    Marković, Nikola / Milinković, Sanjin / Schonfeld, Paul et al. | Transportation Research Record | 2013