Adaptive Constrained Optimization for Neural Vehicle Routing

Thanks for dedicating your time to review our work! We sincerely appreciate your acknowledgment of our contributions. Below are the detailed responses to your concerns. Corresponding experimental results can be found at link.

Response 1: Addressing the relationship between TSP variants and VRP (for weakness 1) and extending to more problem variants (for question 1)

Thank you for your thoughtful feedback. Recent studies in neural combinatorial optimization (Kwon et al., 2020; Bi et al., 2024) often view TSP as a single-vehicle variant of VRP, capturing core route optimization challenges. Studying TSP variants also offers insights into solving multi-vehicle VRP, which can be decomposed into vehicle assignment and route planning, where each vehicle solves a TSP independently. Thanks to your suggestion, we have extended our experiments to multi-vehicle VRP variants, such as CVRPTW. Detailed analyses are provided in Response 5 to Reviewer X7da due to character limits.

Response 2: Difference with Tang et al, 2022 (for weakness 3)

Thank you for your insightful comments. As shown in Equation (2) of Tang et al. (2022), their method ties dual variables to the policy, forming a policy-level $\lambda$ approach. This is conceptually equivalent to the single-$\lambda$ method, where $\lambda$ updates with policy changes but remains invariant across instances. In contrast, our proposed instance-level $\lambda$ method introduces a key distinction: it decouples the dual variable from policy optimization, allowing $\lambda$ to adapt dynamically to each instance and better handle instance-specific variations.

Response 3: Difference between time window and draft limit constraints (for question 1)

Thank you for your valuable question. While these constraints share some similarities, their properties differ. The time window constraint is theoretically more challenging (NP-complete) and empirically shows higher infeasibility rates than the draft limit constraint. TSPDL, however, also has intriguing properties. Although its constraints can be easily satisfied using a Greedy-C heuristic, balancing its objective value and constraint violations remains highly challenging. For example, Table 1 shows that increasing $\lambda$ in TSPDL50 significantly impacts the infeasibility rate and optimality gap. By contrast, the performance variation on TSPTW50 under similar conditions is relatively minor. This observation highlights TSPDL's heightened sensitivity to a method's ability to balance trade-offs, making it a valuable and distinctive benchmark. Thus, both TSPTW and TSPDL are essential for our experiments, offering complementary insights for evaluation.

Response 4: Experimental results without PIP mask (for question 2)

Thank you for your insightful question. We have conducted additional TSPTW50 experiments without the PIP mask, as shown in Table S6. Removing it significantly increases problem difficulty, creating a more challenging benchmark. Interestingly, the results reveal that our ICO method achieves a greater performance improvement under this more challenging setting, further highlighting the superiority of the proposed instance-level adaptive approach.

Response 5: Whether the learning in phase 1 is effective on a certain subset of $\lambda$ (for question 3)

Good point! Yes, the learning is only effective when the range of $\lambda$ is reasonable, i.e., on a certain subset of $\lambda$. In the experiments on TSPDL, we observed that when $\lambda$ exceeds 10 or falls below 0.1, the policy often fails to converge. But fortunately, the reasonable range ($0.1 \le \lambda \le 2.0$) is simple to identify through heuristic trials. If you are curious about more $\lambda$ settings, please see Response 2 to Reviewer LzKt.

Response 6: Description of Figure 3. (for question 4)

The “infeasible part” refers to infeasible instances and their $\lambda$ values (purple in Figure 3), while “infeasible values” denote their constraint violations. We clarify “retain the infeasible part” in lines 250–253 and will revise the paper to avoid misunderstandings.

Response 7: Patterns of $\lambda$ update (for question 5)

Thank you for your thoughtful question. Yes, we observe some common patterns in $\lambda$ updates for certain instances. We refer you to Figure 6 for the information that many infeasible solutions exhibit only minor constraint violations. For this subset of slightly infeasible instances, their $\lambda$s will quickly converge to some relatively small values within 2-3 iterations and remain stable in the subsequent iterations, which is a common pattern, but their updated $\lambda$ values are not exactly the same. In contrast, for instances with larger violations, no common pattern emerges, and $\lambda$ values diverge based on violation magnitude.

