Learning Collaborative Policies to Solve NP-hard Routing Problems
Authors: Minsu Kim
Jinkyoo Park
Joungho Kim
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep reinforcement learning
NP-hard
Policy collaboration
Hierarchical solving strategy

Abstract: Recently, deep reinforcement learning (DRL) frameworks have shown potential for solving NP-hard routing problems such as the traveling salesman problem (TSP) without problem-specific expert knowledge. Although DRL can be used to solve complex problems, DRL frameworks still struggle to compete with state-of-the-art heuristics showing a substantial performance gap. This paper proposes a novel hierarchical problem-solving strategy, termed learning collaborative policies (LCP), which can effectively find the near-optimum solution using two iterative DRL policies: the seeder and reviser. The seeder generates as diversified candidate solutions as possible (seeds) while being dedicated to exploring over the full combinatorial action space (i.e., sequence of assignment action). To this end, we train the seeder's policy using a simple yet effective entropy regularization reward to encourage the seeder to find diverse solutions. On the other hand, the reviser modifies each candidate solution generated by the seeder; it partitions the full trajectory into sub-tours and simultaneously revises each sub-tour to minimize its traveling distance. Thus, the reviser is trained to improve the candidate solution's quality, focusing on the reduced solution space (which is beneficial for exploitation). Extensive experiments demonstrate that the proposed two-policies collaboration scheme improves over single-policy DRL framework on various NP-hard routing problems, including TSP, prize collecting TSP (PCTSP), and capacitated vehicle routing problem (CVRP).

Learning Collaborative Policies to Solve NP-hard Routing Problems
Minsu Kim
Jinkyoo Park Joungho Kim
Korea Advanced Institute of Science and Technology (KAIST)
i School of Electrical Engineering. f Dept. Industrial & Systems Engineering {min-su, jinkyoo parky, joungho)&kaise ac.kr
Abstract
Recently, deep reinforcement learning (DRL) frameworks have shown potential for solving NP-hard routing problems such the traveling salesman problem (TSP) without problem-specific expert knowledge. Although DRL can be used to solve complex problems, DRL frameworks still struggle to compete with state-of-the-art heuristics showing substantial performance gap. This paper proposes a novel hierarchical problem-solving strategy, termed learning collaborative policies (LCP), which effectively find the near-optimum solution using two iterative DRL policies: the seeder and reviser. The seeder generates as diversified candidate solutions possible (seeds) while being dedicated to exploring over the full combinatorial action space (i.e., sequence of assignment action). To this end, we train the seeder's policy using simple yet effective entropy regularization reward to encourage the seeder to find diverse solutions. On the other hand, the reviser modifies each candidate solution generated by the seeder; partitions the full trajectory into sub-tours and simultaneously revises each sub-tour to minimize its traveling distance. Thus, the reviser is trained to improve the candidate solution's quality, focusing on the reduced solution space (which is beneficial for exploitation). Extensive experiments demonstrate that the proposed two-policies collaboration scheme improves over single-policy DRL framework on various NP-hard routing problems, including TSP, prize collecting TSP (PCTSP), and capacitated vehicle routing problem (CVRP).
Introduction
Routing is a combinatorial optimization problem, one of the prominent fields in discrete mathematics and computational theory. Among routing problems, the traveling salesman problem (TSP) is canonical example. TSP can be applied to real-world problems in various engineering fields, such as robot routing, biology, and electrical design automation (EDA) [1, 3, 4, 5] by expanding constraints and objectives to real-world settings coined TSP variants are expanded version of TSP. However, TSP and its variants are NP-hard, making challenging design an exact solver [6].
Due to NP-hardness, solvers of TSP-like problems rely on mixed-integer linear programming (MILP) solvers [7] and handcrafted heuristics [8, 9]. Although they often provide remarkable performance on target problems, the conventional approaches have several limitations. Firstly, the case of MILP solvers, the objective functions and constraints must be formulated into linear forms, but many real-world routing applications. including biology and EDA, have a non-linear objective. Secondly, handcrafted heuristics rely on expert knowledge on target problems, thus hard to solve other problems. That is, whenever the target problem changes, the algorithm must also be re-designed.
Deep reinforcement learning (DRL))routing frameworks [10, 11, 12] is proposed to tackle the limitation of conventional approaches. One of the benefits of DRL is that reward DRL can be any
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

value, even from a black-box simulator; therefore. DRL can overeome the limitations of MILP on real-world applications. Moreover, DRL frameworks can automatically design solvers relying less on a handcrafted manner.
We note that the main objective of our research is not outperforming problem-specific solvers like the Concorde [9], a TSP solver. Our problem-solvin strategy based on DRL, however, ultimately focuses on practical applications' including intelligent transportation [13], biological sequence design [14], routing on electrical device [15] and device placement [16, 17]. Therefore, this paper evaluates the performance of DRL frameworks on TSP-like problems as benchmark for potential applicability to practical applications, including speed, optimality, scalability, and expand-ability to other problems. TSP-like problems are excellent benchmarks as they have various baselines to compare with and can easily be modeled and evaluated.
Contribution. This paper presents novel DRL scheme, coined learning collaborative policies (LCP), a hierarchical solving protocol with two policies: seeder and reviser. The seeder generates various candidate solutions (seeds), each of which will be iteratively revised by the reviser to generate fine-tuned solutions.
Having diversified candidate solutions is important, it gives a better chance to find the best solution among them. Thus, the seeder is dedicated to exploring the full combinatorial action space (i.e., sequence of assignment action) that it can provide diversified candidate solutions as possible. It is important to explore over the full combinatorial action space because the solution quality highly fluctuates depending
its composition; however, exploring over the combinatorial action space is inherently difficult due to its inevitably many possible solutions. Therefore, this study provides an effective exploration strategy applying an entropy maximization scheme.
The reviser modifies each candidate solution generated by the seeder. The reviser is dedicated to exploiting the policy (i.e., derived knowledge about the problem) to improve the quality of the candidate solution. The reviser partitions the full trajectory into sub-tours and revises each sub- tour to minimize its traveling distance in parallel manner. This scheme provides two advantages: (a) searching over the restricted solution space can be more effective because the reward signal corresponding the sub-tour is less variable than that of the full trajectory when using reinforcement learning to derive a policy, and (b) searching over sub-tours of seeds can be parallelized to expedite the revising process.
The most significant advantage of our method is that the reviser can re-evaluate diversified but underrated candidates from the seeder without dropping it out early. Since the seeder explores the full trajectory, there may be mistake in the local sub-trajectory. Thus, it is essential to correct such mistakes locally to improve the solution quality. The proposed revising scheme parallelizes revising process by decomposing the full solution and locally updating the decomposed solution. Thus allows the revisers to search over larger solution space in single inference than conventional local search (i.e.. number of iteration of the reviser is smaller than that of conventional local search 2-opt [18]. or DRL-based 2-opt [19]), consequently reducing computing costs. Therefore, we can keep the candidates without eliminating them early because of computing costs.
The proposed method is an architecture-agnosti method, which can be applied to various neural architectures. The seeder and reviser can be parameterized with any neural architecture; this research utilizes AM [12], the representative DRL model on combinatorial optimization, to parameterize the seeder and the reviser. According to the experimental results, the LCP improves the target neural architecture AM [12], and outperforms competitive DRL frameworks on TSP, PCTSP, and CVRP (N = 20, 50, 100, 500, N number of nodes) and real-world problems in TSPLIB [20]. Moreover, by conducting extensive ablation studies, show proposed techniques, including entropy regularization scheme and revision scheme, clearly contribute to the performance improvement.
2 Related Works
There have been continuous advances in DRL. frameworks for solving various routing problems. DRL framework can generate solvers that do not rely on the ground-truth label of target problems: can be applied to un-explored problems. DRL-based approaches can be categorized into two parts;
'These works [13, 14, 15, 16, 17] are inspired by DRL frameworks [10, 12] combinatorial optimization

