ScheduleNet: Learn to Solve MinMax mTSP Using Reinforcement Learning with Delayed Reward
Authors: Junyoung Park
Sanzhar Bakhtiyarov
Jinkyoo Park
Venue:  (2021)

Abstract: Combinatorial Optimization (CO) problems are theoretically challenging yet crucial in practice. Numerous works used Reinforcement Learning (RL) to tackle these CO problems. As current approaches mainly focus on single-worker CO problems such as the famous Travelling Salesman Problem (TSP), we focus on more practical extension of TSP to multi-worker (salesmen) setting, specifically MinMax mTSP. From the RL perspective, Minmax mTSP raises several significant challenges, such as the cooperation of multiple workers and the need for a well-engineered reward function. In this paper, we present the RL framework with (1) worker-task heterograph and type-aware Graph Neural Network, and (2) the RL training method that is stable, has fast convergence speed, and directly optimizes the objective of MinMax mTSP in a delayed reward setting. We achieve comparable performance to a highly optimized meta-heuristic baseline, OR-Tools, and outperforms it in 10% of the cases, both on in-training and out-of-training problem distributions. Moreover, our problem formulation enables us to solve problems with any number of salesmen (workers) and cities.

Under review as a conference paper at ICLR 2021
SCHEDULENET: LEARN TO SOLVE MINMAX MULTI- PLE TRAVELLING SALESMAN PROBLEM
Anonymous authors Paper under double-blind review
ABSTRACT
There has been continuous effort to learn to solve famous CO problems such as Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) using re- inforcement learning (RI.). Although they have shown good optimality and com- putational efficiency, these approaches have been limited scheduling a single- vehicle. MinMax mTSP, the focus of this study, is the problem seeking to min- imize the total completion time for multiple workers to complete the geographi- cally distributed tasks. Solving MinMax mTSP using RL raises significant chal- lenges because one needs to train a distributed scheduling policy inducing the co- operative strategic routings using only the single delayed and sparse reward signal (makespan). In this study, we propose the ScheduleNet that can solve mTSP with any numbers of salesmen and cities. The ScheduleNet presents state (partial so- lution to mTSP) as a set of graphs and employs type aware graph node embeddings for deriving the cooperative and transferable scheduling policy. Additionally, effectively train the ScheduleNet with sparse and delayed reward (makespan), we propose an RL training scheme, Clipped REINFORCE with "target net," which significantly stabilizes the training and improves the generalization performance. We have empirically shown that the proposed method achieves the performance comparable to Google OR-Tools, highly optimized meta-heuristic baseline.
INTRODUCTION
There have been numerous approaches to solve combinatorial optimization (CO) problems using machine learning. [engio al. (2020) have categorized these approaches into demonstration and experience. In demonstration setting, supervised learning has been employed to mimic the behavior of the existing expert (e.g., exact solvers or heuristics). On the other hand, in the experience setting, typically, reinforcement learning (RL) has been employed to learn parameterized policy that can solve newly given target problems without direct supervision. While the demonstration policy can- not outperform its guiding expert, RL-based policy can outperform the expert because it improves its policy using a reward signal. Concurrently, Mazyavkina et al.) (2020) have further categorized the RL approaches into improvement and construction heuristics. An improvement heuristics start from the arbitrary (complete) solution of the CO problem and iteratively improve it with the learned policy until the improvement stops (Chen & Tian 2019 Ahn al. 2019).. On the other hand, the construction heuristics start from the empty solution and incrementally extend the partial solution using a learned sequential decision-makinn policy until becomes complete.
There has been continuous effort to learn to solve famous CO problems such as Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) using RL-based construction heuristics (Bello et al. 2016: Kool et al.) 2018 Khalil et al., 2017 Nazari et al., 2018). Although they have shown good optimality and computational efficiency performance, these approaches have been limited to only scheduling single-vehicle. The malti-extensions of these routing problems, such multiple TSP and multiple VRP, are underrepresented in the deep learning research community, even though they capture broader set of the real-world problems and pose more significant scientific challenge.
The multiple traveling salesmen problem (mTSP) aims to determine a set subroutes for each salesman, given m salesmen and N cities that need to be visited by one of the salesmen, and depot where salesmen are initially located and to which they return. The objective of a mTSP is either minimizing the of subroute lengths (MinSum) minimizing the length of the longest subroute

---

Under review as a conference paper at ICLR 2021
(MinMax). In general, the MinMax objective is more practical, as seeks visit all cities as soon as possible (i.e., total completion time minimization). In contrast, the MinSum formulation, in general, leads to highly imbalanced solutions where one of the salesmen visits most of the cities, which results in longer total completion time (Lupoaie et al. 2019).
In this study, we propose learning- learning-based decentralized and sequential decision-making algorithm for solving Minmax mTSP problem; the trained policy, which is a construction heuristic, can be employed to solve mTSP instances with any numbers of salesman and cities. Learning a transferable mTSP solver in a construction heuristic framework is significantly challenging comparing to its single-agent variants (TSP and CVRP) because (1) we need use the state representation that is flexible enough to represent any arbitrary number of salesman and cities (2) we need to introduce the coordination among multiple agents to complete the geographically distributed tasks as quickly as possible using a sequential and decentralized decision making strategy and (3) we need to learn such decentralized cooperative policy using only a delayed and sparse reward signal, makespan, that is revealed only at the end of the episode.
To tackle such a challenging task, we formulate mTSP as semi-MDP and derive a decentralized decision making policy in multi-agent reinforcement learning framework using only sparse and delayed episodic reward signal. The major components of the proposed method and their importance summarized as follows:
Decentralized cooperative decision-making strategy: Decentralization of scheduling policy is essential to ensure the learned policy be employed to schedule any size of mTSP problems in a scalable manner; decentralized policy maps local observation of each idle salesman one of feasible individual action while joint policy maps the global state to the joint scheduling actions.
State representation using type-award graph attention (TGA): sents state (partial solution to mTSP) as set of graphs, each of which captures specific relationships among works, cities, and depot. The proposed method then employs TGA compute the node embeddings for all nodes (salesman and cities), which are used to assign idle salesman to an unvisited city sequentially.
the proposed method repre-
Training decentralized policy using a single delayed shared reward signal: Training decen- tralized cooperative strategy using single sparse and delayed reward is extremely difficult in that we need to distribute credits of a single scalar reward (makespan) over the time and agents. To resolve this, we propose a stable MARL training scheme which significantly stabilizes the training and improves the generalization performance.
We have empirically shown that the proposed method achieves the performance comparable to Google OR-Tools, a highly optimized meta-heuristic baseline. The proposed approach outperforms OR-Tool TR-Tools in many cases on in-training, out-of-training problem distributions, and real-world prob- lem instances. We also verified that scheduleNet can provide an efficient routing service to cus- tomers.
RELATED WORK
Construction RL approaches A seminal body of work focused on the construction approach in the
RL setting for solving CO problems (Bello et al. 2016 Nazari et al. 2018 Kool et al. 2018 Khalil al. 2017). These approaches utilize encoder-decoder architecture, that encodes the problem struc- ture into a hidden embedding first, and then autoregressively decodes the complete solution. [Bello] al. (2016) utilized LSTM (Hochreiter & Schmidhuber (997) based encoder and decode the com- plete solution (tour) using Pointer Network (Vinyals et al. 2013) scheme. Since the routing tasks are often represented as graphs. Nazari et al. (2018) proposed an attention based encoder, while using LSTM decoder. Recently, Kool et al. (2018) proposed to use Transformer-like architecture (Vaswani et al. 2017) to solve several variants of TSP and single-vehicle CVRP. On the contrary, Khalil et al. (011)) do not use encoder-decoder architecture, but single graph embedding model, structure2vec (Dai et al. 2016). that embeds a partial solution of the TSP and outputs the next city in the tour)tour. (Kang et al. 2019) has extended structure2vec to random graph and employed this random graph embedding to solve identical parallel machine scheduling problems, the problem seeking to minímize the makespan by scheduling multiple machines.
2