Thank you for your valuable comments and recognizing our contributions. Below please find our responses. Corresponding experimental results can be found at link.

R1: Experiments with post-search strategies (for Q1 and W2)

Thanks for your insightful questions! The post-search strategies such as EAS can integrate well with our proposed framework. Thanks to your suggestion, we have revised to extend the TSPTW experiments with EAS beyond basic sampling. As shown in Table S4, EAS can enhance both PIP and ICO. Our ICO + EAS still holds superior performance compared to the best results of PIP + EAS. This further validates the superiority of our proposed instance-level adaptive method. We will include these results into our revised paper. Thank you very much for your valuable comments.

R2: Runtime of ICO (for Q1 and W1)

Please refer to R3 to Reviewer LzKt due to space limitation.

R3: More problem variants (for Q2 and W3)

Please refer to R5 to Reviewer X7da due to space limitation.

R4: Reasons for using randomly sampled $\lambda$ in pre-training (for Q3)

The rationale of using random $\lambda$ can be explained from two perspectives:

1. Training Efficiency: In the early training stage, the policy is unconverged and generates many infeasible solutions, making instance-specific $\lambda$ updates computationally expensive. Random sampling is a practical alternative. Once the policy has sufficiently converged, the computational cost of updating $\lambda$ for the few remaining infeasible instances becomes more manageable. At this point, the training can transfer to the next stage, where instance-specific $\lambda$ values are iteratively optimized.
2. Enhanced Generalization for Inference: The $\lambda$-conditioned policy aims to behave optimally under any given $\lambda$ values. By exposing the policy to a wide range of random $\lambda$ values, its generalization ability to unseen $\lambda$ is improved. This enhanced generalization is critical for robust performance in the inference stage, where the policy cannot be retrained for every $\lambda$ value.

R5: Sensitivity of $\lambda$ (for Q4 and Q7)

Please refer to R2 to Reviewer LzKt for sensitivity analysis during inference. The hyperparameters used during fine-tuning are configured to align with inference.

R6: Inconsistency of the Gaussian Distribution of $\lambda$ (for Q5 and W4)

When collecting the running scripts for submission, we accidentally pasted the shell file from our earlier attempts into the final train_ICO.sh, where a Gaussian distribution of $\lambda$ appears in the pre-training configuration. We sincerely apologize for this careless mistake and the subsequent misunderstanding. We confirm that the settings of our experiments are entirely consistent with our description in the README file and lines 325-327 in the paper, i.e., the results on both TSPTW and TSPDL are trained using the triangular distribution.

In our early experiments, a Gaussian distribution $N(0.1,1.0)$ and a triangular distribution $T(0.1, 0.5, 2.0)$ were tested to emphasize small $\lambda$ values. We provide the results on TSPTW50 in Table S5. The simple T(0.1, 0.5, 2.0) has the best performance, which is chosen as the default setting for the final experiments. Besides, all the tested distributions outperform the PIP baseline, further verifying the robustness of our method. We will include these discussions in our revised paper. Thank you very much.

R7: ORTools (for Q6)

Thank you for your thoughtful question. The algorithm of OR-Tools generally consists of two steps: (1) generating feasible solutions via greedy heuristics and (2) iteratively refining them. However, for TSPDL, the default greedy heuristic fails to produce feasible solutions. Therefore, the optimization terminates in just a few seconds, without any feasible results.

R8: Ignored $c$ (for Q8)

The heuristic reward $c$ is also utilized in Phase 2. In Section 3.1, where we provide an overview of the proposed framework, the function $g$ is introduced as a conceptual definition that accounts for all constraint violations, and its abstract nature allows the inclusion of $c$. Explicitly adding $c$ to the equations in Section 3.1, however, may compromise the simplicity and readability of the overview. We appreciate your feedback and will revise the paper to address the inaccuracies in the Appendix.

R9: In Essential References: "recent works studying effective updates of the Lagrange Multiplier Method"

