Towards Omni-generalizable Neural Methods for Vehicle Routing Problems
Authors: Jianan Zhou, Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Extensive experiments on both synthetic and benchmark instances of the traveling salesman problem (TSP) and capacitated vehicle routing problem (CVRP) demonstrate the effectiveness of our method. |
| Researcher Affiliation | Academia | 1School of Computer Science and Engineering, Nanyang Technological University, Singapore 2Department of Information Systems, Eindhoven University of Technology, The Netherlands 3Institute of Marine Science and Technology, Shandong University, China 4School of Computing and Information Systems, Singapore Management University, Singapore. |
| Pseudocode | Yes | Algorithm 1 Meta-Training for VRPs |
| Open Source Code | Yes | The code is available at: https: //github.com/Royal Skye/Omni-VRP. |
| Open Datasets | Yes | TSPLIB (Reinelt, 1991) and CVRPLIB (Uchoa et al., 2017) and we generate the diverse task set with hundreds of tasks T (n, d), where n N = {50, 55, ..., 200} and d(c, l) D = {(0, 0), (1, 1)} {c[3, 5, 7] l[10, 30, 50]}. |
| Dataset Splits | Yes | for each task Ti, the few-shot generalization performance of the task-specific model θ(K) i is evaluated on the validation instances. |
| Hardware Specification | Yes | We conduct all experiments on a machine with NVIDIA A100 PCIe (80GB) cards and AMD EPYC 7513 CPU at 2.6GHz. |
| Software Dependencies | Yes | 1) Concorde (Applegate et al., 2006): We use Concorde Version 03.12.19 with the default setting, to solve TSP instances. 2) LKH3 (Helsgaun, 2017): We use LKH3 Version 3.0.7 to solve TSP and CVRP instances. |
| Experiment Setup | Yes | For our method, Adam optimizer (Kingma & Ba, 2015) is used in both inner-loop and outer-loop optimization, with the weight decay of 1e 6. The step sizes (learning rates) are α = β = 1e 4, and decayed by 10 in the last 10% iterations to achieve a faster convergence. The batch size is M =64 (M =32 for instances with sizes larger than 150). The training task set consists of hundreds of (i.e., 341) tasks, with diverse sizes N = [50, 200] and distributions (i.e., uniform (U) and gaussian mixture (GM) distributions). Similar to Finn et al. (2017), we simply set B = K = 1 and empirically observe strong performance. ... For the hierarchical task scheduler, we set η = 1 and Es = 225K. |