Learning to CROSS exchange to solve min-max vehicle routing problems
Authors: Minjun Kim
Junyoung Park
Jinkyoo Park
Venue: ICLR 2023 poster (2023)

Abstract: CROSS exchange (CE), a meta-heuristic that solves various vehicle routing problems (VRPs), improves the solutions of VRPs by swapping the sub-tours of the vehicles. Inspired by CE, we propose Neuro CE (NCE), a fundamental operator of \textit{learned} meta-heuristic, to solve various min-max VRPs while overcoming the limitations of CE, i.e., the expensive $\mathcal{O}(n^4)$ search cost. NCE employs graph neural network to predict the cost-decrements (i.e., results of CE searches) and utilizes the predicted cost-decrements to guide the selection of sub-tours for swapping, while reducing the search cost to $\mathcal{O}(n^2)$. As the learning objective of NCE is to predict the cost-decrement, the training can be simply done in a supervised fashion, whose training samples can be easily collected. Despite the simplicity of NCE, numerical results show that the NCE trained with min-max flexible multi-depot VRP (min-max FMDVRP) outperforms the meta-heuristic baselines. More importantly, it significantly outperforms the neural baselines when solving distinctive special cases of min-max FMDVRP (e.g., min-max MDVRP, min-max mTSP, min-max CVRP) without additional training.

Published as a conference paper at ICLR 2023
LEARNING TO CROSS EXCHANGE TO SOLVE MIN- MAX VEHICLE ROUTING PROBLEMS
Minjun Kim", Junyoung Park", & Jiinyyo Park KAIST, Daejeon, South Korea
(minjum1211 122,, junyoungpark, jinkyoo. pattyooo..arkkkkkstt...ae
ABSTRACT
CROSS exchange (CE), meta-heuristic that solves various vehicle routing prob- lems (VRPs), improves the solutions of VRPs by swapping the sub-tours of the vehicles. Inspired by CE, we propose Neuro CE (NCE), fundamental opera- solve various min-max VRPs while overcoming
tor of learned heta-heuristic, the limitations of CE, i.e., the expensive O(n*) search cost. NCE employs graph neural network to predict the cost-decrements (i.e., results CE searches) and utilizes the predicted cost-decrements to guide the selection of sub-tours for swap- ping, while reducing the search cost to O(n²). As the learning objective of NCE is predict the cost-decrement, the training can be simply done in supervised fashion, whose training samples can he easily collected. Despite the simplicity of NCE, numerical results show that the NCE trained with min-max flexible multi- depot VRP (min-max FMDVRP) outperforms the meta-heuristic baselines. More importantly, it significantly outperforms the neural baselines when solving distinc- tive special cases of min-max FMDVRP (e.g., min-max MDVRP, min-max mTSP, min-max CVRP) without additional training.
INTRODUCTION
The field of neural combinatorial optimization (NCO), an emerging research area intersecting oper- ation research and artificial intelligence, aims to train an effective solver for various combinatorial optimization (CO) problems, such as the traveling salesman problem (TSP) (Bello et al., 2016; Khalil et al., 2017: Nazari et al., 2018; Kool et al., 2018; Kwon et al., 2020), vehicle routing prob- lems (VRPs) (Bello et al., 2016; Khalil et al., 2017; Nazari et al., 2018; Kool et al., 2018; Kwon et al., 2020; Hottung & Tiemney 2019; Lu al., 2019; da Costa al., 2021), and vertex covering problems (Khalil et al., 2017; Li et al., 2018; Guo et al., 2019). As NCO tackles NP-hard prob- lems using various state-of-the-art (SOTA) deep learning techniques, it is considered an important research area in artificial intelligence. At the same time, NCO is an important field from a practical point of view because can solve complex real-world problems. The current study mainly focuses on VRPs. type of CO problems.
Majority of learning-based VRP solvers learns improve the current solution to obtain a better solution (i.e., improvement heuristics) (Hottung & Tierney, 2019; Lu et al., 2019; da Costa et al., 2021) or construct solution sequentially (i.e., construction heuristics) (Bello et al., 2016; Khalil et al., 2017; Nazari et al., 2018; Kool et al., 2018; Kwon et al., 2020; Park et al., 2021; Cao et al., 2021). To learn such solvers, learning- methods either employ supervised learning (SL), which imitates the solutions of the verified solvers, or reinforcement learning (RL), which learn solver from the generated routes. Most NCO studies focus on the well-established "min-sum VRP" that aims to minimize the total traveling distance of vehicles, possibly because the benchmark problems and baseline algorithms are set up for the "min-sum VRP. On the other hand, VRP with different objectives have not received much attention from the NCO community, even though they model various practical scenarios. For example, "min-max VRP" that aims to minimize the total comple- tion time (i.e., makespan) of various time-critical distributed tasks (e.g., vaccine delivery, grocery delivery) has not been widely considered.
Equal contribution

---

Published as a conference paper at ICLR 2023
Repeal until
"stop improvemennt
de 6 00.0
ooo
Problem
Initial solution
Select two bours
Inter operation (CROSS exchange)
Intra Operation
Instance
construction
Solution
Figure 1: The overall procedure of improvement heuristic that uses CE the inter-operation.
This study aims to learn a fundamental and universal operator that can effectively solve various prac- tical "min-max VRP" that have flexible depot constraints. To design an universal and simple, yet powerful operator, we utilize PROSS-exxhaappe to conduct the inter-operation of two routes (i.e., swapping the sub-tours of two selected routes) to reduce the traveling cost. We noticed that the inter-operation of CE is especially effective in improv- ing the quality of "min-max VRP" because it can consider the interaction among multiple vehicles, and effectively reduce the differences between the traveling distances of all vehicles. However, the search cost for selecting the sub-tours from two trajectory Onn²) where n is the tour length. This make CE unapplicable large scale VRPs.
(CE) (Taillard et al., 1997), local search designed
In this paper, we propose Neuro CE (NCE) that effectively conducts the CE operation with signifi- cantly less computational complexity. NCE amortizes the search for ending nodes of the sub-toury by employing graph neural network (GNN), which predicts the best cost decrement, given two starting nodes from two given trajectories. NCE searches over only promising starting nodes using the prediction. Hence, the proposed NCE has (n²²) search complexity. Furthermore, unlike other SL RL approaches, the prediction target labels of NCE is not the entire solution of the VRPs, but the cost decrements of the CE operations (true target operator), which makes the collection of training data simple and easy.
The contributions of this study are summarized as follows:
As NCE lears fundamental and universal operator solve various complex min-max VRPs without retraining for each type of VRPs.
Trainability: The NCE operator is trained in a supervised manner with the dataset comprised of the tour pairs and cost decrements, which make the collection of training data easy and simple.
Practiclitt/Perrornnnce We evaluate NCE with various types of min-max VRPs, including flexible multi-depot VRP (min-max FMDVRP), multi-depot VRP (min-max MDVRP), multi- ple TSP (min-max mTSP), and capacitated VRP (min-max CVRP). Extensive numerical ex- periments validate that NCE outperforms SOTA meta-heuristics and NCO baselines in solving various min-max VRPs, even though NCE is only trained with the data from min-max FMDVRP.
2
PRELIMINARIES
This section introduces the target problem, min-max flexible multi-depot VRP (min-max FMD- VRP), and the CE operator, powerful local-search heuristics that solves min-max FMDVRP.
2.1 MIN-MAX FLEXIBLE MULTI-DEPOT VRP
Min-max FMDVRP is a generalization of VRP that aims to find the coordinated routes of multiple vehicles with multiple depots. The flexibility allows vehicles to go back to any depots regardless of their starting depots. The min-max FMDVRP is formulated as follows:
min max C(T.) TES(P) REV
(I)
where P is the description of the min-max FMDVRP instance that is composed of set of vehicles V. S(P) is the set solutions that satisfy the constraints of the min-man max FMDVRP (i.c., feasible solutions), and (Tx)iev is solution of the min-max FMDVRP. The tour = [N1, No, .., Nuo)
2

---

