A Branch-and-Price-and-Cut Algorithm for the Vehicle Routing Problem with Two-Dimensional Loading Constraints

Xiangyi Zhang (), Lu Chen (), Michel Gendreau () and André Langevin ()
Additional contact information
Xiangyi Zhang: Civil Flight Service, CAE Inc, Saint-Laurent, Quebec H4T 1G6, Canada
Lu Chen: School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
Michel Gendreau: Département de Mathématiques et de Génie Industriel, Polytechnique Montréal, Montreal, Quebec H3C 3A7, Canada; Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montreal, Quebec H3C 3J7, Canada
André Langevin: Département de Mathématiques et de Génie Industriel, Polytechnique Montréal, Montreal, Quebec H3C 3A7, Canada; Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise, la Logistique et le Transport, Montreal, Quebec H3C 3J7, Canada

Transportation Science, 2022, vol. 56, issue 6, 1618-1635

Abstract: The vehicle routing problem with two-dimensional loading constraints (2L-CVRP) is a practical variant of the classic capacitated vehicle routing problem. A number of algorithms have been developed for the problem, but it is very difficult for the existing exact methods to optimally solve instances featuring with large rectangular items. To address this issue, a branch-and-price-and-cut (BPC) algorithm is proposed in this study. A novel data structure and a new dominance rule are developed to build an exact pricing algorithm that takes the loading constraints into account. Several valid inequalities are used to strengthen the linear relaxation. Extensive computational experiments were conducted on the benchmark instances of the 2L-CVRP, showing that the BPC algorithm outperforms all the existing exact methods for the problem in terms of the solution quality. Fourteen instances are solved to optimality for the first time. In particular, the size of solvable instances with large items is nearly doubled. Moreover, managerial insights about the impact of respecting the last-in-first-out constraint are also obtained.

Keywords: capacitated vehicle routing; loading constraints; column generation; Trie (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1135 (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:ortrsc:v:56:y:2022:i:6:p:1618-1635

Access Statistics for this article

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