Learning Collaborative Policies to Solve NP-hard Routing Problems
Year: 2022

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

heading: 1 Introduction
text: 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 a 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, 2, 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 it challenging to 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 a remarkable performance on target problems, the conventional approaches have several limitations. Firstly, in 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 of DRL can be any
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
value, even from a black-box simulator; therefore, DRL can overcome 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-solving strategy based on DRL, however, ultimately focuses on practical applications1 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 a 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 a 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, as 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) so that it can provide as diversified candidate solutions as possible. It is important to explore over the full combinatorial action space because the solution quality highly fluctuates depending on 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 subtour to minimize its traveling distance in a parallel manner. This scheme provides two advantages: (a) searching over the restricted solution space can be more effective because the reward signal corresponding to 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 a 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 it allows the revisers to search over larger solution space in a 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-agnostic 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, we show proposed techniques, including entropy regularization scheme and revision scheme, clearly contribute to the performance improvement.

heading: 2 Related Works
text: 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: it can be applied to un-explored problems. DRL-based approaches can be categorized into two parts;
1These works [13, 14, 15, 16, 17] are inspired by DRL frameworks [10, 12] on combinatorial optimization
constructive heuristics and improvement heuristics. We survey these two categories and current emerging hybrid approaches of machine learning (ML) with conventional solvers.

