A Grid-Based Two-Stage Parallel Matching Framework for Bi-Objective Euclidean Traveling Salesman Problem
| Autor: | Fandel Lin, Hsun-Ping Hsieh |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | ACM Transactions on Spatial Algorithms and Systems. 8:1-33 |
| ISSN: | 2374-0361 2374-0353 |
| DOI: | 10.1145/3526025 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|