---

constructive heuristics and improvement heuristics. We survey these two categories and current emerging hybrid approaches of machine learning (ML) with conventional solvers.
2.1 DRL-baseed Constructive Heuristics
Bello et al. [10] introduced an actor-critic algorithm with a policy parameterized by the pointer network [21]. They proposed constructive Markov decision process (MDP), where the action is defined as choosing one of the un-served nodes to visit, given partial solution; the policy is trained to add a node to provide complete solution sequentially. Later, DRL-based constructive heuristics were developed to design the architecture of neural networks while preserving the constructive MDP [10]. Khalil al. [11] proposed DRL framework with a graph embedding structure. Nazari et al. [22]. Duedon et al. [23] and Kool et al. [12] redesigned the pointer network [21] using the transformer [24] and trained it with policy gradient method [25]. The AM by Kool et al. [12]
reports substantial results on various NP-hard routing problems, including TSP, PCTSP, CVRP, and orienteering problem (OP) in high-speed computation.
After the meaningful success of the AM, many studies are expanded from the AM. Many engineering fields and industries apply AM into their domain. For example, Liao et al. [4] proposed a routing algorithm for the circuit using AM.
AM-variants.
Some researches focus increasing the performances of AM on classic routing problems like TSP by simple techniques. Kwon et al. [26] proposed the POMO, effective reinforcement learning method for AM. They proposed new RL baseline that can reduce the training variance of AM using the problem-specine property of TSP and CVRP. In addition, they presented an effective post-processing algorithm for TSP and CVRP. However, their proposed method has limitation in that it is problem-specifie because it uses the domain properties TSP and CVRP (c.g., their method is limited be applied to PCTSP.).
Xin et al. [27] proposed AM-style DRL-model, MDAM, for NP-hard routing problems. Their method learns multiple AM decoders and derives various solutions through the multiple decoders. The goal of increasing the solution diversity is similar to our research. However, our study different where increases the entropy of a single decoder and improves the mistakes of various solutions through reviser.
2.2 DRL- Improvement Heuristics
Unlike the constructive MDP, DRL-based improvement heuristics are designed to improve the completed solution iteratively. Most researches on DRL-based improvement heuristics are inspired by classical local search algorithms such as 2-opt [18] and the large neighborhood search (LNS) [28].
Chen al. [29] proposed DRL-based local search framework, termed NeuRewriter, that shows a promising performance on CVRP and job scheduling problems. Wu et al. [30], and Costa et al. [31] proposed a DRL-based TSP solver by learning the 2-opt. Their method improves the randomly generated solutions, unlike the method of Chen et al. [29] rewrites a solution given by a conventional heuristic solver. Hottung& & Tiemnyy [32] proposed a novel search method of VRP that destroys and repairs a solution repeatably inspired LNS. Their method gives promising performances on CVRP.
Improvement heuristic approaches generally show better performance than constructive heuristics but are usually slower than constructive heuristics. In the case of TSP, the number of neural network's 's inferences of constructive heuristics is the same the number of citics to visit. However, the number of inferences of the improvement heuristics is generally much larger.
2.3 Hybrid Approaches with Conventional Solvers
There are several studies on hybrid approaches with conventional solvers having promising perfor- mance recently. Lu al. [33] proposed hybrid method, where the policy is learned to control improvement operators (handcrafted heuristic). Significantly, they outperforms the LKH3, which is widely considered as mountain to climb in machine learning (ML) communities. Joshi al. [34] combined graph neural network (GNN) model with the beam search algorithm. They trained the GNN with supervised learning for generating a hit map of candidate nodes. Then trained GNN reduces searching space for improvement heuristics. Similarly, Fu et al. [35] combined supervised
3

---

