Partial path column generation for the vehicle routing problem with time windows

Bjørn Petersen, Mads Kehlet Jepsen

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

    214 Downloads (Pure)


    This paper presents a column generation algorithm for the Vehicle Routing Problem with Time Windows (VRPTW). Traditionally, column generation models of the VRPTW have consisted of a Set Partitioning master problem with each column representing a route, i.e., a resource feasible path starting and ending at the depot. Elementary routes (no customer visited more than once) have shown superior results on difficult instances (less restrictive capacity and time windows). However, the pricing problems do not scale well when the number of feasible routes increases, i.e., when a route may contain a large number of customers. 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
    Title of host publicationInternational Network Optimization Conference (INOC), 2009,
    Place of PublicationPisa, Italy
    Publication date2009
    Publication statusPublished - 2009
    EventInternational Network Optimization Conference (INOC), 2009, - Pisa,Italy
    Duration: 1 Jan 2009 → …


    ConferenceInternational Network Optimization Conference (INOC), 2009,
    Period01/01/2009 → …


    Dive into the research topics of 'Partial path column generation for the vehicle routing problem with time windows'. Together they form a unique fingerprint.

    Cite this