Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times

Q1: The algorithm has not been compared to other existing neural combinatorial optimization works.

A1: To the best of our knowledge, this paper represents the initial application of neural combinatorial optimization to address RTSP/RVRP. Nonetheless, we have tried to compared different network architectures within the proposed methodology.

Q2: It is well known that the POMO algorithm is very effective in solving VRPs. What improvements have you made in the POMO network structure, and whether these improvements have brought improved results?

A2: The POMO approach mainly exploit the symmetries in the representation of a combinatorial optimization solution. In our solution framework, we incorporate the principles of the POMO approach by sampling $n$ trajectories during the training stage and employing instance augmentation during inference stage. Our results reported in Table 5 and Figure 5 can partly verify the training and inference efficiency.

Q3: The coding method of uncertain sets proposed in this paper is not very innovative.

A3: We have tried our best to study a range of encoding methods to capture the characteristics of uncertain sets. The ablation experiment presented in Appendix 7.4, "Effects of the Encoding Approaches", indicates that the uncertainty set encoding method employed in this paper is simple yet effective.

Q: I've also found a minor writing issue: it seems that in definition 3.1, it is not clear what exactly $x_{ij}$ is (one can guess, but it would be good to clarify).

A: Thank you for your advice. We will include the explanation for $x_{ij}$ in the revised version.

Here, $x_{ij}$ is a binary variable that indicates whether the edge $(i,j)$ is selected for the route: 1 for selection, and 0 for non-selection.

Q1: In contrast to [S1], there appear to be some gaps concerning the uncertainty of edge times (for example, another standard way is modeling them by some distributions).

A1: In the field of robust optimization, the modeling of robust uncertainty sets can exhibit significant variation. Apart from the classic robust optimization support sets addressed in the paper, there are also approaches such as stochastic programming with parameter distributions, and distributionally robust optimization where random variables' probability distributions lie within fuzzy sets. While these methods are beyond the scope of the present study, they hold promise as potential topics for our future research endeavors.

Q2: The novelty of the solver is unclear.

A2: Through our problem analysis and research, we found that robust problems under the min-max-regret criterion have a property that the max-regret value can only be computed when a complete solution is obtained, which aligns with the concept of delayed reward in reinforcement learning. Therefore, our work builds upon this foundation to explore the use of neural combinatorial optimization methods. In contrast to traditional robust optimization approaches, neural combinatorial optimization methods do not require complicated and professional combinatorial optimization knowledge to convert robust optimization objectives and constraints. Furthermore, they provide efficient problem-solving capabilities.

Q3: To my understanding, the MatNet solver is used to compute the reward; however, the reward quality may not be high or unclear to me (of course, some solutions at high speed are essential for actual learning, but I wanted a discussion of this area). I am unclear about the quality of the reward from MatNet [W3]. Can you explain this point more?

A3: Referring to the section "Effects of the Built-in TSP Solvers" in Appendix 7.4, it can be observed that the reward calculation methods can influence the overall performance of the model. The MatNet-based pre-trained solver, ultimately adopted in the study, outperforms approaches such as LKH and CMA-ES in terms of both the average training time per epoch and the final performance of the guided model.

Q4: [Augmentation] I'm curious what you are doing; please explain augmentation. If it is mentioned anywhere, please let me know where.

A4: Instance augmentation is a standard technique in neural combinatorial optimization. In our study, we discussed it from line 242 to line 252 in Section 4.4. ''Instance augmentation [19] during inference can also be adjusted to improve the solution quality. Concretely, we employ multiple independent randomizations on the initial one-hot node embeddings $h_{\psi_j}^0$ for each instance to explore various paths towards the optimal solution. Since two matrices are inputted to our model, they share the same randomized one-hot vector. Ultimately, the best solution is selected from the multiple generated solutions.''

Q5: I feel that it could be generalized to cases like following some normal distribution, not discrete intervals. I think the strength of the method can be used in a setting where the elapsed time of an edge is given by a sample from a certain distribution, as this seems to be a common setting in reality. In fact, I felt that it could be handled well in other locations and theoretical developments.

A5: In classic robust optimization, when dealing with uncertainty following specific probability distributions, the approach typically involves incorporating this probabilistic information into the optimization model. Instead of focusing solely on worst-case scenarios, the optimization process takes into account the likelihood or probability of different outcomes based on the known distributions of the uncertain parameters.

There are several ways to cope with uncertainty following specific distributions, e.g., stochastic programming, distributionally robust optimization, chance-constrained optimization. However, our current research is limited to investigating classic robust optimization with interval uncertainty framework.

Q6: From Def. 3.1 and the idea of using intervals, I feel that the interval is regarded everywhere as having the same importance. However, considering the actual application, it seems likely that the closer to , the heavier the penalty may be. I was curious about the generalization and future development in this area.

A6: Classic robust optimization considers the impact of uncertainty by focusing on the most unfavorable situations. By accounting for these worst-case scenarios during the optimization process, the resulting solutions are designed to be robust and resilient, offering a level of performance guarantees even under adverse conditions.

We acknowledge the possibility of associating different penalties with different interval segments. However, our methodology is centered on achieving a resilient solution across all adverse scenarios. It appears that alternative robust modeling techniques may be better suited to address your specific concerns.

