Destroy and Repair Using Hyper-Graphs for Routing
Authors: Ke Li, Fei Liu, Zhenkun Wang, Qingfu Zhang
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments demonstrate that DRHG achieves stateof-the-art performance on TSP with up to 10,000 nodes and shows strong generalization to real-world TSPLib and CVRPLib problems. |
| Researcher Affiliation | Academia | 1School of System Design and Intelligent Manufacturing, Southern University of Science and Technology 2Department of Computer Science, City University of Hong Kong |
| Pseudocode | No | The paper describes the methodology in prose and uses diagrams (Figure 1 and Figure 2) to illustrate the framework and model structure, but does not include any explicit pseudocode blocks or algorithms. |
| Open Source Code | Yes | Code https://github.com/CIAM-Group/DRHG |
| Open Datasets | Yes | Experiments demonstrate that DRHG achieves stateof-the-art performance on TSP with up to 10,000 nodes and shows strong generalization to real-world TSPLib and CVRPLib problems. Table 4 and Table 5 show the test results on real-world TSPLib and CVRPLib instances with different sizes and distributions. |
| Dataset Splits | Yes | There are 10,000 instances for TSP100 and CVRP100, 128 instances for problems of size 200 to 5,000, and 16 instances for TSP10,000. For TSP, we train the model for 100 epochs on 1,000,000 TSP100 instances. We fine-tune 20 epochs on 10,000 TSP1000 instances for large-scale problems. For CVRP, we train the model for 100 epochs on 1,000,000 CVRP100 instances. |
| Hardware Specification | Yes | We train and test our model with a single NVIDIA Ge Force RTX 3090 GPU with 24GB memory. |
| Software Dependencies | No | The paper mentions using the "Adam optimizer (Kingma and Ba 2015)" but does not specify its version or versions for other key software components like programming languages or libraries. |
| Experiment Setup | Yes | We set the embedding dimension of the encoder to 128. The decoder is composed of 6 linear attention modules, and each has 8 attention heads and 16 representative starting nodes. The hidden dimension of the feed-forward layer is set to 512. For TSP, we train the model for 100 epochs on 1,000,000 TSP100 instances. We fine-tune 20 epochs on 10,000 TSP1000 instances for large-scale problems. For CVRP, we train the model for 100 epochs on 1,000,000 CVRP100 instances. We use a batch size of 1024 and sample the training sample size in [20, 0.8n] where n is the problem size. We use the cross-entropy loss and the Adam optimizer (Kingma and Ba 2015). The initial learning rate is 1e-4, and the decay rate is 0.97 per epoch. We set the number of iterations to 1000. |