Title: A clustering approach to solve the multiple travelling salesmen problem
Author: Nishanth Chandran, T.T. Narendran, K. Ganesh
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.
Int. J. of Industrial and Systems Engineering, 2006 Vol.1, No.3, pp.372 - 387
Available online: 12 May 2006