Clique inequalities applied to the vehicle routing problem with time windows

Simon Spoorendonk, Guy Desaulniers

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This work presents an exact branch-cut-and-price algorithm for the vehicle routing problem with time windows (VRPTW) where the well-known clique inequalities are used as cutting planes defined on the set partitioning master problem variables. It shows how these cutting planes affect the dominance criterion applied in the pricing algorithm, which is a labeling algorithm for solving resource-constrained elementary shortest path problems. The idea of using cutting planes defined on the master problem variables for the VRPTW has been recently developed: Chva´tal-Gomory rank-1 cuts were applied. However, to our knowledge, this is a first attempt at incorporating for the VRPTW a set of valid inequalities specialized for the set partitioning polytope. Computational results show that the use of clique inequalities improves the lower bound at the root node of the search tree and reduces the number of nodes in this tree.
    Original languageEnglish
    JournalI N F O R Journal
    Volume48
    Issue number1
    Pages (from-to)53-67
    ISSN0315-5986
    DOIs
    Publication statusPublished - Feb 2010

    Fingerprint

    Dive into the research topics of 'Clique inequalities applied to the vehicle routing problem with time windows'. Together they form a unique fingerprint.

    Cite this