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

Authors: K. Ganesh, T.T. Narendran

Addresses: Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, India. ' Department of Management Studies, Indian Institute of Technology Madras, Chennai 600036, India

Abstract: 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 algorithms 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.

Keywords: logistics management; travelling salesman problem; precedence constraints; delivery; pickup; genetic algorithms; clustering algorithms; shrink-wrap algorithms; logisitcs planning; automated scheduling.

DOI: 10.1504/IJSOM.2005.007496

International Journal of Services and Operations Management, 2005 Vol.1 No.4, pp.320 - 343

Published online: 27 Jul 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article