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

Abstract

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. © 2003 Wiley Periodicals, Inc.