Thanks for your comment. We have discussed and compared the effective updates method such as subgradient and PID-based update in Appendix E.2. If there are any omissions, please let us know; we are happy to discuss and compare them.

---

We hope these can address your concerns, but if we missed anything please let us know.

Thanks for dedicating your time to review our work! We sincerely appreciate your recognition of our contributions to constrained combinatorial optimization. Detailed responses to your concerns are as follows. Corresponding experimental results can be found at link.

Response 1: The derivation of the $\lambda$ update rule

Thank you for your thoughtful question. The update rule for $\lambda$ presented in Section 3.2 is indeed derived from the objective in Equation (1), albeit in a simplified form. Specifically, the subgradient of Equation (1) with respect to the dual variable $\lambda_{I_i}$ can be obtained by directly computing the derivative. This yields the expression This yields the expression $\mathcal{J}\_C(\pi_{\theta^*}, I_i) = 𝔼\_{\tau \sim \pi_{\theta^*}(\cdot | I_i)}[-g\_{I_i}(\tau)]$, where $\theta^*$ denotes the optimal policy parameters corresponding to $\lambda_{I_i}$. Based on it, our update rule has two simplifications: (1) Our policy is optimized but not guaranteed optimal; (2) The expectation in the subgradient should ideally be estimated using the Monte Carlo method, but in our inference setting, the policy only samples one solution at each iteration for computational efficiency, i.e., we simplify the average estimation to a single value, $g_I(\tau_{t-1})$. We will revise the paper for clarity.

Response 2: Time complexity

Thanks for your valuable questions! Due to character limitations, please refer to Response 3 to Reviewer LzKt for a detailed explanation. In conclusion, the training time of our method is approximately the same as the PIP baseline, and our method can outperform PIP even with less inference runtime.

Response 3: Why ICO (random) performs well

Thank you for your insightful question! Unlike constrained RL, ICO (random) does not fine-tune the policy's parameters, so there is no need to enforce smooth $\lambda$ updating to mitigate fluctuations, making randomly sampled $\lambda$ values acceptable. The strong performance may stem from the conditioned policy's generalization ability. During pre-training, the policy is exposed to a wide range of randomly sampled $\lambda$ values, allowing it to generalize well across diverse $\lambda$ settings and adapt seamlessly to the random update rule during inference. Additionally, the random update rule itself is not inherently weak. By evaluating all sampled $\lambda$ values and selecting the best-so-far solution, it has a reasonable ability of identifying an effective $\lambda$.

Response 4: Clarification on Figure 3

Thank you for your insightful comments! The term “infeasible part” refers to the infeasible instances and their associated $\lambda$ values, which are depicted in purple in Figure 3. The phrase “retain the infeasible part” is explained in detail in lines 250–253 of the paper. We apologize for any confusion caused by the use of the term “infeasible part” and will revise the paper to ensure clarity and avoid potential misunderstandings.

Response 5: Extension to more problems/tasks

Thank you for your valuable comments and questions! The idea of instance-level adaptive dual variables is not specially designed for TSPTW and TSPDL; rather, it can be extended to other domains that simultaneously require constraint handling and cross-instance (or cross-environment) generalization of the RL policy, with domain-specific adaptations. To demonstrate generality, we have revised to add more VRP variants to our experiments. Below is a summary of hard-constrained problems addressed in prior works:

CVRPTW is the only problem not addressed in our experiments. While the decision space of CVRPTW appears more complex, it is, in fact, easier to satisfy its constraints compared to TSPTW and TSPDL. This is because its time window constraints can be easily satisfied by a shortcut: Add more vehicles. To construct a challenging benchmark, we propose to set a maximum limit on the number of vehicles, which also aligns more closely with real-world applications.

We have revised to conduct new experiments on CVRPTW50 with limited vehicles using JAMPR's time window generation code. Since PIP has not been extended to this problem, we used POMO as the backbone to implement ICO. Experimental results in Table S3 show that our ICO significantly outperforms the POMO baseline, especially in infeasibility rate. Full results will be included in the final paper. Thank you once again for your insightful questions. We hope these new results address your concerns.

