Circular Jaccard distance based multi-solution optimization for traveling salesman problems

Abstract

Traveling salesman problem is a widely studied NP-hard problem in the field of combinatorial optimization. Many and various heuristics and approximation algorithms have been developed to address the problem. However, few studies were conducted on the multi-solution optimization for traveling salesman problem so far. In this article, we propose a circular Jaccard distance based multi-solution optimization (CJD-MSO) algorithm based on ant colony optimization to find multiple solutions for the traveling salesman problem. The CJD-MSO algorithm incorporates "distancing" niching technique with circular Jaccard distance metric which are both proposed in this paper for the first time. Experimental results verify that the proposed algorithm achieves good performance on both quality and diversity of the optimal solutions.

Keywords

• traveling salesman problem
• multimodal optimization
• multi-solution optimization
• jaccard distance
• metaheuristics