Int. J. of Industrial and Systems Engineering   »   2006 Vol.1, No.3

 

 

Title: A clustering approach to solve the multiple travelling salesmen problem

 

Author: Nishanth Chandran, T.T. Narendran, K. Ganesh

 

Addresses:
Department of Computer Science, University of California, Los Angeles, CA 90095-1596, USA.
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: The multiple travelling salesmen problem (mTSP) involves scheduling m salespersons to visit a set of n nodes so that each node is visited exactly once while minimising the total distance travelled by the salespersons. The mTSP is a harder variant of the well-known travelling salesperson problem (TSP). A less-addressed criterion is the balancing of workloads amongst salespersons. In a departure from other methodologies that have been employed for this purpose, we propose a clustering approach to solve the mTSP. When tested over a range of data-sets, the proposed method is found to achieve a good balance of workloads among the clusters, each of which is visited by a salesperson.

 

Keywords: logistics; multiple travelling salesman problem; clustering; workload balancing; routing problems.

 

DOI: 10.1504/IJISE.2006.009794

 

Int. J. of Industrial and Systems Engineering, 2006 Vol.1, No.3, pp.372 - 387

 

Available online: 12 May 2006

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article