Thank you for reviewing our work and recognizing our contributions. Below are detailed responses. Corresponding experimental results can be found at link.

Response 1: Lacking ablation study

Due to space constraints of the main paper, most of our ablation results were included in Appendix E, including the two-stage training strategy, the updating rule of $\lambda$, the conditioned network architecture, and the prior distribution of $\lambda$. Section 4.3 briefly summarizes these findings, showing the effectiveness of each component. To improve clarity, we will integrate key results into the main text.

Response 2: Sensitivity of $\lambda$

Thank you for your valuable feedback. Since the optimization landscape for $\lambda$ is typically non-convex due to the hardness of combinatorial optimization, we agree that both the initial value and learning rate of $\lambda$ are important for the optimization performance. Thanks to your suggestion, we have revised to conduct a sensitivity analysis of $\lambda$ from these two perspectives, including the initial value of $\lambda$ (denoted as $\lambda_0$) and the learning rate for updating $\lambda$ (denoted as $\alpha$). During the inference stage, we evaluated performance across $\lambda_0 \in \\{0.1, 0.15, 0.20, 0.5, 1.0\\}$ and $\alpha \in \\{0.1, 0.2, 0.5, 0.7, 1.0\\}$ on TSPTW50 and TSPDL50. Each hyperparameter was varied while keeping the other fixed at its default value. Results in Table S1 and S2 show that:

1. In 16 out of 18 settings, our ICO method surpasses the best-performing PIP model in hypervolume (HV), showing its robustness.

2. Although the performance variance (shown in the last row) is relatively small, it is not negligible. This underscores the importance of carefully tuning $\lambda$-related hyperparameters to achieve optimal performance.

Interestingly, some settings (e.g., $\alpha = 0.7$ for TSPTW50) outperform the default, suggesting that advanced hyperparameter optimization techniques like Bayesian optimization could further enhance performance. We will revise the paper to incorporate these results.

Response 3: The additional runtime overhead

Thank you for raising concerns about computational efficiency. Below, we clarify the runtime overhead during training and inference.

Training Time

The training times of the PIP method and the proposed ICO method over 110k epochs are approximately the same: for example, around 60 hours for TSPTW50 and about 10 days for TSPTW100. At first glance, fine-tuning $\lambda$ appears computationally intensive. However, in our implementation, we mitigate this by using a fixed number of batches, and in each batch, only the feasible instances are replaced with new ones, as described in lines 251-253. That is, if there is an increasing number of infeasible instances requiring iterative updates in the current batch, the number of newly generated instances in future batches will decrease correspondingly. As a result, the total number of network forward and backward computations remains equivalent to that of the original PIP method.

Inference Time

Appendix E.5 (Figure 8) provides an anytime performance analysis of hypervolume (HV), infeasibility rate, and optimality gap. The results indicate that ICO consistently outperforms single-$\lambda$ models throughout the entire iterative process on HV and gap. The only exception is the infeasibility rate at the initial stages due to the use of a very small initial $\lambda$ value. Importantly, this suggests that even if the additional runtime overhead was reduced or entirely removed, our method would still demonstrate improved performance. This improvement can primarily be attributed to the fact that the adaptively trained policy itself has better capability even without updating $\lambda$ values.

Therefore, we argue that our method's runtime issue is minor. Future work will explore predicting optimal $\lambda$ values to totally eliminate additional overhead. Thank you very much.

Response 4: Add recent studies on adaptive and dynamic methods in constrained combinatorial optimization

Thank you for valuable comment. We investigated several related works [1, 2, 3] at this aspect and will include discussions about them in the paper. In summary, these related methods proposed many interesting methods for adapting the penalty function, but thay are primarily combined with genetic algorithms instead of neural methods. If there are any omissions, please let us know; we are happy to discuss and compare them.

[1] Adaptive penalty methods for genetic optimization of constrained combinatorial problems, In 1996.

[2] An adaptive penalty scheme for genetic algorithms in structural optimization, In 2004.

[3] Adaptive feasible and infeasible tabu search for weighted vertex coloring, In 2018.