heading: 2.1 DRL-based Constructive Heuristics
text: Bello et al. [10] introduced an actor-critic algorithm with a policy parameterized by the pointer network [21]. They proposed a constructive Markov decision process (MDP), where the action is defined as choosing one of the un-served nodes to visit, given a partial solution; the policy is trained to add a node to provide a complete solution sequentially. Later, DRL-based constructive heuristics were developed to design the architecture of neural networks while preserving the constructive MDP [10]. Khalil et al. [11] proposed a 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 a 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.
AM-variants. 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.
Some researches focus on 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 a new RL baseline that can reduce the training variance of AM using the problem-specific property of TSP and CVRP. In addition, they presented an effective post-processing algorithm for TSP and CVRP. However, their proposed method has a limitation in that it is problem-specific because it uses the domain properties of TSP and CVRP (e.g., their method is limited to 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 is different where it increases the entropy of a single decoder and improves the mistakes of various solutions through a reviser.

heading: 2.2 DRL-based Improvement Heuristics
text: 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 et al. [29] proposed a 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 & Tierney [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 inferences of constructive heuristics is the same as the number of cities to visit. However, the number of inferences of the improvement heuristics is generally much larger.

heading: 2.3 Hybrid Approaches with Conventional Solvers
text: There are several studies on hybrid approaches with conventional solvers having promising performance recently. Lu et al. [33] proposed a 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 et 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 a searching space for improvement heuristics. Similarly, Fu et al. [35] combined supervised
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 are 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.

heading: 3 Formulation of Routing Problems
text: This section explains the Markov decision process (MDP) formulation for the given 2D Euclidean TSP as a representative example. The formulation of MDP for other problems is described in Appendix A.1.
The main objective of TSP is to find the shortest path of the Hamiltonian cycle. The TSP graph can be represented as a sequence of N nodes in 2D Euclidean space, s = {xi}Ni=1, where xi ∈ R2. Then, the solution of TSP can be represented as the permutation π of input sequences:
π = t=N⋃ t=1 {πt}, πt ∈ {1, ..., N}, πt1 ̸= πt2 if t1 ̸= t2
The objective is minimizing the tour length L(π|s) = ∑N−1
t=1 ||xπt+1 − xπt ||2 + ||xπN − xπ1 ||2. Then, we formulate the constructive Markov decision process (MDP) of TSP.
State. State of MDP is represented as a partial solution of TSP or a sequence of previously selected actions: π1:t−1.
Action. Action is defined as selecting one of un-served tasks. Therefore, action is represented as πt where the πt ∈ {{1, ..., N} \ {π1:t−1}}. Cumulative Reward. We define cumulative reward for solution (a sequence of assignments) from problem instance s as negative of tourlength: −L(π|s). Constructive Policy. Finally we define constructive policy p(π|s) that generates a solution π from TSP graph s. The constructive policy p(π|s) is decomposed as:
p(π|s) = t=N∏ t=1 pθ(πt|π1:t−1, s)
Where pθ(πt|π1:t−1, s) is a single-step assignment policy parameterized by parameter θ.

heading: 4 Learning Collaborative Policies
text: This section describes a novel hierarchical problem-solving strategy, termed learning collaborative policies (LCP), which can effectively find the near-optimum solution using two hierarchical steps,
seeding process and revising process (see Figure 1 for detail). In the seeding process, the seeder policy pS generates M number of diversified candidate solutions. In the revising process, the reviser policy pR re-writes each candidate solution I times to 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 a detailed technical explanation.

heading: 4.1 Seeding Process
text: The seeder generates as diversified candidate solutions as possible while being dedicated to exploring the full combinatorial action space. To this end, the seeder is trained to solve the following problems.
Solution space. Solution space of seeder is a set of full trajectory solutions : {π(1), ...,π(M)}. The M is the number of candidate solutions from the seeder: termed sample width.
Policy structure. Seeder is a constructive policy, as defined in section 3 as follows:
pS(π|s) = t=N∏ t=1 pθS (πt|π1:t−1, s)
The segment policy pθS (πt|π1:t−1, s), parameterized by θS , is derived form AM [12]. Entropy Reward. To force the seeder policy pS to sample diverse solutions, we trained pS such that the entropy H of pS to be maximized. To this end, we use the reward RS defined as:
RS = H ( π ∼
t=N∏ t=1 pθS (πt|π1:t−1, s)
) ≈
N∑ t=1 wtH (πt ∼ pθS (πt|π1:t−1, s)) (1)
The entropy of constructive policy is appropriate for measuring solution diversity. However, computing the entropy of constructive policy is intractable because search space is too large: N !. Therefore, we approximate it as a weighted sum of the entropy of segment policies pθS (πt|π1:t−1, s) evaluated at different time step.
We use a linear scheduler (time-varying weights) wt = N−tNw to boost exploration at the earlier stage of composing a solution; higher randomness imposed by the higher weight wt at the early stage tends to generate more diversified full trajectories later. The Nw is the normalizing factor, which is a 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 as follows:
∇J(θS |s) = Eπ∼pS [(L(π|s)− αRS(pS1:N ,π)− b(s))∇log(pS)] (2)
Note that the α is hyperparameter for RS and pS1:N is the sequence of segment polices {pθS (πt|π1:t−1, s)}Nt=1. We use the ADAM [37] optimizer to obtain the optimal parameter θ∗ that minimizes the objective function.

heading: 4.2 Revision Process
text: In the revision process, given a 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 I times to find the best-updated candidate solution. To be specific, the reviser sequentially updates candidate solutions (I 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 ×K segments in parallel (M : number of candidate solutions, K: number of the segment in each candidate solution), I times in series.
The proposed scheme has advantages over conventional local search methods or DRL-based improvement heuristics. It searches larger solution spaces in a single inference; therefore, it reduces iteration I . For example, 2-opt and DRL-2opt [19] search O(N2) solution space (if it is parallelizable, O(MN2)), while the reviser searches O(MK × l!) which is much larger (when the number of nodes of the segment l is big enough) in a single inference. Hence we can reduce the number of iterations I 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 a partial segment of full trajectory solution represented as πk+1:k+l. The k is starting index, and l is the number of nodes of the segment. For details of assigning segment including k and l, see Appendix A.3.
Policy structure. Reviser is a constructive policy as follows:
pR(πk+1:k+l|s) = t=l∏ t=1 pθR(πk+t|πk:k+t−1, πk+l+1, s)
The segment policy pθR , parameterized by θR, is in the similar form with that of AM [12]. Each πk and πk+l+1 indicate the starting point and the destination point of the partial segment, respectively (see red-points in Figure 3).
We modify the context embedding vector h(N)(c) = [h̄ (N), h (N) πt−1 , h (N) π1 ] of AM, which is designed for solving TSP. Hence, h is a 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, h (N) πt−1 is the embedding of previously selected nodes, and h (N) π1 is the embedding of the first node. However, since the destination of reviser is πk+l+1, not the first node π1 , we change the embedding of the first node h(N)π1 to be the embedding of the last node h (N) πk+l+1 for the context embedding as h (N) (c) = [h̄ (N), h (N) πk+t−1 , h (N) πk+l+1 ].
Revision Reward: negative of partial tour length LR(πk+1:k+l|s) = ∑l+1 t=1 ||xπk+t − xπk+t−1 ||2.
Training scheme. The training process is mostly the same as described in section 4.1, except that we have modified the length term L to LR, and set α = 0 to remove entropy reward RS for training the reviser. Note that the seeder and reviser are trained separately.

heading: 5 Experiments
text: This section reports the experimental results2 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, we 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 Nw = ∑N i=1 i for linear weight wt = N−t Nw for entropy scheduling.
Details in the experimental setting, including hyperparameters, dataset configuration, and run time evaluation, are described in Appendix A.5.

heading: 5.1 Target Problems and Baselines
text: We evaluate the performance of LCP in solving the three routing problems: TSP, PCTSP, and CVRP. We provide a brief explanation of them. The detailed descriptions for these problems are in Appendix A.1.
Travelling salesman problem (TSP). TSP is a 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 a prize and a penalty. The goal is to collect the nodes with at least a minimum total prize (constraint) and minimize tour length added with unvisited nodes’ penalties.
Capacitated vehicle routing problem (CVRP). CVRP [39] is a problem where each node has a 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, we use Gurobi [7] (the commercial optimization solver), and the OR Tools [40] (the commercial optimization solver) for all three problems. In Table 1, Gurobi (t) indicates time-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 t. For problem-specific heuristics, we 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 is improved performance over AM. Validating that the two-policies collaboration scheme outperforms the single-policy scheme (i.e., AM) is a crucial part of this research; thus, the most important metric for performance evaluation is 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 (e.g., POMO + LCP is possible). The detailed method for evaluation baselines in Table 1 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 DRL-2opt, in our machine to make a fair comparison of the speed.
PCTSP. We follow baseline setting of Kool et al. [12]. We reproduce AM [12] for DRL baseline.
2See source code in https://github.com/alstn12088/LCP
CVRP. We follow baseline setting of Houttung & Tierney [32]. We report result of RL [22] based on Houttung & Tierney [32] and we reproduce AM [12] and NLNS [32].

heading: 5.2 Performance Evaluation
text: In this section, we report the performance of LCP on small-scale problems (N = 20, 50, 100) in Table 1. Then we provide a time-performance 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, as clearly shown in Table 1.
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 pseudo-code. Our LCP and LCP* outperforms DRL-2opt, the current state-of-the-art DRL-based improvement heuristic in N = 20, 50, 100, surpass 0.33% in N = 100.
In PCTSP, LCP outperforms AM with less time. Our method (AM + LCP {640,1}) outperforms the OR-Tools (10s), with 4× and 2× faster speed in N = 50, 100 respectively. Compared to the ILS, our method (AM + LCP {1280,5}) underperforms by 1.0%, but has 11 × faster speed for N = 100 . For CVRP, our method outperforms competitive DRL frameworks.
Time-performance analysis on N = 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 I . 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 a specific time region among all kind of baseline solvers (for CVRP (N = 100), our method achieves the winner region of t < 5).
Performance on TSPLIB [20] data: see Appendix G.

heading: 5.3 Ablation Study
text: 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-entropy 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 LCP to pointer network [10, 21]: see Appendix D.
Comparison with reviser and other improvement heuristics: see Appendix E.
Training convergence of seeder and reviser in different PyTorch seeds: see Appendix F.

heading: 6 Discussion
text: In this paper, we proposed a novel DRL scheme, learning collaborative policies (LCP). The extensive experiments demonstrate that our two-policies collaboration algorithm (i.e., LCP) outperforms conventional single-policy DRL frameworks, including AM [12], on various NP-hard routing problems, such as TSP, PCTSP, and CVRP.
We highlight that LCP is a 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 an important first step: two-policies collaboration where each policy 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 are 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.

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

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

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.

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.