Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times
Authors: Pei Xiao
Zizhen Zhang
Jinbiao Chen
Jiahai Wang
Zhenzhen Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Robust Routing Problem
Min-max Regret Criterion
Deep Reinforcement Learning
Attention Mechanism
Primary area: deep_learning_architectures

Abstract: We consider the robust routing problem with uncertain travel times under the min-max regret criterion, which represents an extended and robust version of the classic traveling salesman problem (TSP) and vehicle routing problem (VRP). The general budget uncertainty set is employed to capture the uncertainty, which provides the capability to control the conservatism of obtained solutions and covers the commonly used interval uncertainty set as a special case. The goal is to obtain a robust solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. Given the significant advancements and broad applications of neural combinatorial optimization methods in recent years, we present our initial attempt to combine neural approaches for solving this problem. We propose a dual multi-head cross attention mechanism to extract problem features represented by the inputted uncertainty sets. To tackle the built-in maximization problem, we derive the regret value by invoking a pre-trained model, subsequently utilizing it as the reward during the model training. Our experimental results on the robust TSP and VRP demonstrate the efficacy of our neural combinatorial optimization method, showcasing its ability to efficiently handle the robust routing problem of various sizes within a shorter time compared with alternative heuristic approaches.

Neural Combinatorial Optimization for Robust Routing Problem with Uncertain Travel Times
Pei Xiao', Zizhen Zhang" Jinbiao Chen', Jiahai Wang', Zhenzhen Zhang? School of Computer Science and Engineering, Sun Yat-sen University, P.R. China School of Economics and Management, Tongji University, P.R. China 2 xi xiaop39dmai12 sysu. edu. en, zhangzzh7@mail waw.aaillssssueduuuuuu edu.cc chenjb690mail2 sysu. edu, cn, wangjiah0mail. sysu.. edu, cn zhenzhenzhang@tougi edu.
Abstract
We consider the robust routing problem with uncertain travel times under the min-max regret criterion, which represents an extended and robust version of the classic traveling salesman problem (TSP) and vehicle routing problem (VRP). The general budget uncertainty set is employed to capture the uncertainty, which provides the capability to control the conservatism of obtained solutions and covers the commonly used interval uncertainty set special case. The goal is to obtain a robust solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. Given the significant advancements and broad applications of neural combinatorial optimization methods recent years, we present initial attempt combine neural approaches for solving this problem. We propose a dual multi-head cross attention mechanism to extract problem features represented by the inputted uncertainty sets. To tackle the built-in maximization problem, we derive the regret value by invoking pre-trained model, subsequently utilizing it the reward during the model training. Our experimental results the robust TSP and VRP demonstrate the efficacy of our neural combinatorial optimization method, showcasing its ability efficiently handle the robust routing problem of various sizes within a shorter time compared with alternative heuristic approaches.
Introduction
The classic Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) represent fundamental NP-hard combinatorial optimization challenges. these routing problems, an agent commences from designated node and fulfills specific task requisites. The primary objective to minimize the total travel time or cost of access. However, the classic routing problem is mathematically simplified and idealized, lacking the necessary robustness to handle the complexities of the real world. In actual scenarios, the existence of various uncertain factors may significantly impact the final outcome. For example, considering the travel time between two nodes, it is not only affected by objective factors such as traffic conditions, road quality, and weather, but also by subjective factors such the traveler's status and mood. When planning a trip and estimating travel time, uncertainty about the actual travel conditions may arise. To ensure a satisfactory travel experience, it is sensible adopt robust approach, which involves seeking solution that is less vulnerable to adverse conditions, even in the worst-case scenario.
While there several robust routing formulations in the literature, this study primarily focuses classic robust routing problems featuring a budget uncertainty set. The underlying idea is that the uncertainty support set represented by set of interval data, but usually not all ares are affected to
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

