Scholarlink

The Multiple Traveling Salesman Problem (MTSP) is an extension of the Traveling Salesman Problem (TSP), aimed at finding the optimal routes among multiple salesmen to minimize the total journey. Genetic algorithms, as a heuristic optimization method called DCNGA (DBCSAN clustering algorithm & C-N-GA), have shown good performance in solving MTSP. This heuristic algorithm is based on C-N-GA (an improved genetic algorithm) combined with the DBCSAN algorithm. By clustering cities into multiple clusters through the DBCSAN algorithm, by calculating the TSP for each cluster of cities individually to obtain local optimal solutions, which are then combined to form the global optimal solution. The 5 experimental results provided in this article indicate that the algorithm can effectively find the optimal salesman route solution, improve search efficiency by about 2%−4%, and reduce calculation time by about 10%−20%. It is suitable for solving mid-term strategic planning problems in practical applications.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Heuristic Algorithm for Solving the MTSP Problem Based on DBSCAN Clustering Algorithm and CNGA Algorithm

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Guo Chen,
  • Yiwen Cai,
  • Guangqiang Lu,
  • Yanjing Xie,
  • Fangyan Dong,
  • Kewei Chen

摘要

The Multiple Traveling Salesman Problem (MTSP) is an extension of the Traveling Salesman Problem (TSP), aimed at finding the optimal routes among multiple salesmen to minimize the total journey. Genetic algorithms, as a heuristic optimization method called DCNGA (DBCSAN clustering algorithm & C-N-GA), have shown good performance in solving MTSP. This heuristic algorithm is based on C-N-GA (an improved genetic algorithm) combined with the DBCSAN algorithm. By clustering cities into multiple clusters through the DBCSAN algorithm, by calculating the TSP for each cluster of cities individually to obtain local optimal solutions, which are then combined to form the global optimal solution. The 5 experimental results provided in this article indicate that the algorithm can effectively find the optimal salesman route solution, improve search efficiency by about 2%−4%, and reduce calculation time by about 10%−20%. It is suitable for solving mid-term strategic planning problems in practical applications.