The classical Capacitated Vehicle Routing Problem [2] calls for the determination of the optimal set of routes to be performed by a fleet of vehicles, each with a maximum transport capacity, in order to satisfy the demands of a given set of customers. The demands are usually expressed by a positive integer, representing the weight or volume to be delivered. This can lead to a too strong approximation for many practical routing applications, where real demands are composed by items of a given size, and the loading of these items into the vehicles can be difficult. We consider the practical case in which the demand of each customer is defined by a set of rectangular items, each with a given weight and base dimensions. Thus, loading these items into a vehicle requires both checking that the maximum weight capacity is respected, and that the two-dimensional loading is feasible. The problem is composed by a routing part, which was solved through a branch and cut technique, and by a loading part, solved through a dedicated branch and bound derived from the one proposed in [1]. Separation procedures and lower bounds were developed for the new problem, as well as greedy heuristics and local search. The algorithm was coded in C and tested on instances derived from those available in the literature, being able to solve to optimality instances with up to 35 customers and 110 items. References: [1] S. Martello and D. Vigo. Exact Solution of the Two-Dimensional Finite Bin Packing Problem. Management Science 44, 388 - 399 (1998). [2] The Vehicle Routing Problem. P. Toth and D. Vigo editors. SIAM Monographs on Discrete Mathematics and Applications (2002).
M. Iori, J.J. Salazar, D. Vigo (2004). An exact approach for the capacitated vehicle routing problem with twodimensional loading constraints. s.l : s.n.
An exact approach for the capacitated vehicle routing problem with twodimensional loading constraints
VIGO, DANIELE
2004
Abstract
The classical Capacitated Vehicle Routing Problem [2] calls for the determination of the optimal set of routes to be performed by a fleet of vehicles, each with a maximum transport capacity, in order to satisfy the demands of a given set of customers. The demands are usually expressed by a positive integer, representing the weight or volume to be delivered. This can lead to a too strong approximation for many practical routing applications, where real demands are composed by items of a given size, and the loading of these items into the vehicles can be difficult. We consider the practical case in which the demand of each customer is defined by a set of rectangular items, each with a given weight and base dimensions. Thus, loading these items into a vehicle requires both checking that the maximum weight capacity is respected, and that the two-dimensional loading is feasible. The problem is composed by a routing part, which was solved through a branch and cut technique, and by a loading part, solved through a dedicated branch and bound derived from the one proposed in [1]. Separation procedures and lower bounds were developed for the new problem, as well as greedy heuristics and local search. The algorithm was coded in C and tested on instances derived from those available in the literature, being able to solve to optimality instances with up to 35 customers and 110 items. References: [1] S. Martello and D. Vigo. Exact Solution of the Two-Dimensional Finite Bin Packing Problem. Management Science 44, 388 - 399 (1998). [2] The Vehicle Routing Problem. P. Toth and D. Vigo editors. SIAM Monographs on Discrete Mathematics and Applications (2002).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