---

Under review as a conference paper at ICLR 2021
So empty solution
Sy partial solution at
8, partial solution at T+1
St Complete solution
O
"assign"
to "1"
Event 7
Event
T
Time
[(0) = 0
Total completion time: makespan
t(T)
Figure 1: The mTSP MDP The black lined balls indicates the events of the mTSP MDP. The empty, dashed, and, filled rectangles represent the unassigned, assigned, and inactive cities, respectively. The circles represent the workers and the positions of the circles show the 2D coordinates of worker. The orange and blue colored lines shows the subtours of the orange and blue worker, respectively.
Learned m TSP solvers The machine learning approaches for solving mTSP date back to Hoopield
& Tank (1985). However, these approaches require per problem instance training. (Hopfield & Tank] 1985; Wacholder et al., 1989 (Somhom et al. 1999). Among the recent learning methods, Kaempfer & Wolf encodes MinSum m mSS with a set-specialized variant of Transformer ar- chitecture that uses permutation invariant pooling layers. To obtain the feasible solution, they use combination of the softassign method Gold & Rangarajan (1996) and a beam search. Their model is trained in a supervised setting using mTSP solutions obtained by Integer Linear Programming (ILP) solver. Hu et al. (2020) utilizes a GNN encoder and self-attention Vaswani et al. (2017) policy outputs probability of assignment to each salesman per city. Once cities are assigned specific salesmen, they use existing TSP solver, OR-Tools (Perron & Furnon). to obtain each worker's 's sub- routes. Their method shows impressive scalability terms of the number of cities, as they present results for mTSP instances with 1000 cities and ten workers. However, the trained model is not scalable in terms of the number of workers and can only solve mTSP problems with pre-specified, fixed number of workers.
PROBLEM FORMULATION
We define the set of m salesmen indexed by VT = (1,2,..., m)., and the set of N cities indexed by Vc {m + 1,2, ...: m + N). Following mTSP conventions, we define the first city as the depot. We also define the 2D-coordinates of entities (salesmen, cities, and the depot) as p'. The objective of MinMax mTSP
minimize the length of the longest subtour of salesmen, while subtours covers all cities and all subtours of salesmen end at the depot. For the clarity of explanation, we will refer salesman as workers, and cities as a tasks.
3.1 MDP FORMULATION FOR MINMAX MTSP
In this paper, the objective is to construct an optimal solution with a construction RI. approach. Thus, we cast the solution construction process of MinMax mTSP Markov decision process (MDP). The components of the proposed MDP are as follows.
Transition The proposed MDP transits based on events. We define event as the the case where any worker reaches its assigned city. We enumerate the event with the index J for avoiding confusion from the elapsed time of the mTSP problem. t(r) is function that returns the time of event т. In the proposed event event-based transition setup, the state transitions coincide with the sequential expansion of the partial scheduling solution.
State Each entity i has its own state s (pt. 1ectie 1 miiigndd) at the 7-th event. the coordinates p
is time-dependent for workers and static for tasks and the depot. Indicator 1 aetive describes whether
3

---

Under review as a conference paper at ICLR 2021
H times
0
ag
5t
Fr
raw-2-hid hid-2-hid
Assignment Prob.
Sc+1
Figure 2: Assignment action determination step of ScheduleNet
the entity is active or inactive case of tasks, inactive indicates that the task is already visited; in case of worker, inactive means that worker returned to the depot. Similarly, 1, assigned indicates whether worker assigned task not. We also define the environment state s that contains the current time of the environment, and the sequence of tasks visited by each worker, i.e., partial solution of the mTSP. The state 8, of the MDP at the 7-th event becomes The first state 80 corresponds to the empty solution of the given problem instance, i.e., no cities have been visited, and all salesmen are in the depot. The terminal state corresponds to complete so- lution of the given mTSP instance, i.e., when every task has been visited, and every worker returned to the depot (See Figure
([s) H s..)).
Action scheduling action a, defined as the worker-to-tase assignment, i.e. salesman has to visit the assigned city.
Reward. We formulate the problem in a delayed reward setting. Specifically, the sparse reward function is defined r(s,) 0 for all non-terminal events, and r(ST) t(T), where T is the index of the terminal state. other words, a single reward signal, which is obtained only for the terminal state, equals to the makespan of the problem instance.
SCHEDULENET
Given the MDP formulation for MinMax mTSP, propose ScheduleNet that recommend scheduling action a, given the current state 9, represented as a graph, ie., (a (r). The Schedul- Net first presents state (partial solution of mTTS) as of graphs, each of which captures spe- cific relationships among workers, tasks, and depot. Then ScheduleNet employs type-aware graph attention (TGA) compute the node embeddings and use the computed node embeddings to deter- mine the next assignment action (See figure 2)
4.1 WORKER- TASK GRAPH REPRESENTATION
Whenever an event occurs and the global state s, of the MDP updated at r. ScheduleNet constructs directed complete graph G, (V, E) out of s,, where V Vr U Vc is the set of nodes and E is the set of edges. We drop the time iterator 7 to simplify the notations since the following operations only for the given time step. The nodes and edges and their associated features defined as:
Ds denotes the node corresponding entity i in mTSP problem. The node feature æ; for vú is equal to the state s² of entity i. In addition, k; denote the type of node v;. For instance, if the entity i is worker and its poetive = 1, then the A; becomes active-worker type.
Eij denotes the edge between between source node vi and destination node v;, representing the relationships between the two. The edge feature Wiy is equal the Euclidean distance between the two nodes.
4.2 TYPE-AWARE GRAPH ATTENTION EMBEDDING
In this section, we describe type-aware graph attention (TGA) embedding procedure. We denote h; and hu the node and the edge embedding, respectively, at given time step, and h/ and h as the updated embedding by TGA embedding. A single iteration of TGA embedding consists of three phases: (1) edge update, (2) message aggregation, and (3) node update.
4

---

Under review as a conference paper at ICLR 2021
Type-aware Edge update Given the node embeddings h, for us V and the edge embeddings his for Egj E E, ScheduleNet computes the updated edge embedding hl and the attention logit 2ij as:
Rlg TGAg (he h higl k2) Zij T h2, hayl ky)
where TGAg and TGAA are, respectively, the type-aware edge update function and the type-awan attention function, which are defined for the specific type kn of the source node Vj. The updated edge feature Ri, can be thought of the message from the source node V; to the destination node ve and the attention logit Zij will used to compute the importance of this message.
In computing the updated edge feature (message), TGAg and TGA first compute the "type-aware" edge encoding Wij, which can be seen as a dynamic edge feature varying depending on the source node type, to effectively model the complex type-aware relationships among the nodes. Using the computed "type-aware" edge encoding U4j. these two functions then compute the updated edge feature and attention logit using multiplicative interaction (MI) layer (Jayakumar
al.] 2019). The use of MI layer significantly reduces the number of parameters to learn without discarding the expressibility of the embedding procedure. The detailed architecture for TGAg and TGA, provided in Appendix A.4
Type-aware Message aggregation The distribution of the node types in the mTSP graphs is highly imbalanced, i.e., the number of task-specific node types is much larger than the worker specific ones. This imbalance is problematic, specifically, during the message aggregation of GNN, since permu- tation invariant aggregation functions are akin to ignore messages from few-but-important nodes in the graph. To alleviate such an issue, we propose the following type-aware message aggregation scheme.
We first define the type & neighborhood of node vs as the set of the k typed source nodes that are connected to the destination node Us i.e., NN((i) {wikkr k, Vay E [N()), where M(i) is the in-neighborhood set of node 2 containing the nodes that are connected to node e with incoming-
edges.
The node ii aggregates separately messages from the same type of source nodes. For example, the aggregated message m. from k-type source nodes is computed as:
m
Σ anyhky
JENL()
where Oij is the attention score computed using the attention logits computed before as:
exp(2g)
EjeN (s) exp(21g)
Finally, all aggregated messages per type are concatenated to produce the total aggregated message m; for node U; as
concat((nii E K})
(4)
Type-aware Node update The aggregated message m; for node v; then used to compute the updated node embedding li using the type-aware graph node update function TGAy as:
h TGAv mc], ks)
(5)
4.3 ASSIGNMENT PROBABILITY COMPUTATION
ScheduleNet model consists of two type-aware graph embedding layers that utilize the embedding procedure explained in the section above. The first embedding layer raw-2-hid is used to encode initial node and edge features I; and wij of the (full) graph G., to obtain initial hidden node and
(0) h and h respectively.
edge features
We define the target subgraph G as the subset of nodes and edges from the original (full) graph Gr that only includes target-worker mmassigned-worker node and all unassigned-city nodes. The
5

