Clique inequalities applied to the vehicle routing problem with time windows

Research output: Research - peer-reviewJournal article – Annual report year: 2010

View graph of relations

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
Issue number1
Pages (from-to)53-67
StatePublished - Feb 2010
CitationsWeb of Science® Times Cited: 8
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 4677084