This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Iori, M. Articles by Vigo, D. Search for Related Content

An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints

DEIS, Dipartimento di Elettronica, Informatica e Sistemistica, Università degli Studi di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
DEIOC, Departamento de Estadística, Investigación Operativa y Computación, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain
DEIS, Dipartimento di Elettronica, Informatica e Sistemistica, Università degli Studi di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
miori{at}deis.unibo.it
jjsalaza{at}ull.es
dvigo{at}deis.unibo.it

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.

Key Words: vehicle routing; packing; exact algorithms
History: Received: August 2005; revised: April 2006; accepted: May 2006.