---

Under review as a conference paper at ICLR 2021
second embedding layer hid-2-hid embeds the target subgraph Gü H times. In other words, hidden node and edge embeddings 4 and hi are iteratively updated И times to obtain final hidden embeddings ( and h, respectively. The final hidden embeddings are then used to make decision regarding the worker-to-tee assignment.
Specifically, probability assigning target worker i to task j is computed as
Vij = MIP (h) 1 ( 2ig (1))
(6)
Pij softmax ((vn) A(G+))
where the h! and h the final hidden node, edge embeddings, respectively, In addition, AGG)) denote the feasible actions defined as {uylk, "Unassigned-tase v/j E V).
5 TRAINING SCHEDULENET
In this section, we describe the training scheme of the ScheduleNet. Firstly, we explain reward normalization scheme which is used to reduce the variance of the reward. Secondly, we introduce stable RL training scheme which significantly stabilizes the training process.
Makespan normalization As mentioned in Section 3.1 we use the makespan of mTSP as the only reward signal for training RL agent. We denote the makespan of given policy as M().. We observe that, the makespan (Tr) is highly volatile depending on the problem size (number of cities and salesmen), the topology the map, and the policy. To reduce the variance of the reward, propose the following normalization scheme:
M(TT) M(T)
m( Tb)
M (Tb)
where i and na the evaluation and baseline policy, respectively.
The normalized makespan m(л, mb) is similar to (Kool et al. (2018), but we additionally divide the performance difference by the makespan of the baseline policy, which further reduces the variance that is induced by the size of the mTSP instance.
From the normalized terminal reward m( mb), we compute the normalized return as follows:
mT) where T is the index of the terminal state, and y is the discount factor.
G (T, Tb)
The normalized return G, (T,, T&) becomes smaller and converges to (near) zero 7 decreases. From the perspective the RL agent, allows the agent to acknowledge neutrality of current policy compared to the baseline policy for the early phase of the MDP trajectory. It is natural since knowing the relative goodness of the policy hard from the early phase of the MDP.
Stable RL training It is well known that the solution quality of CO problems. including the makespan of mTSP, is extremely sensitive the action selection, and thus prevents the stable policy learning. To address this problem, propose the clipped REINFORCE, variant PPO with- out the learned value function. We empirically found that it hard to train the value function thus normalized returns GT(TT, To) directly. Then, the objective of the clipped REINFORCE is given as follows:
(())
mmnn(cip((pr) e, e)GT mb), GT mb))] T
Note that the value function is trained to predict the makespan of the state to serve as an advantage esti- mator. Due the combinatorial nature of the m mTSP, the target of value function, makespan, is highly volatile, which makes training value function hard. We further discuss this in the experiment section.

---

