This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  1998, with author Rinaldi G., in the category IASI Research Reports (or show them all):

---

IASI Research Report n. 495  (Previous )  

Augerat P., Belenguer J.M., Benavent E., Corberán A., Naddef D., Giovanni Rinaldi

Computational results with a branch and cut code for the capacitated vehicle routing problem

ABSTRACT

In this paper, we present a branch-and-cut algorithm to solve the Capacitated Vehicle Routing Problem (CVRP) to optimality, which is based on the partial polyhedral description of the corresponding polytope. The valid inequalities used in the algorithm are proposed and described in Cornuejols and Harche (1993), De Vitis, Harche, and Rinaldi (1999), and in Naddef and Rinaldi (1999) where also unpublished inequalities of Augerat and Pochet can be found. We concentrated mainly on the design of separation procedures for several classes of valid inequalities. The capacity constraints (generalized subtour elimination inequalities) happen to play a crucial role in the development of a cutting plane algorithm for the CVRP. A number of separation heuristics have been implemented and compared for these inequalities. We also implemented heuristic separation algorithms for other classes of valid inequalities that also lead to significant improvements: comb, capacity strengthened comb, and generalized capacity inequalities. The resulting cutting plane algorithm has been applied to a set of instances taken from the literature. The lower bounds obtained are better than the ones previously known. Some branching strategies have been implemented to develop a branch-and-cut algorithm that has been able to solve large CVRP instances, some of them that were still unsolved. The main results is the solution of two versions of a 134-customer instance proposed by Fisher. These instances are, to the best of our knowledge, the largest in the literature for which an optimal certified solution has been provided by an automatic procedure. Key words: Capacitated Vehicle Routing Problem, branch-and-cut, valid inequalities.