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

Authors: 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

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

Published online: 12 May 2006 *

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