Under review as a conference paper at ICLR 2021
Table I: mTSP Unitorm Results. We report the mean and standard deviation of the makespans for different uniform maps. We evaluate 500 independent maps for each N and m pairs. The gaps between OR-Tools and ScheduleNet are measured per instances.
N 20
N 50
W/
171
10
OR-Tools
2.500:10.24
2.063:1.222
1.820-0.27
2.076=0.22
1.97410.27
1.951=1.29
ScheduleNet
2.7511:.27
2.2551:.22
1.948=0.28
2.372=0.23
2.176:0.26
2.098:10.28
2Phasc-NI
2.814+0.35
2.364=0.35
1.998=0.30
2.506=0.32
2.285 = 0.31
2.111 = 0.28
2Phasc-FI
3.028+0037
2.540=0.37
2.090=0.33
2.712=0.33
2.429 + 0.32
2.198 0.30
2Phase-RI -R
2.88911.37
2.441
2.040=0.32
2.584=0.33
2.351 + 0.31
2.144 = 0.29
2Phasc-NN
2.963=1041
2.456=0.38
2.028=0.32
2.611=0.33
2.348
+ 0.32
2.148 0.29
Gap (vs. OR-Tools)
1.102+0.07
1.095+0.06
0.01=0006
L.14==005
1.106+0.05
1.086=00007
N 100
N 200
me 5
m
TI 15
TI 10
m 15
m 20
OR-Tools
2.373++0.18
2.001=0.30
2.015=0.31
2.145 +0.24
2.302++0.27
2.383++0.61
ScheduleNet
2.88111.199
2.230=1.266
2.161=0.31
2.496=0.53
2.383:0.61
2.444
2Phase-NI
3.116:10.35
2.348+0.31
2.161=0.29
2.750 0,30
2.447: 0.31
2.250:1 0.29
2Phasc-FI
3.348+00.36
2.474#0.31
2.250=0.30
2.916 0.32
2.569+ 0.29
2.354 0.29
2Phase-RI
3.150110.34
2.40010.32
2.187-0.30
2.759 0.31
2.477 0.30
2.281 0.30
2Phase-NN
3.232:0.36
2.405#0.31
2.191=0.30
2.820 0.30
2.5041: 0.30
2.295 0.29
Gap (vs. OR Tools)
1.121:10.06
1.12310.09
1.07910.10
1.164 10.15
1.003:10117
0,954:10.19
where
To To(a, (T)
Pr To.i (a (T)
(10)
and (Gr, ~ my is the state-action marginal following no, and To,ea the old policy.
Training detail We used the greedy version of current policy the baseline policy лe- After updating the policy Te. we smooth the parameters of policy with the Polyak average (Polyak & Juditsky] 1992) to further stabilize policy training. The pseudo code of training and network architecture is given in Appedix A.5.I
Table 2: TSPLib results. The CPLEX results with optimial solutions. Otherwise, the known-best upper bound of CPLEX results are reported (mTS). Meta-heuristic results are repro- duced from Lupoaie et (201). The results of the two leading heuristic algorithms are provided here. The full results are given in the appendix A.7
Instance
CPLEX
OR-Tools
ScheduleNet
SOM
ACO
EA
2Phasc-NI
2Phase-B RI
2
222.73
243.02
259.67
278.44
248.76
276.62
271.25
265.85
172.16
202.85
eit51
5
123.96
127.5
118.94
157.68
135.09
151.21
183.53
150.49
112.07
112.07
112.42
136.84
119.96
123.88
129.65
127.72
2 4110021
4665.47
4816.3
5350.83
4388.99
5038.33
5941.03
5785.00
berlin
3
3244.37
3311131
3372.14
4197.61
3468.9 9
3865.45
38.1..9
4133.85
S
2482.57
2615.57
3461.93
2733.56
2853.63
2972.57
4108.58
7
2440.92
24-40,92
2576.04
3125.21
2510.09
2543.73
2972.57
2998.20
2 280.85
318
334.1
364.02
308.53
365.72
363.21
395.15 15
eil76
197.34
212.41
226.54
278.63
224.56
285.43
276.58
5
150.3
143.38
168.03
210.69
163.93
211.91
191.41
185.77
2
728.75
762.19
789.98
927.36
767.15
896.72
916.55
890.86
3
587.17
552.09
$79.28 28
756.08
620.45
739
802.
843.03
ka19
469.25
473.66
502.49
624.38
525.54
596.87
668.6
675.39
7
443.91
442.47
471.67
564.14
492.13
534.91
$54.19
565. 12
Gap (vs, optimal)
1.00
(.000.006
0.08++0.06
1.31 4-006
1.09++0.03
1.24-10.10
1.30++0.11
1.31-40.14

---

Under review as a conference paper at ICLR 2021
20 m
N m==55m m
2=200,
0.12
0.125
0.10
Probbiiity
0.100
0.0
0.055
0.06
0.15
0.04
0.025
0.05
0.000
0.00
0.00
09
1.0
1.2
11
1.2
0.6
0.8
100
QRP
Figure 3: Gap distributions of the random mTSP instances [Left] Small-size random instance
results, [Right] Medium size random instance results, [Right] Large-size random instance results
EXPERIMENTS
We train the ScheduleNet using mTSP instances whose number m of workers and the number N of tasks are sampled from m ~ (2,4)) and N ~ U(10, 20), respectively. This trained Schedu- leNet policy is then evaluated on the various dataset, including randomly generated uniform mSP datasets, mTSPLib (mTS), and randomly generated uniform TSP dataset, TSPLib, and TSP (dai). See Appendix for further training details.
6.1 MTSP RESULTS
Random mTSP results We firstly investigate the generalization performance of ScheduleNet on the randomly generated uniform maps with varying numbers of tasks and workers. We report the results of OR- OR-Tools and 2Phase heuristics; 2Phase Nearest Insertion (NI), 2Phase Farthest Insertion (FI), 2Phase Random Insertion (RI), and 2Phase Nearest Neighbor (NN). The 2Phase heuristics construct sub-tours by (1) clustering cities with clustering algorithm, and (2) applying the TSP heuristics within the cluster. The details of implementation are provided in the appendix.
Table shows that ScheduleNet in overall produces slightly longer makespan than OR-Tools even for the large-sized mTSP instances. As the complexity of the target mTSP instance increases, the gap between ScheduleNet and OR-Tools decreases, even showing the cases where ScheduleNet outperforms OR- OR-Tools To further clarify, ScheduleNet has potentials for winning the OR-Tools on small and large cases shown in the figure This result empirically proves that ScheduleNet, trained with small-sized mTSP instances, can solve large scale problems well. Notably, on the large scale maps, 2-Phase heuristics show their general effectiveness due to the uniformity of the city positions. It naturally invokes us to consider more realistic problems as discussed in the following section.
mTSPLib results The trained ScheduleNet is employed to solve the benchmark problems in mTT SPLib, without additional training, to validate the generalization capability of ScheduleNet seen mTSP instances, where the problem structure can be completely different from the instances used during training. Table 2 compares the performance of the ScheduleNet other baseline models, including CPLEX (optimal solution), OR-Tools, and other meta- meta-heurissies (Lupoaic et al.) 2019; self orga-nraanizttion Map (SOM), ant-colony Optimization (ACO), and evolutionary algorithm (EA). We report the best known upper-bound for CPLEX results whenever the optimal solution is not known.
OR-Tools generally shows promising results. Interestingly, OR-Tools also discovers the solution even better than the known upper-bounds. (e.g., eil76-m==,77, rat99-m=5) That is possible for the large cases the search space of the exact method, CLPEX, becomes easily prohibitively large. Our method shows the second-best performance following OR-tools. The winning heuristic methods, 2Phase-NI/RI, shows drastic performance degradation mTSPLib maps. It is noteworthy that our method, even in the zero-shot setting, performs better than the meta-heuristic methods, which perform optimization to solve each benchmark problem.
Computational times The mixed-iniee integer linear programming (MILP) formulated mTSP problem becomes quickly intractable due to the exponential growth of search space, namely subtour elim-
8

---

Under review as a conference paper at ICLR 2021
24
spartsn
Cléped REINFORCE PPO+spare
2.2
cist-uti
2.2
PPO+dttt
PPO
2.0
2.0
1.8
1.8
1.8
12
1.2
200 300
training step
training step
Figure 5: [Left] Effect of reward function The blue, orange, and green curve shows the training gap of the sparse reward, the distance reward, and distance-uilliation reward over the training steps, respectively. The shadow regions visualize one standard deviation from the mean trends. We replicates experiments per reward setup. [Right] Effect of training method The orange, green, and red curve shows the training gap of PPO model with the proposed spare, distance, and distance- utilization reward, respectively. We visualize the results of the clipped REINFORCE with the spare reward, which is denoted blue curve, for clear comparisons. The shadow regions visualize one standard deviation from the mean trends. We replicates 5 experiments per setup.
ination constraint (SEC), as the number workers increases. The computational gain of (Meta) heuristics, including the proposed method and OR-Tools, originates from the effective heuristics that trims out possible tours. The computational times of ScheduleNet linearly increase as the number of worker m increases for the number for the fixed number of task N due to the MDP formulation of mTSP On the contrary, it is found that the computation times of OR-Tools depend on m and N, and also graph topology. As result, the ScheduleNet becomes faster than OR-Tool. for large instances as shown in figure
6.2 EFFECTIVENESS OF THE PROPOSED TRAINING SCHEME
Figure compares the training curves of ScheduleNet and variants. We firstly show the effec- tiveness of the proposed sparse reward compared to the dense reward functions; distance reward and distance-utiizatton reward. The distance reward defined as the negative distance between the current worker position and the assigned city. This reward function is often used for solving uttiizainn is defined as distance reward over the number of
TSP(Dai et al. 2016). The active workers. This reward function aims to minimize the (sub) tour distances while maximizing the utilization of the workers. The proposed sparse reward is the only reward function that can train ScheduleNet stable and achieves the minimal gaps, also shown in [Left]
We also validate the effectiveness of Clipped REINFORCE compared to the actor-critic counterpart, PPO. We the same network architecture of the Clipped REINFORCE model for the actor and critic of the PPO model. Counter to the common belief, The actor-critic method (PPO) is not superior to the actor-only method (Clipped REINFORCE) as shown in [ [Right]. We hypothesize this phenomenon is because the training target of the critic (sampled makepsan) is highly volatile and multi- modal as visualized in Figure 4 and the value prediction error would deteriorate the policy due to the bellman error propagation in actor-critic setup as discussed in Fujimoto et al. (2018).
Sampled makespan
0.08
0.06
Probability
0.02
0.00
makespan
Figure makespan dis- tribution
CONCLUSION
We proposed ScheduleNet for solving MinMax mTSP, the problem seek- ing to minimize the total completion time for multiple workers to com- plete the geographically distributed tasks. The use of type-aware graphs and the specially designed TGA graph node embedding allows the trained ScheduleNet policy induce the coordinated strate-

---

Under review as a conference paper at ICLR 2021
gic subroutes of the workers and be well transferred to unseen mTSP with any numbers of workers and tasks. We have empirically shown that the proposed method achieves the performance compara- ble to Google OR-Tools, highly optimized meta-heuristic baseline. All in all, this study has shown the potential that the proposed ScheduleNet can be effectively used to schedule multiple vehicles for solving large-scale, practical, real-world applications.
REFERENCES
mTSPLib.
Sungsoo Ahn, Younggyo Seo, and Jinwoo Shin. Deep auto-deferring policy for combinatorial opti- mization. 2019.
Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 1.09940, 2016.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimiza- tion: methodological tour d'horizon. European Journal of Operational Research, 2020.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimiza- tion. In Advances Neural Information Processing Systems, pp. 6281-6292, 2019.
Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for struc-
tured data. In International conference on machine learning, pp. 2702-2711, 2016.
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprint 10X2v:1802.09477 2018.
Steven Gold and Anand Rangarajan. Softassign versus softmax: Benchmarks in combinatorial optimization. In Advances in neural information processing systems, pp. 626-632, 1996.
Ashley Hill, Antonin Raffin, Maximilian Ernestus, Adam Gleave, Anssi Kanervisto, Rene Traore, Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Rad- ford, John Schulman, Szymon Sidor, and Yuhuai Wu. Stable baselines. / comm hill-al http///tabbeebbeeaaaaa 2018.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8):
1735-1780, 1997.
John J Hopfield and David W Tank. "neural" computation of decisions in optimization problems. Biological cyberneties, 52(3):141-15,, 1985.
Yujiao Hu, Yuan Yao, and Wee Sun Lee. A reinforcement learning approuch for optimizing multiple traveling salesman problems over graphs. Knowledge-Bold Basee Systems, 204: 106244, 2020.
Siddhant M Jayakumar, Wojeiech M Czarnecki, Jacob Menick, Jonathan Schwarz, Jack Rae, Simon Osindero. Yee Whye Teh, Tim Harley, and Razvan Pascanu. Multiplicative interactions and where to find them. In International Conference on Learning Representations, 2019.
Yoav Kaempfer and Lior Wolf. Learning the multiple traveling salesmen problem with permutation invariant pooling networks. arXiv preprint arXiv:1803.088 006.1.99........ 2018.
Hyunwook Kang, Aydar Mynbay, James R Morrison, and Jinkyoo Park. Learning scalable and transferable multi-nobot/machine sequential assignment planning via graph embedding. arXiv preprint arXiv: 12000 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, pp- 2017.
Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.600 1412.6982 2014.
10

---

Under review as a conference paper at ICLR 2021
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.084755 2018.
Vlad-loan Lupoaie, Ivona-Alexandra Chili, Mihaela Elena Breaban, and Madalina Raschip. Som- guided evolutionary search for solving minmax multiple-tsp. In 2019 IEEE Congress on Evolu- lionary Computation (CEC), pp. 73-80. IEEE, 2019.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. arXiv preprint arXiv:2003.03600 2020.
Mohammadreza Nazari, Afshin Oroojlovy, 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 httpps///eevellpprs...o.....o..
iotiiiiaiion
Boris Polyak and Anatoli Juditsky. Acceleration of stochastic approximation by averaging.
SIAM journal on control and oplimization, 30(4):838-8))) 855,, 1992.
Samerkae Somhom, Abdolhamid Modares, and Takao Enkawa. Competition-basee neural network for the multiple travelling salesmen problem with minmax objective. Computers & Operations Research, 26(4):395 407, 1999.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information 2017.
processing systems, pp.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In Advances neural information processing systems, pp. 2692-2700, 2015.
E Wacholder, J Han, and RC Mann. A neural network algorithm for the multiple traveling salesmen problem. Biological Cybernetics, 61(1):11-11 1989.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 DETAILS OF MDP TRANSITION AND GRAPH FORMULATION
Event based MDP transition The formulated semi-MDP for ScheduleNet is event-based. Thus, whenever all workers are assigned to cities, the environment transits in time, until any of the workers arrives to the city (i.e. completes the task). Arrival of the worker to the city is the event trigger, meanwhile the other assigned workers are still on the way to their correspondingly assigned cities. We assume that each worker transits towards the assigned city with unit speed in the 2D Euclidean space, i.e. the distance travelled by each worker equals the time past between two consecutive MDP events.
Graph formulation In total our graph formulation includes seven mutually exclusive node type: (1) assigned-worker, (2) unossigeed-worke, (3) inactive-worker (4) assigned-city, (5) unassigned- city, (6) inactive-city, and (7) depot. Here, the set of active workers (cities) is defined by the union of assigned and unassigned workers (cities). Inactive-city node refers to the city that has been already visited, while the inactive- worker node refers to the worker that has finished its route and returned to the depot.
A.2 DETAILS OF IMPLEMENTATION
2phase mTSP heuristics 2phase heuristics for mTSP is an extension of well-known TSP heuristics to the m > cases. First, we perform K-means spatial clustering of cities in the mTSP instance, where K m. Next, we apply TSP insertion heuristics (Nearest Insertion, Farthest Insertion, Random Insertion, and Nearest Neighbour Insertion) for each cluster of cities. It should be noted that, performance of the 2phase heuristics is highly depended on the spatial distribution of the cities on the map. Thus 2phase heuristics perform particularly well uniformly distributed random instances, where K-means clustering can obtain clusters with approximately same number of cities per cluster.
Proximal Policy Optimization Our implementation of PPO closely the standard implementation of PPO2 from stable-baselines (Hill et al. 2018) with default hyperparameters, with modifications to allow for distributed training with Parameter Server.
A.3 COMPUTATION TIME
Figure 6 shows the computation time curves as the function of number of cities (left), and number of workers (right). Overall, ScheduleNet faster than OR-Tools, and difference in computation speed only increases with the problem size. Additionally, ScheduleNet's computation time depends only on the problem size (N + m), whereas the computation time of OR- OR-Tools on both the size of the problem and the topology of the underlying mTSP instance. In other words, the number of solutions searched by OR- Tools vary depending on the underlying problem.
Another computational and practical advantage of the ScheduleNet is its invariance the number of workers. Computational complexity of ScheduleNet increases linearly with the number workers. On the other hand, the search space of meta-heuristic algorithms drastically increase with the number of workers, possibly, due to the exponentially increasing number Subtour Elimination Constraints investigated that OR-Tools decreases the search space, by deactivating part of the workers. i.c. not utilizing all possible partial solutions (subtours). As result, Figure shows that computation time of the OR-Tools actually decrease due deactivation part of workers, the expense of the decreasing solution quality.
(SEC). Particularly,
A.4 DETAILS OF TYPE-AWARE GRAPH ATTENTION EMBEDDING
In this section, we thoroughly describe rype-aware graph embedding procedure. Similar to the main body, We overload notations for the simplicity of notation such that the input node and edge feature h; and hij. and the embedded node and edge feature h/2 and My. respectively.
The proposed graph embedding step consists of three phases: (1) type-aware edge update, (2) type- aware message aggregation, and (3) type-aware node update.
12