Q7: I did not understand the treatment of $\Gamma$. $\Gamma$ controls the amount of how much each side is inflated from $t^{-}$ , but since $0 \leq \eta_{ij} \leq 1$ , I think it is a sum of real numbers. So I was confused by some explanations that seem to be natural number, for example 1.133 so exactly $\Gamma$ edges. Not related to the main point, but it bothers me.

A7: In practical applications, $\Gamma$ is a parameter commonly designed to be an integer controlling the number of affected edges in the worst case. Interestingly, if $\Gamma$ is set to a real number, the worst-case scenario can still be identified with a minor adjustment to Theorem 1: $\lfloor \Gamma \rfloor$ edges reach their upper bound values, one edge takes a proportional value within $[t_{ij}^-,t_{ij}^+]$, and the remaining edges reach their lower bound values.

Thank you for your comments. We will strive to broaden the literature review to incorporate more recent studies. Additionally, we will carefully review and adjust the table font size and correct any errors.

Q1: The formulation of the robust TSP presented in Section 3 seems to be the same to the one studied in reference [22]; so this just be made clear to the reader?

A1: In Section 3, we provide a detailed mathematical modeling and description of the optimization problem to help readers understand the issue this paper aims to address. This also serves as the motivation for our work moving forward. While the mathematical definition is originated from reference [22], we have extended it to a broader set of budget uncertainties, with the interval uncertainty set mentioned in reference [22] being a special case of this broader framework.

Q2: On page 9 what exactly is meant by blended and fusion in the ablation study?

A2: In the ablation study, the terms "blended" and "fusion" refer to distinct methods of combining two matrices. Their specific definitions are elaborated in Appendix 7.4, under the section titled "Effects of the Encoding Approaches". For a more detailed visual representation of these methods, please refer to Figure 4.

Q3: The choice of the baseline methods (BC - branch and cut, BD - benders decomposition, SA - simulated annealing, iDS - iterated dual substitution, edge generation - EGA) used for the experiments is not well justified; why just these methods? why no others?

A3: To the best of our knowledge, these methods currently stand as representative and effective approaches for RTSP/RVRP. As highlighted in reference [29] from the INFORMS Journal on Computing (2022), their iDS algorithm has been benchmarked against state-of-the-art results, demonstrating significant advancements by surpassing several existing records.

Q4: The datasets are just chosen from reference [22]; but it is unclear whether the observations made in the paper still valid for other datasets; how well do they generalise?

A4: Our approach is not limited to just the interval uncertainty set issue as detailed in reference [22], but extends to a wider range of budget uncertainty sets. Moreover, a hyperparameter $\Gamma$ can be leveraged to adjust the robustness of the uncertainty set. Furthermore, we conducted a study on problem scale generalization in Section 5.2.

Thank you for your valuable suggestions regarding the details and structure of our paper. We will incorporate your recommendations in the revised version, such as including illustrations of problem instances and providing an overview of "blended" and "fusion" concepts in the main text.

We acknowledge your point that while iDS was initially proposed in [29], it was experimentally implemented on RTSP in [12].

Regarding the scaling-up challenge, we regret that we do not have enough time to study the instances with up to 1000 vertexes due to resource limitations, memory constraints, and the inherent restrictions of neural network methodologies. We are committed to addressing these challenges in our future research endeavors.

Neverthless, we have conducted supplementary experiments to validate the effectiveness of our approach under general budget uncertainty conditions. Table 1 presents the comparative results for different $\Gamma$ values at a scale of $N=20$. Our method demonstrates highly encouraging outcomes within a remarkably short time when contrasted with the leading solver EGA.

Q1: Equation 6: why is the loss function minimizing the expected reward? Shouldn’t it maximize it? Moreover, the gradient of the loss is defined in Eq. 10, which is different from the loss (with a different notation).

A1: In order to maximize the expected reward, we invert the reward to align with loss minimization. Furthermore, we utilize a shared baseline technique in Eq. 10 to compute the gradient of the loss.

Q2: No code is provided at the time of submission.

A2: We will make our code publicly accessible once the paper is accepted as stated in line 706.

Q3: Why did you choose MatNet instead of e.g. BQ-NCO [1r] as your backbone?

A3: BQ-NCO presents an exceptional contribution by introducing a novel formulation for COPs as MDPs to improve out-of-distribution generalization. It leverages tail recursion properties and Bisimulation Quotienting to tackle this challenge. However, similar to AM and POMO methods, it treats "node features" as inputs. In robust scenarios where edge uncertainty is a concern, node features may become irrelevant or of limited use in this specific problem context. Hence, we choose MatNet, which handles edge features more effectively, as the backbone network.

Q4: Could the uncertainty in travel times be seen as a sort of “adversarial attack” on the solution - in other words, connecting your approach to ROCO [2r]?

A4: ROCO generates new instances from the original problem using adversarial networks (e.g., by relaxing constraints or lowering some edges) to ensure that these new instances do not lead to worse optimal costs. While both our method and ROCO offer flexibility, as they both accommodate neural networks or built-in worst-case solvers, our approach differs in that it only requires describing the uncertainty set for robust optimization, without needing to modify the policy to generate new altered solutions.

Moreover, as noted by the authors of ROCO, "Our paper also differs from the so-called `robust optimization', where the expected objective score is optimized based on a known data distribution.” ROCO addresses the black-box robustness issue of combinatorial optimization solvers, while we focus on robustness in the actual application environment of the problem.