H-TSP: Hierarchically Solving the Large-Scale Traveling Salesman Problem
Authors: Xuanhao Pan, Yan Jin, Yuandong Ding, Mingxiao Feng, Li Zhao, Lei Song, Jiang Bian
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | To demonstrate effectiveness of the proposed approach, we have conducted extensive experiments on randomly generated TSP instances with different numbers of nodes. |
| Researcher Affiliation | Collaboration | Xuanhao Pan1, Yan Jin1*, Yuandong Ding1, Mingxiao Feng2, Li Zhao3, Lei Song3, Jiang Bian3 1 School of Computer Science, Huazhong University of Science and Technology, China, 2 University of Science and Technology of China, 3 Microsoft Research Asia |
| Pseudocode | Yes | Algorithm 1: Hierarchical TSP Algorithm |
| Open Source Code | Yes | Our algorithm is implemented based on Py Torch (Paszke et al. 2019), the trained models and related data are publicly available. 1https://github.com/Learning4Optimization-HUST/H-TSP |
| Open Datasets | Yes | To make experiment results comparable, Random1000 and Random10000 contain the same instances used by Fu et al. in their work (Fu, Qiu, and Zha 2021), while instances in Random2000 and Random5000 are generated with nodes that are uniformly distributed in a unit square, in line with existing approaches. |
| Dataset Splits | No | The paper mentions training epochs and warm-up stages but does not specify explicit train/validation/test dataset splits with percentages or sample counts. |
| Hardware Specification | Yes | All our experiment results were obtained on a machine with an NVIDIA Tesla V100 (16GB) GPU and Intel(R) Xeon(R) Platinum CPU. |
| Software Dependencies | No | The paper states, 'Our algorithm is implemented based on Py Torch (Paszke et al. 2019)', but does not provide a specific version number for PyTorch or other software dependencies. |
| Experiment Setup | Yes | The upper-level model consists of a pixel encoder and a DRL agent model. We use a 3-layer CNN for the pixel encoder with 16, 32, 32 channels respectively, and it outputs a 128 dimensional feature vector. And our DRL model with actor-critic architecture consists of an actor network and a critic network, each of them is a 4-layer MLP. The lower-level model follows the encoder-decoder structure, there is a 12-layer self-attention encoder and a 2-layer context-attention decoder. Most of the embedding dimension in the neural network is set to 128 except for the CNN layers, the first encoding layer and the outputting layer. During training, we use the Adam W optimizer with a learning rate of 1e-4 and a weight decay of 1e-6. For the sub-problem generation stage, we set k = 40 for the k-nearest neighbor and set the sub-problem length as 200 and the maximum number of new nodes in sub-problem as 190. The lower-level model is trained for 500 epochs in the warm-up stage, and the joint training stage takes 500, 1000, 1500, 2000 epochs respectively for different datasets. |