New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows

Diego Pecin (), Claudio Contardo (), Guy Desaulniers () and Eduardo Uchoa ()
Additional contact information
Diego Pecin: Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal QC H3T 1J4, Canada; and Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada
Claudio Contardo: Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada; and Département de management et technologie, ESG UQÀM, Montréal, QC H2X 3X2, Canada
Guy Desaulniers: Département de mathématiques et de génie industriel, Polytechnique Montréal, Montréal QC H3T 1J4, Canada; and Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada
Eduardo Uchoa: Group for Research in Decision Analysis (GERAD), HEC Montréal 3000, QC H3T 2A7, Canada; and Département de management et technologie, ESG UQÀM, Montréal, QC H2X 3X2, Canada

INFORMS Journal on Computing, 2017, vol. 29, issue 3, 489-502

Abstract: The vehicle routing problem with time windows (VRPTW) consists of finding least-cost vehicle routes to satisfy the demands of customers that can be visited within specific time windows. We introduce two enhancements for the exact solution of the VRPTW by branch-price-and-cut (BPC). First, we develop a sharper form of the limited-memory subset-row inequalities by representing the memory as an arc subset rather than a node subset. Second, from the elementary inequalities introduced by Balas in 1977, we derive a family of inequalities that dominate them. These enhancements are embedded into an exact BPC algorithm that includes state-of-the-art features such as bidirectional labeling, decremental state-space relaxation, completion bounds, variable fixing, and route enumeration. Computational results show that these enhancements are particularly effective for the most difficult instances and that our BPC algorithm can solve all 56 Solomon instances with 100 customers and 51 of 60 Gehring and Homberger instances with 200 customers.

Keywords: vehicle routing; time windows; branch-price-and-cut; elementary inequalities; limited-memory subset-row inequalities (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2016.0744 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:29:y:2017:i:3:p:489-502

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().