CLOSE: a heuristic to solve a precedence-constrained travelling salesman problem with delivery and pickup

Logistics Management sometimes involves pickup as well as delivery along the route. Courier service is a typical example. The imposition of precedence constraints among the places to be visited constitutes a variant of the classical Travelling Salesman Problem (TSP). This well-known np-hard problem is often solved by heuristics. The Precedence-Constrained TSP that incorporates Delivery and Pickup (PCTDP) is a much harder problem to solve. This paper addresses the PCTDP and presents a three-stage heuristic using clustering and shrink-wrap algorithm for finding an initial path as well as genetic algorithms for the final search to obtain the best solution. The proposed heuristic is tested over a range of trial datasets and is found to give encouraging results. With its ability to provide solutions of good quality at low computing times, the proposed heuristic has ample scope for application as an automated scheduler when implemented at the site of a logistics-planning cell. © 2005 Inderscience Enterprises Ltd.