[ESWA] FGDC: A fine-grained divide-and-conquer approach for extending NCO to solve large-scale Traveling Salesman Problem

This repository contains the implementation of our paper FGDC: A fine-grained divide-and-conquer approach for extending NCO to solve large-scale Traveling Salesman Problem.

Highlights

• A divide-and-conquer approach is proposed to extend NCO to solve large-scale TSP.
• An effective dividing strategy is proposed to construct small-scale sub-problems.
• An MST-based merging strategy is proposed for better solution quality.
• POMO trained on TSP-100 is employed to solve TSP-1M, achieving optimal gap < 6%.

Dependencies

Main Dependency Packages

• python >= 3.8

• pytorch >= 2.0.1

• cuda >= 12.2

• LKH >= 3.0.7

• tsplib95

• pylkh

• mpire

• numpy

• tqdm

additional packages may be required to reproduce baselines

Basic Usage

We provide codes of FGDC that utilizes POMO pre-trained on TSP-100 to solve REI / TSPLIB / VLSI instances.

python main.py

To run the comparative study, you need to specify the following parameters in main.py:

• {method}: 'extnco-eff'/ 'extnco-bal'/ 'extnco-qlt'/ 'htsp'/ 'pomo'/ 'deepaco'/ 'difusco'/ 'difusco-2opt'/ 'lkh'
• {stage}: 'first'/ 'second'
• {dataset}: 'rei'/ 'tsplib'/ 'vlsi'

LKH

We provide source codes of LKH-3.0.7, and you need to install it first. For example, on Ubuntu:

cd LKH-3.0.7/
make

GCN-MCTS

This baseline method consists of two steps: 1) generate Heat Map using GCN model, and 2) generate and refine solution using MCTS.

The pre-trained GCN models are available at this link.

Rename the tsp-models/tsp50/best_val_checkpoint.tar file to tsp50.tar, and move it to the baselines/gcn_mcts/gcn/logs/ folder.

step 1

python gcn_mcts_script.py

You need to specify the {dataset} parameter in gcn_mcts_script.py. The options include 'rei', 'tsplib', and 'vlsi'.

step 2

We provide simple sripts for REI(-10K), TSPLib, and VLSI datasets.

Besides, remember to modify the baselines/gcn_mcts/code/TSP_IO.h file (lines 355-372) !!!

cd baselines/gcn_mcts/
bash solve.sh

Citation

If you encounter any difficulty using our code, please do not hesitate to submit an issue or directly contact us!

If you do find our code helpful (or if you would be so kind as to offer us some encouragement), please consider kindly giving a star, and citing our paper.

@article{chen2025fgdc,
  title={FGDC: A fine-grained divide-and-conquer approach for extending NCO to solve large-scale Traveling Salesman Problem},
  author={Chen, Xinwei and Li, Yurui and Yang, Yifan and Zhang, Li and Li, Shijian and Pan, Gang},
  journal={Expert Systems with Applications},
  pages={127950},
  year={2025},
  publisher={Elsevier}
}