Partial Path Column Generation for the Vehicle Routing Problem

Mads Kehlet Jepsen, Bjørn Petersen

    Research output: Book/ReportReportResearch

    276 Downloads (Pure)

    Abstract

    This paper presents a column generation algorithm for the Capacitated Vehicle Routing Problem (CVRP) and the Vehicle Routing Problem with Time Windows (VRPTW). Traditionally, column generation models of the CVRP and VRPTW have consisted of a Set Partitioning master problem with each column representing a route. Elementary routes (no customer visited more than once) have shown superior results for both CVRP and VRPTW. However, the pricing problems do not scale well when the number of feasible routes increases. We suggest to relax that ‘each column is a route’ into ‘each column is a part of the giant tour’; a so-called partial path, i.e., not necessarily starting and ending in the depot. This way, the length of the partial path can be bounded and a better control of the size of the solution space for the pricing problem can be obtained.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages17
    ISBN (Print)978-87-90855-59-8
    Publication statusPublished - 2009
    SeriesDTU Management 2009
    Number12

    Keywords

    • column generation
    • elementary shortest path problem
    • vehicle routing problem

    Fingerprint Dive into the research topics of 'Partial Path Column Generation for the Vehicle Routing Problem'. Together they form a unique fingerprint.

    Cite this