An algorithm for the traveling salesman problem with pickup and delivery customers (Q1071656)

This paper considers the traveling salesman problem with \(2n+1\) cities of which one is a depot, n are pickup points and n are corresponding delivery points. Each possible trip by a salesman from one city to another is represented by an arc of a network to which a cost is allocated. A feasible tour is defined as one in which the salesman starts at the depot, visits all other cities exactly once without travelling to a delivery point before its corresponding pickup point is visited and then returns to the depot. The objective is find a feasible tour for which the total cost of arcs used is a minimum. A lower bound is obtained by selecting the minimum element in each row of the cost matrix and reducing every element in that row by this constant. The matrix is further reduced by applying an identical procedure to the columns. The lower bound is given by the sum of these reducing constants. When some arcs of the tour are known, several results are derived which exclude certain other arcs from a feasible tour; the costs for excluded arcs are set to infinity. A branch and bound algorithm is proposed and computational results for problems with up to 18 pickup and delivery points are provided. A generalization is given to the capacitated problem in which the quantity to be collected at each pickup point is specified and the total quantity carried at any time cannot exceed the vehicle capacity. Also, a generalization to the case that there are several salesmen to perform the pickups and deliveries is given.