Article ID: | iaor20033008 |
Country: | Netherlands |
Volume: | 42 |
Issue: | 1 |
Start Page Number: | 26 |
End Page Number: | 41 |
Publication Date: | May 2003 |
Journal: | Networks |
Authors: | Hadjiconstantinou E., Baldacci R., Mingozzi A. |
Keywords: | programming: integer |
In this paper, we describe a new integer programming formulation for the Traveling Salesman Problem with mixed Deliveries and Collections (TSPDC) based on a two-commodity network flow approach. We present new lower bounds that are derived from the linear relaxation of the new formulation by adding valid inequalities, in a cutting-plane fashion. The resulting lower bounds are embedded in a branch-and-cut algorithm for the optimal solution of the TSPDC. Computational results on different classes of test problems taken from the literature indicate the effectiveness of the proposed method.