Clique inequalities applied to the vehicle routing problem with time windows

Publication: 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
Publication dateFeb 2010
Volume48
Issue1
Pages53-67
ISSN0315-5986
DOIs
StatePublished
CitationsWeb of Science® Times Cited: 2
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 4677084