Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer
Authors: Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, Jing Tang
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Results show that our DACT outperforms existing Transformer based improvement models, and exhibits much better generalization performance across different problem sizes on synthetic and benchmark instances, respectively. and 5 Experiments We evaluate our DACT model on two representative routing problems, i.e., TSP and CVRP [5, 8, 11]. For each problem, we abide by existing conventions to randomly generate instances on the fly for three sizes, i.e., N = 20, 50 and 100. |
| Researcher Affiliation | Academia | Yining Ma1, Jingwen Li1, Zhiguang Cao2, , Wen Song3, , Le Zhang4 , Zhenghua Chen5, Jing Tang6 1National University of Singapore 2Singapore Institute of Manufacturing Technology, A*STAR 3Institute of Marine Science and Technology, Shandong University 4University of Electronic Science and Technology of China 5Institute for Infocomm Research, A*STAR 6The Hong Kong University of Science and Technology {yiningma, lijingwen}@u.nus.edu, zhiguangcao@outlook.com, wensong@email.sdu.edu.cn, zhangleuestc@gmail.com, chen0832@e.ntu.edu.sg, jingtang@ust.hk |
| Pseudocode | No | No structured pseudocode or algorithm blocks were found. |
| Open Source Code | Yes | Our code in Py Torch are available here8. 8https://github.com/yining043/VRP-DACT |
| Open Datasets | Yes | We evaluate our DACT model on two representative routing problems, i.e., TSP and CVRP [5, 8, 11]. and We apply DACT to solve the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). and In Table 2(a), DACT v.s. baselines on benchmark datasets (up to 200 customers, see Appendix E.4 for detailed results and discussion); (b) PE v.s. CPE on different sizes. OR-Tools [37]... TSPLIB [38] and CVRPLIB [39]. The paper also describes generating instances randomly generate instances on the fly. |
| Dataset Splits | No | No explicit percentages or sample counts for training, validation, and test splits were provided. The paper mentions generating instances on the fly for training and inference without specific split details. |
| Hardware Specification | Yes | The DACT is trained and tested on a server equipped with TITAN RTX GPU cards and Intel i9-10940X CPU at 3.30 GHz. |
| Software Dependencies | No | The paper mentions 'Our code in Py Torch are available here8.' but does not specify a version number for PyTorch or any other software dependencies. |
| Experiment Setup | Yes | For each problem, we abide by existing conventions to randomly generate instances on the fly for three sizes, i.e., N = 20, 50 and 100. Initial experiments with three operators including 2-opt, swap and insert show that 2-opt performs best for both TSP and CVRP (with insert better than swap), hence we report results of our method based on 2-opt. Following [4, 11, 27] we use randomly generated initial solutions for training and the solutions generated by the greedy algorithm for inference. Since each problem has its own constraints and node features, we adjust the input, feasibility masks, and problem-dependent hyperparameters for each problem, the details of which are provided in Appendix D and E. |