Seeding process
Revision process
Segments
Revisions
Composed revisions
Optimal TSP solution
decompooiiion (K=2)
Reviser
selecting after ilrr.
Sceder
composition
Revhurr
sanpple widhh
Ro-decempoosing-reviinng by times
Figure 1: Illustration of seeder-reviser collaboration for TSP.
GNN model with Monte Carlo tree search (MCTS) and Kool et al. [36] combined supervised GNN model with dynamic programming. Their method achieves significant performances, showing ML method can effectively collaborate with conventional operational research (OR) methods.
The research scope of hybrid approaches and DRL-based methods is different. Hybrid approaches can overcome classical solvers in target tasks by collaborating with the classical solvers. However, hybrid approaches have inherited limitations from classical solvers that poor expandability to other tasks. The DRL-based method can be applied to various real-world tasks without a classic solver; we can also utilize DRL-based to unexplored tasks. This paper investigates the DRL-based NP-hard routing method without the help of classical solvers.
Formulation of Routing Problems
This section explains the Markov decision process (MDP) formulation for the given 2D Fuclidean TSP as a representative example. The formulation MDP for other problems is described in Appendix A.I.
The main objective of TSP is to find the shortest path of the Hamiltonian cycle. The TSP graph can be represented as sequence of N nodes in 2D Euclidean space, {a; } where E RR. Then, the solution of TSP can be represented as the permutation π of input sequences:
U (m.) Te NJ, Te. * TT2
if t # t2
The objective is minimizing the tour length L(T(s) = 21=1 ||
Dr. llz + ||TTN
Fr. Fri l22.
Then, formulate the constructive Markov decision process (MDP) of TSP.
State. State of MDP is represented partial solution of TSP or a sequence of previously selected actions: T1:-11.
Action. Action is defined selecting one of un-served tasks. Therefore, action is represented Te where the тe E {{I,..., ".l,...,NT N} [T1:)-1])
Cumulative Reward. We define cumulative reward for solution (a sequence of assignments) from problem instance & as negative of tourlength: -L(r]s).
Constructive Policy. Finally we define constructive policy p( [s)s that generates solution π from TSP graph 8. The constructive policy p(T 8) decomposed as:
p T (8)
II pe Ti (1.-1188)
Where pe (T(TTTT 11 8) is single-step assignment policy parameterized by parameter 0.
4 Learning Collaborative Policies
This section describes novel hierarchical problem-solving strategy, termed learning collaborative policies (LCP), which can effectively find the near-optimum solution using two hicrarchical steps,

---

TSP
p (T (1:1)
p 11:22111
Seeds
Wt; Wtz
l/
starting node unvisited node visited node probability for visiting
WiJt (ne
Diversity of Seeds
Scaled Entropy Summation
Figure 2: Illustration of the seeding process. The diversity of seeds is approximated as the sum of scaled entropy of segment policy. The scheduler wi is for giving more weight when is in early step t than 12. In the early step f1, selecting rather than b is critical for the overall solution. In the latter step b2, even though the probability of selecting node and d equal (i.e., has high entropy), they may give similar solutions.
seeding process and revising process (see Figure for detail). In the seeding process, the seeder p policy pd generates M number of diversified candidate solutions. In the revising process, the reviser policy p re-writes each candidate solution 1 times minimize the tour length of the candidate. The final solution is then selected as the best solution among M revised (updated) candidate solutions. See pseudo-code in Appendix A.4 for detailed technical explanation.
4.1 Seeding Process
The seeder generates as diversified candidate solutions as possible while being dedicated to exploring the full combinatorial action space. To this end, the seeder trained to solve the following problems.
Solution space. Solution space of seeder is set of full trajectory solutions: { (T(),, (1),,,,,, (T()),.,,,x(M) (M)). The M is the number candidate solutions from the seeder: termed sample width.
Policy structure. Seeder a constructive policy, as defined section as follows:
1=N
p (T(S)
II pas (T (1t--1,
The segment policy Pas (Ty 11--11 s), parameterized by A is derived form AM [12].
Entropy Reward. To force the seeder policy pd to sample diverse solutions, we trained p such that the entropy H of 7d be maximized. To this end, we use the reward R. defined as:
R H
II Pos
Σ wiPl (n, pos Pos (T
The entropy of constructive policy is appropriate for measuring solution diversity. However, comput- ing the entropy of constructive policy is intractable because search space is too large: N!. Therefore, we approximate as a weighted sum of the entropy segment policies Pas ( 1, 8) evaluated at different time step.
N- to boost exploration at the earlier stage We use a linear scheduler (time-varying weights) w, NN of composing solution; higher randomness imposed by the higher weight w; at the early stage tends to generate more diversified full trajectories later. The N.,, is the normalizing factor, which is hyperparameter.
Training scheme. To train the seeder, we use the REINFORCE [25] algorithm with rollout baseline b introduced by Kool et al. [12]. Then the gradient of each objective function is expressed follows:
J (0 (s) Enayr (LL(T()) - a (pi.N. T)) a
b(s)) Vlog)\)
(2)
5

---

Random TSP:
Decomposed sub-tour
Solution Nieiskee for sub-tour
Starling Point
R2
Reward
p Ma
Portial Tour Lengh
Mailid
Muslos
Figure 3: Training progress of the reviser. From randomly generated TSP, sub- sub-problems are decom- posed. Then reviser infers to make constructive action referring starting and destination node and previous selected actions. The reward is a negative length of the partial tour generated from the reviser.
Note that the a hyperparameter for RS and Fi:N is the sequence of segment polices (pes 11 (1: 8)) 1=1- We use the ADAM [37] optimizer to obtain the optimal parameter #*
that minimizes the objective function.
4.2 Revision Process
In the revision process, given candidate solution, the reviser decomposes the candidate solution into K segments and simultaneously finds the optimum routing sequence for each segment of each candidate solution. The reviser repeats this revising process / times find the hest-updated candidate solution. To be specific, the reviser sequentially updates candidate solutions (7 times) by repeatably decomposing the full trajectories computed from the previous iteration into segments and revising the segments to produce M updated full trajectory solutions. To sum up, reviser solves M x K segments in parallel (M: number of candidate solutions, K: number of the segment each candidate solution), I times in series.
The proposed scheme has advantages over conventional local search methods DRL-based im- provement heuristics. It searches larger solution spaces in a single inference; therefore, reduces iteration I. For example, 2-opt and DRL-2opt [19] search ( solution space (if is parallelizable, O(M N2)), while the reviser searches O K x !!) which is much larger (when the number of nodes of the segment is big enough) in single inference. Hence
reduce the number of iterations T significantly compared to 2-opt, or DRL-2opt [19], thus expediting the speed of the solution search (see Appendix E).
Solution space. Solution space of reviser is partial segment of full trajectory solution represented as T The l is starting index, and is the number of nodes of the segment. For details of assigning segment including &o and I, see Appendix A.3.
Policy structure. Reviser is a constructive policy as follows:
p (TETLAL-()))
II Pon TRA- T8+441,
The segment policy Pan, parameterized by 8t is in the similar form with that of AM [12]. Each and T indicate the starting point and the destination point of the partial segment, respectively (see red-points in Figure 3).
(N) of AM, which is designed for We modify the context embedding vector 1, (.(0)) = [7,(M) (, (
solving TSP. Hence, h is high dimensional embedding vector from the transformer-based encoder, and N is the number of multi-head attention layers. h(N) is the mean of the entire embedding, (N) is the embedding previously selected nodes, and (N) is the embedding of the first node. However, since the destination of reviser is JR+141, not the first node क we change the embedding
of the first node (N) to be the embedding of the last node heeezes for the context embedding as (N)
(N)
(N) NN), ((N) (N) 11111
(N)
((()
i1
Revision Reward: negative of partial tour length L ( =Eit || Ixett-ale.

---

Training scheme. The training process is mostly the same described in section 4.1, except that we have modified the length term L to L L and set remove entropy reward R for training the reviser. Note that the seeder and reviser are trained separately.
Experiments
This section reports the experimental results² of the LCP scheme on TSP, PCTSP, and CVRP (N 20, 50, 100, 500, N: number of nodes). Also, we report several ablation studies in section 5.3 and Appendix B-F. We evaluate performance on real-world TSPs in the TSPLIB in Appendix G.
Training Hyperparamters. Throughout the entire training process of the seeder and reviser, have exactly the same hyperparameters as Kool et al. [12], except that the training batch size of our seeder is 1024. To train the seeder's policy, we set 0.5 (2) and N = Ei= for linear weight
Wy- N-t for entropy scheduling. N,
Details in the experimental setting, including hyperparameters, dataset configuration, and run time evaluation, are described in Appendix A.5.
5.1 Target Problems and Baselines
We evaluate the performance LCP solving the three routing problems: TSP, PCTSP, and CVRP. We provide brief explanation of them. The detailed descriptions for these problems are in Appendix A.1.
Travelling salesman problem (TSP). TSP is problem to find the shortest Hamiltonian cycle given node sequences.
Price collecting travelling salesman problem (PCTSP), PCTSP [38] is a problem, where each node has prize and penalty. The goal is to collect the nodes with least a minimum total prize (constraint) and minimize tour length added with unvisited nodes' penalties.
Capacitated vehicle routing problem (CVRP). CVRP [39] is problem where each node has demand, while a vehicle must terminate the tour when the total demand limit is exceeded (constraint). The objective is to minimize the tour length.
For the baseline algorithms, we use two types of algorithms: conventional heuristics and DRL-based solvers. For the conventional heuristics, use Gurobi [7] (the commercial optimization solver), and the OR Tools [40] (the commercial optimization solver) for all three problems. Table 1, Gurobi (I) indicates Lime-limited Gurobi whose running time is restricted below t. In addition, OR Tools (t) is the OR Tools that allows additional local search over a duration of For problem-specific heuristics, use Concorde [9] for TSP, the iterative local search (ILS) [12] for PCTSP, and LKH3 [41] for CVRP.
For the baselines using DRL-based solvers, we concentrated on the ability of the LCP scheme, which improved performance over AM. Validating that the two-policies collaboration scheme outperforms the single-policy scheme (i.e., AM) is crucial part of this research; thus, the most important metric for performance evaluation improvement between vanilla AM the AM LCP, Also, we reproduced other competitive DRL frameworks: current emerging improvement heuristics. We exclude recently proposed AM-style constructive heuristics, including the POMO [26] and MDAM [27] because they can be candidate collaborators with LCP, not competitors (c.g., POMO + LCP is possible). The detailed method for evaluation baselines in Table is described as follows:
TSP. We follow baseline setting of Kool et al. [12] and Costa et al. [19]. We set DRL baselines
including the S2V-DQN [11], EAN [23], GAT-T [30], DRL-2opt [19], and AM [12]. We show the results of S2V-DQN and EAN reported by Kool et al. [12], and the results of GAT-T reported by
Costa et al. [19]. Then we directly reproduce the two most competitive DRL frameworks among
baselines, the AM and DRt-2opt, in our machine to make fair comparison of the speed.
PCTSP. We follow baseline setting of Kool al. [12]. We reproduce AM [12] for DRL baseline.
See source code in https://gituub..oo//aann o0s. 2088/LCP
7

---

Table 1: Performance evaluation results of the LCP scheme compared with baseline heuristics and the DRL frameworks on TSP. PCTSP, and CVRP. The best costs (objective) among DRL frameworks are marked in bold. The is heuristic and Solver is exact algorithm. The "L.P (640,2)* means that the sampling width M is 640, and the number of iterations / (of the reviser) is 2. We measure the performance
limited time budget, which is seconds per instance. The OB means "out of budget" and IF means "infeasible", where the solver cannot generate solutions satisfying constraints of target problems in a limited time.
Method
N = 20
N = 50
N = 100
Cost
Gap
Time
Cost
Gap
Time
Cost
Gap
Time
Gurobi (Sotver)
3.84
0.00%
0.01s
5.70
0.00%
0.01s
7.76
0.00%
0.02s
OR Tools (H)
3.85
0.37%
5.80
1.76%
8.12
4.53%
Concorde (H)
3.84
0.00%
0.01s
5.70
0.00%
0.01s
7.76
0.00%
0.02s
S2V-DQN
3.89
1.42%
5.99
5.16%
8.31
7.03%
EAN (Ad: 1280]
3.84
0.11%
1.28%
8.75
12.7%
EAN+2OPT LM: 1280)
3.84
0.09%
5.75
1.00%
8.12
4. 6.64%
GAT-T (1: 5000)
3.84
0.00%
5.71
0.20%
7.87
1.42%
TSP
2rpt (I: 2000]
3.84
0.00%
3.58s
5.70
0.12%
4.88s
7.83
0.87%
7.158
AM (M:: 1280)
3.84
0.08%
0.52%
0.09s
7.94
2.26%
0.36s
AM (M: 2560)
3.84
0.06%
0.04s
5.72
0.45%
0.13s
7.94
2.21 %
0).42s
AM (M: 7500)
3.84
0.05%
0,06s
5.72
0.39%
0.29s
7.93
2.13%
1.21s
AM LCP (640,10)
3.84
0.00%
0.18s
5.70
0.13%
0.30s
7.86
1.25%
0.57s
AM + LCP (1280.10)
5.70
0.10%
0.45s
7.85
1.13%
0.90s
AM + LCP* (1280,45)
5,70
0.02%
2.48s
7.81
0.54%
4.30s
Gurobi (Solver)
3.13
0.00%
0.01s
OB
OB
Gurobi [1s] (H)
3.14
0.07%
0.01s
IF
IF
Gurobi [10s] (E
3.13
0.00%
0.01s
5.17
15.6%
0.19s
OR Tools [10s] (H)
0.05%
0.31s
0.70%
0.31s
6.35
6.21%
0.31s
PCTSP
OR Tools [60s] (H)
3.13
0.01%
1.80s
4,48
0.00%
1.80s
6.08
1.56%
1.80s
ILS (If)
3.16
0.77%
0.10s
4.50
0.67%
0.72s
5.98
0.00%
4.32s
AM (.M: 1280)
3.18
0.39%
0.03s
4.52
0.74%
0.07s
6.08
1.67%
0.17s
AM (M: 2560)
3.15
0.41%
0.03s
4.51
0.72%
0.10s
6.07
1.57%
0.288
+ LCP (640.1)
3.14
0.17%
0.04s
0.51%
0.07s
6.06
1.42%
0.15s
AM LCP (1280.5)
3.14
0.08%
0.10s
4.49
0.32%
0.20s
6.04
1.00%
0.39s
Gurobi (Solver)
6.10
0.00%
0.01s
08
OB
OR Tools (H)
5.41%
11.31
9.01% %
17.16
9.67%
I.H3 (H)
6.14
0.58%
0.72s
10.38
0.00%
2.52s
15.65
0.00%
4.68s
RL [M: 10)
6.40
4.92%
11.15
7.46%
16.96
8.39%
NLNS (/: 2000]
1.47%
1.00s
10.54
1.54%
1.63s
16.00
2.17%
2.18s
CVRP
AM (MM: 1280)
6.25
2.49%
0.05s
10.62
2.40%
0.14s
16.23
3.72%
0.34s
AM ( M: 2560)
6.25
2.39%
0,06s
10.61
2.24%
0.31s
16.17
3.34%
0.75s
AM (M:: 7500)
6.24
2.24%
0.09s
10.59
2.06%
0.36s
16.14
3.11%
1.42s
AM + L.CP [640,1]
6.17
1.155
0.07s
10.56
1.74%
0.15s
16.05
2.58%
0.30s
AM + LCP [1280.1]
6.16
0.92%
0.09s
10.54
1.54%
0.20s
16.03
2.43%
0.45s
AM + L.CP [2560.1
6.15
0.84%
0.14s
10.52
1.38%
0.31s
16.00
2.24%
0.77s
AM LCP (6500.1)
15.98
2.11%
1.73s
CVRP. We follow baseline setting of Houttung & Tierney [32]. We report result of RI. [22] based Houttung & Tiemnyy [32] and we reproduce AM [12] and NLNS [32].
5.2 Performance Evaluation
In this section, we report the performance of LCP small-scale problems (N 20, 50, 100) in Table 1. Then we provide a time mene-erfrorance trade-off analysis including large-scale problems (N 500). We note that time- performance analysis is significant because any method can find an optimal solution when given an infinite time budget. From the analysis, we can identify a specific time region, called winner region, where LCP performs the best in terms of both speed and performance.
Performance evaluation on N 20, 50, 100. Our method outperforms all the DRL baselines and OR-tools in TSP. PCTSP, and CVRP, clearly shown in Table 1.
8

---

6.35
AM LCP (ours)
16.6
AM LCP (Ours)
6.30
AM
16.4
7,900
Gi-tools
7.875
16.2
7,850
2apt
7.825
Concards
AM
6.10
16.0
7,800
6.05
6.00
10a
10"
Run Time
(a) TSPI00
(b) PCTSPI00
CVRPI00
14.0
AM LCP (ours)
70
AM +CL (ours)
AM
UKH3
Cost
13.0
Cost
67
AMT LCP COUPS)
12.5
dil 2opt
65
12.0
17
Concordo
10a Run Time
11.5
Run Time
Run Time
(d) TSP500
PCTSP500
(i) CVRP500
Figure 4: Details of time-performance analysis. The left (fast) and lower (lower cost) trend indicates a better performance. In (e), the ILS cannot generate solution in time budget (f < 1000s)
Table 2: Ablation study LCP components on TSP, PCTSP, and CVRP (N 100). The optimal
gap is measured by comparing it with state-of-the-art solvers. The Entropy Regularization indicates training the seeder with RS, while the default is the uniform scheduling. The best performances marked in bold.
Component of the LCP
TSP
PCTSP
CVRP
Entropy Regularization Weight Scheduling
Reviser
cost
gap
cost
gap
cost
gap
7.96
2.65%
6.08
1.64%
16.29
3.43%
7.96
2.68%
6.08
1.76%
16.25
3.16%
7.94
2.45%
6.07
1.62%
16.20
2.86%
7.86
1.32%
6.04
1.13%
16.20
2.86%
7.84
1.17%
6.05
1.16%
16.16
2.59%
7.82
0.88%
6.04
1.02%
16.12
2.37%
Note that for TSP (N = 100), we applied two types of revisers, each of which is denoted LCP and LCP*, respectively. The details are described in Appendix A.4 with pscudo-code. Our LCP and LCP* outperforms DRL-2opt, the current state-of-the-art DRL-based improvement heuristic in N 200 50, 100, surpass 0.33% in
100.
In PCTSP, LCP outperforms AM with less time. Our method (AM LCP (640.1)) outperforms the OR-Tools (10s), with 4x and 2x faster speed in N 50, 100 respectively. Compared to the ILS, our method (AM + LCP (1280.5)) underperforms by 1.0%, but has 11 x faster speed for N = 100.
For CVRP, our method outperforms competitive DRL. frameworks.
Time-performance analysis on 100, 500. In Figure 4, we describe the time-performance analysis. We cannot control the speed of the Concorde, ILS, and LKH3. We can control the speed of DRL solvers by adjusting sample width M or the number of iterations /. For PCTSP, we can change the speed of OR-tools by managing the time for additional local searches.
Our scheme clearly outperforms DRL-solvers in terms of both speed and performance. For PCTSP (N = 100, 500) and CVRP (N = 500), our method achieves the winner region of t < 10, which is best performed in specific time region among all kind of baseline solvers (for CVRP (N 100), our method achieves the winner region of < 5).
Performance TSPLIB [20] data: see Appendix G.

---

5.3 Ablation Study
In this section, we conduct an ablation study on LCP components. We leave further ablation studies to Appendix B-F.
Ablation study of collaborative policies. In Table 2, we ablate three significant components of LCP and show the experimental results for every case. In the case of vanilla AM, having none of LCP components, the performance is the poorest. On the other hand, collaboration of seeder trained with linearly scheduled-entropp and the reviser shows the best performance. Therefore, the experimental results empirically validate our proposal of hierarchically collaborating two policies and also demonstrate the effectiveness of using a linearly scheduled-entropy term shown in section 4.1 and Figure 2.
Ablation study of entropy regularization: see Appendix B.
Ablation study of SoftMax temperature: see Appendix C.
Ablation study of application of L.CP to pointer network [10, 21]: Appendix D.
Comparison with reviser and other improvement heuristies: see Appendix
Training convergence of seeder and reviser in different PyTorch seeds: see Appendix F.
6 Discussion
In this paper, we proposed novel DRL scheme, learning collaborative policies (LCP). The extensive experiments demonstrate that our two-policies collaboration algorithm (i.e., LCP) outperforms con- ventional single-policy DRL frameworks, including AM [12], on various NP-hard routing problems, such TSP, PCTSP, and CVRP.
We highlight that LCP is reusable scheme, can solve various problems. The neural architecture of the seeder and reviser proposed in this paper is derived from AM [12]. It can be substituted by other architectures, such as the pointer network [10, 21] and AM-style architectures including POMO [26] and MDAM [27]. If further studies on neural architecture for combinatorial optimization are carried out, the seeder and reviser can be improved further.
Also, LCP can be directly applied to other combinatorial optimization tasks, including TSP with time windows (TSPTW), orienteering problem (OP), multiple TSP (mTSP), variations of the vehicle routing problem (VRP), and other practical applications.
Further Works. We made important first step: two-policies collaboration where each pol- icy specializing in exploration or exploitation can improve conventional single-policy systems on combinatorial optimization tasks. The important direction of further research is introducing more sophisticated strategies to explore or exploit combinatorial solution space. New exploration strategies for overcoming the proposed approximated entropy maximization scheme needed. Also, it is necessary to investigate more effective exploitation strategies beyond the proposed revision scheme.
Acknowledgements and Disclosure of Funding
This research is supported in part by the KAIST undergraduates research program (URP), 2019. We thank Hankook Lee and Prof. Jinwoo Shin for building part of this project in the URP. We thank Joonsang Park, Keeyoung Son, Hyunwook Park, Haeyeon Rachel Kim, and our anonymous reviewers for feedback and discussions.
10

---

References
[1] Rajesh Matai, Surya Singh, and M.L. Mittal. "Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches", In: Nov. 2010. ISBN: 978-953-307-
426-9. DOE: 10. 57721/211290.
[2] B. Yuan, M. Orlowska, and S. Sadiq. "On the Optimal Robot Routing Problem in Wireless Sensor Networks". In: IEEE Transactions on Knowledge and Data Engineering 19.9 (2007),
pp. 1252-1261. DOI: 10. 1109/ 2007 2007 1062.
[3] Olin Johnson and Jing Liu. "A traveling salesman approach for predicting protein functions". In: Source code for biology and medicine (Feb. 2006), p. 3. DOI: 10. 1ww./111111-1000 1-3.
[4] Haiguang Liao et al. Attention Routing: track-assigument detailed routing using attention- based reinforcement learning. 2020. arXiv: 2004. 09473 [cs. [cs.LG].
[5] M. Kim al. "Reinforcement
boaming-based Auto-router considering Signal Integrity". In: 2020 IEEE 29th Conference Electrical Performance of Electronic Packaging and Systems (EPEPS). 2020, pp. 1-3. DOI: 10. 1119//1EE9SSS/ /EEEP/PPPPP991..1 2020. . 9231473.
[6] Christos H. Papadimitriou. "The Euclidean travelling salesman problem is NP-complete". In: Theoretical Computer Science 4.3 (1977), pp. 237-244. ISSN: 0304-3975. DOr: https:
//doi org/ 10. 1016 / 0304 9002 3. URL: http: : /www. sciencedirect.
90012-
com/ http/scienceeeeeece /ttp://eeee///ttttlc/////////// httpa//cc/aa...eeea//p/////////0
[7] LLC Gurobi Optimization. Gurobi Optimizer Reference Manual. 2021, URL: http::/wtp....... gurobi com.
[8] Keld Helsgaun. "An Effective Implementation of the Lin- Lin-Kenighan Traveling Salesman Heuristic". In: European Journal of Operational Research 126 (Oct. 2000), pp. 106-130, DOr:
10. 1011/1007777-11 2217 (99) 00284-22222 2.
[9] David Applegate al. "Concorde TSP solver". In: 2006. URL: http: // www math uwaterloo. ca/tsp/ concorde/m.
[10] Irwan Bello et al. Neural Combinatorial Optimizatioo with Reinforcement Learning. 2017.
arXiv: 1611 0094999400 [cs. AI).
[11] Elias Khalil et al. "Learning Combinatorial Optimization Algorithms over Graphs". In: Ad- vances in Neural Information Processing Systems. Fd. by I. Guyon al. Vol. 30. Curran Associates, Inc., 2017, pp. 6348-6358, URL:
wwwpppooorennnn.....nr..p.ppp.pp cwtpriis.ccppppeee.e pdf.
2017/file
[12] Wouter Kool, Herke van Hoof, and Max Welling. "Attention, Learn to Solve Routing Prob- lems!" In: International Conference on Learning Representations, 2019. URL: https: openreview www..nee/ff.mmmimmm Bor.mnidd-ByBBBBRRRR
[13] Matthew Veres and Medhat Moussa. "Deep Learning for Intelligent Transportation Systems: A Survey of Emerging Trends". In: JEEE Transactions Intelligent Transportation Systems
21.8 (2020), pp. 3152-3166 316.. DOI: 10. 1...1000 1109/ 1ww1//199STTT.// 2019. 2929020.
[14] Christof Angermueller et al. Ghoddll-Basel Reinforcement Learning for Biological Sequence Design". In: International Conference on Learning Representations, 2020.
[15] Haiguang Liao et al. "Attention Routing: track-assignment detailed routing using attention- based reinforcement learning". In: CoRR abs/2004.09473 (2020). arXiv: 2004. 09473. URL:
attps://arxiv> org/ abs /20b//200.000m 09473.
[16] Azalia Mirhoseini et al. "Device Placement Optimization with Reinforcement Learning". In: Proceedings of the 34th International Conference on Machine Learning. Ed. by Doina Precup and Yee Whye Tch. Vol. 70. Proceedings of Machine Learning Research. PMLR, June 2017, html. [17] Azalia Mirhoseini et al. "Chip Placement with Deep Reinforcement Learning". In: CoRR trrg/bss/200 10746. [18] A. Croes. "A method for solving traveling salesman problems".. In: Operations Research 5 (1958), pp. 791-812.
pp. 2430-2439. URL: http: http:///p/oceeneeeeeeeee .mlr htt..prrees/////mmrroooeiiiniin
abs/2004.10746 (2020). arXiv: 2004. 10746. URL:
[19] Paulo R. de O. da Costa et al. Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning. 2020. arXiv: 2004. 01608 [cs. LG].
[20] Gerhard Reinelt. "TSPLIB-A Traveling Salesman Problem Library". In: ORSA Journal on Computing 3.4 (1991), pp. 376-384.

---

[21] Oriol Vinyals. Meire Fortunato, and Navdeep Jaitly. "Pointer Networks". In: Advances in Neural Information Processing Systems. Ed. by C. Cortes et al. Vol. 28. Curran Associates, Inc., 2015, pp. 2692-2700. URL: https: proceedings neurips cc paper/ap////// 2015 file/ http://9100022000eaaaaaaaaaaaaa2 Papee .dd.
[22] MohammadReza Nazari et al. "Reinforcement Learning for Solving the Vehicle Routing Problem". In: Advances in Neural Information Processing Systems. Ed. by S. Bengio et al. Vol. 31. Curran Associates, Inc., 2018, pp. 9839-9849. URL: https / prw.eedddo........ Paper pdf. [23] Michel Deudon et al. "Learning Heuristics for the TSP by Policy Gradient". In: Integration of Constraint Programming. Artificial Intelligence, and Operations Research. Ed. by Willem-Jan van Hoeve. Cham: Springer International Publishing, 2018, pp. 170-181. ISBN: 978-3-319-
neurips.. cttppp.cc..pooooo cttccc//pppa http/aaprr/2000 satper//01/ffileee
93031-2.
[24] Ashish Vaswani et al. "Attention is All you Need". In: Advances in Neural Informa- tion Processing Systems. Fd. by I. Guyon et al. Vol. 30. Curran Associates, Inc., 2017, pp. 5998-6008. URL: https: proceedings neurips cc / /eeppapr// / 2017 / file/ httpe2/554reee1ffffosscccccceeee
Paper pdf.
[25]
Williams. "Simple statistical gradient-followwie algorithms for connectionist reinforce- ment learning". In: Machine Learning 8 (1992), pp. 229-256.
[26] Yeong-Dae Kwon et al. "POMO: Policy Optimization with Multiple Optima for Reinforcement Learning". In: Advances in Neural Information Processing Systems. Ed. by H. Larochelle et al. Vol. 33. Curran Associates, Inc., 2020, pp. 21188-2111 21198. URL: https: //pooceddgss neurips.. . cc/ pttppppppp////////e/////p htt///2202/1/eff221e2 (1
-a0-0000009b222PPPaaae pdff.
[27] Liang Xin et al. "Multi-decode attention model with embedding glimpse for solving vehicle routing problems". In: Proceedings of 35th AAAI Conference on Artificial Intelligence. 2021. [28] Paul Shaw. A New Local Search Algorithm Providing High Quality Solutions to Vehicle Routing Problems. 1997.
[29] Xinyun Chen and Yuandong Tian. "Learning to Perform Local Rewriting for Combinatorial Optimization". In: Advances in Neural Information Processing Systems. 2019.
[30] Yaoxin Wu et al. Learning Improvement Heuristics for Solving Routing Problems. 2020. arXiv:
1912. 0000557844 84 [II.
[31] Paulo R d O da Costa et al. "Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning". In: Proceedings of The 12th Asian Conference on Machine Learming. Ed. by Sinno Jialin Pan and Masashi Sugiyama. Vol. 129. Proceedings of Machine Learning Research. Bangkok, Thailand: PMLR, 18-20 Nov 2020, pp. 465 480. URL: http: / //proceedings mlr. press/ /v/ 1/////11////// costa20a.......oooc html.
[32] André Hottung and Kevin Tiemeyy "Neural Large Neighborhood Search for the Capacitated Vehicle Routing Problem". In: CoRR abs/191 1999111919999 (2019). arXiv: 1911. 09539. URL.:
http:// org/ absa /1911 09539.
[33] Hao Lu, Xingwen Zhang, and Shuang Yang. "A Learning- based Iterative Method for Solving Vehicle Routing Problems". In: 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL: https:
// //openrevies ew net/ brrmmidd-BJe1ee
[34] Chaitanya K. Joshi et al. Learning TSP Requires Rethinking Generalization. 2020. arXiv:
2006. 07054 [cs LG].
[35] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. "Generalize Small Pre-trained Model to Arbitrarily Large TSP Instances". In: CoRR abs/2012. 10658 (2020), arXiv: 2012. 10658. URL.:
https: /tttss//arrivvv borg/abs/// /0022. 10658.
[36] Wouter Kool et al. "Deep Policy Dynamic Programming for Vehicle Routing Problems". In: CoRR abs/2102.11156 (2021). arXiv: 2102. 11756. URL: 11756.
http///aawi.oo//a////aaaaaa//aaa ab0.
[37] Diederik P. Kingma and Jimmy Ba. "Adam: A Method for Stochastic Optimization", In: 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. Ed. by Yoshua Bengio and Yann LeCun. 2015. URL.: http: http://arxivv org/ abaa 1412/ 6980.
[38] Egon Balas. "The prize collecting traveling salesman problem".. In: Networks 19.6 (1989), pp. 621-636. DOT: https: / doi org 10. 1002 / net 3230190602. onlinelibrary wiley. , com http//do//bb/s/ee 1002 httpg///..oo/////o//...00/////.
URL:: https ://
12

---

[39] Paolo Toth and Daniele Vigo. Vehicle Routing. Ed. by Daniele Vigo and Paolo Toth. Philadelphia. PA: Society for Industrial and Applied Mathematics, 2014. DOI: 10. 1137/ / 1 9781611973594, URL: https / epubs siam org / doi / abs / 10 1137 / 1
9781611973594.
[40]
Laurent Perron and Vincent Furnon. OR-Tools. Version 7.2. Google, 2019. URL: https: / //developers: google. com/optotttoooo httm/pptmiiatiiin
[41] Keld Helsgaun. "An Extension of the Kernighan-Helseee TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems". In: (Dec. 2017). DOI: 10. 13140/RG. 2.
2. 25269.9.. 40807.
13


Reviews:
[{"review_id": "m1D4UGz6rT", "reviewer": "Reviewer_Atn1", "summary": "This paper introduces Learning Collaborative Policies (LCP) for learning to optimize TSP-style routing problems. The goal of this was not to outperform all other optimizers, but to outperform RL optimizers, which are usually less effective than traditional approaches, but also are more scalable to task-variation. This makes this class of optimizers more suitable for real-world problems. LCP uses 2 policies to optimize a TSP: a seeder, and a reviser. The seeder generates many valid but diverse solutions (ensured with an entropy maximization term in the reward). The reviser learns to relax small sections of each seed to create more optimal solutions. Revision is repeated a set number of times and the best solution is given.", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n\n•\tElegant idea.\n             - Macro-optimization through learned seeding + micro-optimization through revision.\n•\tBeat baseline RL algorithms in 3 TSP variants with 20, 50, and 100 nodes.\n             - Variants seemed representative (educated guess).\n•\tReal-world applicability + scalability.\n             - Some of these applications are mentioned.\n•\tFigures are well-made and understandable.\n•\tAblation study is good.\n•\tReproducibility info including hyperparameters is mentioned and indexed in the appendix. Code will also be provided in the final version.\n\nWeaknesses:\n•\tUnprofessional writing.\n            - Most starkly, “policies” is misspelled in the title.\n•\tAt times, information is not given in an easy-to-understand way.\n            - E.G. lines 147 - 152, 284 - 289.\n•\tCaptions of figures do not help elucidate what is going on in the figure. This problem is mitigated by the quality of the figures, but it still makes it much harder to understand the pipeline of LCP and its components. More emphasis on that pipeline would help with the understanding.\n•\t100 nodes seem like a small maximum test size for TSP problems (though this is an educated guess). Many real-world problems have thousands or tens of thousands of nodes.\n•\tIncrease in optimality is either not very significant, or not presented to highlight its significance. It would be better to put the improvement into perspective.\n•\tBlank spaces in table 1 are unclear.\n\nOpportunities:\n\n•\tIt would be good to describe why certain choices were made. For example, why is the REINFORCE algorithm used for training versus something like PPO? I presume it has to do with the attention model paper this one iterates on, but clarification would be good.\n\n•\tMore real-world uses of the algorithm could be included to better understand the societal impact, including details on how LCP could be integrated well.\n\nThe paper lacks a high degree of polish and professionalism, but its formatting (e.g. bolded inline subsubsections) and figures are its saving grace. The tables are also well structured, if a bit cluttered --- values are small and bolding is indistinct. This paper does a good job of giving this information and promises open source-code on publication.\n\nOverall, the paper and its presentation have several problems, but the idea seems elegant and useful. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hours"}, "extra_text": {}}, {"review_id": "A6Wlk2SKiJB", "reviewer": "Reviewer_8gsS", "summary": "The paper addressed the hard routing problems based on a hierarchical strategy consists of two DRL policies called the seeder and reviser. Together with the two policies, to assess the diversity of candidate solutions, the entropy-regularized reward is adopted. The revise divides the tour into subtours and optimizes the length of them. Experimental results suggest that the proposed LCP framework works on TSP, PCTSP, and CVRP instances.", "questions": "", "limitations": "", "rating": 6, "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": "As the authors mentioned, the proposed LCP framework is not designed to outperform problem-specific solvers (e.g., Concorde for TSP). Therefore, the authors formulate the routing problems as MDP and the task of DRL-policies is to sequentially design a new task (i.e., select one of the unserved tasks). Since the next task should be taken depends on the current status (and implicitly already assigned tasks), the MDP-based approach seems to be reasonable. In addition, the reward-based study covers various problem tasks.\n\nThe idea of the seeder (preparing diverse solutions) and revise (updating solutions) is a kind of a traditional approach to solvecombinatorial problems, but the RL-based formulation seems to work efficiently to various problems. Technically the paper seems to be sound but the structure of the paper is a bit hard to follow although the author revised the paper when submission, because the paper covers branches of classes and showed various experimental comparisons (and most of them are included in Appendix).\n\n### Weights for diverse candidate routes\n\nAs far as I understand the proposed formulation correctly, the seeder follows a parameterized policy from the previous work [11]. Therefore, the important part of the LCP seems from the entropy-regularized reward to search diverse areas of all solution spaces, which is supported by the reviser part. Although the entropy is hard to compute exactly, a weighted sum of the selected routings is adopted and the weights on the early stage are set to be higher. This weighting mechanism seems to be interesting to generate diverse solutions.  Although this weighting scheme is a hyper-parameter (or hand-crafted setting), the experimental results indicated that the difference of weights does not affect the result too much (e.g., Table 5 of Appendix B). \n\nMy concerns are\n- (a) Do fixed parameters in Table 5 (e.g., N of TSP, I=10, T=2, ... ) affect the comparison of the provided results?\n- (b) Can we have similar results for real instances? As far as I know, characteristics of random TSP (or other class) instances are hard to tune and in some cases, results are different from those obtained from real instances.\n- (c) In Appendix E, the performance of the reviser is evaluated by a kind of ablation test using Drl2-Opt. Did the author evaluate the performance of the seeder? (i.e., some heuristics + reviser) If this kind of comparison is useless for some reason, please clarify it to highlight the advantage of the proposed method (or, for example, Appendix D covers this kind of experiment?).\n\n### Revise\n\nThe revision process of candidate seeds is essential for LCP. The key background to design the reviser is solving small routing instances is easy (l = L-2). As noted in Sec.4.2, DRL-2opt searches O(N^2) solution space but the LCP searches O(MK l!). \n\n- (d) I suspect that LCP with smaller l (i.e., L) could generate worse solutions than Drl2-opt. Is this correct or do the authors investigate the case?\n- (e) The authors mentioned only Drl-2Opt in Sec.4.2. Since the proposed LCP could be applied to PCTSP and CVRP, some RL-based solvers (e.g., AM, NLNS) should be mentioned on the viewpoint of search space to highlight the advantage of LCP if possible.\n\nIn addition to $l$, the parameter $I$ should be carefully examined in my opinion. For PCTSP and CVRP, relatively small $I$ is used (1, 5), while TSP uses $l=10$ an $45$. Why such small values are used? Please add the concept of these used parameter values if possible.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Solving various classes in a unified manner (or hybrid manner with existing methods) is a promising work in the literature.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3wcJ2mahYK", "reviewer": "Reviewer_AG5Z", "summary": "This paper proposes to learn collaborative policies for routing problems. Collaborative policies firstly learn to generate many diversified and primitive solution candidates. Then for each solution candidate, they segment the original problem into several sub-problems. Another neural network model is trained to improve these sub-problems. The improved solutions of the sub-problems can be merged to form a new solution for the original problem.  They teste their methods on the TSP, PCTSP, CVRP problems and achieve the best performance among all the baselines. ", "questions": "", "limitations": "", "rating": 6, "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": "Originality: \nI think the method is a smart combination of \"Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances\" Fu et al., \"Deep Policy Dynamic Programming for Vehicle Routing Problems\" Kool et al and \"Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning\" Costa et al. However, the related work section mentions these two works but does not discuss the relation to these three works. \n\nQuality:\n\nThe main contribution of this paper is to make the entire pipeline fully deep learning and do not require any label during the training process. The paper uses a neural network model trained with DRL to generate the primitive solutions and proposes an entropy regularizer term to increase the diversity of the solutions.  Previous works typically supervised train a model to predict the importance of each edge and create the sub-problems (solutions). For the improving phase, this paper uses another neural network model trained through DRL to improve the sub-solutions.  While the previous works leverage DP algorithm, MCTS, or require labels.\n\nThe experiment results look good to me. The method beats all the fully neural baselines with reasonable time.\n\nClarity:\n\nThe paper has some important points that I am confused about.\n\n1. How did you generate the sub-problems (segments) of a candidate solution? I assume it is fully random and make sure the points you selected are connected? I think this step is vital in the entire process but it is not explained.\n2. For training the revision policy, how did you generate the training instances? It is exactly the same as the one for seeder policy?\n\nSignificance:\n\nThe method is smart to leverage the previous ideas in fully deep learning and no label required way. \n\nQuestions:\n\n1. I think one interesting ablation study can be: what if you use a supervised trained model to generate the segments/sub-problems like what they did in \"Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances\". I am wondering how the entropy regularize help compared with a supervised method.\n\n2. For the TSP problems, the size of the sub-problems is 10 vertices. In this case, why a revision model is required since you can compute the optimal solution very fast for only 10 vertices? What're the results then? What if you increase the size of the sub-problems (which can potentially be generalized to huge TSP problems).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "For the limitations, the authors do not talk about will the method scale to high problems, e.g., TSP-10000. My feeling is that the seeder policy may be not good enough if the size of the sub-problems is increased a lot. \n\nI don't think this work has some bad societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "N/A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "36SpOWyojTQ", "reviewer": "Reviewer_BKnt", "summary": "Deep reinforcement learning (DRL) has recently been applied to variety of optimization problems, outperforming traditional approaches. This paper investigates the application of DRL to the context of routing problems such as the classical travelling salesman problem. The methodology proposed involves two DRL agents: the seeder, which is tasked with generating candidates for the solution that provide a good coverage of the solution space, and the reviser, which is tasked with attaining better solutions based on the reduced solution space provided by the seeder. To generate diverse candidates, the seeder utilizes entropy regularization reward. The authors present experiments indicating that their framework, called learning collaborative policies (LCP) improves over previous DRL frameworks for various routing challenges (e.g., TSP and capacitated vehicle routing).", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Thanks you for submitting to NeurIPS 2021.\n\nThe paper is reasonably well written and the results are, overall, clearly explained.\n\nI found the approach presented for addressing routing problems (seeder + reviser) interesting.\n\nI wonder what makes routing problems special? Do you expect the same approach to attain good results in other optimization domains? Or is there something about the structure of TSP and the other routing problems discussed that is of special significance here? I encourage the authors to elaborate on this point.\n\nI think that the paper could also benefit from more discussion of why the approach produces good results. Specifically, the seeder-reviser methodology is somewhat reminiscent of traditional local search via genetic algorithms, simulated annealing, etc., where many random solutions are generated and these are combined in various ways to generate better solutions. I realize that the argument is that the generation of such candidate solutions by the seeder is better because of the entropy regularization reward, and that employing DRL by the reviser somehow helps it generalize better, but I would have appreciated more discussion/investigation of this point.\n\nPost author response:\n\nThank you for your responses to my concerns. I still view this as a borderline paper but am adjusting my score to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact is expected.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes Learning Collaborative Policies (LCP) for learning to optimize  routing problems. LCP is  a hierarchical strategy that consists of two RL policies called the seeder and reviser. The seeder generates many valid but diverse solutions (using an entropy maximization term in the reward). The reviser learns to relax parts of  the  seed to create more optimal solutions. This process is repeated and the best solution is given. The authors apply the approach to different routing problems (TSP, PCTSP, CVRP problems) and achieve the best performance among all the baselines. There was some discussion, the reviewers felt the authors made a great effort to address the concerns raised by them, which led to the increase of the score by one of the reviewers, and overall the consensus was that the paper was ok, above the threshold.
Decision: Accept (Poster)