Published as a conference paper at ICLR 2023
Algorithm 1: Neuro CROSS exchange (NCE) for solving VRP family
Input: VRP instance cost-dcerement prediction model fo, Perturbation parameter p Output: Optimized tours {T; ]ee/>]
(T.)eey) x- GetInitiialSolution
Oper 6- 0
while True do
while improvement do
(TI, r2) + SelectTourss(thhee
( T2 BeuroCROSS(1, 72.
// Inter operation
T < IntraOperation(T))) 1,2
71 T +2
if update then
L hei' < (n.
11
Ope = p then
12
L break
Oper Oper
14
(TI, ChooseRandomTours
15
(TI, T2) < RandomExchange(77, T2)
// escape from local minima
of vehicle i is the ordered collection of the visited tasks by the vehicle us and C(T,) is the cost of тi. Min-max FMDVRP can be used to formulate the operation of shared vehicles that can be picked up from delivered any depots. The mixed integer linear programming (MILP) formulation of min-max FMDVRP is provided in Appendix A.3.
Classical VRPs are special cases FMDVRP: iSP a VRP with single vehicle and depot, mTSP is a VRP with multiple vehicles and single depot, and MDVRP is VRP with multiple vehicles and depots. Since FMVDRP is general problem class, learn a solver for FMVDRP and employ it to solve other specific problems (i.e., min-max MDVRP, min-max mTSP, and min-max CVRP), without retraining or fine-tuning. We demonstrate that the proposed method can solve these special cases almost optimally without retraining in Section 4.
2.2 CROSS EXCHINNG
CE is a solution updating operator that iteratively improves the solution until reaches a satisfactory result (Taillard al., 1997). CE reduces the overall cost by exchanging the sub-tours in two tours. The CE operator is defined as:
-/. r2 CROSS(a), b1, 02 be: Tı, T2)
T è TI ai] @ ma b2] mm [b
(3)
A T2|: [2) ma bi] @ To
(4)
where and Ti are the input and updated tours of the vehicle i, respectively. Tı(a: b] represents the sub-tour Tr, ranging from node brevity, we assume that node a1, comes early than node b,, b2 in T1. respectively.
7' represents the concatenation of tours 7 and r'. For
CE selects the sub-tours (i.e., Ti [a] b1], T2(d2 : by)) from T1, 72 and swaps the sub-tours generate new tours Tí. T5. CE seeks to find the four points (a1, b1, 02, by) to reduce the cost of the tours. For min-max VRPs, we define the cost of the two selected tours as C(T1, T2) max(((71). ((T2),, where I(T;) is the traveling distance of tour т,, and apply the CE operator to reduce this cost, i.e., C(Ti, S C(T,, T2) an attempt minimize the traveling distance of the longest route. When the full search method is naively employed, the search cost is O(n²), where is the number of nodes in a tour.
Fig. illustrates how the improvement heuristics utilize CE to solve min-max FMDVRP. The im- provement heuristics start by generating the initial feasible tours using simple heuristics. Then, they repeatedly (1) select two tours, (2) apply inter-operation to generate improved tours by CE, and (3) apply intra-operation to improve the tours independently. The improvement heuristics terminate when more (local) improvement is possible.
3

---

Published as a conference paper at ICLR 2023
Algorithm 2: NeuroCROSS operation
Input: tours 7I, T2, cost-decrement prediction model fa(-)
Output: updated tours rí,
/+ -Fredicct cost decrement
*/
S+ 5+= [0}
17 for (01,02) E TI do
18
(.l + fo a2;
// Cost deccemennttt prediction
19
8 (L(a,, 02). (1,
Cancicate
construction
20 Sort Sy (an, 72) in the descending order
21 Sx < Take first K elements of
/+ Perform search
ai - 00 0. + 0, b2 0. +-
23
Ti; T2, E Sk do for ala1, (a1, TI,
(ai,
24
(bi, +- arg max,, d2 (C(CROSS((an bi, 02, ba: (.))))) C(m, m2))
25
y" (a1, 02: T2) +- C(CROSs((a), az, be:TI, 12)) - ((T..
26
y (1; 2 y then
aj 01,02 a2. bj bi, b2
28
+ (a1; 02; T1,
(71, 72)
CROSS(aj, bi 0z. 05: 72)
NEURO CROSS EXCHANGE
In this section, we introduce Neuro CROSS exchange (NCE) to solve min-max FMDVRP and its special cases. The overall procedure of NCE summarized in Algorithm 1. We briefly explain GetInitialSolution SelectTours, NeuroCROss, and IntraOperation, and then provide the details of the proposed NeuroCROSS operation in the following subsections. NCE is particularly designed to improve the solution quality and problem solving speed of CE when solving min-max VRPs. Each component NCE is as follows:
Get.IiitialSolution. We use a multi-agent extended version of the greedy assignment heuristic (Dell' Amico et al., 1993) to obtain the initial feasible solutions. The heuristic first clusters the cities into [ clusters and then applies the greedy assignment each cluster get the initial solution.
SelectTours. Following the common practice, select Tı, the tours with the largest and smallest traveling distance (i.e., Tı = arg (( 72 = arg min, (M(T))e))))
NeruoCROSS. We utilize the cost-decrement prediction model fn(-) and two-stage search method to find the cost-improving tour pair (Tí, T with O(n?) budget. The details of the NCE operation will be given in Sections 3.1 and 3.2.
IntraOperation. For target VRPs, the intra-operation is equivalent solving TSP. We utilize elkai (Dimitrovski) to solve TSP.
3.1 NEURO CROSS EXCHANGE OPERATION
The CE operation can be shown as selecting two pairs of nodes (i.e., the pairs of a1/b, and az/by from the selected tours (i.e., Ti, T2). This typically involves O(n") searches. To reduce the high search complexity, NCE utilizes the cost-decrement model fo(01, 42; T1, 72) that predicts the maxi- mum cost decrements from the given Ti and 72, and the starting nodes aj and 02 of their sub-tours. That is, fo(a), .2; TI, 72) amortizes the search for the ending nodes b,, b2 given (TI, T2, 01, a2), and helps to identify the promising (01, 0z) pairs that are likely to improve the tours. After selecting the top K promising pairs of (01, 02) using fo(a1, 02; Tı, 72), whose search cost is O(n?). NCE then finds (b,, b2) to identify the promising (a), a2) pairs. Overall, the entire search can be done in On??) The following paragraphs detail the procedures of NCE.
4

---

Published as a conference paper at ICLR 2023
Predicting cost decrement. We employ fo fo d2i T2) (which will be explained in Section 3.2) to predict the optimal cost decrement y defined as:
y (a1, 02; TI, T2)
max (C(CROSS((a), bi, ag, (2i C(Ti, T2))
(5)
b1.02
= (a1, 02; T1, T2)
(6)
where C(ri, 72) max (((()))((2)))) In other words, fo(-) predicts the best cost decrement of 71 and T2, given dj and ag. The real cost decrement labels are obtained from the real search operation.
Constructing search candidate set. By training fo(-), we can amortize the search for i and b2. However, this amortization bears the prediction errors, which can misguide entire improvement process. To alleviate this problem, we selects the top K pairs of (#1, (01)2) that have the top largest y" out of all (a1, (2) choices. Intuitively speaking, NCE exclude the less promising (a1, a2) pairs while utilizing the prediction model fa(+) which can have some errors.
Performing reduced search. NCE finds the best (b), b2) for each (41, (2) in the search candidate sets and selects the best sub-tours (41, 02 b1.by) b2) that maximizes the actual cost decrement (not pre- diction). Unlike the full search of CE, the proposed NCE only performs the search for (b1,62), which reduces the search cost from (n*) ) to O(n²). The detailed procedures of NCE are summarized in Algorithm 2.
3.2
COST-DECREMENT PREDICTION MODEL
NCE saves computations by employing (a d2; T2) to predict y-) from @j 02, Tı and T2- The overall procedure is illustrated in Fig. 2.
Graph representation of (T1, T2). We represent a pair of tours (Ti, T2) as a directed complete graph 9 (N, E), where N U (i.e., the 7hh node n; of is either the city depot of the tours, and eij is the edge from nı; to nj). 9 has the following node and edge features:
(n:) Leeoo [n:)) where coord(n:) is the 2D Euclidean coordinate of us and deeoo (fi: is the indicator of whether n, is a depot.
Tij [dist my)], where dist(n;, n2) is the 2D Euclidean distance between n, and ny-
Graph embedding with attentive graph neural network. We employ an attentive variant of graph-network (GN) block (Battaglia et al., 2018) embed G. The attentive embedding layer is defined as follows:
My de (his leg, 2tas)
Zij a (his lejs bag sieg)
(8)
wi = softmax Zis ()(N())))))
(9)
A/4 = on (hi:
Σ JEN(()
wiyhls)
(10)
where h; and by node and edge embeddings respectively, de, Φu. and on are the Multilayer Perceptron paraat--areeteeiize edge, attention and node operators respectively, and N(i) is the
(H) neighbor set of n,. We utilize H embedding layers to compute the final node (h, n, V) and (H) eiy E E} embeddings.
edge (h
Cost-decrement prediction. Based on the computed embedding, the cost prediction module Φa predicts y" (a1, 02: T1. 72). The selection of the two starting nodes in and T2 indicates (I) the addition the two edges, (a1, a2 + 1) and (a2, 0₁ + 1), and (2) the removal of the original two edges, (01, 0g + 1) and (a2, a2 1), as shown in the third block in Fig. 2 (we overload the notations a1 + 1, 02 + so that they denote the next nodes of 01, 02 in T1, T2, respectively). To consider such design de as follows:
edge addition and removal procedure in cost prediction,
g" (a1, 02) T1, T2) = (c(h(H) 01
(1) Rgg
(H) h h (!)
(I)
Parart ag. (11)
(I)
(I)
Bay +1 02.
embedding
link addition
... link removal

---

Published as a conference paper at ICLR 2023
Cost-decrement prediction model (a T2)
T1
0.0
00o
0-0-O
T2
O 0-0---0 1:
Graph regresenationn of (2)
Embeddled (f).
Addos//emoved edges
Cost-decrement prediction
Figure 2: Cost-decrement prediction procedure
where (i and h denotes the embedding of n, and Eijy respectively.
The quality of the NCE operator highly depends the accuracy of fe. When K 10, experi- mentally confirmed that the NCE operator finds the argmax (a1, 02, b, b2) pair with high probability. We provide the experimental details and results about the predictions of fo in Appendix H.
4 EXPERIMENTS
This section provides the experiment results that validate the effectiveness of the proposed NCE in solving min-max max FMDVRP and various min-max VRPs. To train fe(-). we use the input (Ti, T2, 01, 02) and output y pairs obtained from 50,000 random min-mai max FMDVRP instances. The details of the train data generation are described in Appendix G. The cost decrement model fo(-) is parametrized by the GNN that contains the five attentive embedding layers. The details of the fo(-) architecture and the computing infrastructure used to train fo()) are discussed in Appendix G.
We emphasize that we use single fo(-) that is trained using data obtained from random min-mat max FMDVRP instances for all experiments. We found that fa(.) effectively solves the three special cases (i.e., min-max MDVRP, min-max mTSP, min-max CVRP) without retraining or fine- tuning, proving the effectiveness of NCE universal operator for VRPs.
4.1 MIN-MAX FMDVRP EXPERIMENTS
We evaluate the performance of NCE solving various sizes of min-max FMDVRP. We consider 100 random min-max FMDVRP instances for each problem size (Ne, Na, No), where Ne, Na, N, are the number of cities, depots, and vehicles, respectively. We provide the average makespan and computation time for the 100 instances. For small-sized problems (N, 10), we employ CPLEX (Cplex, 2009) (an exact method), OR-tools (Perron & Furnon), CE (full search), ScheduleNet (Park al., 2021), greedy heuristic (Dell' Amico al.. 1993), and greedy TSP heuristic baselines. For the larger-sized problems, we exclude CPLEX from the baselines due to its limited scalability. To our knowledge, our method is the first neural approach to solve min-max FMDVRP. Please note that we extend the ScheduleNet algorithm (Park et al., 2021), the most performing neural baseline for mTSP, and utilize as neural baseline for the min- max FMVDRP experiments.
Table 1: FMDVRP results (small-sizer instances)
Ne.Na (4)
No(+) Method
2
Cost
Gap(%)
Time(sec.)
Cost
Gap(")
Time(sec.)
CPLEX
1.543
0.00
0.31
1.363
0.00
(7.2)
OR-tools
1,596
3.43
0.01
1,380
1.25
0.01
NCE
1.546
0.02
0.10
1.365
0.01
0.12
N+(+)
2
3
Method
Gap(%)
Time(sec.)
Gap(%)
Timefsec.)
(10.2)
OR-tools
1.820
4.30
0.02
1.521
2.22
0.02
CE
1.749
0.02
0.07
1.493
0.03
0.06
NCE
1.749
0.02
0.13
1.493
0.03
0.16

---

Published as a conference paper at ICLR 2023
Table 2: FMDVRP results imedium-sized instances)
No. Na
(.(++) Method
(4)
Cost
Gap(Xi)
Time(sec.)
Cost
(a)(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
OR-tools
2.39
2.20
1.56
10.64
2.44
1.27
6.72
2.58
(50.6)
ScheduleNet
2.61
26.09
5.21
1.86
3191
5.44
1.57
31.93
6.14
Greedy
3.01
46.38
0.01
2.24
58.87
0.01
1.99
67.23
0.01
Greedy + TSP
2.75
32.85
0.03
2.12
50.35
0.02
1.91
60.50
0.02
CF
2.07
0.00
21.06
1.41
0.00
9.09
1.19
0.00
5.37
NCE
2.08
0.48
1.26
1.40
-0.71
1.82
1.19
0.00
2.23
(-+++ Method
Cost
Gap(
Time(sec.)
Cust
Gap(%)
Time((sec.)
Gap(%)
Time(sec.)
OR-tools
2.00
14.94
30.46
1.51
12.69
32.25
1.20
10.09
34.38
(100,8)
ScheduleNet
2.32
33.33
35.47
1.86
38.81
36.08
1.54
41.28
41.30
Greedy
2.82
62.07
0.04
2.37
76.87
0.05
2,00
83.49
0.05
Greedy + TSP
2.60
49.43
0.07
2.25
67.16
0.07
1.92
76.16
0..77
CE
1.74
0.00
218.46
1.34
0.00
128.40
1.09
0.00
78.56
NCE
1.75
0.57
6.41
1.34
0.00
9.54
1.09
0.00
13.34
Table 3: EMDVRP results (large-sized instances)
(o(
10,10
400,200,0
800),00,40
Method
Cost
Gap(%)
Timcisce.)
Cost
Gap(%)
Time(sec.) )
Cost
Gsp(
Timoosoc.)
Cost
Gap(26)
Timo(see.)
OR-tools
1.47
12.21
418.8
1,08
12,50
9484
0.88
17.33
25967
1.09
67.69
72166
ScheduleNet
42.75
244.8
1.43
48.97
340
1.38
84,00
970
1.18
81.54
2383
Greedy
2.44
86.26
0.22
2.14
122.92
1.46
2.32
209.33
2.71
1.85
184.62
5.78
Greedy TSP
2.06
1.54
2.20
169.23
6.05
NCE
1.31
0.00
70.96
0.96
0.00
520.5
0.75
0.00
1940
0.65
0.00
3802
Table 1 shows the performances of NCE the small-sized problems. NCE achieve similar makespans with CPLEX (optimal solution) within significantly lower computation times. NCE out- performs OR-tools in terms makespan but has longer computation time; however, the computation time for NCE will be much lower than that of OR-tools when the problem size becomes bigger. It is noteworthy that NCE exhibits larger computation time than CE as the forward proaard-roppaattin cost of GNN is larger than exhaustive search for small problems.
Table 2 and Table shows the performances NCE on the medium and large- problems, re- spectively. Applying CPLEX for large min-max FMDVRPs is infeasible, so we exclude it from the baselines. Instead, the serves as an oracle to compute the makespans. For cases, NCE pro- vides solution with almost zero gap from CE but is computationally much faster. This validates that NCE successfully amortizes the search operations of CE with significantly lower computation times. In addition, NCE consistently outperforms OR-tools for both the makespan and computa- tional time. The performance gap between NCE and OR-tools becomes more significant as No/N, becomes large (i.e., each tour length becomes longer).
min-max MDVRP results. We also apply NCE with fo that is trained FMDVRP to solve min- max MDVRP. As shown Tables A. to A.3 in Appendix B, NCE shows leading performance and is faster than the baselines, similar to the FMDVRP experiments.
4.2 MIN-MAX MTSP EXPERIMENTS
We evaluate the generalization capability of NCE for solving min-max mTSPs We provide the average performance of 100 instances for each (Ne, N.) pair. For the baselines, we consider two meta-heuristics; I.KH- (Helsgaun, 2017), which known as the one of the best mTSP heuristics, and OR-tools, and two neural baselines; ScheduleNet (Park et al., 2021) and DAN (Cao et al., 202
As shown in Table 4, NCE achieves similar performance with LKH-3 with significantly shorter computational time. It is noteworthy that LKH-3 employs mTSS-speccfic heuristics top of LKH heuristics, while NCE does not employ any mTSP speeiffc structures. To validate the effect of task- specific information on NCE, train NCE with mTSP data (NCE-mTSP) and solve mTSP The performances NCE and NSE-mTSP are almost identical, which indicates that NCE is highly generalizable. In addition, NCE consistently outperforms the neural baselines. We further apply

---

Published as a conference paper at ICLR 2023
Table Average makespans of the random mTSPs: DAN and ScheduleNet results are taken from the original papers, i computational time of DAN is measured with the Nvidia RTX 3090.
No (1)
(-(+) Method
Cost
Gap(%8
Time(sec)
Cost
Gap (%6)
Time(sec.)
Cost
Gupt Gap(%)
Time(sec.)
LKH-3
2,00
0.00
187 46
1.95
0.00
249.31
1.1
0.00
170.20
OR-tools
2.04
2.00
3.24
1.96
0.51
3.75
1.91
0.00
3:67
0.25t
0:267
0.30
SchendaleNet
2.17
8.50
1.60
2.07
6.15
1.67
1.98
3.66
1.90
NCE
2.02
1.00
2.25
1.96
0.51
2.44
1.91
0.00
3.38
NCE-mTTS
2,02
1.00
2.48
1.96
0.51
2.50
1.91
0.00
3.44
(-())
15
Method
Gap(%)
Time(sec)
Gap(%6
Timo(sec.)
Cost
Gap(%6)
Timetsco.)
LKH-3
2.20
0.00
262.85
1.97
0.00
474.78
1.98
0.00
378.90
OR-lools
3.05
2.53
48.86
100
DAN
2.72
23.64
0.431
2.17
10.15
0.48
2.09
5,56
0,581
SchenduleNet
20.02
NCE
2.25
2.27
16.01
1.98
0.51
12.22
1.98
0.00
24.08
NCE-wISP
23.37
(-+))) Method
10
Cost
Cap(%) (%)
Timo(scc.)
Cost
(9p(%)
Timetsec.)
Cost
Gsp(96)
Timofscc.)
LKH-3
1224.40 675.79
908.14
OR-tools
2.33
14.22
2.33
16.50
604.31
2.37
20.30
649.17
200
DAN
2,40
17.65
0.93
2.20
10.00
0.98'
2.15
9.14
ScheuduleNet
2.45
20.10
193.41
2.24
12,00
213.07
2.17
10.15
225.50
NCE
83,82
72.32
0.00
113.74
NCE-mTSP
2,06
0.98
84.96
2.00
0.00
84.28
1.97
0.00
118.55
NCE to solve mTSPLib mTSPLib, which comprises of mTSP instances from real cities, and large size min-max mTSPs. The experiment results are in Appendix C.
4.3 MIN-MAX CVRP EXPERIMENTS
Table 5: min-max CVRP results: (s.n) indicates the best results of n sampling. The baseline results are taken from (Bogyrbayeva al., 2021).
N (.-)) Method
20,3
30,3
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
OR-tools
2.04
0.99
1.0
2.44
11.42
1.0
AM (Bogyrbayeva et al., 2021)
2.20
8.91
0.1
2.47
12.79
0.2
AM (s. 12000) (Bogyrbayeva et al. 2021)
2.44
20.79
11.4
2.29
4.57
27.6
HM (Bogyrhayeva et al., 2021)
2.28
12.87
0.1
2.39
9.13
0.2
HM (s.1200) (Bogyrbayeva et al., 2021)
2.15
6.44
14.3
2.27
3.65
25.2
NCE
2.06
1.98
1.16
2.25
2.74
2.03
NC
2.02
0.00
2.31
2.19
0.00
5.78
We evaluate the generalization capability of NCE in solving min-max capacitated VRP. As fe(-) trained on min-max FMDVRPs, it does not consider the capacity constraints. However, we can easily enforce such constraints without retraining fe(-), ), but by adjusting the searching range as follows:
(b1. b2) & arg max (CCCRDSS((2), b,, a2, byi TI, T2))) C(Tl, b...
(12)
where the searching range S. is set of nodes that satisfies the capacity constraints. As shown in Table 5, NCE outperforms other neural baselines (i.e., AM and HM) with shorter computation times, which again proves the effectiveness of NCE universal operator. Min-max CVRP with CVRPlib results are provided in Appendix D, Table A.6.
As most NCO studies min-sum CVRP as the canonical benchmark tasks, also employed NCE to solve min-sum CVRP problems. For min-sum CVRP, we trained the NCE cost decrement predic- tion model using different cost definition C(TI, T2) I(T)) I(T2) in attempt to minimize the
8

---

Published as a conference paper at ICLR 2023
sum of the traveling distance. The min-sum CVRP benchmark results provided in Appendix E, Table A.7.
4.4 ABLATION STUDIES
We evaluate the effects of the hyperparameters on NCE. The results are as follows:
Appendix F.I: the performance of NCE converges when the number of candidate K 2 10.
Appendix F.2: the performance of NCE is less sensitive to the selection of intra solvers.
Appendix F3: the performance of NCE is less sensitive the selection of swapping tours.
Appendix F.4: the performance of NCE converges when the perturbation parameter p 2 5.
5 RELATED WORKS
Supervised learning (SL) approach to solve VRPs SL approaches (Joshi et al., 2019; Vinyals et al., 2015; Xin et al., b021b; Li et al., 2021; 2018) utilize the supervision from the VRP solvers as the training labels. (Vinyals et al., 2015; Joshi et al., 2019) imitates TSP solvers using PointerNet and graph convolution network (GCN), respectively. (Joshi et al., 2019) trains a GCN to predict TSP solutions. Even though SL often offer a faster solving speed than existing solvers, their use is limited to the problems where the solvers are available. Such property limits the use SL from general and realistic VRPs.
the edge occurrence probabilities
Reinforcement learning (RL) approach to solve VRPs RL RL approaches (Bello et al., 2016; Khalil et al., 2017; Nazari et al., 2018; Kool et al., 2018; Kwon et al., 2020; Park et al., 2021; Cao et al., 2021: Guo et al., 2019; Wu al., 2019; 2021; Falkner & Schmidt-Thieme 2020; Chen & Tian, 2019) exhibit promising performances that are comparable to existing solvers as they learn solvers from the problem-solving simulations. (Bello al., 2016; Nazari et al., 2018; Kool al., 2018; Guo et al., 2019) utilize an mncoder-decoder structure to generate routing schedules sequentially, while (Park et al., 2021; Khalil et al., 2017) use graph-based embedding to determine the next assignment action. However, RL approaches often require the problem-specifie Markov decision process and network design. NCE does not require the simulation of the entire problem-soo -olving... Instead, it only requires the computation of the swapping operation (i.e., the results of CE). This property allows NCE to be trained easily to solve various routing problems with one scheme.
Neural network-based (meta) heuristic approach Combining machine learning (ML) compo- nents with existing (meta) heuristics shows strong empirical performances when solving VRPs (Hot- tung Tierney, 2019; Xin et al., 2021b; Li al., 2021; Lu et al., 2019; da Costa et al., 2021; Kool et al., 2021). They often employ ML to learn to solve NP-hard sub-problems of VRPs, which are difficult. For example, L2D (Li et al., 2021) learns to predict the objective value of CVRP, NLNS (Hottung& & Tierney, 2019) learns TSP solver when solving VRPs and DPDP (Kool et al., 2021) learss to boost the dynamic programming algorithms. To learn such solvers, these methods apply SL RL. Instead, NCE learns the fundamental operator of meta-heuristics rather than predict or generate a solution. Hence, NCE that trained on FMDVRP generalizes well to the special cases of FMDVRP, Furthermore, the training data for NCE can be prepared effortlessly.
CONCLUSION
We propose Neuro CROSS exchange (NCE), a neural network-enhanced CE operator, to learn fundamental and universal operator that can be used to solve the various types of min-max VRPs. We validated that NCE can solve various min-max VRPs without retraining for each specific problem, exhibiting strong empirical performances. Although NCE addresses more realistic VRPs (i.e., min- max FMDVRP) than existing NCO solvers, NCE does not yet consider complex constraints such as pickup and delivery, and time windows. Our future research will focus on solving more complex VRPs by considering such various constraints during the NCE operation.

---

Published as a conference paper at ICLR 2023
REFERENCES
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzale Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint 2018.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 10t::6611109990 2016.
Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. arXiv 2022.
preprint
Aigerim Bogyrbayeva, Taehyun Yoon, Hanbum Ko, Sungbin Lim, Hyokun Yun, and Changhyun Kwon. A deep reinforcement learning approach for solving the traveling salesman problem with drone. arXiv preprint arXiv:2112.12545: 2021.
Jakob Bossek, Pascal Kerschke, Aneta Neumann, Markus Wagner, Frank Neumann, and Heike Trautmann. Evolving diverse tsp instances by means of novel and creative mutation operators. In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, pp.
58-71, 2019.
Yuhong Cao, Zhanhong Sun, and Guillaume Sartoretti, Dan: Decentralized attention baasd neural network solve the minmax multiple traveling salesman problem. arXiv preprint arXiv:2109.04205. 2021.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, pp. 22222, 2019.
IBM ILOG Cplex. V12. 1: User's manual for cplex. International Business Machines Corporation, 46(53):157, 2009.
Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, Alp Akcay, and Uzay Kaymak. Learning 2-opt heuristics for routing problems via deep reinforcement learning. SN Computer Science, 15):1-16, 2021.
Mauro Dell' Amico, Matteo Fischetti, and Paolo Toth. Heuristic algorithms for the multiple depot vehicle scheduling problem. Management Science, 39(1):115-125, 1993.
Filip Dimitrovski. Elkai. URL httptttt///t http://ww....om/iiiissss////eeee
Jonas K Falkner and Lars Schmidt-Thieme. Learning to solve vehicle routing problems with time windows through joint attention. arXiv preprint 1rXiv:2006.09100. 2020.
Tiande Guo, Congying Han, Siqi Tang, and Man Ding. Solving combinatorial problems with ma- chine learning methods. In Nonlinear Combinatorial Optimization, pp. 207-229. Springer, 2019.
Keld Helsgaun. An extension of the lin-kernighan-helsgeee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
André Hottung and Kevin Tiemny. Neural large neighborhood search for the capacitated vehicle routing problem. arXiv preprint arXiv: 191 1.09539, 2019.
Yuan Jiang. Yaoxin Wu, Zhiguang Cao, and Jie Zhang. Learning solve routing problems via distributionally robust optimization. arXiv preprint arXiv:2202.072241, 2022.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network
technique for the travelling salesman problem. arXiv preprint arXiv: /906./9900////000 0227, 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp- (348-6358, 2017.
10

---

Published as a conference paper at ICLR 2023
Minsu Kim, Jinkyoo Park, al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34, 2021.
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1003 1803.0887 2018.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic pro- gramming for vehicle routing problems. arXiv preprint arXiv:2102. 2021.
Yeong-Dat Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min.
Pomo: Policy optimization with multiple optima for reinforcement learning. Advances Neural Information Processing Systems, 33:21 188-21198, 2020.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing, Ad- vances in Neural Information Processing Systems, 34, 2021.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. Advances in neural information processing systems, 31, 2018.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
arXiv:1711.05101 2017.
Hao Lu, Xingwen Zhang, and Shuang Yang. learning-based iterative method for solving vehicle routing problems. In International conference on learning representations, 2019.
Diganta Misra. Mish: A self regularized non-monotonic activation function. arXiv preprint
arXiv:1908. 08681, 2019.
mTSPLib. mTSPLib. URL
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849, 2018.
Junyoung Park, Sanjar Bakhtiyar, and Jinkyoo Park. Schedulenet: Learn to solve multi-agent scheduling problems with reinforcement learning. arXiv preprint arXiv:2100.03051, 2021.
Laurent Perron and Vincent Furnon. Or-tools. URL httph:tt/////tt htttps://developers..ggo optimmi zation/.
com/
Quang Dung Pham, Kim Thu Le, Hoang Thanh Nguyen, Van Dinh Pham, and Quoe Trung Bui. constraint-based local search for offline and online general vehicle routing. International Journal on Artificial Intelligence Tools, 26(02): 1750004, 2017.
Olcay Polat, Can Kalayci, Osman Kulak, and Hans-Otto Günther. A perturbation based variable neighborhood search heuristic for solving the vehicle routing problem with simultaneous pickup and delivery with time limit. European Journal of Operational Research, 242(2):369-382, 2015.
éric Taillard, Philippe Badeau, Michel Gendreau, François Guertin, and Yves Potvin. A tabu search heuristic for the vehicle routing problem with soft time windows. Trunsportation science, 3102):170-186, 1997.
Son Van Nguyen, Dung Quang Pham, Trung Quoc Bui, and Hoang Thanh Nguyen. Solving min- max capacitated vehicle routing problem by local search. Journal of Computer Science and Cy- bernetics. 33(1):3-18, 2017.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. Advances in neural informa- tion processing systems, 28, 2015.
Yaoxin WU, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving the travelling salesman problem. 2019.
Yaoxin Wu, Wen Song, Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuris- tics for solving routing problem. IEEE Transactions on Neural Networks and Learning Systems, 2021.
11

---

Published as a conference paper at ICLR 2023
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embed- ding glimpse for solving vehicle routing problems. Proceedings of 35th AAAI Conference on Artificial Intelligence, pp. 12042-12049, 2021a.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Neurolkh: Combining deep learning model with fin-kerigghnn-helgeee heuristic for solving the traveling salesman problem. Advances in Neural Information Processing Systems, 34, 2021b.
12

---

Published as a conference paper at ICLR 2023
Neuro CROSS exchange Supplementary Material
A MILP FORMULATIONS FOR MIN-MAX ROUTING PROBLEMS
This section provides the mixed integer linear programming (MILP) formulations of mTSP, MD- VRP, and FMDVRP.
A.1 MTSP
mTSP is multi-vehicle extension of the traveling salesman problem (TSP). mTSP comprises of set of the nodes (i.e., cities) and depot V, a set of vehicles K, and set of depot S. We define d, the cost (or travel time) between node i and j, and the decision variable Zijk denotes whether the edge between node and j are taken by vehicle k. Following the convention, we consider mTSP with |S| = The MILP formulation of mTSP is given follows:
minimize
(A.1)
subject to.
Σ
dyyTijk S Q,
4k K :i
(A.2)
EVV JEV
Σ JEViøj
Tisk = 1,
E K,EES
(A.3)
Σ
Σ
Tijk = 1,
VjEVIS
(A.4)
iEV
Σ Dijk
Σ
Ijhk = 0,
VjEVIS
(A.5)
iEVinj
REVEYi
Uik Uik + |V|ziij
V 1,
vk K.jEV\Ssit)
(A.6)
0 ush I 1V|-1,
Vk KiiEV\ Vk E K, VijiV, Vk E KiiEV
(A.7)
Zigk E {0, 1}.
(A.8)
uik E Z,
(A.9)
where Q denotes the longest traveling distance among multiple vehicles. (i.e., makespan), Eq. (A.3) indicates the vehicles start at the depot, Eq. (A.4) indicates that all cities are visited, Eq. (A.5) indi- cates the balance equation for all cities, Eq. (A.6) and Eq. (A.7) indicate the sub-tour eliminations.
13

---

Published as a conference paper at ICLR 2023
A.2 MDVRP
Multi-depot VRP is a multi-depot extension of mTSP (Appendix A. where each vehicle starts from its own designated depot and returns to the depot. We extend the MILP formulation of mTSP to define the MILP formulation of MDVRP. On top of the mTSP formulation, we define Kü which indicates the of vehicles assigned the depot
minimize subject to.
(A.10)
deyRigh S Q,
Ak K Ki j.
(A.11)
REV
JEV
Σ
Σ
Tijk 1,
VEEVS
(A.12)
jEV KET
Σ
Σ
Tijk 11
VjEVIS
(A.13)
iEV KET
Σ Bijk
Σ
Ljhkk = O,
VjEV UVEVIS,VE SS
(A.14)
iEV
NEV
Uik Usk + IV (rizk 1
tkE K,j (.VVV8::1 8:141,
(A.15)
0 S uA I [V 11,
VK K,ieV\S
(A.16)
Zish E {0, 1}.
AK K,VijeEV,
(A.17)
Usk Z,
vk KiEV
(A.18)
Σ Tijk $
VKE ViES
(A.19)
JEVis
Σ Tisk I 1,
Ah KKEK,
(A.20)
iEV
where Eq. (A.19) and Eq. (A.20) indicate that each vehicle starts and returns its own depot at most once.
14

---

Published as a conference paper at ICLR 2023
A.3 FMDVRP
Flexible MDVRP (EMDVRP) is an extension of MDVRP, allowing the vehicle to return to any depot. We extend the MDVRP formulation (Appendix A.2) to define the FMDVRP formulation. To account for the flexibility of the returning depot, we introduce a dummy node for all depots; a depot modeled with a start and return depot. We define S1 and Sn as the set of start and return depots and Sy as the start node of the vehicle k.
minimize
(A.21)
subject to.
E
Σ JEV
dij S Q,
4k K :iki
(A.22)
Σ
Tifk = 1,
WEVIS
(A.23)
jEVi RET
Σ
Σ
Tijk 1,
VjEV 15
(A.24)
iEV KET
Σ Tigh
Σ
Tjhk 0,
V V (S
(A.25)
hEV
Usk Ujk + |V S I 1,
4k SEA.jeVVSSii
(A.26)
0 S I IV --1, 1,
V K,iEV\S
(A.27)
Zigk E {0,
THE K, Vi,,,,,,
(A.28)
Usk E Z,
vk E KiiEV
(A.29)
Σ Dsujk = 1,
Vk E K
(A.30)
JEV
Σ
Tijk
Vk E K, Vi S\ 8R
(A.31)
JEV
Σ JEV'S
Tijk S 1,
E KG, Vi S1
(A.32)
Σ
Dijk S
Vk E K3, Vj E S2
(A.33)
iEV'S
Σ Dijk O,
Ak E K, Vi E $2
(A.34)
JEVIS
Σ
Dijk
Wk K, Vi S1
(A.35)
JEVIS
ΣΣ
Pijk
ΣΣ SEV JES2
Tisk:
Wk E K
(A.36)
#EST JEVES
where Eqs. (A.30) and (A.31) indicate that each vehicle starts at its own depot. Eqs. (A.32) to (A.35) indicate the start and return depots constraints. Eq. (A.36) indicates the balance equation of the start and return depots.
15

---

Published as a conference paper at ICLR 2023
B MIN-MAX MDVRP RESULTS
In this section, we provide the experiment results of MDVRP. We apply NCE with the fo trained on FMDVRP instances solve MDVRP. For each (No; Na, N₂) pair, we measure the average makespan of 100 instances. We provide the MDVRP results in Tables A.1 to A.3. Similar to the FMDVRP experiments, NCE shows leading performance while being faster than the baselines. From the results, we can conclude that the learned fe is transferable to the different problem sets. This phenomenon is rare in many ML-based approaches. It again highlights the effectiveness of learning fundamental operators (i.e., learn what should be cross exchanged) when solving the VRP families.
Table A.1: MDVRP results (small-sized instances)
Na (L)
(-)+) Method
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Timo(sec.)
CPLEX
1.626
0.00
0.32
1.417
0.00
0.54
(7.2)
OR-tools
1.704
4,80
0.01
1,433
1.13
0.01
0.05
(-++
2
Method
Cost
Gap(%)
Time(sec.)
Cost
Gap (%)
Time(sec.)
CPLEX
(10,2)
OR-tools
1.926
5.30
0.02
1.590
2.32
0,02
0.09
NCE
1.839
0.00
0.17
1.558
0.01
0.20
Table A.2: MDVRP results (medium-sized instances)
No, Na.
N.(+)
3
Method
(ap(%)
Time(sec.)
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
2.24
2,94
1.36
(50.6)
CF
2.25
0.00
23.45
1.53
0.00
10.40
1.28
0.00
6,85
NCE
2.25
0.00
2.08
1.53
0.00
2.63
1.28
0.00
2.93
N.(++)
Meihod
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
OR-tools
2.17
17.30
33.08
1.60
11.89
36.45
1.29
9.32
37.54
(100,8)
CE
0.00
259.82
1.43
0.00
140.63
1.18
0.00
86.27
NCF
1.86
0.54
11.61
1.43
0.00
11.96
1.18
0.00
15.70
Table A.3: MDVRP results (large- sized instances)
Ne, Ná. No(+)
200, 10,10
400,20,20
600,30,30
Method
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
OR-tools
1.49
9.56
452.08
1.13
13.00
5179
1.01
24.69
22411
Greedy
2.99
119.85
0.20
2.77
177.00
0.93
3.20
295.06
2.69
Greedy + TSP
2.78
104.41
0.37
2.58
158.00
1.48
3.03
274.07
3.24
NCE
1.36
0.00
77.73
553.83
0.81
0.00
3173.5
16

---

Published as a conference paper at ICLR 2023
C MIN-MAX MTSP RESULTS
In this section, we provide the additional experiment results of m'TSP We further apply NCE to solve mTSPLib (mTSPLib), which comprises of mTSP instances from real cities, and large scale problem. As reported in Table A.4 and Table A.5 NCE achieves the best results as compared to the baselines.
Table A.4: TSPLLib results: CPLEX results with * are optimal solutions. Otherwise, the known- best upper bound of CPLEX results are reported. The results of other baselines are taken from Park et al. (2021).
N,(+)
ERS5
Berfin52
Ei778
Kurty
Ne(-t)
2
3
Gap
222.7"
134.0
4110
3244
2441
2441
139.6
443.9
LKTE3
232.7
159.6
124.0
112.1
4110
3254
2441
2441
290.9
197.3
150.3
139.6
728.8
567.2
469.3
443.8
1.00
OR-Tools
170.1
127.5
4665
3311
2482
2441
318.0
212.4
128.3
762.2
552.1
442.5
1.03
ScheddlaNet
SchohhleNet (x.4)
239.3
173.5
125.8
112.2
4992
3276
2517
2441
317.7
220.8
153.8
131.7
781.2
627.1
902.1
464
1.05
DAN
274.2
178.9
138.6
118.1
5226
4278
2759
2007
361.1
253.5
170.9
148.5
930.8
074.1
504.0
466.4
1.18
DAN (s.4)
NCE
235.0
170.3
121.6
112.1
4110
3274
2660
2441
265.5
211.0
144.6
127.6
695.8
527.8
48&
441.6
1,00
NCE-6TSP
236.1
166.3
119.9
112.1
4128
3191
2474
2441
282.
197.5
147.2
127.6
666,0
533.2
462.2
443.9
0.98
Table A.5: mTSP results (large-sized instances)
Ne(+)
mrSP3300
#rSP5500
mTSP750
Method
Gap(%)
Time(sec.)
(96(
Time(sec.)
Gap(%)
Timo(sec.)
LKH-3
2.12
1620
2981
OR-tools
2.90
36.79
3605
7.63
265.07
9877
10.91
448.24
47225
ScheduleNet
2.25
6.13
689
2.17
3.83
3788
2.12
6.53
12199
Greedy
2.82
33.02
1.07
2,85
36.36
3.78
2.76
38.69
4,56
Gready TSP
2.80
32.08
1.39
2.84
35.89
4.48
2.75
38.19
5.53
NCE
2.12
0.00
301
2.09
0.00
583
1.99
0.00
580
17

---

Published as a conference paper at ICLR 2023
D MIN-MAX CVRP RESULTS
We also provide min-max CVRP results for CVRPlib. We include two local search heuristic base- lines N2 (Pham al., 2017) and NMCF (Van Nguyen al., 2017). We evaluate each instance 20 times and average it. As shown in Table A.6, NCE outperforms other Operation Research baselines terms of computation speed and cost.
Table A.6: CVRPlib result: Results are taken from Van Nguyen et al. (2017)
Method
N2
NMCF
NCE (s.10)
VRP instance
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
Cost
Gap(%)
Time(sec.)
E-n22-k4
110.00
-0.63
4.98
110.00
-0.63
3.62
R-n23-K3
202.10
0.04
20,50
243.45
0.60
27.35
242.00
14.09
B-n30-K3
192.95
0.63
53.72
192.45
0.37
10.85
191.75
0.00
10.45
E-n33-k4
244.15
0.00
85.87
244.00
-0.06
11.07
244.15
0.00
6.43
E-n51-k5
118.70
5,42
119.50
113.50
0.80
67.09
112.60
0.00
14,40
B-n76-k7
119.35
12.44
115.85
107.35
1.13
120.49
106.15
0.00
34.94
E-n76-k8
118.85
18.67
140.44
100.05
-0.10
94.57
100.15
0.00
31.27
E-n76-k10
117.40
23.71
149.21
99.55
4.90
31.69
94.90
34.94
E-n76-k14
111.10
27.12
146.64
93.60
7.09
27.22
42.13
E-a101-88
141.65
26.42
140.07
117.05
4.46
69.01
112.05
71.96
E-n101-k14
113.25
13.19
161.05
101.50
1.45
68.04
100.05
0.00
83.74
18

---

Published as a conference paper at ICLR 2023
E MIN-SUM CVRP RESULTS
In this section, we provide the results for min-sum CVRP benchmark instances. To solve min-sum CVRP, we trained NCE to predict min-sum cost decrement with C(Ti, 72) defined ((T)) + ((T2). As shown in Table A.7, NCE is on par with or outperforms other neural baselines. However, NCE efficient in terms of computation speed. This is because we initially design the CE operation to solve the min-max VRPs nor min-sum sum VRPs. According to the experimental results, when CE operation conducted reduce the min- mim cost of tours, typically requires larger iterations to improve the solution to near optimum. This results indicates that other (local) search operator is required to efficiently solve the min-sum problems.
Best bold; Second underline, (s.n) indicates the best results of n sampling, (i.m) indicates the best results after improvement steps, and indacates that the computation times of the neural baselines are measured with GPU. The run times of Lu et al. (2019) and Kwon et al. (2020) taken from Kwon et al. (2020). The run times of the other neural baselines are taken from Kim et al. (2021).
Table A.7: CVRP benchmark results:
CVRP20
CVRP50
CVRP100
Methed
Cost
Gap(3)
Time(sec.)
Cost
Gap(XS)
Time(sec.)
Cost
Gap(56)
Time(sec.)
LKH.3
OR TooTo
6.43
4.72
0.01
11.31
8.17
0.05
17.16
10.29
0.23
(x.((x.1) (Nazari
6.40
4.23
0.45
(x.128))) (Kool ct 2018)
6.25
1,79
0,05
10.62
2.40
0.14
16.23
3.72
0.34
(s.M (Xin al., 2021a)
6.14
0.00
0.03
10.48
0.96
0.09
13.99
2.17
0.32
POMO (s.8 (Kowo
2020)
6.14
0.00
0.01
10.42
0.35
0.01
15.73
0.43
0.01
NLNS'G 1280) (Hottong & Tierney 2019)
6.19
0.81
1,00
10.54
1.54
1.63
16.00
2.24
2.18
LCP (s.1280)
2021)
Leam2OPT' 2000) (da Costa et al., 2021)
6.16
0.37
1,00
10.54
2,66
1.44
16.72
6.40
7,20
(i.0000)
2021)
NeuroRewriter! (Chen & Tian, 2019)
6.16
0.48
0,13
10.51
1.25
0.21
16.10
2.88
0.40
6.21
1.14
0.77
10.69
2.99
11.11
16.28
4.03
79.12
NCE (s p.20)
6.13
40.16
3.99
0.29
20.17
15.81
1,02
90.12
19

---

(i.e., pick two tours Published as a conference paper at ICLR 2023
F ABLATION STUDY
In this section, we provide the results the ablation studies.
F.1 CANDIDATE SET
NCE constructed a search candidate set. mitigate the prediction error fo(.) finding the argmax of (41, d2 b1, b2), NCE search the top K pairs of (Q1,02) that have the largest y out of all (a1, (2) choices. We measure how the performance changes whenever the size of the candidate set Kehanges. As shown in Table A.8, the size of K increases, the performance tends increase slightly. When K 2 10, the performance of NCE almost converges. Thus, we choose = 10 as the default hyperparameter of NCE.
Table A.8: Effect of number of candidate
5
7
10
20
30
N.
time
time
time
time
time
(30,3,2)
2.47
0.26
2.44
0,30
2.44
0.34
2.43
0.38
2,43
0.43
2.43
0.48
2.43
0.63
2.43
0.81
(30,3.3)
1.87
0.27
188
0.31
184
0.35
1.84
0.41
0.48
1.83
0.55
1.83
0.79
1.83
1.04
(30.3,5)
1,50
0.50
1.47
0.61
1.47
0.66
1.46
0.71
1.46
0.83
1.46
0.91
1.47
1.27
1.46
1.54
(50,3,3)
2.23
0.58
2.20
0.80
2.19
0.93
2.18
1.13
2.19
1.26
2.18
1.51
2.19
2.17
2.18
2,70
(50,3,5)
1.67
0.86
1.63
1.12
1.62
1.34
1.61
1.56
1.61
1.81
1.61
2.17
1.61
3.14
1.61
4.07
(50.3.7)
1.49
1.05
1.47
1.31
1.47
1.59
1.46
1.93
1.46
2.18
1.46
2.59
1.46
3.79
1.46
4.98
F.2 INTRA-SOLVER
NCE repeatedly applies the inter- and intra-operation. In this view, the choice of the intra-operation may affect the performance of NCE. In this subsection, we measured the performance of NCE according to intra-operation. We compare the results of NCE that uses Elkai, OR-tools, and 2-opt as the intra-operator. To solve TSP the task intra-operator has to solve Elkai, OR-tools, and 2-opt show the best, second best, and third best performances. shown Table A.9, the performances of NCE are almost identical to the selection of an intra-operator. We validate that the effect of the intra-operation choice negligible to performance.
Table A.9: Effect of Intra TSP solver
N,,NN
(30,3,2)
(30,3,3)
(30,3,5)
(50,3,3)
(50,3,5)
(50,3,7)
Intra solver
cost
time
cost
time
cost
time
cost
time
cost
time
cost
time
2-opt
2,46
0.23
0.33
1.47
0.53
2.22
0.72
1.62
1.24
1.46
1.58
OR-tools
2.44
1.04
1.83
1.08
1.47
1.06
2.20
3.31
1.61
2.72
1.46
2.72
Elkai
2.43
0.41
1.83
0.55
1.46
0.69
2.18
1.55
1.61
2.17
1.46
2.13
F.3 SELECTING TWO VEHICLES
NCE chooses two tours for improvement during the iterative process. To understand the effect of the tour selection strategy, we measure the performance NCE according to tour selection. We compare NCE results in max-min selection case and random selection randomly). As shown Table A.10, the performances of NCE are almost identical to the tour selection strategy. Therefore, validate that the effect of the tour selection strategy is negligible.
20

---

Published as a conference paper at ICLR 2023
Table A.10: Effect of selecting two vehicles
No.Na.N
(30,3,2)
(30,3,3)
(30,3,5)
(50,3,3)
(50,3,5)
(50,3,7)
cost
time
cost
time
cost
time
time
time
cost
time
Random
2.43
0.42
1.84
0.61
1.48
0.94
2.18
1.43
1.62
2.39
1.47
2.62
Max-Min
2.43
0.41
1.83
0.55
1.46
0.69
2.18
1.55
2.17
1.46
2.13
F.4 PERTURBATION
NCE employs perturbation increase performance. Perturbation is commonly used strategy for enhancing the performance meta-heuristics (Polat et al., 2015). It is done by randomly perturbing the solution and solving the problem with the perturbed solutions. This technique is beneficial to escape from the local optima. As described Algorithm 1, when falling into the local optima, NCE randomly selects two tours and performs a random exchange. We compare the performance of NCE with different perturbations. As shown in Table A.1I, the performance of NCE increases and converges as the number of perturbations p increases. When p 5, the performance of NCE converges. Thus, we choose p 5 as the default hyperparameter of NCE.
Table A.11: Effect of perturbation
P
3
5
7
10
20
Ne. NN,
cost
time
cost
time
cost
time
cost
time
cnst
time
cost
time
cost
time
cost
time
(30,3,2)
2.50
0.12
2.48
0.17
2.46
0.22
2.44
0.27
2.43
0.38
2.43
0.49
2.42
0.69
2.41
1.34
(30.3,3)
1.89
0.16
1.86
0.22
1.84
0.30
1.84
0.35
1.82
1.81
0.81
1.81
1.42
(30.3,5)
1.49
0.29
1.48
0.33
1.48
0.43
1.47
0.50
1.47
0.67
1.46
0.85
1.46
1.25
1.46
2.28
(50,3.3)
2.24
0.49
2.22
2.19
2.17
2.16
2.61
2.14
(50,3,5)
1.66
0,52
1.64
0.77
1.63
0.94
1.62
1.24
1.61
1.97
1.61
2.59
1.60
3.61
1.59
6.53
(50,3.7)
1.48
L.04
1.47
1.43
1.47
1.46
2.95
1.46
3.77
1.45
6.44
21

---

Published as a conference paper at ICLR 2023
G TRAINING DETAIL
Dataset preparation. To train the cost-decrement prediction model fo(-), we generate 50,000 random FMDVRP instances. The random instance is generated by first sampling the number of cus- tomer Ne and depots Na from (10, 100) and ((2 and N, = 2 respectively, and then sampling the 2D coordinates of the cities from (((0,)) 1). As we set N,, 2, we generate two tours by apply- ing the initial solution construction heuristics explained in Section 3.1. From тI, 72, we compute the best true cost-decrements of all feasible (a), a2) prepare the training dataset. We generated 47,856,986 training samples from the 50,000 instances.
Hyperparameters. fo(.) is parametrized via the GNN which employs five layers of the attentive embedding layer. We employ 4 layered MLPs to parameterize Φe, Pw: On and des whose hidden dimensions and activation units are 64 and Mish (Misra, 2019). [o(.) is trained to minimize the Huber loss for three epochs via AdamW (Loshchilov & Hutter, 2017) whose learning rate is fixed as 5 10-1
Computing resources. We run all experiments on the server equipped with AMD Threadripper 2990WX CPU and Nvidia RTX 3090 GPU. We use single CPU core to evaluate all algorithms.
22

---

Published as a conference paper at ICLR 2023
H EVALUATION OF THE COST DECREMENT MODEL
In this section, we evaluate the prediction accuracy of fo(-). To evaluate fo(.), we randomly generate 1,000 FMDVRP instances by sampling Nc (110, 100) and ND U(2 9), and (r,y) (0, 1)². From the instances, we measure the ratio of existence of the argmax (4), a2) pair the search candidate find the argmax pair with at least 0.9 probability. We also provide the results of the cost-decrement predictions and its corresponding cost. As shown in Fig. A.I, fo(-) predicts the general tendency well.
whose size is K. As shown Table A.12, when K 10. NCE can
Table A.12: fo(-) prediction performance test
K
5
10
20
argmax ratio (%)
42.9
71.3
78.6
90.9
97.4
Prediteed cost-leremen
deaemeent
0..35
0.25
0.20
0.15
0.05
0.00
0.05
0.10
0.15
0.20
0.25
0:30
0.35
0.00
0.05
0.10
0.15
Tue cest-decrement
True cast decrement
Predicted cnst-deceemeet
oust-occeemntt
0.20
0.35
0.30
0.15
0.30
0.20
Tue cost-decrement
True cost-decrwmert
Figure A.1: Predicted cost-decrements vs. true cost-decrements
23

---

Published as a conference paper at ICLR 2023
I COMPARISON WITH FULL SEARCH
To verify whether NCE successfully amotrizes CE, we evaluate CE and NCE(K=10, p=0) on FMDVRP. For the testing instances, we randomly generate 100 instances for each N, {20, 30, 40, 50, 60, 70, 80, 90, 100} with the fixed Na = and N,, 3. As shown in Table A.13, NCE shows nearly identical performances with CE, but with significantly faster computation speed than CE as shown in Fig. A.2. We also test the mTSP and CVRP cases as shown in Table A.14.
Table A.13: FMDVRP performance comparison of CE and NCE(K=10, y=0)
Na .No
(3.3)
Ne
20
30
40
50
60
70
80
90
100
CE
1.651
1.893
2,088
2.257
2.384
2.531
2.695
2.811
2.929
NCE
1.651
1.891
2,088
2.262
2.390
2.530
2.697
2.806
2.934
Computation time comparison
NCE
Computation time: log stale
109
10-1
60
90
100
Number customer
Figure A.2: Computation speed comparison
Table A.14: mTSP, CVRP performance comparison CE and NCE
VRP instance
mrTSP50.N,
nITS1100.M
mTTSP20.N,=I1
CVRP20
CVRP50
CVRP100
cost
time
time
COST
time
cost
time
time
cost
time
CE
2,02
11.35
1.97
87.28
2.00
414.9
6.21
0.96
10.91
11.38
16.23
80.23
NCR
2.02
2.48
1.97
13.00
2.00
84,28
6.21
0.57
10.90
2.93
16.23
14.08
24

---

Published as a conference paper at ICLR 2023
J EXAMPLE SOLUTIONS
This section provides the routing examples. Fig. A.3 shows the solution of Rat99-2 computed by LKH-3 and NCE. Figs, A.4 and A.5 shows the solution of FMDVRP and MDVRP instance com- puted by OR-Tools and NCE.
NCE
LKH-3
200
200
100
100
0-
100
Figure A.3: Rat99-2 solutions computed by NCE and LKH-3
NCE FMDVRP
OR-tools FMDVRP
1.0
1.0
0.8
0.8
0.6
D3
0.6
D1
0.4
0.4
0.2
0.2
0.0
0.0
0.0
0.2
0.4
0.6
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure A.4: FMDVRP solutions computed by NCE and OR-tools
25

---

Published as a conference paper at ICLR 2023
NCE MDVRP
OR-tools MDVRP
1.0
1.0
0.8
24
24
0.6
0.6
D1
0.4
0.2
0.2
0.0
0.0
0.0
0.2
0.4
0.6
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Figure A.5: MDVRP solutions computed by NCE and OR-tools
26

---

Published as a conference paper at ICLR 2023
K CASE STUDY: PLANNING PATH FOR STERILIZING ROBOTS
We applied the trained NCE to solve a real-world application, the task of deriving the cooperative path for multiple sterilizing robots to sterilize the open space of building in the minimum time. Here, the task nodes correspond to the spatial grids composing the entire building floor area, as shown in Fig. A.6. It consists of a total of 500 grids, of which 25 are obstacle areas (gray grids) that a robot cannot move into, and 99 are contaminated areas (orange grids) a robots need to sterilize. We assume the traveling time between the two adjacent grids is the service time for the general area (green grids) is I, and 2 for the contaminated areas. The upper left corner is the starting point. We formulate finding the cooperative paths for multiple robots to minimize the operation time as the min-max mTSP problem.
Fig. A.7 shows the path derived from NCE when there are robots, and Table A. shows the time and objective value of solving the problem for each algorithm. The results show that the NCE algorithm trained using a synthetic dataset can produce an efficient cooperative path for multiple robots without retraining fine-tuning NCE reduces more than 10% of the makespan compared to Google OR-tool and 20% to Greedy+TSP when the number of robots is 5.
Note that the distribution of tasks is far from uniform distribution; each grid is clustered, and each cluster is separated due to the unique floor plan of a building. Thus, the experiment results verify the generalization capability of NCE problem instances generated from a different distribution.
JARCE
020
43383
4.00
010
171
Figure A.6: Grid representation for the open space of the target building
Figure A.7: NCE planned trajectories of the robots under different number of robots
Table A.15: Case study results
No (-+)
2 Gap
J
Method
Cost
Cost
Time
Cost
Time
Cod
Time
Cost
TTme
Gready
1122
6.45
0.18
631
19.06
0.21
458
25.48
01.4
362
24.83
0.28
306
34.90
0.29
Greedy TSP
591
14.33
432
4.51
OR-icols
1.14
8.11
1634.6
383
4.93
1554.
306
5.52
2052.5
1043.8
NCF
0.00
365
383.8
233.2
27

---

Published as a conference paper at ICLR 2023
L BALANCE BETWEEN PERFORMANCE AND COMPUTATION TIME
Because NCE an improvement heuristic, the more computation time used, the better outcome will be produced. Thus, we investigate how the performance varies with the allowed computation time. We sampled 100 instances of FMDVRP (No. Na. No (660, 5, 5) and computed the average cost and computation time of NCE and baselines on these problem instances.
Fig. A.8 depicts the relationships between "Run time (computational cost) vs. Cost curve" in the form of Pareto curve for the case of FMDVRP (Ne: Na, =600 5, 5). The result shows how the performance of NCE improves with more computation time, and this trend is always superior to another baseline.
26
Greedy Greedy+
Cost
2.0
ORTools
CE
NCE
1092
12a
Run time
Figure A.8: Performance vs Computation time curve
28

---

Published as a conference paper at ICLR 2023
M GENERALIZATION TO DIFFERENT DISTRIBUTION
We investigate the generalization capability of NCE to the problem instances generated from dif- ferent distributions. We have employed the NCE trained by FMDVRP random instances to the problems generated by the different distributions introduced in (Bi et al., 2022). We used cluster, expansion, explosion, grid, implosion, and mixed distribution as unseen distributions for testing. We followed the definition in the (Bossek et al., 2019; Jiang et al., 2022; Bi et al., 2022), and the data were taken from the (Bi et al., 2022).
Table A.16 summarizes the experiment result. As in the case of uniform distribution, NCE shows leading performance while being faster than OR-Tools and CE. Note that we did not retrain our NCE algorithm but just employed the already trained existing NCE algorithm to new distribution tasks. From the results, we can conclude that the learned fe is generalizable to the different distributions other than the uniform. It again highlights the effectiveness of learning fundamental operators when solving the VRP families.
Table A.16: Results from various distributions
No. Na. N,(+)
FMDVRP (46,5,5)
Distribution
Cluster
Expansion
Explosion Gap(%)
Method
Cost
Gap(%)
Time(sec.)
Cost
Gap(%))
Time(sec.)
Cost
Time(sec.)
OR-tools
0.92
4.55
1.92
1.25
6.90
1.75
1.33
9.92
1.75
Greedy
1.32
50.00
0.01
1.94
67.24
0.01
1.96
61.98
0.01
Greedy TSP
1.25
42.05
0.02
1.82
56.90
0.02
1.86
53.72
0.02
CB
0.88
0.00
5.82
1.16
0.00
6.50
1.39
0.00
6.39
NCE
0.88
0.00
1.51
1.16
1.39
0.00
1.64
Distribution
Grid
Implosion Gap(%))
Mixed Gap(%)
Method
Cost
Gap(%)
Time(sec.)
Cost
Time(sec.)
Cost
Time(sec.)
OR-tonls
1.51
7.86
1.79
1.52
1.79
1.36
7.09
1.91
Greedy
2.27
62.14
0.01
2.20
58.27
0.01
2.06
62.20
0.01
Greedy TSP
2.16
54.29
0.02
2.10
51.08
0.02
53.54
0.02
CE
1.41
0.71
6.07
1.39
0.00
6.34
3.03
0.00
7.41
NCE
1.40
0.00
1.77
1.39
0.00
1.84
1.27
0.00
1.90
No. N.. N.(++
FMDVRP (94.7.7)
Distribution Method
Cluster Gap(%)
Expansion
Explosion Gap(%)
Cost
Time(sec.)
Cost
Gap(%))
Time(sec.)
Cost
Time(sec.)
OR-tonls
0.91
5.81
24.86
1.16
7.41
23.37
1.21
10.00
24.25
Greedy
1.41
63.95
0.04
1.92
77.78
0.04
1.97
79.09
0.04
Greedy TSP
1.35
56.98
0.08
1.81
67.59
0.07
1.84
67.27
0.06
CE
0.86
0.00
105.66
1.08
0.00
104.06
1.10
0.00
105.82
NCE
0.86
0.00
9.11
1.08
0.00
8.60
1.10
0.00
9.70
Distribution
Grid
Implosion Gap(%)
Mixed Gap(%)
Method
Cost
Gap(%)
Time(sec.)
Cost
Time(sec.)
Cost
Time(sec.)
OR-tools
1.50
9.49
25.14
1.49
11.19
24.13
1.37
7.87
27.94
Greedy
2.38
73.72
2.35
75.37
0.04
2.26
77.95
0.04
Greedy + TSP
2.24
63.50
0.06
2.23
66.42
0.06
69.29
0.07
1.37
0.00
98.27
1.34
0.00
98.55
1.27
0.00
148.73
NCE
1.37
0.00
9.24
1.34
0.00
9.49
1.27
0.00
10.11
29


Reviews:
[{"review_id": "xuv95bfYmcM", "reviewer": "Reviewer_5SXq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "Authors propose a method of accelerating cross exchange (CE) heuristic by approximating the associated \"value\" function with a neural network. Authors adapt standard GNN architectures to approximate the value function. The method applies to a general class of min-max flexibile multi-depot vehicle routing planning (FMDVRP) problems. The proposed method is evaluated on several classes of FMDVRP problems, outperforming strong neural and non-neural baselines, either in solution quality or in computation.\n\n", "summary_of_the_review": "Generic, principled approach that delivers good advantage over strong baselines on synthetic experiments. ", "strength_and_weaknesses": "Strengths:\n\nAuthors demonstrate a significant benefit against strong neural & non-neural baselines across several classes of VRPs. The consistency of empirical benefit is quite impressive. Authors also provide a good breadth of ablation studies to justify most components of the proposed method.\n\nAuthors build upon well-established methodology from GNN literature, making the method principled and also opening up future adoption of innovations on GNNs.\n\nAuthors make a novel connection between a well-established meta-heuristic (CE) and neural combinatorial optimization. The idea of connection (estimating the value function of the heuristic) is interesting on its own. \n\nWeakness:\n\nNCE is only evaluated on a single configuration in Table 1, 2, 3, 4, 5. Since NCE is much more expensive than Greedy/Greedy+TSP, it would be interesting to see the entire compute cost vs. gap curve for both these baselines and the proposed NCE method. \n\nEvaluation is only on synthetic datasets, which limits our understanding on how the method would perform in real-world problems.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "xQhsj4pxST7", "reviewer": "Reviewer_vbx7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper proposed a new learning-based heuristic, named NeuroCROSS, to solve several routing problems. Unlike the previously learned intra-operations like 2-opt and swap, the proposed NeuroCROSS is an inter-operation between two routes, which requires different learning task formulation and neural network design. The proposed method utilizes a supervised learning formulation to predict the best cost-decrement based on two starting nodes and thus reduce the complexity. Several numerical experiments are conducted, and the proposed method outperforms meta-heuristic baselines and neural baselines.  \n", "summary_of_the_review": "This paper improves the complexity of a fundamental CE operation by using supervised learning to predict the cost decrement. The heuristic solvers can utilize the proposed NeuroCROSS to reduce time consumption. This work is not bad, but the novelty is limited, making it not reach the standard of a top venue. Furthermore, the proposed method is a little too heuristic and the experiments also need to be enhanced.", "strength_and_weaknesses": "Strength:\n- The proposed NeuroCROSS is reasonable to reduce the complexity of CE operation.\n- The experimental results show the proposed method has favorable performance on both medium-sized and large-sized instances and can be generalized to similar problems.\n\nWeaknesses:\n\n- There has been many works trying to learn heurisitcs (using reinforcement learning or supervised learning) for combinatorial optimization. This work is just another piece of standard implemention, using supervised learning. Indeed I did not find any new insight. \n\n- The design to search two starting nodes by prediction is too heuristic. There are four nodes to search in the CE operation, but the reason why to select the two starting nodes for prediction is not well-explained. \n\n- The generalization performance on different instance-generation distributions is not validated in the paper. The customer nodes of all the training and testing instances are generated by uniform distribution. The authors should verify the generalization performance on other distributions such as explosion, implosion, and so on [1].\n\n[1] Jiang Y, Wu Y, Cao Z, et al. Learning to Solve Routing Problems via Distributionally Robust Optimization[C]. 36th AAAI Conference on Artificial Intelligence (AAAI), Virtual Event, 2022, 9786--9794.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "pJKSNK98Xt", "reviewer": "Reviewer_LBRJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper addresses the problem of vehicle routing, esp.\nlearning local search neighborhoods. The authors investigate\nesp. the cross operator that swaps two subsequences between\ntwo tours. The authors propose a hybrid neighborhood that\nuses a model that given two tours predicts and two candidate\nstarting points of the two segments predicts the cost savings,\nand then searches through all possible end points to find good\ncrossings. In experiments they compare their method against\nseveral baselines from operations research and machine learning\nacross different variants of the VRP problem.\n\n", "summary_of_the_review": "I see two potential issues:\nw1. results are hard to compare due to two objectives (cost & runtime)\n\n  For mTSPs (tab. 4) baseline DAN is way faster than the proposed method.\n  To compare just the cost for different runtimes, is not so meaningful.\n  Cannot DAN also make good use of the remaining time, with random\n  samplings (as done in table 5 for baseline HM) or with post-processing\n  of the solutions with a heuristic local seach?\n\nw2. focus only on min-max / makespan problems, without results\n  for more intensily researched vanilla CVRPs. \n\n  Also covering the less researched problems is good, of course.\n  But cannot you also compare your method on vanilla CVRPs where\n  you would have more learned local search baselines and other\n  ML baselines? -- If not, is there anything special about the min-max\n  VRP problems that your method is designed to model? \n  \n", "strength_and_weaknesses": "s1. very simple idea.\ns2. learnable in a supervised way.\ns3. applicable to different problem variants.\n\nw1. results are hard to compare due to two objectives (cost & runtime)\nw2. focus only on min-max / makespan problems, without results\n  for more intensily researched vanilla CVRPs. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster