Learning to delegate for large-scale vehicle routing
Authors: Sirui Li, Zhongxia Yan, Cathy Wu
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We perform extensive experiments to evaluate our learning framework, aiming to answer the following questions: 1. Uniform distribution. How does our method compare with baselines, in terms of solution time and quality, on problems with uniformly distributed cities? 2. Clustered distributions. How does our method perform on problems with clustered cities? 3. Out-of-distribution. Can our model generalize, such as to larger or real-world instances? 4. VRP variants. Can our method address more sophisticated VRPs? E.g., CVRP with Time Windows (CVRPTW) [37] or VRP with Mixed Pickup and Delivery (VRPMPD) [33]. 5. VRP solvers. Can our method be adapted to leverage other VRP subsolvers? |
| Researcher Affiliation | Academia | MIT siruil@mit.edu Zhongxia Yan* MIT zxyan@mit.edu MIT cathywu@mit.edu |
| Pseudocode | Yes | Algorithm 1: Learning to Delegate Input: Problem instance P, initialized solution X, subproblem selector f , subsolver Subsolver, number of steps T, parameter k denoting the size of subproblems 1 for Step t = 1: T do 2 Sk,local Construct Subproblems(P, X, k) 3 S f (Sk,local) 4 S Subsolver(S) 5 X X S [ XP \S 6 end for |
| Open Source Code | Yes | Our code is publicly available at https://github.com/mit-wu-lab/learning-to-delegate. |
| Open Datasets | Yes | We generate the training set by running our iterative framework and selecting subproblems by enumerating the subsolver on all S ∈ Sk,local. The real-world CVRP distribution derives from a CVRP dataset [4] consisting of 10 very-large-scale instances on 5 Belgium regions with N ranging from 3000 to 30000 and randomly generated demand distribution. |
| Dataset Splits | Yes | Given a particular distribution of VRP, we generate separate sets of training, validation, and test problem instances. Unless otherwise stated, our validation and test sets contain 40 instances each. We generate a dataset of instances for every (N, nc, m) ∈ {500, 1000, 2000} × {3, 5, 7} × {Clustered, Mixed} and train a single model on the entire dataset. We evaluate the model on validation and test sets of 10 instances per (N, nc, m) combination (i.e. 60 instances per N). |
| Hardware Specification | Yes | While generation times differ depending on several factors, typically it takes less than 10 hours with 200 Intel Xeon Platinum 8260 CPUs to generate a training set of 2000 instances. Training takes at most 8 hours on a single NVIDIA V100 GPU. |
| Software Dependencies | No | The paper mentions using LKH-3 and HGS solvers, and OR Tools. It also mentions training a Transformer. However, it does not provide specific version numbers for these software components or any other libraries like PyTorch or TensorFlow. |
| Experiment Setup | Yes | We select the best hyperparameters via manual search based on validation set performance. We record final results on the test set as the mean and standard error over 5 runs with different random seeds. Given a particular distribution of VRP, we generate separate sets of training, validation, and test problem instances. Unless otherwise stated, our validation and test sets contain 40 instances each. For each problem instance, we generate a rough initial solution by partitioning it into disjoint subsets of cities and briefly running the subsolver on each subset. Due to its compatibility with many VRP variants, we use LKH-3 [13] as the subsolver for all VRP distributions unless otherwise stated. |