Abstract

Traveling salesman problem (TSP) is one of the most studied combinatorial optimization problems; several exact, heuristic or even learning-based strategies have been proposed to solve this challenging issue. Targeting on the research problem of bi-objective non-monotonic Euclidean TSP and based on the concept of the multi-agent-based approach, we propose a two-stage parallel matching approaching for solving TSP. Acting as a divide-and-conquer strategy, the merit lies in the simultaneously clustering and routing in the dividing process. Precisely, we first propose the Two-Stage Parallel Matching algorithm (TSPM) to deal with the bi-objective TSP. We then formulate the Grid-Based Two-Stage Parallel Matching (GRAPE) framework, which can synergize with TSPM, exact method, or other state-of-the-art TSP solvers, for solving large-scale Euclidean TSP. According to this framework, the original problem …

Date

November 2, 2022

Authors

Fandel Lin, Hsun-Ping Hsieh

Journal

ACM Transactions on Spatial Algorithms and Systems

Volume

8

Issue

4

Pages

1-33

Publisher

ACM