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

Fandel Lin, Hsun Ping Hsieh

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Article number3526025
JournalACM Transactions on Spatial Algorithms and Systems
Issue number4
Publication statusPublished - 2022 Nov 2

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems
  • Modelling and Simulation
  • Computer Science Applications
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'A Grid-Based Two-Stage Parallel Matching Framework for Bi-Objective Euclidean Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this