An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints
By Manuel Iori, Juan José SALAZAR-GONZÁLEZ, Daniele Vigo. Transportation Science, 2007
309 citations recorded by the source corpus.
We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is NP-hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.
Subfields: Industrial and Manufacturing Engineering
View Paper: https://www.semanticscholar.org/paper/6f07433b35854d8540b0fba7b8a91ec57d3a9380
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Industrial and Manufacturing Engineering
- Thibaut Vidal
- Manuel Iori
- Silvano Martello
- Piotr Matl
- Gilbert Laporte
- Michel Gendreau
- Jean-François Cordeau
- Teodor Gabriel Crainic
Citations in the corpus
- Routing problems with loading constraints (2010, methodology): “On similar instances, the exact algorithm by Iori, Salazar González and Vigo [59] solved to optimality all instances with n ≤ 25 (in less than one CPU hour per instance), and 37 % of those with 25 < n ≤ 35 (with time limit set to one CPU day per instance), failing for the larger instances.”
- A concise guide to existing and emerging vehicle routing problem variants (2019, background): “2017), 2D packing (Iori et al. 2007), and 3D packing constraints (Gendreau et al.”