Learning a Transferable Scheduling Policy for Various Vehicle Routing Problems based on Graph-centric Representation Learning
Authors: Inwook Kim
Jinkyoo Park
Venue:  (2021)
Keywords: Vehicle Routing Problem
Multiple Traveling Salesmen Problem
Capacitated Vehicle Routing Problem
Reinforcement Learning
Graph Neural Network

Abstract: Reinforcement learning has been used to learn to solve various routing problems. however, most of the algorithm is restricted to finding an optimal routing strategy for only a single vehicle. In addition, the trained policy under a specific target routing problem is not able to solve different types of routing problems with different objectives and constraints. This paper proposes an reinforcement learning approach to solve the min-max capacitated multi vehicle routing problem (mCVRP), the problem seeks to minimize the total completion time for multiple vehicles whose one-time traveling distance is constrained by their fuel levels to serve the geographically distributed customer nodes. The method represents the relationships among vehicles, customers, and fuel stations using relationship-specific graphs to consider their topological relationships and employ graph neural network (GNN) to extract the graph's embedding to be used to make a routing action. We train the proposed model using the random mCVRP instance with different numbers of vehicles, customers, and refueling stations. We then validate that the trained policy solve not only new mCVRP problems with different complexity (weak transferability but also different routing problems (CVRP, mTSP, TSP) with different objectives and constraints (storing transferability). 

Under review as a conference paper at ICLR 2021
LEARNING A TRANSFERABLE SCHEDULING POLICY FOR VARIOUS VEHICLE ROUTING PROBLEMS BASED ON GRAPH-CENTRIC REPRESENTATION LEARNING
Anonymous authors Paper under double-biee blind review
ABSTRACT
Reinforcement learning has been used to learn to solve various routing problems. however, most of the algorithm is restricted to finding optimal routing strategy for only single vehicle. addition, the trained policy under a specific target rout- ing problem is not able to solve different types of routing problems with different objectives and constraints. This paper proposes an reinforcement learning approach solve the min-max capacitated multi vehicle routing problem (mCVRP), the problem seeks to minimize the total completion time for multiple vehicles whose one-time traveling distance is constrained by their fuel levels serve the geograph- ically distributed customer nodes. The method represents the relationships among vehicles, customers, and fuel stations using relationship-specife graphs to consider their topological relationships and employ graph neural network (GNN) to extract the graph's embedding to be used to make routing action. We train the proposed model using the random mCVRP instance with different numbers of vehicles, customers, and refueling stations. We then validate that the trained policy solve not only new mCVRP problems with different complexity (weak transfcrability but also different routing problems (CVRP, mTSP, TSP) with different objectives and constraints (storing transferability).
INTRODUCTION
The Vehicle Routing Problem (VRP), a well-known NP-hard problem, has been enormously studied since it appeared by Dantzig & Ramser (1959). There have been numerous attempts to compute the exact (optimal) or approximate solutions for various types of vehicle routing problems by using mixed integer linear programming (MILP), which uses mostly branch-and-price algorithm appeared in Desrochers et al. 1992) or a column generation method (Chabrier 2006), or heuristics ((Cordeau let al. | Clarke & Wright [9644] Gillett & Miller 1974; Gendreau et al. [9944)) However, these approaches typically require huge computational time to find the near optimum solution. For more information for VRP, good survey papers (Cordeau et al. 2002 Toth & Vigo 2002).
There have been attempts to solve such vehicle routing problems using learning based approaches. These approaches can be categorized into supervised-learning based approaches and reinforcement- learning based approaches (Bengio et al. 22020); supervised learning approaches try to map target VRP with solution or try solve sub-problems appears during optimization procedure, while reinforcement learning (RL) approaches seek to learn to solve routing problems without supervision (i.e, solution) but using only repeated trials and the associated reward signal. Furthermore, the approachs can be further categorized into improvement heuristics and construction heuristics (Mazyavkina al., 2020);; improvement heuristics learn to modify the current solution for better solution, while construction heuristics learn to construct solution in sequential decision making framework. The current study focuses on the RL-based construction heuristic for solving various routing problems.
Various RL-based solution construction approaches have been employed to solve the traveling salesman problem (TSP) (Bello et al.) 2016; Khalil et al.) 2017, Nazari et al. 2018 Kool al. 2018) or the capacitated vehicle routing problem (CVRP) (Nazari et al. 2018 Kool et al. 2018). (Bello al. 2016 Nazari et al. 2018 Kool al. 2018) has used the encoder-decoder structure

---

Under review as a conference paper at ICLR 2021
sequentially generate routing schedules, and (Khalil al. 2017) uses graph based embedding to determine the next assigmment action. Although these approaches have shown the potential that the RL based approaches can learn to solve some types of routing problems, these approaches have the major two limitations: (1) only focus on routing a single vehicle over cities for minimizing the total traveling distance (i.e., min-sum problem) and (2) the trained policy for a specific routing problem cannot be used for solving other routing problems with different objective and constraints (they show that trained policy can be used to solve the same type of the routing problems with different problem sizes).
In this study, We proposed the Graph-centric RL-based Transferable Scheduler (GRLTS) for various vehicle routing problems. GRLTS is composed of graph- representation learning and RL- based scheduling policy learning. GRLTS is mainly designed to solve min-max capacititated multi vehicle routing problems (mCVRP); the problem seeks to minimize the total completion time for multiple vehicles whose one-time traveling distance constrained by their fuel levels to serve the geographically distributed customer nodes. The method represents the relationships among vehicles, customers, and fuel stations using relationship-speetie relationships and employ graph neural network (GNN) extract the graph's 's embedding to be used to make a routing action. To effectively train the policy for minimizing the total completion time while satisfying the fuel constraints, representation learning for graph and the decision making policy are trained in an end-to-end fashion in an MARL framework. In addition, effectively explore the joint combinatorial action space, we employ curriculum learning while controlling the difficulty (complexity) of a target problem.
graphs to consider their topological
the specially designed reward signal in RL framework. The
The proposed GRLTS resolves the two issues raised in other RL-based routing algorithms:
GRLTS learns to coordinate multiple vehicles to minimize the total completion time (makespan). It can resolve the first issue of other RL-based routing algorithms and can be used to solve practical routing problems of scheduling multiple vehicles simultaneously. (Kang et al. 2019) also employed the graph based embedding (random graph embedding) to solve identical parallel machine scheduling problem, the problem seeking to minimize the makespan by scheduling approach is more general in that it can consider capacity
multiple machines. However, constraint and more fast and scalable node embedding strategies.
GRLTS transfers the trained scheduling policy with random mCVRP instances to be used for solving not only new mCVRP problems with different complexity but also different routing problems (CVRP, mTSP, TSP) with different objectives and constraints.
2 FORMULATION
2.1 MIN-MAX SOLUTION FOR MCVRP
We define the set of vehicles Vy = 1,.., Nv. the set of customers = 1,.., Nc. and the set of refueling stations Vn = I,... NR. where NA, NN. and NR are the numbers of vehicles, customers, and refueling stations, respectively. The objective of min-max mCVRP is minimizing the makespan that is the longest distance among all vehicle's s traveling distance, i.c., min maxeev L; with L, being the traveling distance of vehicle i, while each vehicle's ' one-time traveling distance is constrained by its remaining fuel. The detailed mathematical formulation using mixed integer linear programming (MILP) is provided in Appendix. Figure (I) (left) shows snapshot of mCVRP state and Figure (1) (right) represents a feasible solution of the mCVRP.
2.2 DEC-MDP FORMULATION FOR MCVRP
We seek sequentially construct an optimum solution. Thus, we frame the solution construction procedure as decentralized Markov decision problem (Dec-MDP) as follows.
2.2.1 STATE
We define the vehicle state s;, Vu E Vy, the customer state sf, Vc E Vc, and the refueling station state s;, Vr E Vn as follows:
2

---

