An exact algorithm for the Traveling Salesman Problem with Deliveries and Collections

An exact algorithm for the Traveling Salesman Problem with Deliveries and Collections

0.00 Avg rating0 Votes
Article ID: iaor20033008
Country: Netherlands
Volume: 42
Issue: 1
Start Page Number: 26
End Page Number: 41
Publication Date: May 2003
Journal: Networks
Authors: , ,
Keywords: programming: integer
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.