Decomposition Strategies for Vehicle Routing Heuristics

Alberto Santini (), Michael Schneider (), Thibaut Vidal () and Daniele Vigo ()
Additional contact information
Alberto Santini: Department of Economics and Business, Universitat Pompeu Fabra, 08005 Barcelona, Spain; Data Science Centre, Barcelona School of Economics, 08005 Barcelona, Spain; Department of Information Systems, Decision Sciences and Statistics, ESSEC Business School, 95021 Cergy, France; Institute of Advanced Studies, Cergy Paris Université, 95000 Neuville-sur-Oise, France
Michael Schneider: Deutsche Post Chair—Optimization of Distribution Networks, RWTH Aachen University, 52072 Aachen, Germany
Thibaut Vidal: CIRRELT, Montréal, Québec H3T1J4, Canada; Scale AI Chair in Data-Driven Supply Chains, Polytechnique Montréal, Montréal, Québec H3T1J4, Canada; Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T1J4, Canada; Department of Computer Science, Pontifical Catholic University of Rio de Janeiro, Rio de Janeiro 38097, Brazil
Daniele Vigo: Department of Electrical, Electronic and Information Engineering, Alma Mater University of Bologna, Bologna 40136, Italy; CIRI-ICT, Alma Mater University of Bologna, 47521 Cesena, Italy

INFORMS Journal on Computing, 2023, vol. 35, issue 3, 543-559

Abstract: Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterization of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: We discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight their strengths and weaknesses, and derive a set of desirable properties. Through an extensive numerical campaign, we investigate the impact of decompositions within two algorithms for the capacitated vehicle routing problem: the Adaptive Large Neighborhood Search of Pisinger and Ropke (2007 ) and the Hybrid Genetic Search of Vidal et al. (2012 ). We evaluate the quality of popular decomposition techniques from the literature and propose new strategies. We find that route-based decomposition methods, which define subproblems by means of the customers contained in selected subsets of the routes of a given solution, generally appear superior to path-based methods, which merge groups of customers to obtain smaller subproblems. The newly proposed decomposition barycenter clustering achieves the overall best performance and leads to significant gains compared with using the algorithms without decomposition.

Keywords: vehicle routing; heuristics; decomposition methods (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1288 (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:35:y:2023:i:3:p:543-559

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 ().