Under review as a conference paper at ICLR 2021
C (xt Je .E
of
MOVSP
An example of mCVRP. (Left) a snapshot of environment state at time f. The circular range of each vehicle indicates the possible moving range with the current fuel level. (Right) feasible solution of the environment example.
Figure I:
State of vehicle v. s/ (27 ft' ..)). zi the allocated node that vehicle e to visit; f is the current fuel level; and of is the number of customers served by the vehicle v so far.
State of a customer c, o = (x², v²). ). xf is the location of customer node e (static). Visit indicator
vf E {0, 1} becomes if the customer e visited and otherwise.
State of a refueling station of x². x² is the location of the refueling station (static).
The global state S, then becomes S, ((5)) (5)) (5))
2.2.2 ACTIONS & STATE TRANSITION
Action a. for vehicle at time is indicating node to be visited by vehicle at time + 1, that is, O. = #i+1 E (Vo VR.. Therefore, the next state of vehicle becomes 8 = (2T+1) fi+1 lit1) where f and 1.41 determined deterministically by action Of follows:
(F', (sv - d(z;,a)),
if o E VR otherwise. if af e Vn otherwise.
Fuel capacity update: fi+1
( q
Customer visit number update: F4t1
oh
+
2.2.3 REWARDS
The goal of mCVRP is to force all agents to coordinate to finish the distributed tasks quickly while satisfying the fuel constraints. achieve this global goal a distributed manner, we use the specially designed independent reward for each agent as:
To encourage vehicles to visit the customer nodes faster, in turn, minimizing makespan, define customer visit reward yh misit of This reward is provided when agent visits a customer; the more customer nodes vehicle agent n visits, the greater reward it can earn.
visiting reward:
Refueling reward: To induce strategic refueling, we introduce refuel reward ree = o x (F""-()(("-1))" We define the refuel reward as an opportunity cost. That is, vehicles with sufficient fuel are not necessary to refuel (small reward). In contrast, refueling vehicles with lack of fuel worth as much as visiting customers. this study, we set F 10 (which the equivalent to the total traveling distance that vehicle can travel with the fuel tank fully loaded) and a 2.
2.3 RELATIONSHIPS WITH OTHER CLASS OF VRPS
mCVRP, the target problem of this study, has three key properties: 1) the problem seeks to minimize the total completion time of vehicles by forcing all vehicles to coordinate (in distributed manner), 2) the problem employs fuel capacity constraints requiring the vehicles to visit the refueling stations strategically, 3) the problem considers multiple refueling depots (revisit allowed).
3

---

Under review as a conference paper at ICLR 2021
Belueiiggnsee mondl emiberlcing
If hoas
Va: RefuelingNod Node Ve Customernodes Wehidle nodes
S 9t
Kistomet mode ambeddiee
(N AC.... Mid
x(oEl)) - Eotato (XC6)))
Vehdlenok embeocing
hope
Decision Making & State Update
Figure 2: Sequential decision- framework with trained GRLTS.
If some of these requirements relaxed, min-max mCVRP can be degenerated into simpler conventional routing problems:
TSP is the problem where single vehicle is operated to serve every customer while minimizing the total traveling distance. The agent needs or needs not come back to the depot. This problem does not have capacity constraints.
CVRP constriied TSP) is the problem where single vehicle is operated to every customer while minimizing the total traveling distance and satisfying the fuel constraint. The vehicles need to comeback depot charge.
mTSP (multi-agent TSP) is the problem where multiple vehicles should serve all the customers as quickly as possible. This problem does not have capacity constraints.
mCVRP (multi-agent, capacity-constraine TSP) is our target problem having the properties of both mTSP and CVRP. Additionally, we add more than one refueling depot.
The mathematical formulations for these problems are provided Appendix. We train the policy using random mCVRP instances with varying numbers of agents and customers and employ the trained policy without parameter changes to solve TSP, CVRP and mTSP to test its domain transferability.
METHOD
This section explains how the proposed model, given state partial solution), assigns an idle vehicle to next node to visit under the sequential decision-making framework (see Figure 2p.
3.1 STATE REPRESENTATION USING CELLTTIONSIP-SPECIIEE MULTIPLE GRAPHS
The proposed model represents the global state s; using as a weighted graph G. = G(V, E, w) where == (Vv, Ve, VR), and E. is the set of edges between node i, E V and is weight for edge (i, j) (here, distance d.j). Each node corresponding to vehicle. customer, and refueling station will be initialized with its associated states defined earlier.
Although we can assume that nodes are connected with each other regardless of types and distance, we restrict the edge connection to its neighboring nodes to reduce the computational cost. Specifically, each type of node can define its connectivity range and connect an edge if any node located within its range follows (see Figure 2)
Enj = Vo V.,
d(v,j) S Ry S
Crj = 1 Ve E Va,
d(c, < Re
(2)
Erj = 1 Vr VR,
d(r,j) < RR max F
(3)
4

---

Under review as a conference paper at ICLR 2021
That is, the vehicle node V. connects the edges with nodes that are located within its traveling distance (i.e., the current fuel level ft"). ). In addition, the customer nodes E Ve connects the edges with nodes that are located within the constant range Re. We set R while following typical hyperparameter selection procedure. Finally, the refueling node E Vn connects the edges with nodes within maximum distance that the vehicle with the largest fuel capacity can travel with the full loaded fuel (in this study F 10 for all vehicles). Note that the target node that can be connected each node can be any types of nodes.
3.2 NODE EMBEDDING USING GNN
The proposed model employs Graph neural network (GNN) (Scarselli et al. 20088) to compute the
node embeddings for nodes. The node embedding procedure starts with constructing the graph Ge out of the global state S, ({5] [_m]) [ { ). The method then compute the initial node embeddings h2 and edge embeddings huy for all the nodes and edges of Ge by employing encoder
network. The sequel will explain how the GNN layer update these node and edge embeddings.
3.2.
EDGE UPDATE
The edge feature hi at r iteration is updated using the edge updater function dE as
h OE ( hT h, ViE E
(4)
where n/-1 and h5-1 are node embedding vectors of node and node j at r iteration.
3.2.2 EDGE FEATURE AGGREGATION
The updated edge feature hT can be thought of as an message sent from node j to node i. Node aggregates these messages from its neighboring nodes j E (N)()))Nc((),Na())), where Ny (i) is the neighboring vehicle nodes of node
(h. C... k..))
Σ
asght
aight
aighiy
(5)
(E
jENe
JENz(1
where the attention weight aıj sofmax;(ess) where eij (s; sy: We), scores the significance of node to node i. Note that message aggregation separately conducted for different types of noes and the aggregated messages per type are concatenated.
3.2.3
NODE FEATURE UPDATE
The aggregated edge node embeddings (hi.v- , K..ch h per its neighborhood type are then used to update the node embedding vector h? using node update function Φv as
hT = Φv (h, (hT v he,0, Bicchh,, 1T,,))
(6)
The node embedding procedure repeated (hop) times for all nodes, and final node embeddings h# [ Fi=1 is used to determine the next assignment action of an idle vehicle.
3.3 DECISION MAKING USING NODE EMBEDDING
When an vehicle node reaches the assigned customer node, an event occurs and the vehicle node i computes its node embedding left and selects of its feasible actions, choosing one of unvisited customer nodes refueling nodes around vehicle node i. The probability for agent i to choose node j. af j. computed by the parameterized actor (aa ols';)) as:
cxp(F(h (F :0)
ा (af j(s";
ExENY(OUNn() exp (h.H 1H
where F(N N): ) is the fitness function evaluating the goodness for agent i to choose node j as the next action (i.e., af j).
5

---

Under review as a conference paper at ICLR 2021
3.4 TRAINING GRLTS
We train the proposed model using random mCVRP instances with varying numbers of vehicles, customers. We employ the actor-critic algorithm train the parameters for the GNN, the critic, and the actor (GRLTS).
We first approximate the action-value function Q* a) & Q (s, a: 0) using a neural network with the critic parameter 0. The parameter for the centralized critic is optimized minimize the loss L:
((0) Eo [((" (s, a: 0) y)²
(8)
Eo....'' (h Nor; 0) y)²
where y r 7②) (h (hop is the target value evaluated with the the actor x' raals; o') and the critic Qs a: 0') using the target parameters ø' and 0'. In addition, D is state transition memory.
To train the actor network, we use PPO method (Schulman et 2017) to maximize J(Ø). PPO aims to maximize the clipped surrogate objective function follow:
JLLPP
[[. clip(R.
+ c)
where (Φ)
(.. Taat (a' (=))
We compute the advantage estimator A, by running the policy for T
time steps
A = +0.+1+.... -
6, = rz + 7V (Kittrr V(h,
Mhop Nho 0)
(10)
In addition, equation (9) added by value function error and an entropy bonus for sufficient exploration because critic and actor share parameters as follow:
JLIPP (Ø) E, [] (o) c1 (Vo(s:) - -Vugga)2 (s,
(11)
where Vs(ss) Vh, NooP; from the centralized critic; H/ denotes an entropy bonus; and ei and c2 are hyperparameters.
On updating the centralized critic parameter and the decentralized (but, shared) actor parameter o. we use Monte-Carke simulation. To sequentially update both parameters, we follow an update rule as follow:
g++1 . 1++1 +- arg max E
[JLUPP (0) ei (Vo(s)) - Vinzess 2 + e2 (2.H (((,,
(12)
Algorithm focus on sequence of the parameter update using above equations.
Algorithm Parameter update in decentralized actors with PPO and Monte Carto simulation
1:
for i 1,, N do for Updale ileration = 1, ......,K
2:
do Evaluate policy Te..a in environment for an experienced episode
1,2,..., K
3:
4:
Compute (6) in Equation 9
5:
Compute advantage estimates A,.... År in Equation 10
6:
Optimize surrogate objective in Equation (11) with batch size T
7: fold +- 8, Pold x- followed by (12)
8:
end for
9:
end for
4 EXPERIMENTS
The trained policy is used to solve various types vehicle routing problems, mCVRP, mTSP, CVRP, and TSP without changing the parameters. For each type except mCVRP, types of data

---

Under review as a conference paper at ICLR 2021
sets: random instances with varying numbers of vehicles and customers whose locations are sampled randomly, and (2) benchmark problems obtained from the library (mTSP library, CVRP library, and TSP library).
To validate the proposed GRLTS, we develop mixed integer linear programming (MILP) formulations and compute the solutions using CPLEX 12.9 (all the optimization formulations provided in the Appendix). We also use Google OR- PoR-roolsPPerron & Furnon) as the representative heuristic solvers. For the problems where other deep RL based approaches tried solve (TSP and CVRP), compare the performance of the proposed approach to those of deep RL baselines. All experiments are conducted on Windows 10, Intel(R) Core(TM) 19-9900K CPU 3.6 GHz, and 32GB RAM. GPU acceleration is not used in testing.
4.1 PERFORMANCE COMPARISON OF MCVRPs
Table I: Performance comparison of mCVRPs on random instances
mCVRP25
mCVRP50
mCVRPI00
Method
Ny = 2
No = 3
No = 5
No = 2
No 3
No
5
No = 5
N, 10
2.51
1.60
1.29
4.31
2.71
1.77
1.87
ORT
(4.5)
(16.7)
(45.2)
(12.1)
(19.2)
(51.9)
(00)
(489.2)
3.15
2.0
1.20
3.72
2.65
1.71
2.71
1.88
GRLTS
(0.9)
(1.0)
(1.0)
(4.7)
(4.1)
(3.9)
(11.8)
(11.7)
Gap (%)
25.5
25.0
-7.0
-13.7
-2.2
-3.4
0.5
Table 2: Scalability test of the trained GRLTS with large-scale mCVRPs
mCVRP25-5
mCVRP100-10
mCVRP400-20
mCVRP2500-50
1.2 (0.98)
1.88 (12.1)
4.09 (420.2)
11.71 (3,861.2)
We apply the trained policy (GRLTS) to solve mCVRP with different numbers of vehicles N,, E 2, 5 and the numbers of customers No E 25, 50, 100. The number of refueling stations are set to be 4, and in case of N. = 25, N₂ 50 and N₂ 100. For every combination of N, and N₂, we randomly generate 100 mCVRP instances, each of which has randomly located customer nodes and refueling nodes. The x and y coordinates of each node is randomly sampled from the uniform distributions; U00 1] and y ~ U(0, 1), respectively. We employ GRLTS and ORT to solve the same 100 random mCVRP instances and compute the average makespan and the computational time required to solve the mCVRP instance with the policies. Table compares the average makespan and computational times.
ORT (Google OR-tool) produces the best results for the small-sized problems with reasonable computational time: however, it requires extensive time even fails to compute any feasible solution for the large scale problem (oo means that ORT cannot find a feasible solution). Notably, the GRLTS achieves a better performance than ORT for large-scale problems with significantly shorter computational time.
To validate the scalability of the proposed model, we further conduct test experiments with the four cases: No 25 with N, .N. 100 with N, 10, N. 400 with N, 20, and N. 2, 500 with N, = 50. Table shows how the makespan and the computational time increases with the size of the problem. By comparing the ratio between the number of customers that each vehicle need to serve, (5: 10: 20: 50), and the makespan, (1.20: 1.88: 4.09; 11.71),
roughly confirms that the trained model can perform reasonably well even in large sized problem that have never been experience during the training.
For all different sizes of the mCVRP problem, we also compare the performance of the proposed method with the solution computed by CPLEX solver. Because it typically takes long time to compute the near-optimum solution by CPLEX, we only compare the single mCVRP case. The result provided in the Appendix.
7

---

Under review as a conference paper at ICLR 2021
4.2 PERFORMANCE COMPARISON ON MTSP
We apply the trained network (without parameter changes) to solve mTSP, which seeks to minimize the total completion time of multiple vehicles (minmax mTTP). This problem is a relaxed version of mCVRP in that it does not require the capacity constraints (we maintains the fuel level to be maximum during execution). We solve the randomly generated 100 mTSP instances for every combination of No E 50, 100, 400 and N₂ E 2, 4, 6, 8 (or N₂ E 10, 20, 30, 40). Table 7 compares the average makespan and computational time. The trained model outperforms ORT in the large-size problems (see N. 100 and N. 400 cases in Table 7 in terms of both makespan and the computational time. For large scale problems, GRLTS achieves roughly 28% shorter makespan than ORT on average with significantly reduced computational time (50% reduction).
Table 3: Performance comparison mTSP for random instances
mTSP50
mTSPI00
mTSP400
N₂
4
6
8
2
6
8
10
20
30
40
ORT
3.20
2.21
1,60
1,11
5.13
2.69
2.25
1,71
3.02
2.0
1.91
1.61
(1.3)
(1.2)
(1.2)
(1.2)
(25.4)
(21.1)
(21.5)
(22.1)
(1358.8)
(965.9)
(1115.6)
(1025.7)
3.94
2.83
1.47
0.98
5.13
2.34
2.16
1,71
2.64
2.06
1.34
1.15
(3.1)
(3.2)
(3.0)
(3.0)
(16.3)
(11.2)
(10.9)
(11.1)
(432.6)
(452.1)
(442.1)
(465.7)
Gap (5)
28.1
8.1
-1.7
0.0
-3.00
4.0
0.0
-12.6
-2.88
-28.6
Similarly, for all the sizes of mTSP case, we compare the performance of GRLTS to the solution computed by CPLEX in the Appendix. We also employed the trained model to solve mTSP benchmark problems in MTSPLib I solving MinMax mTSP The performance results on 124 instances (four different number of vehicles per 31 different maps) are provided in Table in Appendix.
4.3 PERFORMANCE COMPARISON ON CVRP (PAYLOAD CAPACITY)
Table 4: Performance comparison on CVRP for random instances
CVRP20
CVRP50
CVRPI00
Methods
Obj.
Gap (%)
Time
Obj.
Gap (%)
Time
Obj.
Gap (%)
Time
L21 (Lu et al.
2019
6.12
12m
10.35
17m
15.57
24m
LKH3
[Helsgaun
2017
6.14
0.33
2h
10.38
0.29
7h
15.64
0.45
13h
TR-Tools
6.46
5.56
2m
11.27
8.89
13m
17.12
9.96
46m
AM
Kool al.
2018
greedy
6.4
4.58
Is
10.61
2.51
16.17
3.85
8s
AM Sampling
6.25
2.12
6m
10.59
2.32
28m
16.12
3.53
2h
Nazari et al.
2018
6.4
4.58
11.15
7.73
16.96
8.93
Chen & 1ian
2019
6.16
0.65
10.51
1.55
16.1
3.40
Random Sweep
7,08
15.69
12.96
25.22
20.33
30.57
Random CW
6.81
11.27
12.25
18.36
18.96
21.77
GRLTS (Ours)
6.97
13.89
2s
12.91
24.73
5s
19.74
26.78
15s
We employ the trained model to solve randomly generated 100 CVRP instances with N, 20, 50. 100 with single capacitated vehicle. All nodes are randomly scattered in the unit square of [0, x (o. 1). To make the trained policy compatible with the CVRP settings, we fix the number of vehicles to be one and use a single refueling node as if it were the depot in CVRP environment. As a result, the single vehicle needs revisit the depot due to payload capacity (which is equivalent to fuel constraint). The payload capacity is set to be 30, 40 and 50 for CVRP20, CVRP50 and CVRP100, respectively. Demand are uniformly sampled from (1,..., 9}. These test cases have been widely used by the studies seeking to develop RL-based solvers for CVRP problems.
Table summaries results for the random CVRP environment. I.21 and LKH3 are well-known best performing heuristic algorithms developed from the OR community, thus can serve as an oracle for comparing the performance. We also consider other RL-based approaches (Kool et al. 2018
www.infoiasi.ro mtsplib
8

---

Under review as a conference paper at ICLR 2021
Nazari et al. 2018 Chen & Tian 2019). In general, our model is not outperforming other RL-based approaches and OR-tool. However, all RL-based approaches, except our model, are trained under the same environment of CVRP cases (the training and test instances are sampled from distribution). However, our model trained with the complete different mCVRP environment and tested with the CVRP environment (strong transferability).
We also employed the trained policy to solve the CVRP benchmark problem instances from CVRPLib (Uchoa et al. 2017). Table [0] Appendix provides all the performance results compared with other RL-baseline models. The results show that our model has better performance than one of the state-of-art RL-based approach (Kool al. 2018).
4.4 PERFORMANCE COMPARISON OF TSP
Table Performance comparison on TSP for random instances
CVRP20
CVRP50
CVRP100
Methods
Obj.
Gap (%)
Time
Obj.
Gap (%)
Time
Obj.
Gap (%)
Time
Concorde
3.84
0.00
Im
5.70
0.00
2m
7.76
0
3m
LKH3
3.84
0.00
18s
5.70
0.00
5m
7.76
0
21m
OR-Tools
3.85
0.26
Os
5.80
1.75
1s
7.99
2.96
3s
AM (greedy)
3.85
0.26
Os
5.80
1.75
2s
8.12
4.64
6s
AM (sampling)
3.84
0.00
5m
5.73
0.53
24m
7.94
2.32
1h
Nearest Insertion
4.33
12.76
1s
6.78
18.95
2s
9.46
21.91
6s
Random Insertion
4.00
4.17
Os
6.13
7.54
1s
8.52
9.79
3s
Farthest Inscrtion
3.93
2.34
1s
6.01
5.44
2s
8.35
7.60
7s
Bello ct al.
2016
3.89
1,30
5.95
4.39
8.3
6.96
Khali al
2017
3.89
1.30
5.99
5.09
8.31
7.09
GRETS (Ours)
3.92
2.08
1s
6.32
10.88
38
8.79
13.27
9s
Lastly, we employ the trained model to solve 100 randomly generated TSP with different number of customers N. 20, 50, 100 and single vehicle. Table shows summarized the results. Although GRLTS is not outperforming other RL-based scheduling methods, it shows the reasonably perfor- mance that is comparable to some of well known heuristic algorithms. Given that the GRLTS trained with mCVRP environment and have never seen TSP instances, this result can validate that GRLTS can be transferred to TSP as well.
We also employed the trained policy to solve the TSP benchmark problem instances fromTSPLib (Reinhelt) 2014). Table M in Appendix provides all the performance results compared with other RL-baseline models. The results show that model has comparable performance with the-state-of- art RL- approaches (GPN (Ma et al. 2019) and S2V-DQN (Khalil et al., 2017)) and heuristic algorithms, especially for large-scale TSP problems.
5 CONCLUSION
We proposed the Graph-centric RL-based Transferable Scheduler for various vehicle routing prob- lems using graph-centric state presentation (GRLTS) that can solve any types of vehicle routing problems such as mCVRP, mTSP. CVRP, and TSP. The transferability is achieved by graph-centric representation learning that can generalize well over various relationships among vehicles, customers, and refuel stations (depot). GRLTR is computationally efficient for solving very large-scale vehicle routing problems with complex constraints, which provides potential that such RI-baased scheduler can be used for large-scale realistic applications in logistics, transportation, and manufacturing.
REFERENCES
Irwan Bello, Hieu Pham, Quoc Le. Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: I. /09940, 2016.

---

Under review as a conference paper at ICLR 2021
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour hororizo.. European Journal of Operational Research, 2020.
Alain Chabrier. Vehicle routing problem with elementary shortest path based column generation. Computers & Operations Research, 33(10):2972-299) 2006.
Xinyun Chen and Yuandong Tian. Learning perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, pp. 6281-6292, 2019.
Geoff Clarke and John W Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 124)):668-51, 1964.
Fran-Francois Cordeau, Michel Gendreau, Gilbert Laporte, Yves Potvin, and Frédéric Semet. A guide to vehicle routing heuristics. Journal of the Operational Research society, 53(5):112522,, 2002.
George B Dantzig and John H Ramser. The truck dispatching problem. Management science, 6(1): 80-91, 1959.
Martin Desrochers, Jacques Desrosiers, and Marius Solomon. A new optimization algorithm for the vehicle routing problem with time windows. Operations research, 40(2):342-354, 1992.
Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on real-world graphs in linear time. arXiv preprint arXiv:2006.03775 03755, 2020.
Michel Gendreau, Alain Hertz, and Gilbert Laporte. A tabu search heuristic for the vehicle routing problem. Management science, 40(10):1276-1290, 1994.
Billy E Gillett and Leland R Miller. A heuristic algorithm for the vehicle-dispatch problem. Opera- tions research, 22(2):340-349, 1974.
Keld Helsgaun. An extension of the dternighan-helseee tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, 2017.
Hyunwook Kang, Aydar Mynbay, James Morrison, and Jinkyoo Park. Learning scalable and
transferable multi--roho//machine sequential assignment planning via graph embedding. arXiv preprint arXiv: /905. /2204, 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348 6358, 2017.
Wouter Kool, Herke Van Hoof, and Max Welling, Attention, learn solve routing problems! arXiv preprint
2018.
Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-basee based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
Qiang Ma, Suwen Ge, Danyang He, Darshan Thaker, and Iddo Drori. Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint 2019.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey, arXiv preprint arXiv:2003.03660 0000000000000, 2020.
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-329, 1960.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pp. 9839-9849, 2018.
Laurent Perron and Vincent Furnon. Or-tools. URL htt.tts//deeeloprss..oo optimm: zation/
10

---

Under review as a conference paper at ICLR 2021
G Reinhelt. {TSPLIB): library of sample instances for the tsp (and related problems) from various sources and of various types. URL: htttp://comopt. ifi. uniheidelberg. delsoftware/SSPLIB95, 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 1707006377 2017.
Paolo Toth and Daniele Vigo. The vehicle routing problem. SIAM, 2002.
Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-35) 2017.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 MILP FORNULATIONS FOR ROUTING PROBLEMS
The MILP formulations for mCVRP, mTSP, and TSP are provided in this section. All problems formulated to find the optimum routes of vehicles to minimize the makespan. For TSP formulation, the makespan minimization is equal total distance minimization due single-vehicle operation. Although mTSP here is same as multi- VRP by its definition, we denote the problem as mTSP because we focus on the makespan minimization problem with multi-vehicle operation.
A.1.1 TSP
A fundamental formulation in the context of routing problems is based on TSP formulation by Miller-Tucker-22 Tucker-Zemlin (MTZ) formulation (Miller al. 1960
minimize
Σ
Σ
dij
iEV JEV
subject to.
Σ Diy =
VjEV
(1)
iEV
Σ Tij = 1,
vi V :i
(2)
jEV
U4 "j + [a Fij
[ 1,
Vi,j V SStart,
(3)
0 S 04 S 1 11,
ViED V uStart, (4)
Fiy {0, 10.
Vi,j V, Vi V uStart.
(5)
U; E Z,
(6)
The routing problem is defined in a graph G(V, E, w) where V, E and w are nodes, edges, and weight (distance d cost c). æiy 1 if the edge between node and node exists, otherwise, Here, corresponding distance of the edge is dyy. Constraint (3,4) with dummy variable is for subtour elimination. As setting d,j- = 0, Vj E uStart, the problem can be arbitrary end assumption.
A.1.2
MTSP
The goal of mTSP is to find the sub-routes of multiple vehicles to minimize the makespan. Thus, decision variables are expanded to
settings, and the objective function is modified from A.I.I to consider the makespan minimization setting (MinMax problem). minimize
Q
subject to.
ΣD
dijTaij S IQ,
Va E A Ai
(1)
NEV
JEV
Σ
Taij 1,
Va E A, E uStarta i j,
(2)
JEV
E
Foij
Vj E Ta ii
(3)
aeA iEG jEG
Σ Taij Σ Paji = 0,
Va E A, EV :i
(4)
IEG
iEG
Uui - Uaj + |V| < -V -1
Va E A, E V vStarta i j.
(5)
5 uai $
1,
Va E A,i E V vStarta.
(6)
Taij E 10,
Va E A, Vi, E V,
(7)
Uui E Z,
Va E A,i E V vStarta.
(8)
Here, we denoted Q as the makespan, which is the longest traveling distance among multiple vehicles. By minimizing this maximum traveling distance, the above formulation minimize the makespan. Therefore, the above formulation is to minimize the makespan. We also allow a vehicle to start a tour any staring node staart, (constraint (2)).
12

---

Under review as a conference paper at ICLR 2021
A.1.3 MCVRP
We extend the above mTSPP formulation in A.1. to to include the fuel constraint (i.e., allowable traveling distance per sub-tour). In this formulation, vehicles can start their tour at an arbitrary location.
minimize
Q
subject to.
ΣΣ
dijuaij SQ²
Va A A:i#1
(1)
NEV JEV
Σ
Jaij 1,
Wa A,i vStarta
(2)
E
E
Toij =
Vj E Taak : i j.
(3)
aEΛ JEG
Σ Jaij Σ Taji = O,
YEE A.EA,EEV. ii
(4)
iEG
IEG
Uai Maj + V Faij S [V 1,
Va E A,J E V
vttarta : j.
(5)
Vai $ |||| 171-1.
Va A,i SSaarta:
(6)
Taij E (0,1},
Va E J, EVV,
(7)
Uai E Z,
Va A,i E eStarta
(8)
fa Far
Va E A, E fuef
(9)
Jat digstasj 2 0,
Va A,Vi,j E fueff
(10)
Saj Soi + dis F1 Nnigh,
Va A, E vTask.
(11)
Constraint (9) indicates that a vehicle can charge fuel as much as the vehicle's maximum fuel capacity Fa- In addition, constraint (10) requires that vehicle must have enough remaining fuel visit refueling node. Constraint (11) indicates that a vehicle cannot consume (travel) more than its fuel capacity. We allow vehicles visit refueling nodes as many times as possible by introducing sufficient number of dummy variables.
A.1.4 CVRP
Similar to the above mCVRP with fuel constraint, we also solve CVRP constrained by payload capacity (not fuel constraint) and with single vehicle (m mm=11 so that |A| = 1). We consider single depot to start mission and unload some burdens. Therefore, fueffuel in the MILP of mCVRP becomes same as vStarta. Fuel consumption as much as distance di₃ between node i and node is equivalent to payload capacity consumption much as demand dy at node j. As result, constraint (9-11) the mCVRP model becomes:
Coi = Ca.
Va A, uStart, Va E A,Vi,j E Task.
(9)
Cag - Cas + dyFais 2 C1 - Tait),
(10)
The constraint (10) in the mCVRP model dropped because payload capacity is independent in returning to the starting depot.
A.2 COMPARISON WITH CPLEX SOLUTIONS
For single mCVRP and mTSP instances, compare the performance of the proposed approach with the exact solution computed by CPLEX. This experiment shows how the solution computed from the proposed method is comparable to the near-optimum solution calculated by the powerful optimization solver. Note that the mCVRP instance for this experiment was generated from the grid environment. The distance between customer nodes are different from the experiments for Table 1.
13

---

Under review as a conference paper at ICLR 2021
A.2.1 MCVRP
Table 6: Performance comparison of mCVRPs on random instances
N: 25
N₂ = 50
N₂ 100
Ny
CPX
ORT
N,
CPX
ORT
N₂
CPX
ORT
RL
20 (oc)
15 (3.9)
20 (0.96)
34 (38.3)
30 (4.8)
27 (510.3)
29(11.9)
14 (oc)
(36.6)
(1.01)
(2.2)
(4.1)
10
20 (12.1)
12 (oc)
(0.98)
14 (1.7)
(3.8)
We apply the already trained model to solve mCVRP with different numbers of vehicles No. E 2,3, 5 and the numbers of customers N₂ E 25, 50, 100. The number of refueling stations are set to be 4, and 10 in case of N₂ 25, N₂ = 50 and N. 100. For all cases, we compute the total completion time and the computational time (the number in the parenthesis) required to construct a scheduling. We set the limit of the computational time to be 18,000 (sec) for all cases. The symbol case where the computational time is reached and the solution at that moment used in the table. The blanks with the hyphen indicate the case where the algorithm could not find any feasible solution.
indicate the
First, CPX (CPLEX) can only solve for mCVRPs with N. = 25; for large scale problems, cannot compute any feasible solution. ORT (Google OR-tool) produces the best results for the small sized problem with reasonable computational time; however, for the large scale problem it requires extensive amount time even fail to compute any feasible solution. Notably, the proposed GRLTS achieves the good performance with the least amount of computational time.
A.2.2 MTSP
For the grid environment, single mTSP instance was generated and used for comparing the performances of GRLTS to CPLEX and ORT.
Table 7: Performance comparison on mTSP for random instances
N₂
19
N₂ = 100
Ng
400
N₂
CPX
ORT
RI.
Ng
CPX
ORT
RL
No
CPX
24
26
32
51
57
57
63
55
2
2
10
(7.9)
(2.1)
(3.0)
(oo)
(32.2)
(15.9)
(1619.8)
(361.2)
13
18
23
54
31
26
41
43
4
(xc)
(1.1)
(3.2)
(oc)
(16.9)
(10.7)
(782.8)
(415.9)
13
13
12
46
25
24
44
28
6
30
(oc)
(1.1)
(3.3)
(oo)
(15.4)
(10.5)
(1192.1)
(452.3)
8
51
19
19
8
40
(6467.3)
(1.6)
(3.4)
(00)
(13.8)
(10.8)
(627.0)
(485.1)
A.3 EXPERIMENT RESULTS ON BENCHMARK PROBLEMS
We apply the trained network to solve benchmark problems for TSP, mTSP and CVRP.
A.3.1 TSP
Table 8 shows results of TSPLib (Reinhelt 2014) with some RI.-based approaches (GPN (Ma et 2019) and S2V-DQN (Khalil et al. 2017) and heuristics. The average performance of the proposed model is not outperforming the state of the art RL approaches. However, we observed that the proposed method is scalable in that the performance on the large-scale problem does not degrade compared to other approaches. We compare the performance by problem instance size (eil51 ~ tsp225 Vs. pr226 pch442). Our model showed 1.1% % reduction in the optimality gap (15.4% - 14.3%). However, the other RL-based approaches show much higher increases in the optimality gap (Drori al. (2020): 3.1 % 10.0%, GPN: 14.1 % 33.1% 1%, Drori al. (2020): 4.7% 10.6%).
14

---

Under review as a conference paper at ICLR 2021
Table 8: Performance comparison on TSP library
RL
Approx
City
Opt.
Ours
Drori et al. 2020
GPN
S2V-DQN
Farthest
2-opt
Nearest
eilS1
426
471
439
485
439
448
452
514
berlin52
7542
8269
7681
8795
7734
8121
7778
8981
st70
675
770
684
701
685
729
701
806
ei176
538
648
555
591
558
583
597
712
pr76
108159
135145
112699
118032
111141
119649
125276
153462
rat99
1211
1368
1268
1472
1250
1319
1351
1566
kreA100
21282
25282
21452
24806
22335
23374
23306
26856
kroB100
22141
25939
22488
24369
22548
24035
23129
29155
kroC100
20749
23644
21427
24780
21468
21818
22313
26327
kroD100
21294
23397
21555
23494
21886
22361
22754
26950
kroE100
22068
26326
22267
23467
22820
23604
25325
27587
rd100
7910
9237
8243
8844
8305
8652
8832
9941
cil101
629
753
650
704
667
687
694
825
lin
14379
17173
14571
15795
14895
15196
16184
20363
pr124
59030
66554
59729
67901
61101
61645
61595
69299
bier127
118282
125233
120672
134089
123371
127795
136058
129346
ch130
6110
6987
6208
6457
6361
6655
6667
7575
pr136
96772
111563
98957
110790
100185
104687
103731
120778
pr144
58537
59197
60492
67211
59836
62059
62385
61651
ch150
6528
7264
6729
7074
6913
6866
7439
8195
1.50
26528
32492
27419
30260
28076
28789
28313
33610
kroB150
26130
32438
27165
29141
26963
28156
28603
32825
u159
42080
51542
43687
52642
45620
46842
42976
53637
rat1
2323
2774
2384
2686
2567
2620
2569
2762
d198
15780
16217
17754
19249
16855
16161
16705
18830
kroA200
29368
34160
30553
34315
30732
31450
32378
3S798
kroB200
29437
35848
30381
33854
31910
31656
32853
36982
ts225
126643
141754
130493
147092
140088
140625
143197
152494
tsp225
3916
4536
4091
4988
4219
4233
4046
4746
pr226
80369
83861
86438
85186
82869
84133
85306
94390
gil262
2378
2889
2523
5554
2539
2638
2630
3218
pr264
49135
51836
$2838
67588
53790
54954
58115
58634
a280
2579
3059
2742
3019
3007
3011
2775
3311
pr299
48191
59257
53371
68011
55413
52110
52058
61252
18n318
42029
49167
45115
47854
45420
45930
45945
54034
rd400
15281
16631
16730
17564
16850
16864
16685
19168
f4417
11861
12768
13300
14684
12535
12589
12879
15288
pr439
107217
124333
126849
137341
122468
122899
111819
131258
pch442
50778
61757
55750
58352
59241
57149
57684
60242
Gap
15.1
4.9
19.0
6.2
8.4
9.1
24.7
A.3.2 MTSP
Table 9 shows results from m TSPLibb D solving MinMax TSP. Our model shows 3% longer results than ORT. However, computational time is, on average, about 30 seconds faster, which about 45%. In addition, we calculate difference of the optimality gap by N, 2, 2,3, 5, 7. Our model shows better performance as N, increases (N, case: 9.8%, No, = 3 case: 8.9%. N, case: 2.8%, N, = case: -7.5%)
wwwwinfoiasi.rom ro/ mtsplib
15

---

Under review as a conference paper at ICLR 2021
Table Performance comparison on mTSP library
ORT
Ours
ORT
Ours
Maps
N₂
MS
Time
MS
Time
gop
Maps
N.
MS
Time
MS
Time
2
223
1.14
281
2.95
26.2
2
12214
15,06
13721
9.41
12.3
el151
159
0.67
244
2.92
53.7
kroB 100
8957
14.81
10197
9:52
13.8
120
165
2.93
37.5
7108
10.31
6271
9.19
-13.3
109
1,03
86
2.67
-26.5
7108
10.24
6119
9.49
-16.2
12453
berlin52
3195
1.35
3452
3.03
8.0
kraC100
8725
12.58
7985
9.48
99.3
2606
2179
-19.6
9.50
-5.2
2440
1.42
2182
2,87
-11.8
7
6154
12.83
5740
9.30
-7.2
288
4,46
361
5.81
25.4
13130
11.27
12815
9.32
-2.5
ct176
227
7.2
kroD100
8889
9,36
9359
9,40
179
4.79
170
5.61
-5.1
6976
9.67
6660
9.34
-4.7
388
3.77
451
4,87
16.2
2
13424
9.02
1361 I
9.53
1
sC70
2.04
282
4,98
-1.2
kroE100
9334
14.61
8929
10.76
4.5
251
2.26
249
4.69
0.8
7599
20.27
6992
10.05
-8.6
251
2.22
253
4.78
0.9
7
8727
17.14
5868
9.42
-18.7
33.1
9.70
pe76
51074
6.25
65567
5,67
28.4
eil101
3
237
10.32
264
9.64
11.3
22,9
9.67
36116
5.85
33082
5,50
-15.2
123
15.29
141
9.63
14.6
709
16.47
756
9.11
6.6
8846
18.50
10220
10.20
15.5
549
13.86
565
9.28
2.9
lin105
7112
16.20
8168
10.30
14.8
463
11.12
373
9.14
24.0
7060
18.79
5487
10.34
28.7
4406
17.94
4520
9.54
2.6
2
31692
14.29
26369
10.96
20.2
100
pr107
-7.0
2435
20.78
2629
9.32
8.0
21455
16,70
20985
10.80
-2.2
2803
17.38
2375
9.38
-18.0
21365
17:45
20620
10.81
-3.6
12647
12.19
L3560
9.49
7.2
35094
18.82
36472
15.02
3.9
9116
14.37
9635
9.49
5.7
27257
16.70
27598
14.75
1.3
kroA100
pr124
8229
13.31
7147
9,24
15.1
7
22725
25.29
21556
14.75
-5.6
22.72
26171
27864
26.35
bicr127
47347
22.61
52749
15.68
11.4
3
19014
56,26
19519
25.87
2.7
2Y560
38.21
30946
15.76
4.7
5
14308
72.44
16719
26.34
16.9
24891
47.49
25074
15.48
0.7
7
14776
67.59
16077
26.03
8.8
3393
31.44
3755
16.85
10.7
2
1285
205.86
1524
43.66
18.6
ch130
1575
39.03
2307
16.69
46.5
1a1195
70R
152.43
638
43.57
10.9
32.88
2077
55.2
631
130.31
495
43.85
-27.5
59999
34.54
59113
18.18
-1.5
2
10416
170.17
9226
45,20
122.9
pr136
40643
14.45
45017
18.25
10.8
d198
9663
71.48
7813
45.36
-23.7
29958
29.59
32858
18.14
9.7
8577
113.45
6086
45.21
40.9
30138
20.66
30222
17.98
0.2
7
8577
115.69
$892
45. 64
-45.6
pr144
31305
36.20
42179
20.72
34.7
kroA200
12253
161.74
13778
46.44
12.4
25262
46.69
28153
20.55
1.4
5
8185
190.01
10770
46.35
31,6
24361
42.25
27168
20.52
11.5
7
6675
186.54
7142
46.36
7.0
3914
43.40
3637
22.75
-7.6
16127
92.48
18758
47.00
16.3
2663
42.67
2870
22.78
7.7
11814
103.17
13199
46.13
11.7
ch150
1915
75.00
1994
22.66
4.1
8525
126.04
10618
46.83
24.6
15326
40,34
16578
22,77
8.2
2
70660
230.60
71594
64.01
1.3
10810
47.01
12600
22.83
16.6
55237
245.30
$2330
63.12
-5.6
kroA150
7323
54.11
8567
23.05
17.0
Lx225
38748
189.31
31318
64.13
-23.7
6290
42.09
7901
22.66
25.6
35460
213.09
2792.1
63.53
27.0
14633
54.68
18342
22.84
25.3
2
2145
277.23
2481
62.39
15.7
10565
36,80
11512
22,91
8.9
1612
145.43
1743
63.56
8.1
kroB150
1sp225
1308
63.83
10.6
8221
31.13
6057
22.92
-35.7
7
1044
209.54
1016
63,80
-2.7
43922
$2.08
51982
23.71
18.3
38752
50.79
48138
23.35
24.5
33006
91.95
43940
23.27
33.1
32245
41624
23.57
29.1
A.3.3
CVRP
Table 10 shows results from CVRPLib (Uchoa et al.) 2017). Those values are the total traveling distance. Although our model is trained to minimize makespan (MinMax), our model shows better performance than AM in the total distance (MinSum).
16

---

Under review as a conference paper at ICLR 2021
Table 10: Performance comparison on CVRP library
Instance
Opt
OR-Tools
AM (N=1280)
AM (N=5000)
Ours
X-n101-k25
27591
29405
39437
37702
39133
X-n106-k14
26362
27343
28320
28473
27940
X-n110-k13
14971
16149
15627
15443
17388
X-n115-k10
12747
13320
13917
13745
19292
X-n120-k6
13332
14242
14056
13937
16589
X-n125-k30
55539
58665
75681
75067
69919
X-n129-k18
28940
31361
30399
30176
36649
X-n134-k13
10916
13275
13795
13619
X-119-k110
13590
15223
14293
14215
16368
X-n143-k7
15700
17470
17414
17397
23548
X-n148-k46
43448
46836
79611
79514
62240
X-n153-k22
21220
22919
38423
37938
33079
X-n157-k13
16876
17309
21702
21330
19702
X-n162-k11
14138
15030
15108
15085
19491
X-n167-k10
20557
22477
22365
22285
25676
X-n172-K51
45607
50505
86186
87809
63191
X-n176-k26
47812
52111
58107
58178
66997
X-1811-233
25569
26321
27828
27520
27220
X-n186-k15
24145
26017
25917
25757
30086
X-n190-k8
16980
18088
37820
36383
18651
X-n195-k51
44225
50311
79594
79276
66957
X-2200-336
58578
61009
78679
76477
68502
Gap
8.06
32.97
31.62
30,22
A.4 GRAPHICAL SOLUTIONS EXAMPLE
This section provides the visual results for several vehicle routing problems solved by the trained policy.
A.4.1
TRAINING RESULTS ON MCVRP
(b) Final state using train epoch
(c) Final state using train epoch #420 model
Initial
#2 model
Figure 3: N, = 100, N, case of mCVRP
Figure 3 depicts the evaluation case (N₂ 100, N, = 5 case of mCVRP) during training process. This test environment is designed mimic the search and rescue problems, operating multiple drones to search victims distributed over a map.
Green grids are for refueling nodes, blue circles are for vehicles (color becomes black as fuel capacity diminishes), and grey grids are for unvisited customers. a customer visited by a vehicle, the color becomes red or white; the red girds indicate the victims, while the white indicates victim in that cell. These red grids do not have any effect on performance measure, because visiting all customers (grey grids) is top-priority.
17

---

Under review as a conference paper at ICLR 2021
(a) CPLEX
(b) OR-Tools
(c) Ours (trained on mCVRP)
Figure 4: No = 20, N, = 2 case mTSP
CPLEX
OR-Tools
Ours (trained mCVRP)
Figure 5: TSP with a single vehicle
At the very beginning of the training process (figure (b)), the trained model cannot have vehicles search over the cells and make them die due to lack of fuel. At the end of the training process (figure 3 (c)), however, all customers are visited by the vehicles.
A.4.2 MVRP (MTSP)
Figure depicts an example solutions of mTSP using CPLEX, OR-Tools, and RL. The RL-based solver is trained under mCVRP environment but we solve mTSP with the trained model.
A.4.3 TSP
Figure depicts an example solutions of TSP using CPLEX, OR-Tools, and RL. The RL-based solver trained under mCVRP environment but solve TSP with the trained model.
A.5 NETWORK ARCHITECTURE AND HYPERPARAMETERS
Table II is summary of hyperparameters used in training process.
Table 11: Hyperparameters
Parameters (for PPO update)
Value
Parameters (for GRLTS)
Value
Optimizer
Adam
MLP units
(32, 32)
betas (81, 32)
(0.9. 0.999)
Neuron initialization
Kaiming normal
Learning rate (ppotiey)
2 x 10
Activation fn.
ReLU
Learning (ri- (ettnot
2 10
Node umbedding epoch (Nhopp)
gamma (r)
0.99
Node feature dim.
clip ratio (c)
0.2
Edge feature dim.
10
value function coeffi.
0.5
Max. decision epoch
3 Ne
entropy coeffi.
0.01
PPO update epoch (K)
10
Training epoch
18

---

Under review as a conference paper at ICLR 2021
A.6 TRAINING PERFORMANCE
Figure (6) shows how the trained policy perform on the thee set of validation problems while the policy is being trained by the random mCVRP inc stances. The three validation problems are 1) 100 customers covered by 5 vehicles, 2) 100 customers by 10 vehicles and 3) 400 eustomers covered by 20 vehicles. The first row show the performance on the random training instances while the second, third, and fourth row show the performances on the three validation problems.
As training processes progress, the trained model gradually becomes more efficient, that is, a fleet of vehicles visits more customers faster. After about 200 training epochs, the trained model converges, but there are some randomness due to the nature of policy gradient structure. Although the makespan curves in the second column training case seems relatively constant (the first row row), the level of difficulty is increasing curriculum becomes harder (The number of refueling is also increasing as curriculum becomes harder).
Comparison of case #1 and case #2 give two interpretations: 1) case #1 shows the model is trained to visit all customers and 2) in case #2, the model achieves consistent performance as training iterations progress in spite of same visit ratio as 1 around 100 epoch and 350 epoch. Besides, the makespans both training epochs are very close. Case #2 is relatively easier environment than case #1 in that more vehicles are deployed serve same number of customers.
Delortt
Train [3, (3]20]
20
30
60
4/5
180
24
30
400
180
1.0
44
N,-
180
200
180
60
256
Test
240
3.4
N.
Ne- 100
120
Tes k3
No 70
N, 400
(4) Rewand Clvvrr
Makcspan
(4) Denti ratio
(D) Number ofreflcting
Figure 6: Performance curves of training (Ist row) and testing (2nd, 3rd and 4th rows). Note that we plot a reward curve and cover ratio curves in 1st column for training and tesing, respectively.
A.7 PSEUDO CODE
Simulation: Problem Instance generation We generate random mCVRP instances and use these training instances to train the proposed model. For training, we randomly select the number of vehicles, customers, and refueling stations. We randomly assign these entities over the grid world with the distance between each grid cell being 1. When transforming the snapshot of the mCVRP to graph, we use the Manhattan distance between the two cells as the edge weight. In addition, the speed of each vehicle is set to be I; thus, each vehicle moves over one cell during single time-tic. Although the world is represented as discrete gird, the mCVRP problem's 's state transition event-based. Whenever the agent reaches the assigned eustomer, the event occurs, and all the edge distance is updated.
Initially, this grid world is developed distributed victims over the goid-world. Because each vehicle (drone) can search specific zone within certain amount of time, using cell-based grid world is reasonable choice.
the trained policy for search and rescue problems, seeking
19

---

Under review as a conference paper at ICLR 2021
Once the policy is trained, it can be used for both discrete world continuous world because these environments can be transformed into a graph without any difference. We validated the proposed method using CVRP and TSP instances defined over the continuous state to compare the performance of the proposed model to other deep baseline line models. Other deep baseline line models all use the continuous state.
To boost training, we vary the difficulty level of random mCVRP instances during training process (see Algorithm (2). For the curriculum instance generation in line compute Neurr. the number of customers which are assumed to be vivited already, as Neurr N₂ x (1 - 2 x Lurr 10). Then, we choose Neurr tasks randomly and mark as visited and distribute Neurr for all agents' visit number q²
Algorithm Training instance generation
1: Generate random problem instances No. No. Nr, x.g x.
2: Level
3: for Straining = 1, 1,.... Naraining do
4:
for each 100 training iterations do
5: currLevel & currLevel + 1
6: end for
7: Generate random number Pourr U[0, 1]
8: if Peurr 2 0.5 then Curriculum instance generation
9:
10: else
Non-curriculum instance generation (followed by line 1)
12: end if
end for
Simulation: Episode generation As a medium for the interaction of the two components such as environment and the GRLTS, simulation conducts the agents' actions and stores the state transitions which are used to update the GRLTS. Starting from the problem instance generation (Algorithm (2).
simulation assigns the agents' assignment d'ggt using the action probability π (- (-lo'g)) computed from the proposed GRLTS. Simulation computes the agent agt's 's transition time Angt as follow:
Aatt Dist(a ge a / Dist(r'agt: dagtt)
(13)
where velocity of agents are constant 1 and distance between and j Dist(i.j) can be the Manhattan distance or Euclidean distance.
20

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Episode generation
1: Initialize problem instances (based on Algorithm
2: lermination, done &- False, L & O, memory
3: idle.Alss 21.2..... ... N. aclingAgls +- 0
4: while termination do
5: for agt E idle.ggs do
6: Send an obervation agg agt to GRLTS
7:
Choose an action oaga ~ T-- T--loggt) where an action probability is from GRLTS
8:
Assign the action aagt to the agent
9:
end for
10: Compute and update transition time Aagt for agt E idleAgts (Equation B3
actingAgts t {agt Aagt min Aagt] for all agents
12:
t millagt Aagt
13:
for agt E actingAgts do
14:
Perform the recently assigned action dngt assigned by ग x-110'gt)
15:
Observe the observation ongt- reward r and done
16:
Append state transition tuple < t', oug d' rl rages dagt to memory end for
17:
18:
if done then
19:
termination + True else
21:
end idleAgls +- actingAgls
22:
23:
end while
RL networks: GRLTS Most of algorithms in the RL model is explained the paper that we focus on the interaction between simulation and GRLTS networks and internal message exchanges.
Algorithm 4 GRLTS
1: Receive an observation Tag: at time from simulation (line of Algorithm
2: Generate (*.(0) with input of observations 11,of
3: for node embedding iteration т I,..., Nhop do
4: Compute connectivity Cij for all nodes i,
For agent nodes Ong [f",
Vj 14 UVR
00,
VjEVA VA-
For refueling nodes r. Crj EvvjeV
For task nodes t, Ct = 5,
5: Store the node embedding vector h at memeory;
6: Update the connected edges following Equation (3)
7: Aggregate the incoming edge featured at each nodes following Equation (4)
8: Update the node feature with the node updator function dv
9: end for
10: Compute Q(h: a) for agent where a E A(o,) = {v e (VR U VT = 1} exp(o(MŞ a))
11: Compute (alo;) E.EA(H)) exp(Q((()aa)
12: Send the action probability (alo;) to simulation
21


Reviews:
[{"review_id": "__c7moOLpiT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nAn end-to-end RL algorithm, Graph-centric RL-based Transferable Scheduler (GRLTS) is proposed to solve the capacitated multi-vehicle VRP problem. \nThe fuel capacity of vehicles is considered and vehicles can visit charging stations in the middle of their routes toward the customers, and if their charge is about to finish, they get a reward as good as visiting a customer. \nThe goal is to minimize the makespan (completion time), which is the time between starting and finishing visiting all customers. \nThe state of each vehicle includes the current fuel level, the number of customers served up to now, the allocated node to visit. The state of customers involves its location and a visit indicator flag. And, the state of each charging station is its location. The action for each vehicle is the next node to visit, and the reward consists of two parts: (i) the number of visited customers, (ii) a reward to refuel the vehicle worth visiting a customer node when the battery is almost empty, otherwise a small value. \n\nTo use the proposed states, node and edge embedding are done by following GNN, a graph attention network that learns the attention weight over the neighbor nodes/edges to build the representation of each node. The edge values are considered a message that the source node sends to the target node. Also, in the GNN only the neighbor nodes/edges are considered.\n\n\nMajor comment:\nQ1- By just reading the main body of the paper, it is not clear what RL model you have used, and what does it mean to obtain a softmax operator over the Q-values in equation (7). If it is a regular actor-critic model, you do not need the critic for decision making, and the critic is only involved in the training. I am not sure why the critic is involved in decision making in equation (7). Can you please clarify?\n\nQ2- GRLTS does not perform better than the benchmarks in CVRP and TSP. What is the point of having those results in the main body of the paper? \nTo me, the current paper does not give any idea about your training algorithm and just provides the MDP definition and the result. I would suggest moving them to the appendix and explain some details of your training algorithms in the main body instead of the appendix. \n\nQ3- Why Table 6 and Table 7 does not involve other RL and heuristic algorithms? It looks like a cherry-picking among the benchmark algorithms is performs. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "45G0C9kZyiJ", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n--------------\nThe paper presents a reinforcement learning approach to learn a routing policy for a family of Vehicle Routing Problems (VRPs). More precisely, the authors train a model for the min-max capacitated multi vehicle routing problem (mCVRP), then use it to solve variants of the problem that correspond to various VRP problems (with a single vehicle, no capacity constraints, no fueling stations, etc). They use a GNN to represent the states and the PPO algorithm to learn the policy. They validate their approach on both random instances and literature benchmarks.\n\nStrong points\n-------------------\n1. The goal of using a single policy to solve a variety of routing problems\n2. First RL-based approach to tackle the multiple vehicle setting of VRPs\n3. Extensive numerical experiments on both randomly generated and benchmark instances\n\n\nWeak points\n-----------------\n4. There are a lot of imprecisions/typos/lack of definitions/mathematical imprecisions (see Feedback to improve the paper)                                                        \n5. According to the definition of the rewards, the expected return of the policy would be: $\\sum_v \\sum_t (r^v_{visit} + r^v_{refuel})$. It is important to note that this does not correspond to the objective function of the mCRVP problem. This choice of reward does not look natural to me and it would be useful to better motivate it.\n6. Sec 3.3: “When an vehicle node i reaches the assigned customer node, an event occurs and the vehicle node i computes its node embedding and selects one of its feasible action…”. This is crucial but not clear to me. At a step t, some vehicles might still be in between two cities. How is that taken into account in the state s_t? With the definition of the transition function, I understand that when an action is taken at t, the vehicle arrives at destination at t+1. Does it mean that you sequentially assign only one vehicle to a city and then “wait for it to arrive” before computing the next assignment? In that case what are the events about?\n7. Tables 1, 2, 3: to be relevant the results should averages over a number of random instances. Maybe it’s already the case but it is not mentioned.\n8. Sec 3.4 about the training should be more precise. It was difficult for me to find the relevant information because it was scattered at different places in the (10 pages) appendix.\n9. The authors do not mention whether they will share their code.\n\nRecommendation\n-------------------------\nI would vote for reject. Although the problem addressed is interesting, the paper is not well-written and there are too many typos and missing explanations to understand the method.\n \nArguments for recommendation: \n----------------------------------------------\nsee weak points\n\n\nQuestions to authors\n-----------------------------\n10. What prevents a vehicle from getting to a customer and then not having enough fuel to go back to a refuelling station?\n11. Table 1: are the results averaged over a number of random instances?\n12. To improve the results on TSP and VRP, have you tried including instances with only 1 vehicle during training?\n\t\n\n\nFeedback to help improve the paper\n---------------------------------------------------\n13. In the formal definition of the mCRVP (Section 2.1), there is no mention that the customers should all be visited. As it is presented, the problem is solved trivially by all vehicles doing nothing.\n14. In the state definition, in the vehicle state “x_v^t is the allocated node that vehicle v to sist”. This is important and not clear. I think the authors mean that it’s the node where the vehicle v is currently located. But then in customer state, x_c^t is a location. V^c should depend on t. \n15. Action a_t in {V_c union V_R} is not mathematically correct with the definition of V_C and V_R. The update of the v_t^c variable is missing (although in definition there was no dependence on t)\n16. In the definition of the refuelling rewards (section 2.2.3)\n(a) the index t is missing in q^v. The rewards should also be dependent on t.\n(b) What values for \\alpha? If F_v < 1 then the reward is negative or might be undefined if F_v =1\n17. Section 2.3: TSP is a special case of mCRVP. The fact that there is no fuel constraint is missing\n18. Equation (2) what is R_C. How is it chosen?\n19. Equation (3) R_R = F^v for which v?\n20. Right after equation (5),\\alpha_ij is defined as softmax(e_ij) but then e_ij is defined as a function of \\alpha\n21. Equation 7, I believe the sum should be over N_C(i) \\union N_R(i)\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "3P9WluSBrK", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the problem of capacitated vehicle routing which is a famous combinatorial optimization problem that is known to be NP-hard. This paper takes the approach of solving instances of this problem using RL. The goal is this problem is to minimize the maximum time (or makespan objective) for multiple vehicles to complete various tasks subject to fuel constraint. The paper trains a graph embedding from random instances and then show that it solves new instances of this problem with reasonable accuracy. Moreover, they also show that the embedding can be transferred to other related objectives.\n\nThe strengths of this paper are as follows.\n\n- Contributions to the literature of RL for combinatorial optimization which has become a recent growing paradigm. In this paradigm, we seek to obtain statistical algorithms (based on RL for instance) to NP-hard problems where the average instance tends to be computationally easy while the hard instances are not abundant. It is important to identify the set of combinatorial optimization problems for which we can surpass computational hardness and this paper adds to this literature.\n- Extensive experimentation: The second strength of this paper is that the paper does a good job of extensively evaluating their method on a variety of instances and also other related problems/objectives.\n\nHaving said that, the paper has a number of weakness in my opinion.\n\n- I find this paper to be rather incremental since this is not the first paper to study RL algorithms for this problem. The paper does not make a good case for why (yet) another RL based algorithm is useful for this problem and along what dimensions is this algorithm having the most novel improvements? The paper gives two reasons, but I do not find it convincing enough. In particular, it does not really show empirically why prior methods do not extend to this setting and why a new algorithm needs to be proposed.\n- I found very little generalizable learnings from this paper that could be useful for the machine learning community. The paper should make a better case for why the results from this paper are important to the ICLR community. It seems like this paper is more suitable for an appropriate operations research journal such as OR/INFORMS. I would like the authors to expand/justify more along these lines. May be the paper brings to light some hard application that could lead to new algorithmic developments? \n\n\nOverall, I think the paper is scientifically sound. My ratings stem from the fact that it may not be a good fit for ICLR. As I state above, I do not find generalizable results that can appeal to a broad (or even narrow) machine learning audience and will be a better fit for more domain specific venues.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper looks at a natural application of robust learning for vehicle routing. The paper introduces some new ideas for this RL problem; although the problem has been considered before.  The paper gives a nice algorithm with extensive experimental contributions.  

The paper has some shortcomings. The reviewers found there to be a lack of clarity in the mathematical definitions.  Moreover, there were modeling choices that the reviewers felt needed more thorough explanation.   For these reasons, this paper falls below the bar.  The authors are encouraged to revise the manuscript taking these concerns into consideration.


Decision: Reject