Neural Deconstruction Search for Vehicle Routing Problems

Thank you for reviewing our paper and providing feedback!

Just replacing a heuristic process of removing nodes with a DNN is too simple. The contribution here does not significantly advance the field. I think the authors need to explain what are the differences and advantages of the proposed method for removing nodes over the previous methods?

We do not just replace a single component of an already existing method. NDS as a whole is a completely new large neighborhood search method. All components of NDS have been designed with a GPU-accelerated search in mind.

We highlight the advantages of NDS in the conclusion as follows: "NDS presents several key advantages. First, it delivers superior performance, consistently outperforming state-of-the-art OR methods under equal runtime. Second, NDS scales effectively to larger problem instances, handling up to N=2000 customers, due to the fact that the number of customers selected by the policy is independent of the problem size. Third, it demonstrates strong generalization across different data distributions. Finally, NDS is easily adaptable to new vehicle routing problems, requiring only small adjustments to the greedy insertion heuristic and the model input."

We also take issue with the reviewer implying that a simple mechanism is not sufficient for publication at a top conference. Quite the contrary, simple is good. Does the reviewer only want complicated methods?

Consider previous works at top conferences, such as the POMO method at NeurIPS (Kwon et al (2020)). This method introduces two simple ideas, instance augmentation and a modified loss function. That is it -- and it is NeurIPS paper. It was accepted because (1) simple is good and (2) it improves performance. NDS has a relatively simple idea (admittedly the details are not so simple), and it works. If any of the details are unclear, we would be happy to try to clear them up and thank the reviewer for their constructive input.

A similar approach of using DNNs to remove and reconstruct solutions has been used in papers [1]. However the proposed method only uses DNNs for node removal and greedy methods for reconstruction. There are three other papers[2-4] on learning similar local search operations in VRP, and those methods can also be used directly to learn removal and reconstruction.

There are significant differences between NDS and these methods. Most of the methods make only small changes to a solution at each step (considering only a very small neighborhood), in contrast NDS is a large neighborhood search method that makes significant changes at each step. Furthermore, these method reinsert with a neural network [1] or swap edges directly [2-4]. In contrast, we focus on only learning the deconstruction and use a greedy insertion algorithm for reconstruction.

IMPROVEMENTSTEP is used first in Algorithm 1, with no specific explanation as to why.

We write in line 186: "By refining s with NDS’s main search component before the training rollouts, we ensure that the training focuses on improving non-trivial solutions."

There are no details about the way you use DNNs in the decoding process, leading the reader to have little understanding of the mechanism.

Thank you for pointing this out. We will try to make this more clear in Section 3.3.

This part of the formulation needs further discussion: “This contrasts with construction-based methods, where each decision is independent of prior selections.”. However, the current construction-based methods also retain the customer information selected in the previous step or part of the path information during the decoding process.

For construction approaches the order in which previous customers have been visited is irrelevant when deciding where to go next. We will rephrase the sentence to make this more clear.

Thank you for reviewing our paper and providing feedback!

From my point of view, the framework of this paper is mainly based on SISRs. This paper replaces the heuristic destruction process of SISRs with a learning-based destruction strategy. The greedy insertion with simulated annealing in this paper is essentially the same as the heuristic reconstruction process "greedy insertion with blinks" in SISRs, both of which have the probability of accepting differential solutions to jump out of the local optimum. Based on the above observations, I think the framework of this paper remains at the engineering level. It is a migration of the framework of SISRs, which is not novel enough.

NDS and SISRs are both based on the large neighborhood search framework so there are naturally some similarities. However, both methods are still very different. As you write correctly, SISRs uses "greedy insertion with blinks". However, we do not use this mechanism during reconstruction and there is also no similarity of this mechanism to anything we do. Furthermore, the repair of SISRs is significantly more complex, as it uses different handcrafted ordering heuristics that order customers before insertion. We do not use this. We use a simple greedy insertion heuristic because it is literally the simplest heuristic to implement (except maybe random insertion).

Even if our work were merely "a migration of the framework of SISRs," it would still be remarkable that we outperform the complex original SISRs destroy mechanism using a learned policy.

We emphasize that the reviewer guidelines state "Submissions bring value to the ICLR community when they convincingly demonstrate new, relevant, impactful knowledge.".

Before the NDS paper, it was not known that using DNNs in the way we use them could lead to such good performance. If it had been known, certainly someone would have published it. We encourage you to rethink your score with these guidelines in mind.

Since the performance of SISRs is promising, it is foreseeable that it will be better after adding the machine learning strategy.

It is absolutely not foreseeable that adding a powerful ML components improves performance of a method. The computational expense of ML components has inhibited their widespread use in optimization techniques. If it was so easy, we would have nothing left to research by now. Consider that the ML community has mostly ignored SISRs until now.

There needs more baselines to compare. It should introduce more comparison algorithms for VRPTW and PCVRP, and CVRP should also introduce newly emerged baselines such as ELG [1] and UDC [2].

Why do we need more baselines? Do you have any OR methods in mind that in your opinion will outperform our current baselines? We aim to include comparisons to ELG and UDC in the future, as these methods do show good performance, but we note that it ought to be clear from the results tables in both of those papers that ELG and UDC will not outperform NDS on the instances presented.

Why is greedy insertion used to reconstruct the solution, rather than other methods such as regret insertion?

We chose greedy insertion because it is the most trivial reconstruction method we could think of (besides random insertion). We want to keep the non-learning based part of this method as simple and trivial as possible to allow for an easy adaption of the method to new problems. Regret insertion is of course a very interesting idea to try, and we thank the reviewer for the suggestion.

Can the proposed method solve the TSP?

Yes, it could be adapted to the TSP. However, we recommend to use the Concorde or LKH for solving the TSP. Large neighborhood techniques have not traditionally beaten LKH on the TSP.

There is no ablation study on the random seed v. And could you describe the reason for choosing the hyper-parameters in this paper, such as threshold factor and temperature?

We are considering including an additional ablation study. The parameters were chosen based on preliminary experiments, during which we tested a few carefully hand-selected values.

Figure 3 should be corrected to a vector diagram.

Thank you. We will correct the figure.

Thank you for reviewing our paper and providing your feedback!

We thank you for pointing out three critical strengths of the paper and we hope that you will adjust your score to reflect those strengths. We address the rest of your review below.

The paper introduces a deconstruction and re-insertion heuristic for VRP improvement, but it lacks a clear comparison with well-known heuristics, such as the 2-opt method, which also iteratively refines solutions.

The LKH3 method is an improved 2-opt method (with some other tricks as well). HGS and SISRs are far superior even to LKH3 and all other simple heuristics for this problem (savings, etc.). There is no point to compare to them.

We are curious why you believe that adding adding 2-opt as a baseline provides any additional information?

Providing an explanation of how the proposed approach differs from 2-opt would clarify the advantages of using a learning-based method for the deconstruction-recreation process.

The destroy and repair paradigm we use and 2-opt are standard concepts known in the routing literature, hence we do not explain the differences, but it is possible we have not been clear enough somewhere. If you are having trouble understanding the NDS algorithm, we would appreciate knowing what parts are not clear so that we can improve these parts of the paper.

While the paper presents NDS as a novel learning-based improvement heuristic (Costa, 2020), it does not include comparisons with other learning-based approaches in the same category. A comparative analysis with similar methods would offer a more complete view of NDS’s performance and highlight its specific strengths and weaknesses within the context of learning-based VRP solvers.

There are no learning-based improvement methods that come close or match the performance of HGS on the CVRP (and by proxy NDS). We hence focused on comparing to state-of-the-art OR methods only. If there any ML methods in particular that you have in mind, we can of course show them in the experimental results? We have not included extra ML algorithms to avoid unnecessary computation; we note that most papers in the field just copy/paste results from previous works and ignore the hardware/computation times, leading to awkward comparisons. Our goal is to have a clean comparison.

The current experiments are restricted to a specific subset of VRP problems, but VRP encompasses a wide variety of problem settings (see Berto, 2024). Testing the proposed approach on additional VRP problems, or explaining any limitations that prevent its application to other settings, would strengthen the generalizability of the method and provide clarity on its applicability across diverse VRP scenarios

Having three applications has been a standard in the AI/ML literature for many years. We hope the reviewer will consider that it would be unfortunate for the community if papers where the "experiments are thorough" and show the "approach's robustness" are given reject scores based on criteria that are not widely accepted by the community. Let us also note that we have not cherry-picked VRP variants-- the three variants in our paper are the only ones we tried.

We of course agree that results for a wider range of VRP variants would be interesting; more is always better. The work of Berto et al. (2024) specifically focuses on introducing a foundation model, so it is only natural that they would test on many problems. They use the RL4CO framework, which we are unable to use in this work.

Our work clearly demonstrates that NDS can be used to solve various VRP variants by evaluating on three significantly different VRP variants. How many different VRP variants would we need to solve to convince you of significance of our method?

The paper lacks details on how LEHD, BQ, and other learning-based solver baselines were trained and configured for this study. This is especially crucial because the reported performance for these methods differs from their original papers. Specifically, LEHD was originally trained on problems with up to 100 nodes; further clarification on how it was trained in this paper’s setting is necessary to interpret the experimental results accurately. Including these details would make the experimental setup more transparent and allow for better reproducibility and understanding of the baseline comparisons.

For LEHD and BQ, we use the model provided by the authors (both trained on instances with 100 nodes). We will update the paper and make this clear. To ensure a fair comparison, our test instances have been sampled from the same distribution as the instances used during training. At test time, we limit the search duration of LEHD by runtime (identical to NDS). For BQ we set the beam search size to 64. We believe that giving all methods a similar search budget allows for a more fair comparison.

Thank you for reviewing our paper and providing extensive feedback!

This relates to the fact that numerical experiments are - to some extent - comparing apples with oranges due to limiting the computation times of the studied algorithms instead of using a proper performance-based stopping criterion. This experimental design choice clearly favors the search technique proposed by the authors, as the neural deconstruction works instantaneously. In practice, one would not use such a time-based criterion as the problems studied are static problems usually solved in a day-ahead fashion, where solution times are not limited to seconds. In such cases, one would usually finetune an algorithm based on a performance-based stopping criterion, i.e., the number of consecutive iterations without improvements.

We acknowledge disagreements between communities about whether one should investigate iterations or runtime. However, it is important to note that runtime is the accepted criterion for routing problems in the entire operations research community and much of the work within AI. The paper associated with the well-known HGS solver [1] used a similar "unconventional experimental design" setup where all methods are limited by runtime. Can you point us to any central paper of the field that argues that runtimes are always irrelevant when solving VRP variants?

Let us also note that we are addressing the vehicle routing problem as an operational problem, not as a strategic or tactical problem. We view this in the context of human-in-the-loop, interactive decision support. This means solutions cannot be solved the day before. They must be solved fast, and the solutions are then displayed to users who may incorporate further constraints into the model and re-solve. While this work is not at the stage where we can implement it in an interactive system, we are proud to have achieved the necessary speed.

Beyond this rather unconventional experimental design decision, the authors also do not provide details if and if so how the benchmark algorithms have been tuned. Looking at the fact that hyperparameter tuning seems to be missing for the benchmark algorithms and that the experimental design in general favors the proposed algorithm, I think that statements like "Our approach surpasses the performance of state-of-the-art operations research methods" are not sufficiently substantiated and should be toned down, not only in the abstract but in the manuscript.

We have not performed hyperparameter optimization on either NDS or any of the baseline approaches. We note that the baselines have likely undergone tuning by their respective authors. Tuning all methods for the different scenarios is very computationally expensive. Both our main baselines HGS and SISRs have been designed and evaluated on instances very similar to ours as we use the instance generator from [2] and would likely not benefit much from tuning. We note that it is not standard to tune all baseline methods in the ML community due to the high computational costs associated with tuning a method that requires GPUs.

[1] Vidal, Thibaut. "Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood." Computers & Operations Research 140 (2022): 105643.
[2] Eduardo Queiroga, Ruslan Sadykov, Eduardo Uchoa, and Thibaut Vidal. 10,000 optimal CVRP solutions for testing machine learning based heuristics. In AAAI-22 Workshop on Machine Learning for Operations Research (ML4OR), 2022.

As indicated in my summary, the authors are currently (significantly) overselling the contribution of the proposed method.

Based on our responses above, we honestly do not believe that we oversell our method. Does NDS need a costly GPU at test time? Yes. Does it need an expensive training phase? Yes. Does it dominate other approaches across all possible runtime limits? Likely not (but which method does?) Does it surpasses the performance of state-of-the-art operations research methods across three challenging vehicle routing problems of various problem sizes in our experiments? Yes! And this is a rather exciting result, one that we have been working towards for many years.

In Section 4.4 you discuss generalization against distribution shifts, did you also investigate this for varying instance sizes?

No, currently we focus on distribution shifts only. We are currently considering showing the generalization ability of a model trained on instances with 1000 customers when applied to instances with 2000 customers.