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

Manuel Iori (), Juan-José Salazar-González () and Daniele Vigo ()
Additional contact information
Manuel Iori: DEIS, Dipartimento di Elettronica, Informatica e Sistemistica, Università degli Studi di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy
Juan-José Salazar-González: DEIOC, Departamento de Estadística, Investigación Operativa y Computación, Universidad de La Laguna, 38271 La Laguna, Tenerife, Spain
Daniele Vigo: DEIS, Dipartimento di Elettronica, Informatica e Sistemistica, Università degli Studi di Bologna, Viale Risorgimento 2, 40136 Bologna, Italy

Transportation Science, 2007, vol. 41, issue 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 (N-script)(P-script)-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: vehicle routing; packing; exact algorithms (search for similar items in EconPapers)
Date: 2007
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (64)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1060.0165 (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:41:y:2007:i:2:p:253-264

Access Statistics for this article

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