Capacitated Vehicle Routing with Non-Uniform Speeds

Inge Li Gørtz, Marco Molinaro, Viswanath Nagarajan, R. Ravi

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    288 Downloads (Pure)

    Abstract

    The capacitated vehicle routing problem (CVRP) [21] involves distributing (identical) items from a depot to a set of demand locations in the shortest possible time, using a single capacitated vehicle. We study a generalization of this problem to the setting of multiple vehicles having non-uniform speeds (that we call Heterogenous CVRP), and present a constant-factor approximation algorithm. The technical heart of our result lies in achieving a constant approximation to the following TSP variant (called Heterogenous TSP). Given a metric denoting distances between vertices, a depot r containing k vehicles having speeds {λ i } i = 1 k , the goal is to find a tour for each vehicle (starting and ending at r), so that every vertex is covered in some tour and the maximum completion time is minimized. This problem is precisely Heterogenous CVRP when vehicles are uncapacitated. The presence of non-uniform speeds introduces difficulties for employing standard tour-splitting techniques. In order to get a better understanding of this technique in our context, we appeal to ideas from the 2-approximation for minimum makespan scheduling in unrelated parallel machines of Lenstra et al. [19]. This motivates the introduction of a new approximate MST construction called Level-Prim, which is related to Light Approximate Shortest-path Trees [18]. The last component of our algorithm involves partitioning the Level-Prim tree and matching the resulting parts to vehicles. This decomposition is more subtle than usual since now we need to enforce correlation between the lengths of the parts and their distances to the depot.
    Original languageEnglish
    Title of host publicationLecture Notes in Computer Science : The 15th Conference on Integer Programming and Combinatorial Optimization
    Volume6655/2011
    Place of PublicationBerlin
    PublisherSpringer
    Publication date2011
    Pages235-247
    ISBN (Print)9783642208065
    DOIs
    Publication statusPublished - 2011
    Event15th International Conference on Integer Programming and Combinatoral Optimization - New York, United States
    Duration: 15 Jun 201117 Jun 2011
    Conference number: 15

    Conference

    Conference15th International Conference on Integer Programming and Combinatoral Optimization
    Number15
    Country/TerritoryUnited States
    CityNew York
    Period15/06/201117/06/2011
    SeriesLecture Notes in Computer Science
    ISSN0302-9743

    Bibliographical note

    This Conference Proceeding is brought to you for free and open access by Research Showcase @ CMU. It has been accepted for inclusion in Tepper
    School of Business by an authorized administrator of Research Showcase @ CMU. For more information, please contact researchshowcase@
    andrew.cmu.edu.

    Fingerprint

    Dive into the research topics of 'Capacitated Vehicle Routing with Non-Uniform Speeds'. Together they form a unique fingerprint.

    Cite this