Selective pricing in branch-price-and-cut algorithms for vehicle routing

Guy Desaulniers (), Diego Pecin () and Claudio Contardo ()
Additional contact information
Guy Desaulniers: GERAD and Department of Mathematics and Industrial Engineering Polytechnique Montréal
Diego Pecin: GERAD and Department of Mathematics and Industrial Engineering Polytechnique Montréal
Claudio Contardo: ESG UQÀM

EURO Journal on Transportation and Logistics, 2019, vol. 8, issue 2, No 3, 147-168

Abstract: Abstract Branch-price-and-cut is a leading methodology for solving various vehicle routing problems (VRPs). For many VRPs, the pricing subproblem of a branch-price-and-cut algorithm is highly time consuming, and to alleviate this difficulty, a relaxed pricing subproblem is used. In this paper, we introduce a new paradigm, called selective pricing, that can be applied in this context to reduce the time required for solving hard-to-solve VRPs by branch-price-and-cut. This paradigm requires the development of a labeling algorithm specific to the pricing subproblem. To illustrate selective pricing, we apply it to a branch-price-and-cut algorithm for the VRP with time windows, where the relaxed pricing subproblem is a shortest ng-path problem with resource constraints. We develop a labeling algorithm for this subproblem and show through computational experiments that it can yield significant time reductions (up to 32%) to reach a good lower bound on certain very-hard-to-solve VRPTW instances with 200 customers. We also introduce a new labeling heuristic which also leads to computational time reductions.

Keywords: Column generation; Vehicle routing problem; Branch-and-price; Shortest path problem under resource constraints; Selective pricing (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-017-0112-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:eurjtl:v:8:y:2019:i:2:d:10.1007_s13676-017-0112-9

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-017-0112-9

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().