Year: 2020

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).

heading: 1 INTRODUCTION
text: 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 a branch-and-price algorithm appeared in Desrochers et al. (1992) or a column generation method (Chabrier, 2006), or heuristics ((Cordeau et al., 2002; Clarke & Wright, 1964; Gillett & Miller, 1974; Gendreau et al., 1994)). However, these approaches typically require huge computational time to find the near optimum solution. For more information for VRP, see 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 reinforcementlearning based approaches (Bengio et al., 2020); supervised learning approaches try to map a target VRP with a solution or try to 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 RL approaches can be further categorized into improvement heuristics and construction heuristics (Mazyavkina et al., 2020); improvement heuristics learn to modify the current solution for a better solution, while construction heuristics learn to construct a solution in a 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 et al., 2018) or the capacitated vehicle routing problem (CVRP) (Nazari et al., 2018; Kool et al., 2018). (Bello et al., 2016; Nazari et al., 2018; Kool et al., 2018) has used the encoder-decoder structure to
sequentially generate routing schedules, and (Khalil et al., 2017) uses graph based embedding to determine the next assignment 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-centric representation learning and RLbased 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 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. To effectively train the policy for minimizing the total completion time while satisfying the fuel constraints, we use the specially designed reward signal in RL framework. The representation learning for graph and the decision making policy are trained in an end-to-end fashion in an MARL framework. In addition, to effectively explore the joint combinatorial action space, we employ curriculum learning while controlling the difficulty (complexity) of a target problem.
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 multiple machines. However, our approach is more general in that it can consider capacity 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.

heading: 2 FORMULATION

heading: 2.1 MIN-MAX SOLUTION FOR MCVRP
text: We define the set of vehicles VV = 1, ..., NV , the set of customers VC = 1, ..., NC , and the set of refueling stations VR = 1, ..., NR, where NA, NC , 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 traveling distance, i.e., min maxi∈VV Li with Li 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 (1) (left) shows a snapshot of a mCVRP state and Figure (1) (right) represents a feasible solution of the mCVRP.

heading: 2.2 DEC-MDP FORMULATION FOR MCVRP
text: We seek to sequentially construct an optimum solution. Thus, we frame the solution construction procedure as a decentralized Markov decision problem (Dec-MDP) as follows.

heading: 2.2.1 STATE
text: We define the vehicle state svt ,∀v ∈ VV , the customer state sct ,∀c ∈ VC , and the refueling station state srt ,∀r ∈ VR as follows:
• State of vehicle v, svt = (xvt , fvt , qvt ). xvt is the allocated node that vehicle v to visit; fvt is the current fuel level; and qvt is the number of customers served by the vehicle v so far. • State of a customer c, sct = (xc,vc). xc is the location of customer node c (static). Visit indicator v c ∈ {0, 1} becomes 1 if the customer c is visited and 0, otherwise.
• State of a refueling station r, srt = xr. xr is the location of the refueling station r (static).
The global state st then becomes st = ({svt } Nv v=1, {sct} NC c=1, {srt} NR r=1).