achieve their worst values simultancously in one realistic scenario. More concretely, the travel time between two nodes given by range with upper and lower values, and parameter I' is used to specify the number of affected arcs. In addition, the min-max regret criterion (also known as robust deviation criterion (1) is generally considered, which avoids overconservatism while considering certain degree of robustness. It aims to minimize the maximum deviation from the optimal route over the realization of edge costs in all scenarios. Detailed definition of such criterion will be provided in Section 3
To tackle the robust routing problem, traditional robust optimization methods have been employed, including both exact and heuristic approaches. These methods treat the problem instances individually and aim to generate optimal or near-optimal robust solutions within reasonable computation time. However, their efficiency diminishes when dealing with large set of instances that exhibit similar interval uncertainty structures. Specifically, the uncertain travel time of edges in different instances may share comparable upper and lower limits, following certain hourly daily patterns. To overcome these limitations, we can leverage advanced neural techniques to exploit the underlying patterns and similarities in the data, thus enabling the derivation of more efficient solutions.
In summary, this paper attempts explore the neural combination optimization methods address the robust routing problem with uncertain travel times characterized by budget uncertainty set. The contributions of our work can be highlighted as follows.
We introduce the robust routing problem with the general budget uncertainty set, which covers the interval uncertainty set as special case, and treat the problem from the perspective of deep reinforcement learning.
We propose an end-to-end neural model to capture the features of robust routing problem, and use a pre-trained neural model to efficiently calculate the reward with respect to the worst-case scenario during training.
We conduct extensive experiments on Robust Traveling Salesman Problem (RTSP) and Robust Capacitated Vehiele Routing Problem (RVCRP) instances. The results substantiate the efficacy of our approach in efficiently handling robust routing problems across diverse scales within shorter computation time.
The remainder of the paper is structured as follows. In Section 2 we provide an overview of existing works related to robust optimization and neural combinatorial optimization, respectively. Section 3. taking the Robust Traveling problem as an example, we describe the problem definition of RTSP in detail. In Section 4 we elaborate the proposed neural combinatorial optimization method. In Section 5 we provide experimental results for different RTSP and RCVRP instances. In Section 6 we conclude our work with possible future directions.
2 Related Work
Robust Optimization. As early the 1950s, Bellman and Zadeh [2] initiated research uncer- tainty optimization. Robust optimization, as introduced by Ben-Tal et al. [3), adopts a conservative approach based on worst-case optimization, ensuring that the obtained solution remains feasible for any possible realization of uncertain parameters. The formulation of robust optimization models varies significantly depending on the choice of uncertainty sets and robustness standards. Uncertainty polyhedron sets [5], budget sets (6), and more. Robustness standards encompass criteria such as the normal min-max standard, min-max min-max-regret standard [I] adjustable robustness 77. etc. Considering the literature of RTSP, Montemanni al. [8] proposed exact algorithms for RTSP with interval uncertainty sets, employing the robust deviation criterion. Chassein and Goerigk [9] introduced a recoverable robust model that allows a tour to modify a limited number of edges once a scenario becomes known. Lu et al. [10 proposed heuristic method based on simulated annealing and the LKH algorithm to solve RTSP with the min-max regret criterion and interval uncertainty sets. Additionally, Hasegawa and Wu [1] presented an intriguing heuristic edge generation algorithm to tackle this problem. On the issue of Robust VRP, Sungur et al. 12 applied the MTZ model to the traditional CVRP problem and
sets encompass various types, including interval sets (3. ellipsoid sets 4 3
VRP

---

robustly modeled demand uncertainty. Subsequently, Solano-Charii Charris et al. [13] introduced a meta- heuristic algorithm based on local search address the lexicographic min-max criterion. Eufinger et al. [4 proposed a heuristic algorithm for solving the k-adaptability min-max-min criterion.
Neural Combinatorial Optimization. Neural combinatorial optimization methods for end-to-end solving of the Vehicle Routing Problem (VRP) can be broadly categorized into supervised learning (SL. and deep reinforcement learning (DRL) approaches [[5]. While SL requires high-quality solutions to the VRP as training labels [6 DRI. methods are divided into value-based [19 21 and policy-based techniques. Given the complexity of routing policies, policy-based DRL approaches have become the mainstream choice, achieving notable success various combinatorial optimization problems (42,24), including routing (25H28). In recent years, advancements have continued. For example, Zhang et al. [29] introduced a DRL method employing an edge-based graph attention network for solving the practical Vehicle Routing Problem with Time Windows (VRPTW). ). Additionally, Kwon et al. 30 designed a neural model utilizing cross attention to handle matrix inputs, while Zhou et al. [3] presented general meta- meta-learning framework that considers the generalization of size and distribution in vehicle routing problems. These studies collectively contribute to the advancement of neural combinatorial optimization methods, showcasing their ability to tackle various types of routing problems.
Neural Methods for Robust Optimization. In recent studies, there have been initial attempts to apply neural methods the field of robust optimization. Jacobs al. [32] employed reinforcement learning to solve min-max robust optimization problems. They precisely solved the inner minimization problem and utilized the DQN method to handle the outer problem. Dumouchelle et al. (3 proposed an efficient Sechinn-eearnng---eee
instantiation of the column-and-constraal generation algorithm for two-stage min-max-min robust optimization problems. Our approach differs in that we solely train a neural model capable of rapidly constructing high-quality solutions through inference. By focusing on training neural model, we aim to provide novel perspective on addressing the robust routing problem.
3 Problem Description
In the subsequent discussion, employ RTSP paradigmatic illustration of the robust routing problem for comprehensive exposition. More detailed formulations of RTSP and RCVRP can be referenced in Appendix 7.3
3.1 Nominal TSP
The traveling salesman problem is a classic combinatorial optimization problem mathematically defined as follows. Given a complete symmetric graph G = (V, E), where V = {1, 2..., nz is the node set, 4... as nominal value, denote the expected travel time of edge (i,j) E E. Here, Taj is binary variable that indicates whether the edge (i,j) is selected for the route, with 1 for selection and 0 for non-selection. The objective is to find close route with the minimum total travel time.
For simplicity, we hereinafter use S to represent the solution space, which is the set of all feasible TSP routes.
3.2 Robust TSP
Based on historical data, it is relatively straightforward determine the fluctuation range [Ly Gt) of travel time for each edge (i,j), where t.y and ti denote the lower and upper bounds of possible values, respectively. The interval uncertainty set is defined as Vinterval [t]t.s [t t Vii,j) e E} = (tlt,, = t. + t. 0 < T, < 1, Vi.,) E E}. where by = = t... To provide flcxibility to control the conservatism of obtained solutions, the budget uncertainty set is usually considered, which is defined as Unudget [t]t,, f, + Tyj 0 S 7i S 1, vi.j) E E; E(iJ)E Mhj S l). Here, the parameter I' controls the number of affected edges. It is apparent that the budget uncertainty set simplifies to the interval uncertainty set when 2 (t) and the deterministic version when I' = O. Hence, the budget uncertainty set demonstrates certain level of generalization.
3

---

To specify the objective of RTSP, the mex-rex criterion is adopted. For better understanding, we first introduce the concept of regret.
Definition 3.1 (regret). Given a TSP solution x and a scenario u, the regret value denotes the difference between the objective value of and the optimal solution under u.
regret(x, u) = Σ tijo.
min
Σ 4f
(I)
VEB
(N,)
((,)EE
where t is the actual travel time of edge (i.j) under scenario y is the 0-1 decision variable of TSP
nominal TSP under scenario u.
Definition 3.2 (min-max- max--egret criterion). It aims to find a TSP solution that minimizes the maximum regret over all realizations of edge costs.
min max mnaxregret(z; u), x
(2)
where U is the uncertainty set including all possible scenarios.
From Equation (2) it is evident that RTSP is difficult to solve directly due to its triple optimality judgment. However, it is worth mentioning that in Montemanni et al. S a theorem regarding the derivation of the worst-case scenario in budget uncertainty set is proposed under the min-max-regret criterion. By leveraging this theorem, the complexity of RTSP can be significantly reduced.
Theorem 1. Given TSP solution x, the worst-case scenario in budget uncertainty set for solution (i.e., the scenario that maximizes the regret of solution x) is the one where exactly I edges with the largest upper bound in takes its upper bound (i.e., 7aj and taj ti + txgh. and the remaining
edges take its lower bound (i.e. Tkj = O and tig = t,y))
Proof. See Appendix 7.1
Given that the interval uncertainty set a special case of the budget uncertainty with 1' corollary can be outlined as follows.
(?)
Corollary 1. Given TSP solution x; the worst-case scenario interval uncertainty set for solution x (i.e., the scenario that maximizes the regret of solution x) is the one where all the traversed edges of solution x reach their upper bound limit and the remaining edges reach their lower bound limit.
Taking the interval uncertainty for example, let we(x) denote the worst-case scenario for solution
Its associated travel time we((z)
ig is given by:
ig
wc(x)
= I. + (1 x.
v(i,j) E E
(3)
Therefore, the formulation of RTSP can be simply expressed as:
min WEB
{
Σ
min WEB
Σ
Vig
(UJEE
(UJ)
In Figure [ we give a specific example to illustrate the solution process of RTSP with interval uncertainty. There are 4 nodes and 6 edges. Each edge is associated with uncertainty interval (see Figure Th). Assuming that a feasible solution x is "I + 2-3 + 4 + 1" represented by the green edges, its nominal total time is 5 9 + 4 4 22. According to Corollary [| we can obtain the worst-case scenario wc(x) with respect to x, as indicated by the edge values in Figure Tb. In this case,
determine the optimal solution under the scenario wc(z), represented by the red edges in Figure l.. with a total time 5 + 1 + +4 4- = 14. The max-regret value for x is then calculated as 22-14
14 = 8. By obtaining the max-regret for every feasible solution, the final optimal solution is the
one with the minimum max-regret.
Methodology
The objective of the robust routing problem is to discover robust route that minimizes the max- regret. Only when route complete can we calculate max-regrel value. This observation bears resemblance to the concept of delayed reward in deep reinforcement learning. We propose employing the neural combinatorial optimization method to construct such route an end-to-end manner. To elaborate approach, also employ RTSP with interval uncertainty for the study.

---

[2.5]
[5]
[4.6]
[3,5]
[3,4]
[9]
[4]
x: 1-2-344-
[1,4)
[4]
[4]
wa(k]
optimal sol in wa(s)
(a)
(b)
(c)
Figure 1: An instance of RTSP with interval uncertainty. (a) Interval support (b) Worst case
scenario wc(x) corresponding to route z. (c) Optimal TSP solution under scenario wc(x).
4.1
Solution Framework
context -----
State
Doea?
Ap
Update
Reward
π
Actiona
cost(e) a (ppernetuuree))
Output
MatNet
Input
Mutt-had
Maried
Attertis
Pyy PPp
Encoder
Adtertion
Decoder
The complete solution framework of our method. Variable a represents the action of selecting the next node according the probability distribution. The reward r is sparse variable that takes its max-regret value only in the complete sequence, while being set to zero for all other time steps.
Figure 2:
The overall solution framework, as illustrated in Figure 2 is based on the encoder-decoder model. In this model, the encoder component receives the input data and exploits series of neural networks extract embeddings that represent the problem features. These embeddings are then utilized by the decoder component compute probabilities for node selection and construct complete solution in an autoregressive manner. Specifically, the model trains a stochastic policy p(T(s) to generate solution æ, permutation æ equivalently, for an instance s. It is parameterized by as:
(p( II (1-11)
(5)
Note that the input data consists of a dual-weighted graph, where each edge is associated with an upper value and lower value. Taking inspiration from MatNet (30), we the input as two matrices: one composed of the upper range values ("Up Matrix"), and the other composed of the lower range values ("Low_Matri) Matrix"). These matrices are then fed into the encoder.
Furthermore, the model requires reward signal for adjusting the network weight parameters. Once all the decoding steps complete, obtain nominal solution for the instance The loss function is defined as:
L(()s) Eps(s [R(T),
(6)
where R(T) is the expectation of the robustness of x, or its (negative) reward, given by
R(T) = t ( TSP (we(t)).
Equation originated from Equation where (+() the total travel time of solution æ using the upper range value. TSP" (we(TT) calculates the optimal TSP route under the worst-case scenario
5

---

with respect to solution æ. Because a large number of samples has to be generated to train the model, we need to find solver to tackle TSP efficiently. In fact, is not necessary to exactly solve TSP in the training stage due to the expectation of R(xx) and high complexity of TSP. We turn to approximate optimal solutions by using a pre-trained TSP model detailed in Section 4.3
4.2
Model Architecture
4.2.1
Encoder
The encoder takes two matrices ("Up_Maatee "ast___axi""" and "Low_Matrix" as the input. Each matrix can be regarded as a bipartite graph G (Φ, V, D), where = (Ø1...., pn) is the set of nodes with outgoing edges, V/- = (vi...., (6)) ) is the set of nodes with incoming edges, and D = [di]|xx gives the edge values by the corresponding matrix.
We extract the feature embeddings of and V. denoted as he and hy, using MatNet [30 (detailed architecture can be found in Appendix 7.7p. To achieve this, we initialize the initial embedding hg. for each d; E & the initial embedding ho, is initialized as a one-hot vector to obtain discriminative first attention layer representations. Next, these initial embeddings are combined with the corresponding matrix D and passed through attention layers iteratively update the embeddings. should be noted that the encoding process for sets & and V/ is performed mutually. Specifically, for the encoding process of set L, by serves as the query vector, by acts as the key-value vector, and the matrix is utilized for weighted fusion. Therefore,
vector, enabling the model support variable-sized inputs. For each wy v,
obtain the updated embedding ht' the output of the MatNet: h/s MatNet(ho, hy, D). Conversely, for the encoding process of set V, we swap the roles hap and hi and employ the transpose of matrix D. Consequently, we have 1ig = MatNet(ha, ha, D
Since there are two matrices involved, we use fiz and h to denote the output embeddings for "Up_Matrix" Similarly, we use h and by denote the output embeddings for Finally, the graph embeddings, denoted as pair (ho, hy), are obtained by fusing the features of "Up_ Matrixx and "ot__xarix". We simply perform the summation on their embeddings: hg h hgg hw = h hng
4.2.2 Decoder
The decoder module generates complete solution in an autoregressive manner based on the graph embeddings (h4, fww) obtained from the encoder.
The key component of the decoder is the masked multi-head cross attention mechanism. At each decoding step f, it utilizes hy, (j 1..... n2 as the key/value vector (k/v for short), and context vector he as the query vector (q for short), which is formed by concatenating ho with the first and last nodes of the current solution, i.c., he = [ her, The multi-hear cross attention operation is then performed and mask nodes that have already been visited.
After calculating the compatibilities ((]] (c symbolizes the current context node), the decoder pro- ceeds compute the probabilities for the remaining unmasked nodes. This probability computation accomplished using single-head attention mechanism. To scale the compatibility results within the range of [] (S = 10), the tanh function is applied. Subsequently, a softmax function is utilized to calculate the final output probability vector.
tanh(
if j not masked; otherwise.
(()))
Vite
(8)
00,
Pj = Po (T+ 518, 11
(9)
"ceis"
At last, the decoder selects node according to the probability vector and proceeds to the next decoding step.
4.3 Training

---

To train the model for RTSP, we adopt a combi- nation of the classic REINFORCE 34] policy gradient algorithm and the POMO training ap- proach (27), which primarily exploits the solu- tion symmetry. We utilize Monte Carlo meth- ods to sample n solution trajectories for each instance, with each trajectory using different starting node. The reward computed for each of these trajectories, and the average reward of the n trajectories is used as a shared baseline within mini-batch, To maximize the expected return J. we employ gradient ascent to approx- imate J, and the Adam optimizer (35) is used to optimize the policy network parameters.
Algorithm 1 Training process for the RTSP model
Input: Sample S, number of epochs E, number of steps per epoch T, batch size B, total number of starting nodes per instance n
Initialization: policy network parameter 0
1:
for epoch + to E do for step + to 7 do
2:
3:
8, (SampleInstace((S) Vi E {1, B}. {st,, st...., st; + StartNodes(s:) e (1.... B).
4:
5:
T/ <- Sa $2, s2,
Vi (L...., B), Vij nI........ wc! <- WorstCaseTSSP(r)
6:
Vi {1,... B), vj (1,-.,, n).
7:
R(m²)) <- Σ wx! m Pretrained(SSP(cc)))
In the following equations, т. represents the generated solution the i-th sampled trajectory.
Vi {1, ..... B}, Vj (1,...n) n].
8:
b. + j= R(m))) vi fI,...,
and [())) denotes the reward of the solution as defined in Equation 7
9:
(.J(0)
Dm Σ E
- b:) logg
To efficiently calculate the reward R(T), a pre- 10:
0 + 0 (V)
trained "MatNet" used as a TSP solver. Since 11: end for
TSP instance can also be represented by 12:
end for
bipartite graph, it is inputted into the MatNet
to construct a TSP route. Multiple greedy trajectories with different starting nodes and instance augmentation are utilized to generate TSP solutions.
n Σ ((T.) - b(s)) Vo logpo (mi(s), n
n R(T.).
VoJ(O)
b(s)
(10)
n
Finally, Algorithm| outlines the training process for RTSP. line 7, we feed the worst-case scenario corresponding to the current solution into the pre-trained TSP model, which provides with near-optimal TSP solution as feedback.
4.4 Inference
Once the RTSP model is trained, it can be used to make fast inference on a batch of instances. Algorithm p the overall inference process.
We use the POMO inference approach to sam-
Algorithm Inference with the pre-trained TSP model
ple multi-start solutions. Instance augmentation [30 during inference can also be adjusted to improve the solution quality. Concretely, employ multiple independent randomizations on the initial one-hot node embeddings h%, for each instance to explore various paths towards the optimal solution. Since two matrices are inputted to our model, they share the same ran- domized one-hot vector. Ultimately, the best solution is selected from the multiple generated solutions.
Input: instance s, augmentation factor K, policy pe. total number of starting nodes per instance
Output: target solution x²', target objective value obj" I: SK. + Augment_ Onehot Embedddngs(s)) StartNodes(ss)
2: st.
.... sth)
E [L...,K},
3: oh < GreedyRollout(st/, s.)) Vj (1....,, n), Vk E [1,.... K}.
4: wel WorsICaseTSP(mm) Vj (l...., n), Vk E {1, K}.
5: R(T() + Σ wc PretrainedTSP((c))) Vi {1, n), 4k fl, K}.
Recall that our proposed method is still an ap- proximate approach. To ensure a fair and accu- rate comparison of the final results during the experimental sessions, we adopt a consistent ap- proach by utilizing an exact TSP solver, namely to determine the target value achieved through different methods (line 8).
6: kmaz, Imax + arggarr., R(m().
7: Nt- f- n Ahmas'
8: ob3" + "rr("") yr" Gurobi(wee(")) return n "bb"".
Gurob E
https://pypi. /ttp///r/jcttttbbpppy
7

---

Experiments
Our proposed approach was programmed with Pytorch. All the experiments were conducted on a workstation with Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz, 8.0 GB RAM and TITAN Xp GPU.
5.1 Experimental Setup of RTSP
Experimental Data. The experimental data in this study was generated following the work of Montemanni et al. [8] The data generation process follows a specific rule: a "R-N-M" type problem considered, where N represents the number of nodes, and M is a range threshold (for the upper bounds). The control parameter is set to r 2 (2) In this case, the upper bound travel time for each pair of nodes, denoted as t. is randomly selected from set {0, ..., The lower bound travel time, denoted as 1.g. is randomly chosen from set {0, 1, .... f To maintain consistency, the distance values of the upper and lower bounds are then normalized using scale factor of M. addition, we ensure the upper and lower bound values to satisfy the triangle inequality, respectively.
Hyper-parameters. During the training process, we follow specific configurations based on the scale of the problem. For small-scale instances with 20 and 30 nodes, training conducted single GPU. The batch size is set to 200 and 100, respectively. We use the Adam optimizer with a learning rate 4 10-2 Each epoch consists of training on 1000 instances. For larger-scale instances with 40 and nodes, training is performed on two and three GPUs, respectively. The batch size is adjusted to 64 and 32, respectively, to accommodate the GPU memory limitations. The learning rate for the Adam optimizer is set to a = 2 x 10 10-4, Each GPU handles 400 training instances per epoch. For the built-in TSP models, they trained for 2000 epochs to ensure their effectiveness and convergence.
Baselines. We have collected typical algorithms for solving RTSP as our baselines. These algo- rithms can be further categorized into exact and heuristic approaches.
Exact approaches: Branch-and-Cut (BC) and Benders Decomposition (BD) are exact algorithms proposed by Montemanni al. for solving RTSP. We have implemented these algorithms using the Python programming language and the Gurobi optimizer. For small-scale problems, such as those with 20 nodes, these two algorithms exhibit fast solution speeds. However, as the problem size increases, for example, with 50 nodes, the computation time required obtain a solution is significantly increased.
Heuristic approaches: There three heuristic baselines introduced for comparisons: heuristic algorithms based on simulated annealing (SA-based) [1O], iterated dual substitution method (iDS) (36) and edge generation algorithm (EGA) [II]. To ensure fairness, we utilize the source codes provided by the authors, with the exception of SA-based, which we re- implemented ourselves. Furthermore, we maintain most of the original settings of these algorithms.
The time limit of all above algorithms are set to 3600 seconds for every instance, except that the SA-based method has time limit of 15n due to the limitation of repeated calls of the LKH algorithm. Nevertheless, some algorithms may stop earlier when reaching their termination criteria.
For the experimental setting of RCVRP, please refer to Appendix 7.5
5.2 Results and Discussions
In the following reported tables, "Obj"" represents the average objective value accurately computed using Gurobi to solve the worst-case routing scenario. "Gap" indicates the relative difference between the objective value obtained by each algorithm and the best-known optimal value, expressed as a percentage: Gap = Obj-Objsza x 100%. "Time" represents the average solving time per instance.
Objnest
Comparison Results of RTSP. Table T presents the main results of our trained model and other methods on randomly generated instances. The methods are categorized into three groups: exact methods, heuristic methods, and our proposed methods. The results of our methods reported
8

---

Table 1: Computational results on generated RTSP instances.
Method
Obj
Gap
Time(*)
Ohj
Gap
Time(s)
Ohj
Gap
Time(s)
Ohj
Gap
Time(s)
R-20-10
R-30-10
R-40-10
R-50-10
BC
4.79
0.00%
2.3
7.23
0.00%
10.3
9.14
0.00%
12.1
11.36
0.00%
135.9
BD
4.79
0.00%
26.9
7,23
0.00%
71.3
9.14
0.00%
107.7
11.36
0.00%
626.5
SA-based
4.88
1.88%
300.1
7.45
3.04%
450.2
9.69
6.02%
600.4
12.11
6.60%
750.5
IDS
4,79
0.00%
3600.0
7.23
0.00%
3600.0
9.14
0.00%
3600.1
11.37
0.09%
3600.1
EGA
4.79
0.00%
1682.7
7.23
0.00%
3037.9
9.14
0.00%
3452.3
11.36
0.00%
3617.0
ours.
0.21%
7.35
1.66%
9.30
1.75%
2.58%
ours,
4.79
0.00%
0.7
7.32
1.24%
1.5
9.21
0.77%
2.8
11.52
1.41%
5,5
ours, X (2.6
4.79
0.00%
9.5
7.26
0.41%
23.2
9.16
0.22%
49.3
11.44
0.70%
45.8
R: 18-20-100
R-30-100 100
R-40-100
R-50- 100
BC
4.078
0.00%
11.1
6.008
0.00%
553.8
7.824
0.06%
2978.2
9.717
0.64%
1466.7
BD
4.078
0.00%
392.9
6.047
0.65%
3448.9
7.883
0.82%
3600.1
9.693
0.39%
3600.2
SA based
4.142
1.57%
300.0
6.234
3.76%
450.1
8.288
5.14%
600.2
10.546
9.23%
750.3
iDS
4.078
0.00%
3600.0
6.020
0.20%
7.849
0.38%
3600,3
9.670
0.16%
3601 A
EGA
4.078
0.00%
1407.0
6,008
0.00%
3605.9
7,819
0.00%
3623.3
9.655
0.00%
3636.4
0.54%
6.116
1.80%
7.915
1.23%
1.99%
ours,X8 X
4.079
0,02%
0.7
6.039
0.525%
1.5
7.871
0.67%
2.9
9.767
1.16%
5.1
ours, X (2-
6.017
0.15%
23.7
7.828
0.12%
9.707
0.54%
45.6
R-20-1000
R-30-1000
R-40-1000
R-50-1000
BC
3.8366
0.00%
7.9
6.1996
0.00%
835.8
7,8578
0.40%
2941.8
9.9995
1.79%
3600.3
BD
3,8366
0.00%
270.8
6,2582
0.95%
3329.9
7,8859
0.76%%
3600.1
9.9017
0.80%
3600.1
SA-based
3,8679
0.82%
300.0
6.4963
4.79%
450.1
8,3930
6.43%
600.2
10.6223
8.13%
752.2
DDS
3600.0
0.25%
7,8568
0.38%
0.51%
3669.6
EGA
3.8366
0.00%
1406.6
6.1996
0.00%
3604.8
7,8268
0.00%
3618.1
9.82,3
0.00%
3658.2
3,8608
0.63%
0.3
6.2740
1.20%
7,9697
1.80%
0.6
9:9870
1.67%
0.8
x8.
3,8366
0.00%
0.7
6,2229
0.38%
1.5
7,9084
1.04%
2.9
9.8948
0.73%
5.4
ours, (20.0x500
0.04%
7.8516
0.32%
49.7
0.31%
for three versions: augmentation, augmentation with 8 instances, and augmentation with 128 instances (except 64 instances for 50 nodes due to memory limitations).
From Table I it is evident that our approach consistently achieves high-quality solutions in signifi- cantly small time. Without instance augmentation, the gaps obtained by our method are consistently below 2.6%. When utilizing instance augmentation, our method can obtain approximately accurate or even exact solutions for small scales (such as 20 nodes). For larger scales, our method also produces solutions with gaps less than 0.7%. In terms of runtime, under both scenarios with and without instance augmentation, our approach has a large and significant advantage over exact methods and heuristics, taking only fraction of a second. The results verify the effectiveness of our approach.
Generalization Results of RTSP.
We conduct experiments to evaluate the generalization ability of our model,
trained M=20
M=20
M=40
specifically its performance on test in- stances that are outside the training distribution. To illustrate this, we con-
M-50
78
58
sider an example where M = 100 and
the augmentation involves 8 instances, We evaluate our models, trained with varying numbers nodes, on test data with different node sizes. The results are depicted in Figure As expected, the model trained on the correspond- ing node size achieves the best per- formance on the test data. Moreover, the model trained on 50 nodes demon- strates competitive results when tested the other three scales (N 20,30, 40), suggesting
18
34-00
5-44
N-53
Figure 3: Performance on varying-scale problems. Gap relative to the test results of the models trained on the consistent scales.

---

Table Results of different encoding methods for the uncertainty sets' upper and lower bounds on
R-40-100.
No augmentation
Augmentation (x8)
Augmentation (x 128)
Method
Obj
Gap
Obj
Gap
Obj
Gap
7.9610
1.55%
7.8985
0.75%
7.8600
0.26%
blended
8.0640
2.86%
7.9095
0.89%
7.8760
0.47%
fusion
8.0080
2.15%
7.9045
0.83%
7.8645
0.32%
Table 3: Computational results for RCVRP.
Method
Obj
Gap
Time(s)
Obj
Gap Time(s)
Obj
Gap
Time(s)
Obj
Gap
Time($)
R-20-100
R-20-1000
R-50-100
R-50-1000
BC
5,2855
0.46%
3605.5
4.87385
1.75%
3607.8
20.6335
73.35%
3804.4
20.30060
77.13%
3856.6
BD
5,2130
0.99%
3663.1
4.86765
1.62%
3662.9
12.3385
3.66%
3961.1
12.17785
6.26%
3960.9
ours.
5,3130
2.93%
0.3
4,96790
3.72%
0.3
12,2270
2.72%
0.9
11,95765
4.33%
1.0
x
5,1810
0.37%
0.8
4.81545
0.53%
0.8
11.9395
0.31%
6.3
11.62230
1.41%
6.2
x32.
5,1620
0.00%
2.7
4.78990
0.00%
2.8
11,9030
0.00%
25.6
11.46090
0.00%
25.9
strong generalization capability, Conversely, the models trained on smaller scales exhibit weaker generalization capability.
Ablation Studies RTSP. We investigate the impact different designs for feature encoding of the uncertainty support set. We explore three encoding methods, namely "ours", "blendedd"(a (a blended matrix is computed by the weighted sum of the upper and lower bound matrices, which is then encoded by MatNet) and "fusion" "(ww distance matrices and attention scores fused through an MLP in the multi-head mixed score attention layer of the encoder), with their architectures depicted Figure 5 Appendix 7.4
We compare these encoding methods on R-40-100 with 20 random instances. As shown in Table 2 our method outperforms both "blended" and "fusion" methods in all cases, including scenarios without instance augmentation, as well as those with x8 and 128 instance augmentation.
Comparison Results of RCVRP. Table 3 shows the comparison results between method and the exact algorithm. The results are all obtained using the Gurobi solver a uniform manner. To knowledge, this specific type of RCVRP has never been discussed before. The results show that our algorithm still achieves high solution quality and has a clear advantage in the solution time of RCVRP. On 20-node scale, gap is around 0.5%. On 50-node scale, our gap is below 4.5%. In terms of time consumption, we only need a few tenths of a second to dozens of seconds.
Conclusions
This paper focuses on addressing the robust routing problem with uncertain travel times, relevant to real-world scenarios. We introduce a neural combinatorial optimization approach, employing an end-to-end model with attention mechanism for automatic policy learning. Leveraging a pre-trained model, experimental results demonstrate that our method can generate near-optimal solutions much faster than exact and heuristic approaches. However, due to hardware memory limitations and constraints of the POMO algorithm used in training, our method is currently limited in scale and to problems satisfying the max-regret theorem. Moving forward, we aim to expand our approach to handle larger-scale problems and tackle a broader range of robust optimization problems.
Acknowledgements and Disclosure of Funding
This work supported by the National Natural Science Foundation of China (62072483) and Guangdong Natural Science Funds (2024A 151501015010811
10

---

References
[1] Panos Kouvelis and Gang Yu. Robust discrete optimization and its applications, volume 14. Springer Science & Business Media, 2013.
[2] Richard E Bellman and Lotfi Asker Zadeh. Decision-making in a fuzzy environment. Manage- ment science, 17(4) 141, 1970.
[3] Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust optimization,, volume 28. Princeton university press, 2009.
[4] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press. 2004.
[5] Dimitris Bertsimas and Aurélie Thiele. Robust and data-driven optimization: modern decision making under uncertainty. In Models, methods, and applications for innovative decision making, pages 95-122. INFORMS, 2006.
[6] Dimitris Bertsimas and Melvyn Sim. The price of robustness. Operations research, 52(1): 35-53, 2004.
[7] Aharon Ben-Tal, Alexander Goryashko, Elana Guslitzer, and Arkadi Nemirovski. Adjustable robust solutions of uncertain linear programs. Mathematical programming, 99(2)3351-376. 2004.
[8] Roberto Montemanni, János Barta, Monaldo Mastrolilli, and Luca Maria Gambardella. The robust traveling salesman problem with interval data. Transportation Science, 41(3)3366-381, 2007.
[9] André Chassein and Marc Goerigk. On the recoverable robust traveling salesman problem. Optimization Letters, 10:1479-1492, 2016.
[10] Chung-Cheng Lu, Shih- Wei Lin, and Kuo-Ching Ying. Minimizing worst-case regret of makespan on single machine with uncertain processing and setup times. Applied Soft Comput- ing, 23:144-11114 111144155 151, 2014.
[11] K Hasegawa and W Wu. A heuristic approach for the robust traveling salesman problem. In 2022 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pages 0561-0565. IEEE, 2022.
[12] llgaz Sungur, Fernando Ordónez, and Maged Dessouky. robust optimization approach for the capacitated vehicle routing problem with demand uncertainty. lie Transactions, 40(5):509-523, 2008.
[13] Elyn Solano-Chariss. Christian Prins, and Andréa Cynthia Santos. Local search based meta- heuristics for the robust vehicle routing problem with discrete scenarios. Applied Soft Computing, 32:518-531, 2015.
[14] Lars Eufinger, Jannis Kurtz, Christoph Buchheim, and Uwe Clausen. A robust approach to the capacitated vehicle routing problem with uncertain costs. INFORMS Journal on Optimization, 2(2):79-95, 2020.
[15] Aigerim Bogyrbayeva, Meraryslan Meraliyev, Taukekhan Mustakhov, and Bissenbay Daulet- bayev. Machine learning to solve vehicle routing problems: A survey. IEEE Transactions on Intelligent Transporaatinn Systems, 2024.
[16] Marijn Van Knippenberg, Mike Holenderski, and Vlado Menkovski. Complex vehicle routing with memory augmented neural networks. In 2020 IEEE Conference on Industrial Cyberphysical Systems (ICPS), volume 1, pages 303-308. IEEF, 2020.
[17] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint (tte::990000277. 2019.

---

[18] Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1):70-98, 2022.
[19] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[20] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533, 2015.
[21] Martin Riedmiller. Neural fitted q iteration-fire experiences with data efficient neural reinforcement learning method. In Machine learning: ECML 2005: 16th European conference on machine learning, Porto, Portugal, October 3-7, 2005. proceedings 16, pages 317-328. Springer, 2005.
[22] Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in Neural Information Processing Systems, 28, 2015.
[23] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combina- torial optimization with reinforcement learning. arXiv preprint arXiv: 0e/////11.99999 2016.
[24] Mohammadreza Nazari, Afshin Oroojlooy. Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[25] Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprini arXiv: /803008800 2018.
[26] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[27] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 1888-188-11 28192, 2020.
Min. Pomo:
[28] Zizhen Zhang, Hong Liu, MengChu Zhou, and Jiahai Wang. Solving dynamic traveling salesman problems with deep reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 3492)221192213,, 2021.
[29] Yongxin Zhang. Jiahai Wang, and Zizhen Zhang. Edge-based formulation with graph attention network for practical vehicle routing problem with time windows. In 2022 International Joint Conference on Neural Networks (LJCNN), pages 01-08. IEEE, 2022.
[30] Yeong-Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. Advances in Neural Informa- tion Processing Systems, 34:5138-5144 2021.
[31] Jianan Zhou, Yaoxin WI, Wen Song. Zhiguang Cao, and Jie Zhang. Towards omai-geneellizable neural methods for vehicle routing problems. arXiv preprint arXiv:2305. 19587, 2023.
[32] Tobias Jacobs, Francesco Alesiani, and Gülcin Ermis. Reinforcement learning for route optimization with robustness guarantees. In IJCAI, pages 2592-2599 2021.
[33] Justin Dumouchelle, Esther Julien, Jannis Kurtz, and Elias B Khalil. Neur2ro: Neural two-stage robust optimization. arXiv preprint arXiv:2310.04345 2023.
[34] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforce- ment learning. Machine learning, 0-229-256, 1992.
[35] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv.1412.6980, 2014.
12

---

[36] Wei Wu, Manuel Iori, Silvano Martello, and Mutsunori Yagiura. An iterated dual substitu- tion approach for binary integer programming problems under the min max regret criterion. INFORMS Journal on Computing, 34(5) 2022.
[37] Clair E Miller, Albert W Tucker, and Richard A Zemlin. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), 7(4):326-33 329, 1960.
[38] Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European journal of operational research, 126(1):106-13)) 2000.
[39] Nikolaus Hansen. The ema evolution strategy: A tutorial. arXiv preprint arXiv:1604.0077.
2016.
13

---

7 Appendix
7.1 Proof of Theorem
Proof. To provide a coherent description of the proof process, we first introduce shorthand notation for certain equations.
The optimal tour under scenario u is denoted as y (u).
2. The worst case scenario obtained by solution x according to the theorem is denoted as wc(z)).
3. The tour length of solution z under scenario is denoted as Cu,, x). By the definition of regret, the value of regret for solution æ under scenario u has the equation: regrel(u, x)) C(u, C(u, y" (u)).
We then outline concise proof procedure. Assume that have solution æ, goal is to prove that the regret value under scenario we(x) is greater than or equal to the regret value under any other scenario, i.c., regred(u,x) S (ogre((wc(z)).>)) Here,
regret(u, x) = C(u, x) - C( (u))
Σ 5
Σ
(i,))r
(1.))Ey"())
(11)
(A.))xlly")))
(i
Based on the definition of we(x), evident that when (1,j) E x 30 (1), (u).ey0(x)) (o(()) 2 t.. Similarly,
when (1,5) E y x, tgg S f.j. We have:
regret(u, = C(u,x) v(u,y"(w))
Σ
(mo())
Σ
(x.)) (u)
(1i))Ey (ujiz
Σ
(oc(a)
Σ
E
wc(w)
ii
(ir))
(u))
= Σ
Σ
wc(a)
Σ
(e(())
+
(td)) (u)
(u))e
Σ vc((x)
Σ
()c(a))
(1))
(1)))
C(wc((x)x))
C(we(x), (u))
S C(we(x), x))
C(wo(x), v'(((x)))
regret(we(z). x).
(12)
Therefore, the proof of Theorem concluded.
7.2 RTSP Example with budget uncertainty
In Figure we provide specific example to illustrate the solution process of RTSP with budget
(:) Recall that the budget uncertainty set is defined as Upudget = {1/44 =
uncertainty while r = 4
1. Eyyyy S my < ((, E:E.EE my r}. where f.j = t b.. Figure depicts a graph with nodes and edges. Suppose the values of tú of each edge are as shown Figure 4h. For simplicity, let's assume that all fy values set to the same value though in real
14

---

[
[4]
[
[4]
2
[6]
[2]
[6]
[2]
sol 1-2-3-4-1
[3]
[3]
33
wolk)
optimal sol in wo(x)
(a)
(b)
Figure 4: An instance of RTSP with budget uncertainty and r
(a)
1i-- (b) Worst case
scenario wo(x) corresponding route æ.
(c) Optimal TSP solution under scenario wc(x).
implementation, these values would differ. Consider feasible solution "1 + 3
highlighted by the green edges in Figure under the given I' the worst scenario corresponding to this solution is also shown Figure Ap, with nominal total time 1 1
12. The optimal solution in this scenario, highlighted in red in Figure 4.. is either the route + 2 4 + 1 or 1 + + 2 1. both of which have total cost of 10. The max max-reeret value for the original solution is calculated as 12 10 2. By evaluating the max-regret for each feasible solution, the final optimal solution is identified as the one with the smallest max regrett value.
7.3 Formulations Robust Routing Problems
RTSP Formulation Based on the TSP formulation and Corollary [ we present the following mathematical model for RTSP with the min-max-regret criterion. This modeling serves the foundation for both exact algorithms and heuristic algorithms this field.
The mathematical scenario for RTSP is defined as follows. Given a complete symmetric graph G = (V, F),, where V = {1, 2,...... n) is the set nodes. The travel time (cost) of an edge (i,j) defined by an interval uncertainty set [t t.yy where tú and t denote the lower and upper bounds of possible values, respectively.
min
Σ tn -
(13)
(FJ)EE
s.t.
S Σ
Visti + Σ
Di
Verlt - 1.
Ayes
(14)
(E,)EE
(15)
E R
(16)
In the above model, miy are the decision variables for the RTSP solution, while Yi serves as temporary auxiliary decision variables representing the decision variable for TSP in the worst-case scenario corresponding to each z. To establish the nonlinear interaction between Tı and Yij. a free variable r introduced.
The objective function Equation (13) aims minimize the maximum regret value, while Constraint (14) ensures the maximization of regret. We define the set of all feasible TSP solutions as S, which is
15

---

bounded by the following constraints.
Σ Tij 1,
VjEV
(17)
iEVi
Σ Zij =
ViEV
(18)
JEVijt
Σ IJES
Tij S | -1 1,
SA V V,S +
(19)
Fij E (0,
v(i,j) E F
(20)
Constraint (15) guarantee the feasibility of zy as a TSP solution. It important to note that Vij must also be a feasible and valid TSP solution, and thus we have y E S in Equation (14).
RCVRP Formulation CVRP an extension of TSP that additionally considers vehicle capacity constraints. Similar to RTSP, we can use the mathematical model of the nominal CVRP and Corollary to extend the mathematical model of RCVRP.
The RCVRP scenario is defined as follows. We have a fleet of vehicles with a capacity of Q per vehicle, and n customers distributed geographically. Each customer has its own demand de (where i == 1......, n).. Each customer can only be served by one vehicle, and there is no limit on the number of available vehicles. Let V be the set of demand nodes and single depot, represented The set E represents the edge connections between nodes. Similar to RTSP, we consider the robust scenario where the travel time is subject interval uncertainty. The travel time (cost) of edge (i, j) is within the interval i, ty], where t, and t represent the lower and upper bounds of possible values, respectively. Note that in our setting, we assume that f,y = Ejj. meaning that the travel time matrix is symmetrie.
node O.
min
Σ
-
(21)
(FE)
s.t.
S
Σ
yisti +
Σ
Be (o - -iy)aass Vyes
(22)
(i,))
(WIE
S
(23)
E R
(24)
The model is the same as the one described in Section 73 It should be noted that & is defined as the set of all feasible solutions for CVRP, subject to the following constraints.
Σ
Inj =
Vj V \ {0}
(25)
xEV.
Σ
Zij 1,
Wi V \ {0}
(26)
JEV
0; + Q(1 xii)) 2 dj,
Vi,j E V (0).
(27)
d: < < Q
Wi V \ (0)
(28)
Zy E (0,
v(i.j) E E
(29)
The main difference between CVRP and TSP lies in the consideration of capacity constraints. In CVRP, it crucial to ensure that the total demand of customers served on each route does not exceed Tucker
(MTZ) constraint [37) introduces the vehicle's 's capacity. To address this, the {0). which represent the flow in the vehicle after it visits continuous variables u; for every customer i. Constraints (27)-28) enforce both the capacity and connectivity requirements of feasible routes.
7.4 Additional Results of RTSP
Generalization on the Threshold Value. In addition to considering the generalization on dimension N, depicted in Figure 3 also test the generalization ability dimension M. The models
16

---

Table 4: Performance on varying M-threshold problems among instances of N 20, with
instance augmentation.
Test threshold
M=10
M=100
M=1000
Train threshold
Trained with M=10
4.8100
4.0010
4.0762
Trained with M=100
4.9150
3.9895
4.0621
Trained with M=1000
4.8800
4.0105
4.0637
Table 5: Results of various built-in TSP solving algorithms on R-20-100. The training time refers to the average training time per epoch.
x1
x8
x128
Method
Training time
Obj
Gap
Obj
Gap
Obj
Gap
ours
4.0140
0.63%
3.9895
0.01%
3.9895
0.01 %
2 min epoch
CMA-ES
4,0430
1.34%
3.9925
0.08%
3,9895
0.01 %
= min epoch
LKH
4.0135
0.60 %
3.9905
0.04%
3.9895
0.01 %
7.5 min / epoch
trained with different ranges of M are respectively used to test the instances across all ranges of M. As shown the Table [] it can be seen that model trained within specific threshold value can achieve relatively ideal experimental results within other threshold values. This shows that under the premise of fixed N, our model can achieve good generalization results for different M values.
Effects of the Encoding Approaches. In Figure 5)a) (labeled "ours"), proposed approach is depicted. It involves encoding the upper and lower bound matrices separately using MatNet and then adding the embeddings of the corresponding nodes. In Figure (5]b (labeled "blended"). blended matrix is computed by taking the weighted sum of the upper and lower bound matrices, represented D D (1.0- w) Dlow Here, w is initialized 0.5 and serves learnable parameter. The blended matrix is subsequently encoded using MatNet. Matuee.Figuuee33 (labeled as "fusion") illustrates the third approach, which involves fusing the two matrices and attention scores through multi- perceptron (MLP) in the multi-head mixed-score attention layer within the MatNet encoder.
Effects of the Built-in TSP Solvers. We also explore different built-in TSP solvers under the worst-case scenario. In addition to the pre-trained TSP model used in our method, we further consider the well-known heuristic algorithms like LKH training time are reported in Table
38 and CMA-ES 30 The optimality gap and
Even though LKH is the state-of-the-art TSP solver that can almost find the optimal solution in small-size cases, it has no superiority with regard to solution quality for training an RTSP model and even spends more training time. On the other hand, although CMA-ES evolutionary algorithm could be accelerated through parallelization techniques in a large number of model training processes, it faced a trade-off between solving speed and solution quality. As can be seen, the pre-trained TSP model used in our method exhibits almost the smallest optimality gap and the shortest training time compared with other methods.
Training Details. In Figure 6 present the training progress curves that illustrate the loss and objective values for "R-50- 12-50-100 100" instances, serving as an illustrative example. The figure demonstrates that the training loss steadily converges, and the training score is minimized after 1000 epochs. These observations indicate that the model successfully learns the implicit features of RTSP during the training process.
7.5 Experimental Setup of RCVRP
Data Generation
We generate random instances of RCVRP for two different sizes: 20 and 50. The control parameter is set > (*). The following settings are used.
.
The vehicle capacity is fixed at Q 1.0.
17

---

Dup
MatNet
Dup
Sum
embeddings
Weighted
D
MatNet
embeddings
S
low
MatNet
Dlow
(a)
(h)
embeddings
Add & Norm
Add
MatNet
FF
FF
Norm
Add Norm
Multi-head mixed score cross attention
Multi-head mixed score cross attention
MatMul
MatMul
Softmax
S Sotmmax
MLP
MatMul SScale
Scodsuen
MatMul &
k
q
hgg.
hgp
hig.
hig
Aup
uup
Dlow
(c)
Figure 5: Different encoding methods for the uncertainty set. (a) ours. (b) blended. (c) fusion.
The demand d; for each node is determined by dividing uniformly sampled value d, from the set {1,2, 9} by a value D. For n 20, set to 30, while for n = 50, set to 40.
The uncertain variable tay represents the travel time between nodes i and j. The upper bound travel time t is randomly selected from the set 2,. M), while the lower bound travel time fij is randomly chosen from the set {0, 1,... 1.
To ensure consistency, the distance values of upper and lower bounds are normalized using scale factor of M.
In the data generation process, we also consider the triangle inequality. This inequality indepen- dently applied to both the upper bound and lower bound. For example, for each triplet (i, k) in the upper bound, we check t + tt > by is violated. the inequality violated, we replace tt with tt + tty to ensure that the triangle inequality holds.
Hyper-paran hypper-parameters During the training process, we adopt specific configurations based on the problem scale. For small-scale instances with 20 nodes, training is conducted on single GPU. The batch size is set to 200. We utilize the Adam optimizer with learning rate a = 10-1 -0,4, Each epoch involves training 1000 instances.
18

---

train_scorc score
18
14
12
train loss
1350 3000
(a)
(b)
Figure 6: The training loss and score curves for R-50-100 instances. The horizontal axis represents epochs, while the vertical axis represents the values of loss score (i.e. the objective value). (a) Training loss. (b) Training score.
For larger-scale instances with 50 nodes, training is performed three GPUs. The batch size adjusted to 25 to accommodate the GPU memory limitations. The learning rate for the Adam optimizer is set to
x 10-4 Each GPU handles 400 training instances per epoch. The models are uniformly trained for 4000 epochs.
As for the built-in CVRP models, they are trained for 5000 epochs to ensure their effectiveness and convergence.
7.6 Effectiveness of Budget Uncertainty Set
The hyperparameter I can be leveraged to adjust the robustness of the budget uncertainty set. Nevertheless, we conducted supplementary experiments validate the effectiveness of our approach under general budget uncertainty conditions. Toalle the comparative results for different values. Our method shows highly promising outcomes within a remarkably short time, especially when compared to the leading solver, EGA.
Table 6: Comparison result of different I' on 20.
Method
Obj
Time(s)
Obj
Time(s)
Obj
Time(s)
C(N.2)
r
C(N22)
r 0
EGA
0.7870
55.9
0.3175
56.7
0.0000
38.4
ours 128
0.7870
11.2
0.3180
10.9
0.0005
11.3
ours
0.7945
0.8
0.3305
0.79
0.0365
0.8
7.7 Architecture of MatNet
MatNet 30 is graph attention network model designed for data objects that can partitioned into two sets of nodes in a bipartite graph. To facilitate the description, we refer to the set of nodes acting as the heads of edges as Q and the set nodes acting as the tails edges as V. The framework diagram of MatNet is depicted in Figure 7 MatNet consists of stack of L attention layers. Each attention layer comprises two sub-layers: the multi-head mixed-score cross-attention layer and fully connected feed-forward (FF) layer. Both sub-layers incorporate skip connections and batch normalization. In the FF sub-layer, a hidden layer dimension 512 and a ReLU activation function employed. The multi-head mixed-scor between each node in one set and all nodes in the other set. This mechanism enables the learning of association features between the two sets of nodes.
crossaateention sub-layer calculates attention scores
The update of two node sets and V performed in dual manner, where the roles of queries and keys/values are exchanged, accompanied by the transposition of the matrix. Taking the update of h! as an example, where denotes the current encoder layer being updated, and has represents embedding representation of node the node set Φ. We define the query qi for each node in the set & by projecting the embedding h/ (-1 Simultaneously, we obtain the key ky and value vy from the embedding h/
ds
19

---

q: 1 k2
wk Uj -V 4j
(30)
The compatibility dij is calculated using gi and liz:
k
May ddk
(31)
where de is the dimensions of the attention vector k and
During the feature update process of the nodes in the attention layer, edge weight information represented by matrix is added with a multi-layer perceptron (MLP) in addition to the network output of the previous layer.
weights = coftmar((wws)) ReLa(w,, scoress" b₂1)) + bs2)²),
(32)
where scoresij Uey (ujl and dij denotes the corresponding distance matrix element.
Next, update the corresponding node embedding.
11-1"
Σ
weights:f15>
(33)
Then, proceed through the multi-head sub-layer and the feed-forward sub-layer sequentially to obtain the updated embedding representation for the next layer.
M
MH A 2h 1 015 .-, M
Σ
Wo øim
(34)
R1 BN (1 + .HMMAA A0 (M i. NoN))):
(35)
N1g BN (hos + (
(36)
As depicted in Figure 7 the final node feature embedding representation for the two node sets can be obtained y repeating the above process times.
Add Norm
Add Norm
Add Norm
Add Norm
ulti-head mixed cross attention
Multi-head mixed cross attention
L
MatMuu
MatMul
Softmax
MLP P
MLP
Mathuul
Scale
Scale
Agp
hpg
Aya
Ragg
D
Figure 7: The schematic of MatNet for a single bipartite graph. D is the corresponding matrix representation of the bipartite graph.
20

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We describe our problem scenario in the abstract and also describe our outstanding contributions to this problem. We consider the robust routing problem with uncertain travel times under the min-max regret criterion. The contributions of our work can be highlighted as follows: We introduce Robust routing problem with the general budget uncertainty set which covers the interval uncertainty set as a special case, and treat the problem from the perspective of deep reinforcement learning. We propose an end-to-end neural model to capture the features of Robust routing problem, and use pre-trained routing model to efficiently calculate the reward with respect the worst-case scenario during training. We conduct extensive experiments on RTSP and RCVRP instances. The results substantiate the efficacy of our approach in efficiently handling robust routing problems across diverse scales within shorter computation time.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Due to the limitations of hardware memory and the limitations of the POMO algorithm used the training process, our method can currently only be solved within the range of 20 for small scale and 50 for large scale. Our method is theoretically applicable to all problems that satisfy the max max-regret theorem, but it also limited to solving problems that satisfy this theorem.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
21

---

If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Question:
Answer: [Yes]
Justification: Our question is based on an important theorem assumptior for which we have also given complete proof, which can found the appendix 7.1
7.1
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification:
We describe the experimental settings in the subsection 5.1 and 7.5
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
22

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We will make the relevant code and data public on GitHub after we organize them.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
public/guidee wwwss/ooooSSmmssooooooooo.o
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https /nips.cc/pput httppppwwpppppppppppppppppaaaaep httpe//guiddee/eeeebbbbsseeeeee ssioioolicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We describe the experimental settings in the subsection 5.1 and The training and test details is described in the subsection and
7.5
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
23

---

Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
We report the main experiment results in table 1 and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Our proposed approach was programmed with Pytorch. All the experiments were conducted on a246 workstation with Intel(R) Core(TM) i5-4590 CPU @ 3.30GHZ, 8.0 GB RAM and TITAN Xp GPU.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: our reasearch conducted follow the NeuIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
24

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper does not explicitly discuss both potential positive and negative societal impacts of the work performed. This could be due primary focus the technical aspects addressing the robust routing problem using neural combinatorial optimization, without delving into the broader societal implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
25

---

Answer: [Yes]
Justification: For previous existing works, have cited relevant references.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's ' creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
26

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
27


Reviews:
[{"review_id": "gWt8f5eXRr", "reviewer": "Reviewer_Xutw", "summary": "The paper proposes a neural network based approach and applied it to the robust version of the traveling salesman problem (TSP) and the related vehicle routing problem (VRP) where interval uncertainty is taken into account and the goal is to minimise the max-regret value. The architecture (encoder, decoder) is described as well as the training process, and for the POMO approach is used for fast inference with a pre-trained model. Then experiments are conducted to compare the proposed approach to existing approaches from the literature.", "questions": "- 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?\n\n- On page 9 what exactly is meant by blended and fusion in the ablation study?\n\n- The choice of the baseline methods (BS - branch & 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?", "limitations": "- 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?", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The robust version of TSP and VRP have been widely studied in the literature, so it is good to see a paper that continues the existing work \n\n- The proposed approach has been implemented and used to conduct experiments\n\n- The paper is written in good English", "weaknesses": "- The paper is not easy to follow; at the end of the introduction (i.e., Section 1) there should be an outline of the organisation of the paper to give the reader orientation\n\n- The discussion of related work is too brief to give a comprehensive overview of the state-of-the-art of ML-based approaches, including neural network based methods. The paper below is a recent survey paper that discusses supervised as well as reinforcement learning-based approaches:\nBogyrbayeva et al: Machine Learning Solve Vehicle Routing Problems: A Survey, IEEE Trans. on Intelligent Transportation Systems, 2023\n\n- As emphasised by the authors their proposed approach is a bit similar to the approach in MatNet described in reference [19]; so the novelty of the proposed method is limited; the paper's contribution is more the application to the robust TSP and VRP\n\n- The font size in Table , Table 3 and Fig. 2 are far too small\n\n- Careful proofreading is needed as the paper contains a range of typos, for example: page 3, line -2: \"budge\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n**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?\n\n**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.\n\n**Q2:** On page 9 what exactly is meant by blended and fusion in the ablation study?\n\n**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.\n\n\n**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?\n\n**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.\n\n\n**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?\n\n**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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UBCqW8xxTu", "reviewer": "Reviewer_g5Qe", "summary": "This paper proposes a neural combinatorial optimization (NCO) method to solve robust routing problems under uncertain travel times under the min-max regret criterion - a common occurrence in real-life scenarios in which one wants to minimize worst-case scenarios.  The proposed approach employs the transformer-based MatNet approach, which can model edge features such as uncertain travel times and project features into the latent space. Moreover, a secondary pre-trained model is employed to evaluate the optimal tour efficiently under the max-regret condition. The approach can obtain near-optimal solutions with much faster solution times compared to baselines.", "questions": "1. Why did you choose MatNet instead of e.g. BQ-NCO [1r] as your backbone?\n    \n2. 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]?\n    \n\n----\n### References\n\n[1r] Drakulic, Darko, et al. \"Bq-nco: Bisimulation quotienting for efficient neural combinatorial optimization.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[2r] Lu, Han, et al. \"Roco: A general framework for evaluating robustness of combinatorial optimization solvers on graphs.\" The Eleventh International Conference on Learning Representations. 2023.", "limitations": "See the above weaknesses. The authors describe the main limitation of the approach, namely that the scale is currently pretty small, although this is expected from a seminal paper.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "To my knowledge, this paper is the first to apply a neural approach to the specific application of uncertain travel times with min-max regret, which is an important practical application. This includes the use of edge features, which is very important in practice but understudied in NCO for VRPs. The proposed model is a reasonable approach and shows good performance while cutting down considerably on computational requirements both in training and inference.\n\nI have no major concerns regarding the paper's quality and experimental results. While the paper is specific to an application, I would recommend acceptance based on its quality, originality, and practical application.", "weaknesses": "I have spotted some weaknesses here and there, but no major ones.\n\n1. This paper's main weakness may be its specificity to a task. However, as described above, given its importance and overall quality, I believe this is not a major flaw.\n    \n2. 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).\n    \n3. No code is provided at the time of submission.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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).\n\n**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.\n\n**Q2:** No code is provided at the time of submission.\n\n**A2:** We will make our code publicly accessible once the paper is accepted as stated in line 706.\n\n\n**Q3:** Why did you choose MatNet instead of e.g. BQ-NCO [1r] as your backbone?\n\n**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.\n\n\n**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]?\n\n**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. \n\nMoreover, 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E3ecc5DleI", "reviewer": "Reviewer_tvNa", "summary": "The min-max regret criterion is employed, and the routing problems are solved when the moving cost of an edge varies (perhaps uniformly) within a certain range. The authors have discussed two (possibly) uncertain classes and proposed a theoretical analysis and a learning-based solver (on TSP and CVRP).", "questions": "- [Augmentation] I'm curious what you are doing; please explain augmentation. If it is mentioned anywhere, please let me know where.\n- Two questions from [W1].\n    - 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.\n    - From Def. 3.1 and the idea of using intervals, I feel that the $[t^-, t^+]$ interval is regarded everywhere as having the same importance. However, considering the actual application, it seems likely that the closer to $t^+$, the heavier the penalty may be. I was curious about the generalization and future development in this area.\n- I am unclear about the quality of the reward from MatNet [W3]. Can you explain this point more?\n- I did not understand the treatment of $\\Gamma$.\n    - $\\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 l.133 so `exactly $\\Gamma$ edges`. Not related to the main point, but it bothers me.\n- [minor comment].\n    - I understand that this is a space issue, but the location of Table 1 came before the explanation, and it was difficult to understand at first what x8 and x128 meant.\n\n---\n\nAfter the rebuttal, I have updated my score.", "limitations": "In my opinion, the authors have addressed the issue adequately and mentioned these points.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- [S1] The whole concept and problems are interesting. The interval-based uncertain is one of the standard formulations but it is applied to various real problems.\n- [S2] The learning method (i.e., REINFORCE + POMO training approach) achieved a promising performance, though the method is possibly a combination of existing concepts.\n- [S3] The proposed method can generate at least better solutions faster than simple solvers (e.g., SA-based).", "weaknesses": "- [W1] 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).\n- [W2] The novelty of the solver is unclear.\n- [W3] 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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).\n\n**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.\n\n**Q2:** The novelty of the solver is unclear.\n\n**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.\n\n**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?\n\n**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.\n\n\n**Q4:** [Augmentation] I'm curious what you are doing; please explain augmentation. If it is mentioned anywhere, please let me know where.\n\n**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.''*\n\n**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.\n\n**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.\n\nThere 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.\n\n**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.\n\n**A6:**\nClassic 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.\n\nWe 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.\n\n**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.\n\n**A7:**\nIn 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "51JiMOUTrI", "reviewer": "Reviewer_88Rd", "summary": "The paper concerns robust routing problem with uncertain travel times under the min-max regret criterion, which represents an extended and robust version of the classic traveling salesman problem (TSP) and vehicle routing problem (VRP). The authors proposed a dual multi-head cross-attention mechanism to extract problem features represented by the inputted uncertainty sets and achieved very good results in experiments.", "questions": "I do not have any questions now.", "limitations": "Yes, the authors have addressed the limitations in the Conclusions section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduced model seems to be quite innovative, especially in the domain of routing problems. The paper is well-written and the quality of the review of related works, theoretical background, setup of experiments, and the presentation of results are very good. Taking into account that the authors tackle a more realistic variant of TSP/VRP and look for robust solutions, the methodology may have some practical applications.", "weaknesses": "I haven't identified significant weaknesses. The only one I have in mind is the fact that neither the code, nor the dataset are available, so it is not possible to verify the results. The authors promised to make the code publicly accessible once the paper is accepted. I am not sure about the datasets. 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**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).\n\n**A:** Thank you for your advice. We will include the explanation for $x_{ij}$ in the revised version. \n\nHere, $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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jRAyNnSoxa", "reviewer": "Reviewer_3PAJ", "summary": "The authors propose a dual multi-head cross attention mechanism to extract problem features represented by the inputted uncertainty sets for the robust vehicle routing problem with uncertain travel times under the min-max regret criterion. The experimental results on the robust TSP and VRP demonstrate the efficacy of our neural combinatorial optimization method, showcasing its ability to efficiently handle the robust routing approaches.", "questions": "See the weaknesses.", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors have proposed an end-to-end neural model to capture the features of the robust routing problem and have used a pre-trained neural model to efficiently calculate the reward with respect to the worst-case scenario during training. They conducted extensive experiments on Robust Traveling Salesman Problem (RTSP) and Robust Capacitated Vehicle Routing Problem (RCVRP) instances. The results confirm the effectiveness of their approach in efficiently handling robust routing problems across diverse scales within a shorter computation time.", "weaknesses": "[1] The algorithm has not been compared to other existing neural combinatorial optimization works.\n\n[2] 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?\n\n[3] The coding method of uncertain sets proposed in this paper is not very innovative.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q1:** The algorithm has not been compared to other existing neural combinatorial optimization works.\n\n**A1:** \nTo 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.\n\n**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?\n\n**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.\n\n**Q3:**  The coding method of uncertain sets proposed in this paper is not very innovative.\n\n**A3:** \nWe 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studied the robust routing problem with uncertainty travel time. The proposed method leverages a dual multi-head cross attention mechanism and incorporates a pre-trained model to efficiently compute regret values during training, demonstrating strong performance in terms of both computational efficiency and solution quality.

Reviewers generally agree that this paper offers a valuable contribution to the field, particularly in applying deep learning methods to robust combinatorial optimization problems. The authors have satisfactorily addressed concerns raised during the review process, including clarifications on the novelty of the approach and improvements made over existing methods. All reviewers consistently view this paper as strong in terms of methodological innovation, practical relevance, and experimental validation.
Decision: Accept (poster)