An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints
- 1 May 2007
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 41 (2) , 253-264
Abstract
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 𝒩𝒫-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.Keywords
This publication has 27 references indexed in Scilit:
- The Two-Dimensional Finite Bin Packing Problem. Part II: New lower and upper bounds4OR, 2003
- The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case4OR, 2003
- Multistars, partial multistars and the capacitated vehicle routing problemMathematical Programming, 2002
- Heuristics for the container loading problemEuropean Journal of Operational Research, 2002
- A hybrid genetic algorithm for the container loading problemEuropean Journal of Operational Research, 2001
- A polyhedral study of the asymmetric traveling salesman problem with time windowsNetworks, 2000
- LP‐based bounds for the container and multi‐container loading problemInternational Transactions in Operational Research, 1999
- A result on projection for the vehicle routing problemEuropean Journal of Operational Research, 1995
- Two-Dimensional Finite Bin-Packing AlgorithmsJournal of the Operational Research Society, 1987
- A Sequential Route-building Algorithm Employing a Generalised Savings CriterionJournal of the Operational Research Society, 1976