heading: 2.2.2 ACTIONS & STATE TRANSITION
text: Action avt for vehicle v at time t is indicating a node to be visited by vehicle v at time t+ 1, that is, avt = x v t+1 ∈ {VC ∪ VR}. Therefore, the next state of vehicle v becomes svt+1 = (xvt+1, fvt+1, qvt+1) where fvt+1 and q v t+1 are determined deterministically by an action a v t as follows:
• Fuel capacity update: fvt+1 = { F v, if avt ∈ VR ftv − d(xvt , avt ), otherwise.
• Customer visit number update: qvt+1 = { qvt , if a v t ∈ VR
qvt + 1, otherwise.

heading: 2.2.3 REWARDS
text: The goal of mCVRP is to force all agents to coordinate to finish the distributed tasks quickly while satisfying the fuel constraints. To achieve this global goal in a distributed manner, we use the specially designed independent reward for each agent as:
• visiting reward: To encourage vehicles to visit the customer nodes faster, in turn, minimizing makespan, we define customer visit reward rvvisit = q v t . This reward is provided when an agent
visits a customer; the more customer nodes a vehicle agent n visits, the greater reward it can earn. • Refueling reward: To induce a strategic refueling, we introduce refuel reward rvrefuel = qvt ×
((F v−fvt )/(Fv−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 a lack of fuel is worth as much as visiting customers. In this study, we set F v = 10 (which is the equivalent to the total traveling distance that vehicle v can travel with the fuel tank fully loaded) and α = 2.

heading: 2.3 RELATIONSHIPS WITH OTHER CLASS OF VRPS
text: 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 a 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).
If some of these requirements are relaxed, min-max mCVRP can be degenerated into simpler conventional routing problems:
• TSP is the problem where a 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 (capacity-constrained TSP) is the problem where a single vehicle is operated to serve every customer while minimizing the total traveling distance and satisfying the fuel constraint. The vehicles need to comeback depot to 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-constrained 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 in 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.

heading: 3 METHOD
text: This section explains how the proposed model, given a state (a partial solution), assigns an idle vehicle to next node to visit under the sequential decision-making framework (see Figure 2).

heading: 3.1 STATE REPRESENTATION USING RELATIONSHIP-SPECIFIC MULTIPLE GRAPHS
text: The proposed model represents the global state st using as a weighted graph Gt = G(V,E,w) where V = {VV , VC , VR}, and E is the set of edges between node i, j ∈ V and w is weight for edge (i, j) (here, distance dij). Each node corresponding to vehicle, customer, and refueling station will be initialized with its associated states defined earlier.
Although we can assume that all 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 is located within its range as follows (see Figure 2):
evj = 1 ∀v ∈ Vv, d(v, j) ≤ RV = fvt (1) ecj = 1 ∀c ∈ Vc, d(c, j) ≤ RC (2) erj = 1 ∀r ∈ VR, d(r, j) ≤ RR = max
v∈Vv F v (3)
That is, the vehicle node v ∈ Vv connects the edges with nodes that are located within its traveling distance (i.e., the current fuel level fvt ). In addition, the customer nodes c ∈ Vc connects the edges with nodes that are located within the constant range RC . We set RC = 5 while following a typical hyperparameter selection procedure. Finally, the refueling node r ∈ VR 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 v = 10 for all vehicles). Note that the target node j that can be connected to each node can be any types of nodes.

heading: 3.2 NODE EMBEDDING USING GNN
text: The proposed model employs Graph neural network (GNN) (Scarselli et al., 2008) to compute the node embeddings for all nodes. The node embedding procedure starts with constructing the graph Gt out of the global state st = ({svt } Nv v=1, {sct} NC c=1, {srt} NR r=1). The method then compute the initial node embeddings hi and edge embeddings hij for all the nodes and edges of Gt by employing encoder network. The sequel will explain how the GNN layer update these node and edge embeddings.

heading: 3.2.1 EDGE UPDATE
text: The edge feature hτij at τ iteration is updated using the edge updater function φE as
hτij = φE(h τ−1 ij , h τ−1 i , h τ−1 j ), ∀i ∈ V,∀j ∈ Ni (4)
where hτ−1i and h τ−1 j are node embedding vectors of node i and node j at τ − 1 iteration.

heading: 3.2.2 EDGE FEATURE AGGREGATION
text: The updated edge feature hτij can be thought of as an message sent from node j to node i. Node i aggregates these messages from its neighboring nodes j ∈ {NV (i),NC(i),NR(i)}, where NV (i) is the neighboring vehicle nodes of node i, as
(h̄τi,V , h̄ τ i,C , h̄ τ i,R) =  ∑ j∈NV (i) αijh τ ij , ∑ j∈NC(i) αijh τ ij , ∑ j∈NR(i) αijh τ ij  (5) where the attention weight αij = sofmaxi(eij), where eij = fe(si, sj ;we), scores the significance of node j to node i. Note that message aggregation is separately conducted for different types of noes and the aggregated messages per type are concatenated.

heading: 3.2.3 NODE FEATURE UPDATE
text: The aggregated edge node embeddings (h̄τi,V , h̄ τ i,C , h̄ τ i,R) per its neighborhood type are then used to update the node embedding vector hτi using node update function φV as
hτi = φV ( hτ−1i , (h̄ τ i,V , h̄ τ i,C , h̄ τ i,R) )
(6)
The node embedding procedure is repeatedH (hop) times for all nodes, and the final node embeddings hH = {hHi }Ni=1 is used to determine the next assignment action of an idle vehicle.

heading: 3.3 DECISION MAKING USING NODE EMBEDDING
text: When an vehicle node i reaches the assigned customer node, an event occurs and the vehicle node i computes its node embedding hHi and selects one of its feasible actions, choosing one of unvisited customer nodes or refueling nodes around vehicle node i. The probability for agent i to choose node j, ait = j, is computed by the parameterized actor π(a i t = j|st;φ) as:
π(ait = j|st;φ) = exp(F (hHi , h H j ;φ)∑
k∈NV (i)∪NR(i) exp(F (h H i , h H k ;φ)
(7)
where F (hHi , h G j ;φ) is the fitness function evaluating the goodness for agent i to choose node j as the next action (i.e., ait = j).

heading: 3.4 TRAINING GRLTS
text: We train the proposed model using random mCVRP instances with varying numbers of vehicles, customers. We employ the actor-critic algorithm to train the parameters for the GNN, the critic, and the actor (GRLTS).
We first approximate the action-value function Qπ(s,a) ≈ Q̂π(s,a; θ) using a neural network with the critic parameter θ. The parameter θ for the centralized critic is optimized to minimize the loss L:
L(θ) = Eo,a,r,o′∼D[(Q̂π(s,a; θ)− y)2] = Eo,a,r,o′∼D[(Q̂π(hNhop ; θ)− y)2]
(8)
where y = r + γQ̂π ′ (hNhop ; θ′) is the target value evaluated with the the actor π′ = π(a|s;φ′) and the critic Q̂π(s,a; θ′) using the target parameters φ′ and θ′. In addition, D is a state transition memory.
To train the actor network, we use PPO method (Schulman et al., 2017) to maximize J(φ). PPO aims to maximize the clipped surrogate objective function as follow:
JCLIP(φ) = Et[min(Rt(φ)Ât, clip(Rt(φ), 1− , 1 + )Ât)] (9)
where Rt(φ) = πφ(at|st) πφold (a
t|ot) . We compute the advantage estimator Ât by running the policy for T time steps as
Ât = δt + γδt+1 + · · ·+ · · ·+ γT−1δt+T−1 δt = rt + γV (h Nhop t+1 ; θ)− V (h Nhop t ; θ)
(10)
In addition, equation (9) is added by a value function error and an entropy bonus for sufficient exploration because critic and actor share parameters as follow:
JCLIP ′
t (φ) = Et[JCLIPt (φ)− c1(Vθ(st)− Vtarget)2 + c2H(st, πφ(·))] (11)
where Vθ(st) ≈ V (h Nhop t ; θ) from the centralized critic; H denotes an entropy bonus; and c1 and c2 are hyperparameters.
On updating the centralized critic parameter θ and the decentralized (but, shared) actor parameter φ, we use Monte-Carlo simulation. To sequentially update both parameters, we follow an update rule as follow:
θk+1, φk+1 ← arg max θi,φk E oi,ai∼π
θi k
[ JCLIPt (φ)− c1(Vθ(st)− Vtarget)2 + c2H(st, πφ(·)) ] (12)
Algorithm (1) focus on sequence of the parameter update using above equations.
Algorithm 1 Parameter update in decentralized actors with PPO and Monte-Carlo simulation 1: for Agent i = 1, 2, . . . , N do 2: for Update iteration = 1, 2, . . . ,K do 3: Evaluate policy πθold in environment for an experienced episode 4: Compute rt(φ) in Equation (9) 5: Compute advantage estimates Â1, . . . , ÂT in Equation (10) 6: Optimize surrogate objective in Equation (11) with batch size T 7: θold ← θ, φold ← φ followed by (12) 8: end for 9: end for

heading: 4 EXPERIMENTS
text: The trained policy is used to solve various types of vehicle routing problems, mCVRP, mTSP, CVRP, and TSP without changing the parameters. For each type except mCVRP, we use two types of data
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 are provided in the Appendix). We also use Google OR-Tools(Perron & Furnon) as the representative heuristic solvers. For the problems where other deep RL based approaches tried to solve (TSP and CVRP), we compare the performance of the proposed approach to those of deep RL baselines. All experiments are conducted on Windows 10, Intel(R) Core(TM) i9-9900K CPU 3.6 GHz, and 32GB RAM. GPU acceleration is not used in testing.

heading: 4.1 PERFORMANCE COMPARISON OF MCVRPS
text: Method Nv = 2 Nv = 3 Nv = 5 Nv = 2 Nv = 3 Nv = 5 Nv = 5 Nv = 10
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 vehiclesNv ∈ 2, 3, 5 and the numbers of customers Nc ∈ 25, 50, 100. The number of refueling stations are set to be 4, 5 and 10 in case of Nc = 25, Nc = 50 and Nc = 100. For every combination of Nv and Nc, 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; x ∼ U [0, 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 1 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 or even fails to compute any feasible solution for the large scale problem (∞ means that ORT cannot find a feasible solution). Notably, the GRLTS achieves a better performance than ORT for large-scale problems with a significantly shorter computational time.
To validate the scalability of the proposed model, we further conduct test experiments with the four cases: Nc = 25 with Nv = 5, Nc = 100 with Nv = 10, Nc = 400 with Nv = 20, and Nc = 2, 500 with Nv = 50. Table 2 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), we can 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 a long time to compute the near-optimum solution by CPLEX, we only compare the single mCVRP case. The result is provided in the Appendix.

heading: 4.2 PERFORMANCE COMPARISON ON MTSP
text: We apply the trained network (without parameter changes) to solve mTSP, which seeks to minimize the total completion time of multiple vehicles (minmax mTSP). 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 Nc ∈ 50, 100, 400 and Nv ∈ 2, 4, 6, 8 (or Nv ∈ 10, 20, 30, 40). Table 7 compares the average makespan and computational time. The trained model outperforms ORT in the large-size problems (see Nc = 100 and Nc = 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).
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 1 solving MinMax mTSP. The performance results on 124 instances (four different number of vehicles per 31 different maps) are provided in Table 9 in Appendix.

heading: 4.3 PERFORMANCE COMPARISON ON CVRP (PAYLOAD CAPACITY)
text: We employ the trained model to solve randomly generated 100 CVRP instances withNc = 20, 50, 100 with a single capacitated vehicle. All nodes are randomly scattered in the unit square of [0, 1]× [0, 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 to 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 4 summaries results for the random CVRP environment. L2I 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;
1www.infoiasi.ro/ mtsplib
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 is 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 10 in 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 et al., 2018).

heading: 4.4 PERFORMANCE COMPARISON OF TSP
text: Lastly, we employ the trained model to solve 100 randomly generated TSP with different number of customers Nc = 20, 50, 100 and a single vehicle. Table 5 shows summarized the results. Although GRLTS is not outperforming other RL-based scheduling methods, it shows the reasonably performance that is comparable to some of well known heuristic algorithms. Given that the GRLTS is 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 8 in Appendix provides all the performance results compared with other RL-baseline models. The results show that our model has comparable performance with the-state-ofart RL-based approaches (GPN (Ma et al., 2019) and S2V-DQN (Khalil et al., 2017)) and heuristic algorithms, especially for large-scale TSP problems.

heading: 5 CONCLUSION
text: We proposed the Graph-centric RL-based Transferable Scheduler for various vehicle routing problems 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 RL-based scheduler can be used for large-scale realistic applications in logistics, transportation, and manufacturing.

heading: A APPENDIX
text: A.1 MILP FORMULATIONS FOR ROUTING PROBLEMS
The MILP formulations for mCVRP, mTSP, and TSP are provided in this section. All problems are formulated to find the optimum routes of vehicles to minimize the makespan. For TSP formulation, the makespan minimization is equal to total distance minimization due to 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-Zemlin (MTZ) formulation (Miller et al., 1960):
minimize ∑ i∈V ∑ j∈V,i6=j dijxij
subject to. ∑ i∈V
xij = 1, ∀j ∈ V : i 6= j, (1)∑ j∈V xij = 1, ∀i ∈ V : i 6= j, (2)
ui − uj + |V |xij ≤ |V | − 1, ∀i, j ∈ V \ vStart, (3) 0 ≤ ui ≤ |V | − 1, ∀i ∈ V \ vStart, (4) xij ∈ {0, 1}, ∀i, j ∈ V, (5) ui ∈ Z, ∀i ∈ V \ vStart. (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 or cost c). xij is 1 if the edge between node i and node j exists, otherwise, 0. Here, corresponding distance of the edge is dij . Constraint (3,4) with dummy variable ui is for subtour elimination. As setting dij = 0,∀j ∈ vStart, 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 multi-vehicle settings, and the objective function is modified from A.1.1 to consider the makespan minimization setting (MinMax problem).
minimize Q subject to. ∑ i∈V ∑ j∈V
dijxaij ≤ Q, ∀a ∈ A : i 6= j, (1)∑ j∈V
xaij = 1, ∀a ∈ A, i ∈ vStarta : i 6= j, (2)∑ a∈A ∑ i∈G ∑ j∈G
xaij = 1, ∀j ∈ vTask : i 6= j, (3)∑ i∈G xaij − ∑ i∈G xaji = 0, ∀a ∈ A, j ∈ V : i 6= j, (4)
uai − uaj + |V |xaij ≤ |V | − 1, ∀a ∈ A, j ∈ V \ vStarta : i 6= j, (5) 0 ≤ uai ≤ |V | − 1, ∀a ∈ A, i ∈ V \ vStarta, (6) xaij ∈ {0, 1}, ∀a ∈ A,∀i, j ∈ V, (7) uai ∈ Z, ∀a ∈ A, i ∈ 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 can minimize the makespan. Therefore, the above formulation is to minimize the makespan. We also allow a vehicle to start a tour at any staring node vStarta (constraint (2)).
A.1.3 MCVRP
We extend the above mTSP formulation in A.1.2 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. ∑ i∈V ∑ j∈V
dijxaij ≤ Q, ∀a ∈ A : i 6= j, (1)∑ j∈V
xaij = 1, ∀a ∈ A, i ∈ vStarta : i 6= j, (2)∑ a∈A ∑ i∈G ∑ j∈G
xaij = 1, ∀j ∈ vTask : i 6= j, (3)∑ i∈G xaij − ∑ i∈G xaji = 0, ∀a ∈ A, j ∈ V : i 6= j, (4)
uai − uaj + |V |xaij ≤ |V | − 1, ∀a ∈ A, j ∈ V \ vStarta : i 6= j, (5) 0 ≤ uai ≤ |V | − 1, ∀a ∈ A, i ∈ V \ vStarta, (6) xaij ∈ {0, 1}, ∀a ∈ A,∀i, j ∈ V, (7) uai ∈ Z, ∀a ∈ A, i ∈ V \ vStarta (8) fai = Fa, ∀a ∈ A, i ∈ vRefuel, (9) fai − dijxaij ≥ 0, ∀a ∈ A,∀i, j ∈ vRefuel, (10) faj − fai + dijxaij ≥ Fa(1− xaij), ∀a ∈ A,∀i, j ∈ 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 a vehicle must have enough remaining fuel to visit a refueling node. Constraint (11) indicates that a vehicle cannot consume (travel) more than its fuel capacity. We allow vehicles to visit refueling nodes as many times as possible by introducing a 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 = 1 so that |A| = 1). We consider a single depot to start a mission and unload some burdens. Therefore, vRefuel in the MILP of mCVRP becomes same as vStarta. Fuel consumption as much as distance dij between node i and node j is equivalent to payload capacity consumption as much as demand dj at node j. As a result, constraint (9-11) of the mCVRP model becomes:
cai = Ca, ∀a ∈ A, i ∈ vStart, (9) caj − cai + djxaij ≥ Ca(1− xaij), ∀a ∈ A,∀i, j ∈ vTask. (10)
The constraint (10) in the mCVRP model is dropped because payload capacity is independent in returning to the starting depot.
A.2 COMPARISON WITH CPLEX SOLUTIONS
For a single mCVRP and mTSP instances, we 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.
A.2.1 MCVRP
We apply the already trained model to solve mCVRP with different numbers of vehicles Nv ∈ 2, 3, 5 and the numbers of customers Nc ∈ 25, 50, 100. The number of refueling stations are set to be 4, 5 and 10 in case of Nc = 25, Nc = 50 and Nc = 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∞ indicate the case where the computational time is reached and the solution at that moment is used in the table. The blanks with the hyphen (-) indicate the case where the algorithm could not find any feasible solution.
First, CPX (CPLEX) can only solve for mCVRPs with Nc = 25; for large scale problems, it 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 of time or 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, a single mTSP instance was generated and used for comparing the performances of GRLTS to CPLEX and ORT.
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 RL-based approaches (GPN (Ma et al., 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 et al. (2020): 3.1%→ 10.0%, GPN: 14.1%→ 33.1%, Drori et al. (2020): 4.7%→ 10.6%).
Table 8: Performance comparison on TSP library
RL Approx.
City Opt. Ours Drori et al. (2020) GPN S2V-DQN Farthest 2-opt Nearest
eil51 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 eil76 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 1565
kroA100 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 eil101 629 753 650 704 667 687 694 825 lin105 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
kroA150 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 rat195 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 35798 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 52838 67588 53790 54954 58115 58634 a280 2579 3059 2742 3019 3007 3011 2775 3311 pr299 48191 59257 53371 68011 55413 52110 52058 61252 lin318 42029 49167 45115 47854 45420 45930 45945 54034 rd400 15281 16631 16730 17564 16850 16864 16685 19168 fl417 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 0 15.1 4.9 19.0 6.2 8.4 9.1 24.7
A.3.2 MTSP
Table 9 shows results from mTSPLib 2 solving MinMax TSP. Our model shows 3% longer results than ORT. However, computational time is, on average, about 30 seconds faster, which is about 45%. In addition, we calculate difference of the optimality gap by Nv = 2, 3, 5, 7. Our model shows better performance as Nv increases (Nv = 2 case: 9.8%, Nv = 3 case: 8.9%, Nv = 5 case: 2.8%, Nv = 7 case: -7.5%)
2www.infoiasi.ro/ mtsplib
Table 9: Performance comparison on mTSP library
ORT Ours ORT Ours
Maps Nv MS Time MS Time gap Maps Nv MS Time MS Time gap
eil51
2 223 1.14 281 2.95 26.2
kroB100 2 12214 15.06 13721 9.41 12.3 3 159 0.67 244 2.92 53.7 3 8957 14.81 10197 9.52 13.8 5 120 1.48 165 2.93 37.5 5 7108 10.31 6271 9.19 -13.3 7 109 1.03 86 2.67 -26.5 7 7108 10.24 6119 9.49 -16.2
berlin52
2 4634 1.27 4247 3.01 -9.1
kroC100 2 11440 8.90 12453 9.39 8.9 3 3195 1.35 3452 3.03 8.0 3 8725 12.58 7985 9.48 -9.3 5 2606 1.18 2179 3.03 -19.6 5 6616 15.66 6291 9.50 -5.2 7 2440 1.42 2182 2.87 -11.8 7 6154 12.83 5740 9.30 -7.2
eil76
2 288 4.46 361 5.81 25.4
kroD100 2 13130 11.27 12815 9.32 -2.5 3 212 3.26 227 5.75 7.2 3 8889 9.36 9359 9.40 5.3 5 179 4.79 170 5.61 -5.1 5 6976 9.67 6660 9.34 -4.7 7 179 4.78 121 5.41 -47.4 7 6485 12.00 7246 9.25 11.7
st70
2 388 3.77 451 4.87 16.2
kroE100 2 13424 9.02 13611 9.53 1.4 3 285 2.04 282 4.98 -1.2 3 9334 14.61 8929 10.76 -4.5 5 251 2.26 249 4.69 0.8 5 7599 20.27 6992 10.05 -8.6 7 251 2.22 253 4.78 0.9 7 8727 17.14 5868 9.42 -18.7
pr76
2 60679 4.99 80789 5.69 33.1
eil101 2 345 11.23 386 9.70 11.8 3 51074 6.25 65567 5.67 28.4 3 237 10.32 264 9.64 11.3 5 39167 3.55 48143 5.48 22.9 5 163 11.15 167 9.67 2.3 7 38116 5.85 33082 5.50 -15.2 7 123 15.29 141 9.63 14.6
rat99
2 709 16.47 756 9.11 6.6
lin105 2 8846 18.50 10220 10.20 15.5 3 549 13.86 565 9.28 2.9 3 7112 16.20 8168 10.30 14.8 5 463 11.12 373 9.14 -24.0 5 7060 18.79 5487 10.34 -28.7 7 440 12.01 367 9.24 -19.8 7 6444 18.84 4802 10.35 -34.2
rd100
2 4406 17.94 4520 9.54 2.6
pr107 2 31692 14.29 26369 10.96 20.2 3 3224 20.31 3136 9.61 -2.8 3 24904 12.82 23283 10.90 -7.0 5 2435 20.78 2629 9.32 8.0 5 21455 16.70 20985 10.80 -2.2 7 2803 17.38 2375 9.38 -18.0 7 21365 17.45 20620 10.81 -3.6
kroA100
2 12647 12.19 13560 9.49 7.2
pr124 2 35094 18.82 36472 15.02 3.9 3 9116 14.37 9635 9.49 5.7 3 27257 16.70 27598 14.75 1.3 5 8229 13.11 7462 9.42 -10.0 5 23231 21.44 23651 14.75 1.8 7 8229 13.31 7147 9.24 -15.1 7 22725 25.29 21526 14.75 -5.6
bier127
2 62458 22.72 67706 15.83 8.4
u159 2 26171 47.80 27864 26.35 6.5 3 47347 22.61 52749 15.68 11.4 3 19014 56.26 19519 25.87 2.7 5 29560 38.21 30946 15.76 4.7 5 14308 72.44 16719 26.34 16.9 7 24891 47.49 25074 15.48 0.7 7 14776 67.59 16077 26.03 8.8
ch130
2 3393 31.44 3755 16.85 10.7
rat195 2 1285 205.86 1524 43.66 18.6 3 2550 23.90 3425 16.65 34.3 3 975 101.40 937 43.82 -4.0 5 1575 39.03 2307 16.69 46.5 5 708 152.43 638 43.57 -10.9 7 1338 32.88 2077 16.30 55.2 7 631 130.31 495 43.85 -27.5
pr136
2 59999 34.54 59113 18.18 -1.5
d198 2 10416 170.17 9226 45.20 -12.9 3 40643 14.45 45017 18.25 10.8 3 9663 71.48 7813 45.36 -23.7 5 29958 29.59 32858 18.14 9.7 5 8577 113.45 6086 45.21 -40.9 7 30138 20.66 30222 17.98 0.2 7 8577 115.69 5892 45.64 -45.6
pr144
2 38104 23.11 52344 20.72 37.4
kroA200 2 17148 154.68 20696 46.46 20.7 3 31305 36.20 42179 20.72 34.7 3 12253 161.74 13778 46.44 12.4 5 25262 46.69 28153 20.55 1.4 5 8185 190.01 10770 46.33 31.6 7 24361 42.25 27168 20.52 11.5 7 6675 186.54 7142 46.36 7.0
ch150
2 3914 43.40 3637 22.75 -7.6
kroB200 2 16127 92.48 18758 47.00 16.3 3 2663 42.67 2870 22.78 7.7 3 11814 103.17 13199 46.13 11.7 5 1915 75.00 1994 22.66 4.1 5 8525 126.04 10618 46.83 24.6 7 1661 66.54 1603 23.10 -3.6 7 7720 120.19 8678 46.41 12.4
kroA150
2 15326 40.34 16578 22.77 8.2
ts225 2 70660 230.60 71594 64.01 1.3 3 10810 47.01 12600 22.83 16.6 3 55237 245.30 52330 63.12 -5.6 5 7323 54.11 8567 23.05 17.0 5 38748 189.31 31318 64.13 -23.7 7 6290 42.09 7901 22.66 25.6 7 35460 213.09 27921 63.53 -27.0
kroB150
2 14633 54.68 18342 22.84 25.3
tsp225 2 2145 277.23 2481 62.39 15.7 3 10565 36.80 11512 22.91 8.9 3 1612 145.43 1743 63.56 8.1 5 7257 35.87 7539 22.82 3.9 5 1183 184.62 1308 63.83 10.6 7 8221 31.13 6057 22.92 -35.7 7 1044 209.54 1016 63.89 -2.7
pr152
2 43922 52.08 51982 23.71 18.3 3 38752 50.79 48238 23.35 24.5 5 33006 91.95 43940 23.27 33.1 7 32245 102.58 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).
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
Figure 3 depicts the evaluation case (Nc = 100, Nv = 5 case of mCVRP) during training process. This test environment is designed to 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. If a customer is visited by a vehicle, the color becomes red or white; the red girds indicate the victims, while the white indicates no victim in that cell. These red grids do not have any effect on performance measure, because visiting all customers (grey grids) is top-priority.
At the very beginning of the training process (figure 3 (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 4 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 5 depicts an example solutions of TSP using CPLEX, OR-Tools, and RL. The RL-based solver is trained under mCVRP environment but we solve TSP with the trained model.
A.5 NETWORK ARCHITECTURE AND HYPERPARAMETERS
Table 11 is summary of hyperparameters used in training process.
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 customers 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 of training case seems relatively constant (the first row row), the level of difficulty is increasing as curriculum becomes harder (The number of refueling is also increasing as curriculum becomes harder).
Comparison of case #1 and case #2 give us 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 of both training epochs are very close. Case #2 is relatively easier environment than case #1 in that more vehicles are deployed to serve same number of customers.
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 a 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 1; thus, each vehicle moves over one cell during a single time-tic. Although the world is represented as discrete gird, the mCVRP problem’s state transition is event-based. Whenever the agent reaches the assigned customer, the event occurs, and all the edge distance is updated.
Initially, this grid world is developed to use the trained policy for search and rescue problems, seeking distributed victims over the grid-world. Because each vehicle (drone) can search a specific zone within a certain amount of time, using a cell-based grid world is a reasonable choice.
Once the policy is trained, it can be used for both a discrete world or a 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 9, we compute Ncurr, the number of customers which are assumed to be visited already, as Ncurr = Nc × (1− 2× currLevel/10). Then, we choose Ncurr tasks randomly and mark as visited and distribute Ncurr for all agents’ visit number qt.
Algorithm 2 Training instance generation
1: Generate random problem instances Nv , Nc, Nr, x0v , x 0 r , 2: currLevel← 0 3: for itraining = 1, . . . , Ntraining do 4: for each 100 training iterations do 5: currLevel← currLevel + 1 6: end for 7: Generate a random number pcurr ∼ U[0, 1] 8: if pcurr ≥ 0.5 then 9: Curriculum instance generation
10: else 11: Non-curriculum instance generation (followed by line 1) 12: end if 13: 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 as atagt using the action probability π(·|otagt) computed from the proposed GRLTS. Simulation computes the agent agt’s transition time ∆agt as follow:
∆agt = Dist(x t agt,a t agt)/vagt = Dist(x t agt, a t agt) (13)
where velocity of agents are constant as 1 and distance between i and j Dist(i, j) can be the Manhattan distance or Euclidean distance.
Algorithm 3 Episode generation 1: Initialize problem instances (based on Algorithm 2) 2: termination, done← False, t← 0, memory ← ∅ 3: idleAgts← {1, 2, . . . , Nv}, actingAgts← ∅ 4: while termination do 5: for agt ∈ idleAgts do 6: Send an obervation Πagtotagt to a GRLTS 7: Choose an action atagt ∼ π(·|otagt) where an action probability is from GRLTS 8: Assign the action atagt to the agent 9: end for 10: Compute and update transition time ∆agt for agt ∈ idleAgts (Equation (13)) 11: actingAgts← {agt|∆agt = minagt ∆agt} for all agents 12: t← t+ minagt ∆agt 13: for agt ∈ actingAgts do 14: Perform the recently assigned action at ′ agt assigned by π(·|ot ′ agt) 15: Observe the observation otagt, reward r t agt and done 16: Append a state transition tuple < t′, ot ′ agt, a t′ agt, r t agt, o t agt > to memory 17: end for 18: if done then 19: termination← True 20: else 21: idleAgts← actingAgts 22: end if 23: end while
RL networks: GRLTS Most of algorithms in the RL model is explained the paper so that we focus on the interaction between simulation and GRLTS networks and internal message exchanges.
Algorithm 4 GRLTS
1: Receive an observation Πagtotagt at time t from simulation (line 6 of Algorithm 3) 2: Generate Gt,(0) with an input of observations Πioti 3: for node embedding iteration τ = 1, . . . , Nhop do 4: Compute connectivity Cij for all nodes i, j:
For agent nodes n,Cnj = { fn, ∀j ∈ VT ∪ VR ∞, ∀j ∈ VA.
For refueling nodes r, Crj = F,∀j ∈ V For task nodes t, Ctj = 5,∀j ∈ V
5: Store the node embedding vector hAi at memeoryi 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 φv 9: end for
10: Compute Q(hAi , a) for agent i where a ∈ A(oi) = {v ∈ {VR ∪ VT }|Civ = 1} 11: Compute π (a|oi) =
exp(Q(hAi ,a))∑ a∈A(oi)
exp(Q(hAi ,a)) 12: Send the action probability π (a|oi) to simulation

Review summaries:
The 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.

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.