A novel clustering method for breaking down the symmetric multiple traveling salesman problem

Abstract

Purpose: This study proposes a new two-stage clustering method to break down the symmetric multiple traveling salesman problem (mTSP) into several single standard traveling salesman problems, each of which can then be solved separately using a heuristic optimization algorithm. Design/methodology/approach: In the initial stage, a modified form of factor analysis is used to identify clusters of cities. In the second stage, the cities are allocated to the identified clusters using an integer-programming model. A comparison with the k-means++ clustering algorithm, one of the most popular clustering algorithms, was made to evaluate the performance of the proposed method in terms of four objective criteria. Findings: Computational results and comparison on 63 problems revealed that the proposed method is promising for producing quality clusters and thus for enhancing the performance of heuristic optimization algorithms in solving the mTSP. Originality/value: Unlike previous studies, this study tackles the issue of improving the performance of clustering-based optimization approaches in solving the mTSP by proposing a new clustering method that produces better cluster solutions rather than by proposing a new or improved version of a heuristic optimization algorithm for finding optimal routes.

Keywords

• clustering, factor analysis, k-means, multiple traveling salesmen