A Grid-Based Two-Stage Parallel Matching Framework for Bi-Objective Euclidean Traveling Salesman Problem

• Published in: ACM transactions on spatial algorithms and systems 2022-11, Vol.8 (4), p.1-33, Article 31
• Main Authors: Lin, Fandel, Hsieh, Hsun-Ping
• Format: Article
• Language: English
• Subjects: Algorithm design techniques; Theory of computation
• ISSN: 2374-0353; 2374-0361
• DOI: 10.1145/3526025

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 space is divided into smaller regions and then computed in parallel, which helps to tackle and derive solutions for larger-scale Euclidean TSP within reasonable computational resources. Preliminary evaluation based on TSPLIB testbed shows that our proposed GRAPE framework holds a decent quality of solutions in especially runtime for large-scale Euclidean TSP. Meanwhile, experiments conducted on two real-world datasets demonstrate the efficacy and adaptability of our proposed TSPM in solving the bi-objective non-monotonic TSP.