---

Under review as a conference paper at ICLR 2021
Fixed number of workers (m=5)
Flxed number of cltes (N-100)
mothhd
method
Computzatoor time (505)
200
OR-Toola
ScheduleNee
80
ScheduleNet
OR-Too's
45
150
time
40
100
36
80
20
0
16
40
80
100
140
10
12
(N)
(m)
Figure 6: Computation time of ScheduleNet and OR-Tools. Figures show the computation time (in seconds) of ScheduleNet and OR-Tools of workers (right). We sample 10 mTSP instances per N-m combination for OR-Tools due to variability in the runtime due to underlying instance's topology. We measure all times on CPU
function of number of cities (left) and number
machine equip AMD Ryzen Thereadripper 29990WX without any parallelization.
Type-aware Edge update The edge update scheme designed to reflect the complex type relation- ship among the entities while updating edge features. First the context embedding Cij of edge eij computed using the source node type ky such that:
Cj = MLP (lPe))pp((k))
(11)
where MLPerype is the edge type encoder. The source node types are embedded into the context embedding Czj using MLPetgpes Next, the type-aware edge encoding Ui is computed using the Multiplicative Interaction (MI) layer (Jayakumar et al.) 2019) as follows:
Uij Mledge ((he; hy; hegl, cig)
(12)
where Mledge is the edge MI layer. We utilize the MI layer, which dynamically generates its pa- rameter depending on the context Gy and produces "type-aware" aware" edge encoding Majs to effectively model the complex type relationships among the nodes. "type-aware" edge encoding Vi can be seen as a dynamic edge feature which varies depending on the source node type. After the updated edge embedding hi and its attention logit 2j is obtained as:
h/ MLP edge (uig)
(13)
Z/j MLP actn (Miz)
(14)
where MLPede edge and MLPats, is the edge updater and logit function, respectively. the edge updater and logit function produces updated edge embdding and logits from the "type-aware" edge.
The computation steps of equation 11
12 and 13 are defined as TGAg, Similarly, the computation steps of equation [1 12 and 14 are denned TGA
Message aggregation First, we define the type-k neighborhood of node such that N&(i) {uz ky = k, Vuz E (i)), where Niii) is the in-neigborhood set of node i. i.e., The type-k neigh- borhood is the set of edges heading node i, and their source nodes have type k. The proposed type-aware message aggregation procedure computes attention score asj for the eij, which starts from node and heads to node i, such that:
exp(z4)
(15)
EieNi, exp(za)
Intuitively speaking, The proposed attention scheme normalizes the attention logits of incoming edges the types. Therefore, the attention scores sum up to 1 over each type-k neighborhood.
13

---

Under review as a conference paper at ICLR 2021
Message Aggregation
Type-aware Node Update
MI node
MLP node
h'4
Σ
MLParype
mi,k
K
h4
Figure 7: Type-aware graph attention embedding We omit the type-aware edge update for the clarity of visualization.
Next, the type-k neighborhood message mi,k for node is computed as:
m
anyhky
(16)
JEN(
In this aggregation step, the incoming messages of node are aggregated type-wisely. Finally, all incoming type neighborhood messages are concatenated produce (inter-type) aggregated message my for node U; such that:
m, concat((mi) k E IK))
(17)
Node update Similar to the edge update phase, first, the context embedding e computed for each node ny:
C MLP mttpee (kz)
(18)
where MLP ntype is the node type encoder. Then, the updated hidden node embedding hς is com- puted below:
K = MLP (h,, u4)
(19)
where MInode (m, (i) is the type-aware node embedding that is produced by MInade layer using aggregated messages m, and the context embedding G.
The computation steps of equation 18 and 19 are defined TGAg. The overall computation pro-
cedure TGA is illustrated in Figure
A.S DETAILS SCHEDULENET TRAINING
A.5.1 TRAINING PSEUDO CODE
In this section, we presents pseudocode for training ScheduleNet.
Algorithm 1: ScheduleNet Training
Input: Training policy xe
Output: Smoothed policy Te
Initialize smoothed policy with parameters á +- 0.
for update step do
Generate random mTSP instance I
for number of episodes do
Construct mTSP MDP from the instance
Ty < arg max(#²)
Collect samples with and Ti from the mTSP MDP.
+ me
for inner updates K do
L 0 - 0 + (
10
11
3 + (1 3)8
14

---

Under review as a conference paper at ICLR 2021
A.5.2 HYPERPARAMETERS
In this section, we fully explain hyperparameters ScheduleNet.
Network Architecture We use the same hyperparmeters for the raw-2-hid TGA layer and the hid- 2-hid TGA layer. M MLPaype atype and M LP has one hidden layer with 32 neurons and their output dimensions are both 32. Both MI layers has 64 dimensional outputs. M edge. M L.LPauo and M bode has hidden layers with neurons. L.ctto has 2 hidden layers and the hidden layers has 128 neurons each. We use ReLU activation functions for all hidden layers. The hidden graph embedding step H two.
Training We use the discount factor of 0.7. We use Adam (Kingma & Ba 2014) with learning rate value 0.001. We set the clipping parameter as 0.2. We sample 40 independent mSSP trajectories gradient update. We clipped the maximum gradient whenever the norm of gradient is larger than 0.5. Inner updates steps K is three. The smoothing parameter |3 is 0.95.
A.6 TRANSFERABILITY TEST ON TSP (m = 1)
The trained ScheduleNet has been employed to solve random TSP instances. Because ScheduleNet can be used to schedule any m number of workers, if we set m 1, it can be used to schedule TSP instance without further training. Table shows the results on this transferability experiments.
Table shows that the trained ScheduleNet can solve reasonably well on random TSP instances, although ScheduleNet has never been exposed such TSP instances. Note that as the size of TSP increases, the gap between the ScheduleNet and other models becomes smaller. If the ScheduleNet trained with TSP instances with m 1, the performance can be further improved. However, we did not try that experiment to check its transferability over different types of routing problems with different objectives.
Table 3: Performance comparison on random uniform TSP instances.
The Obj. defines the
makespan, i.e., the length of the tour of the salesman.
N 20
N = 50
N = 100
Method
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Concorde
3.84
0.00%
(1m)
5.70
0.00%
(2m)
7.76
0.00%
(3m)
LKH3
3.84
0.00%
(18s)
5,70
0.00%
(5m)
7.76
0.00%
(21m)
Gurobi
3.84
0.00%
(7s)
5.70
0.00%
(2m)
7.76
0.00%
(17m)
Nearest Insertion
4.33
12.91%
(1s)
6.78
19.03%
(2s)
9.46
21.82%
(6s)
Farthest Insertion
3.93
2.36%
(1s)
6.01
5.53%
(2s)
8.35
7.59%
(7s)
OR-Tools
3.85
0.37%
(1s)
5.80
1.83%
(2s)
7.99
2.90%
(7s)
Bello et al. (2016)
3.89
1,42%
5.95
4.46%
8.30
6.90%
Khalil al. (2017)
3.89
1.42%
5.99
5.16%
8.31
7.03%
AM (greedy)
3.85
0.34%
(0s)
5.80
1.76%
(2s)
8.12
4.53%
(6s)
(sampling)
3.84
0.08%
(5m)
5.73
0.52%
(24m)
7.94
2.26%
(Ih)
ScheduleNet
4.01
4.34%
(2s)
6.11
7.01%
(9s)
8.71
12.35%
(34s)
A.7 EXTENDED MTSPLIB RESULTS
15

---

Under review as a conference paper at ICLR 2021
2phase NN
387.20
222.13
210.75
147.81
6519.51
3581.1 1.21
3581.21
3198.18 18
373.75
357.77
197.54
161.36
929.82
809.90 809.90
641.89 19.889
504.71
1,40
2phase RI
265. .85
195.89
150.49.
127.72
5785.00
4133.85
4108.58 08.58
2998.20 20
395.15
276.58
185.77
155.54
890.86
843.03
675.39
565.12
1.31
Heuristics
2phase Fl
311.26
218.71
180.21
144.11
6605.05
4037.10
4037.10
3033.00
403.56
279.33
204.16
172.94 .4
965.94
802.88 88
645.91
$77.00
1.38
2phase NI
271.25
202.85
183.53
129.65
5941.03
3811.49
2972.57
2972.57
363.21
302.1
191.41
173.81
916.55
802.84 84
668.6
554.19
1.30
EA
276.62
208.16
151.21
123.88
5038.33
3865.45
2853.63
2543.73
365.72
285.43
211.91
177.83
896.72
739.43
596.87
534,91
1.24
Meta heuristics
ACO
248.76 76
180.59
119.96
4388.99
3468.9
2733.56
2510.09
308.53
224.56
163.93
146.88
767.15
620.45
525,54
492.13
1.09
135
SOM
278 44
210.25
157.68
136.84
5350.83
4197.61
3461 1461.93
3125.21
364.02
278.63
210.69
183.09
927.36
756.08
624.38
564.14 14
1.31
SN
259.67
172.16
118.94
112.42
4816.3
3372.14
2615.57
2576.04
334.1
226.54
168.03
151.31
789.98
579.28
502.49
471.67
1.08
OR
243.02
170.05
127.5
112.07
4665.47 .47
3311.31
2482.57
2440.92
92
318
212.41
143.38
128.31
762.19
552.09
473.66
442.47
1.03
CPLEX
222.73
159.57
123.96
112.07
4110.21
3244.37
2441.39 ...9
2440.92
280.85
197.34
150.3
139.62 62
728.75
587.17
469.25
443.91
711
3
2
2
e15
berlin
c
rat99
gap
16


Reviews:
[{"review_id": "r0LDSStHGC", "reviewer": "AnonReviewer1", "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": "The mTSP with the goal of minimizing the longest route is considered, which minimizes the maximum route. This objective results in a balanced-length set of routes, which compared to the sum of routes obtains a more practical result. A graph representation based on the worker and assigned tasks is defined, then a type-aware graph attention (TGA) embedding procedure is proposed in which it obtains an embedding for node and edge representation. The state for each entity involves the 2D coordinates of the entity and the boolean indicator of idleness and assigned task of the worker. The action is worker-to-task assignment, and the reward is the makespan of finishing the problem, which is a sparse function. In type-aware graph attention (TGA) embedding, the embedding of node and edge are obtained and using the attention mechanism, an important weight for the embedding of each edge is obtained. The embedding functions are type-dependent which means the embedding considers the source node-type. The final message value for each node is obtained by multiplying the weight and edge embedding value of its neighbors. Then, an MLP is used to obtain a value for each source and possible target node, which takes the final value of the source, target, and edge between those as input. Then, the output of the MLP is used to get the final probability of choosing the next node.\n\nMajor comment: \nThe proposed algorithm looks interesting. Specifically, this problem can be modeled as multi-agent cooperative RL problem, and this paper suggests a model to handles it as a single RL problem. (For example, see paper [1] which suggests a multi-agent approach for a similar problem). However, the numerical results do not suggest a competitive algorithm yet and there are several baselines which obtain smaller objective in a smaller time, and yet it does not make sense to solve mTSP with a RL method. Note that this is not the case in VRP, since the current non-learning/non-commercial algorithms are not powerful in solving even medium-size problems with 50 nodes.\n\n[1] Zhang, Ke, et al. \"Multi-Vehicle Routing Problems with Soft Time Windows: A Multi-Agent Reinforcement Learning Approach.\" arXiv preprint arXiv:2002.05513 (2020).\n\n+\n\nminor comment:\nThe citation of mTSPLib is missing. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "gOu69LaeVD-", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "The authors propose an RL framework, called ScheduleNet trained by clipped REINFORCE, for minmax multiple traveling salesman problem (minimax mTSP), which uses a clipping idea to stabilize learning process as PPO does. The authors empirically show the feasibility of the proposed framework.\n\n- Unfortunately, the proposed method has poorer performance than existing works, in particular, OR-Tool. This decreases the merit significantly.\n\n- In addition, it is hard to find contribution from proposing new RL method since the stabilizing effect of the clipped REINFORCE is shown in only limited environment (only minimax mTSP).\n\n- Table 2 is not completed.\n\n- The nature of \"minimax\" mTSP should be more clearly represented and exploited. Currently, the proposed RL framework seems to work for other formation of mTSP, and also it seems not to exploit the nature of minimax.\n\n- In order for showing novelty of the proposed method, it might be useful to devise and investigate actor-critic methods sharing the main idea. In the submission, only footnote 1 simply mentions the hardness of learning value function.\n\n- The behavior of ScheduleNet need to be studied further, e.g., when your algorithm works well, and not.", "extra_scores": {}, "extra_text": {}}, {"review_id": "d0mcg8kxVVa", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n-------------\nThe paper proposes a reinforcement learning approach to solve the min-max multiple TSP, where there are multiple salesmen and the goal is to minimize the longest subtour while every city is visited by one salesman. The authors propose an architecture, ScheduleNet, that encodes a partial solution or state and outputs a policy, i.e. a probability distribution over the actions. They train the model using a variant of the REINFORCE algorithm. The approach is validated on randomly generated mTSP instances as well as the standard literature benchmark TSPlib.\n\n\nStrong points\n-------------------\n1. The addressed problem, TSP with multiple salesmen is an important combinatorial problem that is more challenging than the standard TSP because of the multi-agent cooperation that it involves. It is true that although there is a lot of literature on learning-based approaches that solve the TSP, only a few very recent papers deal with the multiple agent setting\n2. The MDP formulation with the notion of events is sound and clearly explained. It is more sophisticated than the standard MDPs used in the “one agent” setting\n3. The type-aware embeddings are interesting here to differentiate the interactions between the different types of nodes.\n\n\nWeak points\n-----------------\n4. The numerical experiments are not convincing me that the approach would be useful in practice  \n5. To be informative, results in Table 1 should be the average over a number of random instances for each characteristic. Maybe it’s already the case but it is not mentioned. Moreover, the random instances should also follow different distributions to be varied and really helpful to evaluate the method.\n6. Table 1 and 2: I found the reported gap (fraction of objectives) not so clear to get a precise sense of the performance. In Table 2, using the standard (approximate) optimiality gap would be better (obj_heuristic – obj_cplex)/obj_cplex. \n7. It would be informative to report CPLEX results for the randomly generated instances as well.\n8. Although the TSP is a natural special case of mTSP, the performance on of the approach on randomly generated TSP instances (cf Table 3) is significantly poorer than that of other learned heuristics. It would be useful to report the results for TSPlib as well.\n9. The authors claim that they propose a new approach for training “Clipped REINFORCE, a variant of clipped PPO without the learned value function”. It would be useful to give more explanations for this choice.\n10. In equation (9), I believe there is a missing sum over \\tau. This does not help in understanding \n\n\nRecommendation\n-------------------------\nI would vote for reject. In summary, the proposed approach is an adaptation of known techniques, to a specific interesting problem, that does not lead to a clear gain in performance.\n\nArguments for recommendation\n---------------------------------------------\n11. The MDP framework and type-aware GNNs are interesting and new in this context but not novel \n12. To me, the numerical experiments are very limited and do not demonstrate the added-value of this method, see weak points above\n\n\nQuestions to authors\n-----------------------------\n13. Sec 4.1: It is said that you consider the complete graph and that the edge features are the Euclidian distance which is symmetric. So what is the point of using a *directed* graph?\n14. Sec 4.1: “v_i denotes the node corresponding entity i in mTSP problem”. It sounds like v_i is a node of the graph. But if at \\tau a worker is in between two cities, what would be v_i?\n15. Sec 4.1: what are the types exactly? You give an example “active-worker” but it would be useful to list them all.\n16. Sec 4: There is a confusion between source and destination indices. “eij denotes the edge between between source node vi and destination node vj” but then for the edge embedding “the specific type kj of the source node vj” and “the message from the source node vj to the destination node vi”. Similarly, equation (2), it is confusing to use j as a source index.\n17. Sec 4.2: the definition of Nk(i) = {vj |kj = k, ∀l ∈ N (i)} does not make sense. What is the correct one? Because the graph is complete, is N(i) different from the entire V? \n18. Sec 5: “\\pi_b is the evaluation and baseline policy”. What baseline did you use?\n19. Sec 5: equation 8, can you explain the choice of the exponent of gamma?\n20. Sec 6:  “m ∼ U(2, 4) and N ∼ U(10, 20)”. Are m and N switched here? Otherwise there would be more workers than cities.\n21. Table 2: what are SOM, ACO and EA? These baselines should be described (at least named) in the text.\n\nFeedback to help improve the paper\n--------------------------------------------------\n22. “For the clarity of explanation, we will refer to salesman as a workers, and cities as a tasks.” I actually found it more confusing. Especially because task is standardly used to refer to the entire problem that the RL algorithm is addressing\n23. “We define the set of m salesmen VT = {1, 2, ..., m}, and the set of N cities VC = {m+1, 2, ..., m+ N}” -> set of m salesmen *indexed by* VT = {1, 2, ..., m}, and the set of N cities *indexed by* VC = {m+1, 2, ..., m+ N}\n24. “CPLEX results are reported as the average of the upper and lower bound”. It would make more sense to report the upper bound, i.e. the value of the best feasible solution found by the solver within the time limit.\n25. To be able to better generalize to the TSP instances, why not include instances with N=1 during training.", "extra_scores": {}, "extra_text": {}}, {"review_id": "7tweN75oHy7", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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 of the paper:\nThis paper proposes a deep reinforcement learning (DRL) approach for learning a solution strategy for the minimum-makespan multiple Traveling Salesman Problem (mTSP). The makespan mTSP is a challenging combinatorial optimization problem in which we are given the 2-dimensional locations of a set of customers that must be visited by a (much smaller) set of trucks. The trucks depart from the same depot, and must return to it after their tours. The minimum makespan version of mTSP asks for a set of such tours such that the length of the longest tour is minimized.\n\nThis work is part of a recent interest in using machine learning to design algorithms for hard discrete optimization problems. A number of such methods have been proposed for the standard TSP problem, but the minimum-makespan mTSP brings a number of challenges: the makespan is a sparse reward signal in RL terms, in that it is realized only after a full solution has been constructed (at the end of the episode); unlike the TSP, the mTSP has multiple trucks to be managed at every iteration of a sequential constructive algorithm.\n\nThe authors make two main contributions towards establishing a DRL approach to min-makespan mTSP:\n\n1- They propose a specialized graph neural network architecture which combines known ingredients in a way that is suitable to the structure of the mTSP;\n\n2- They modify the RL training algorithm to take into account the intricate discrete structure of the makespan objective, which stabilizes the training process.\n\nExperimentally, the proposed ScheduleNet method is trained on a single set of random instances with a small number of customers and trucks, then tested on similar and larger random instances, as well as some benchmark mTSP instances from the literature. Compared to some other learned and non-learned algorithms, ScheduleNet seems to be competitive.    \n\nStrengths:\n1- Interesting engineering of the graph network model and of the RL training procedure to take into account mTSP and makespan structure;\n\n2- Generalization from very tiny instances to much larger ones (though not too large in an absolute sense).\n\nWeaknesses:\n1- Experimental evaluation leaves many questions unanswered;\n\n2- Motivation for tackling yet another variant of the TSP is not very strong, in that it is unclear that practitioners solving mTSP in practice would be interested in using the proposed method. No discussion of how the ideas presented here could extend to other variants of TSP or significantly improve performance on some class of instances that are of great interest to the community or an application domain. \n\n3- Submission seems to have been rushed, with missing citations and weird captions in a couple places.\n\nRecommendation: Overall, I have to recommend a rejection, but I do think that the authors are on a good path towards a paper if they strengthen the motivation and experiments. I don't know if that will be possible within the ICLR rebuttal.\n\nQuestions to the authors:\n\n1- Table 1: how many instances are considered for each (N, m) pair here? Please provide standard deviations for the values provided here, without which it's hard to tell how stable the reported average makespan is.\n\n2- Table 1: Why was CPLEX not run on the MTSP Uniform instances as was done in Table 2? This way you can compute the exact approximation ratio.\n\n3- Table 1: Are the results reported for Hu et al. copied from that paper? If so, are you using the exact same set of graphs? If not, a direct comparison such as that claimed in Table 1 is not possible.\n\n4- Table 2: The caption is hard to parse. The following does not make sense: \"CPLEX results are reported as the average of the upper and lower bound.\" Instead, you should report the best solution found by CPLEX (i.e., the best upper bound at termination).\n\n5- Table 2: Please define SOM, ACO and EA, and cite the respective papers as well as any additional implementation details.\n\n6- OR-Tools: You should tune the parameters of OR-Tools (e.g., https://developers.google.com/optimization/routing/routing_options) on the same training set of instances that you train your model on. The tuning can be performed using some kind of grid search or more sophisticated tuning tools such as SMAC (https://github.com/automl/SMAC3).\n\n7- Running time results: There is no mention whatsoever of the running time of ScheduleNet (in training, but more importantly at test time), and how it compares to OR-Tools and the other heuristics of Table 1-2.\n\n8- ScheduleNet hyperparameters: You list the values but no mention of if/how they were tuned.\n\n9- Relation to VRP: mTSP is a special case of VRP in which there are no worker (truck) capacities. Have you considered comparing ScheduleNet to VRP learning approaches from the literature, such as Nazari et al. (which you cite)?\n\nMinor:\n- \"In this study, we formulate (MinMax mTSP as a Markov\" --> remove \"(\"\n- Section 3.1, \"Transition\": I find this paragraph hard to parse.\n- \"is equals to the makespan\" --> \"is equal to the makespan\"\n- \"since the following operations only for the given time step\" --> \"since the following operations only apply to the given time step\"\n- \"instances whose number m of tasks and the number N of workers are sampled\" --> shouldn't this be the opposite?\n- \"benchmark problems in mTSPLib (cite),\" --> please add the appropriate citation: https://profs.info.uaic.ro/~mtsplib/\n- Appendix: \"and produces and produces “type-aware”\"\n- Appendix: \"The computation steps of equation 11, 12,and ??\"\n- Appendix: \"hyperparameters of SchduleNet\" --> \"hyperparameters of ScheduleNet\"", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a deep reinforcement learning approach for solving minimax multiple TSP problem. Their main algorithmic contribution is to propose a specialized graph neural network to parameterize the policy and used a clipped idea to stabilize the training. Unfortunately, the reviewers remain to be unconvinced by the experiments after the rebuttal and the writing need to be significantly improved. Also, it would be worthwhile to study how the proposed method can generalize to other problems. 

Decision: Reject