A clustering approach to solve the multiple travelling salesmen problem. (15th May 2006)

• Record Type: Journal Article
• Authors: Chandran, Nishanth; Narendran, T.T.; Ganesh, K.
• Is Part Of: International journal of industrial and systems engineering. Volume 1:Number 3(2006)
• Page Start: 372
• Page End: 387
• Publication Date: 2006-05-15
• Subjects: logistics -- multiple travelling salesman problem -- clustering -- workload balancing -- routing problems; Systems engineering -- Periodicals; Industrial engineering -- Periodicals; 620.001171
• Languages: English
• ISSNs: 1748-5037

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.