PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Collaborative Policies to Solve NP-hard Routing Problems

Minsu Kim, Jinkyoo Park, Joungho Kim

arXiv:2110.13987v1cs.LGstat.ML

TL;DR

DRL routing methods still lag state-of-the-art heuristics on NP-hard problems, motivating a method that improves both solution diversity and quality. LCP uses a seeder for broad exploration and a reviser for sub-tour exploitation, and experiments show gains over single-policy DRL across several routing tasks. The scheme is reusable, but the paper identifies more sophisticated exploration and exploitation strategies as future work.

  • Problem

    DRL frameworks can address NP-hard routing without problem-specific expertise but still struggle to compete with state-of-the-art heuristics.

  • Method

    LCP hierarchically combines a diverse-solution seeder with a reviser that improves candidates through parallel sub-tour revision.

  • Results

    LCP outperforms conventional single-policy DRL frameworks on TSP, PCTSP, and CVRP, with ablations favoring collaboration between the reviser and linearly scheduled entropy seeding.

  • Takeaways & Limitations

    LCP is reusable across neural architectures and can be applied to additional combinatorial optimization tasks and practical applications.

  • Takeaways & Limitations

    Further work is needed on exploration strategies beyond approximate entropy maximization and exploitation strategies beyond the proposed revision scheme.

Abstract

from arXiv · show

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

1 Introduction

Routing problems such as TSP are NP-hard, while conventional solvers face formulation and portability limits. LCP addresses these challenges with collaborative exploration and revision, improving DRL performance across routing benchmarks.

  • TSP and its variants are NP-hard, complicating the design of exact solvers for engineering applications.
  • MILP solvers require linear objectives and constraints, while handcrafted heuristics depend on problem-specific expertise and redesign.
  • LCP combines a seeder that generates diverse candidates with a reviser that iteratively fine-tunes them.
  • The seeder explores the full combinatorial action space to produce diversified candidates, while the reviser partitions trajectories into sub-tours for local improvement.
  • Parallel sub-tour revision lets LCP retain diversified candidates while reducing the computing cost of repeated local search.
  • LCP improves the AM architecture and outperforms competitive DRL frameworks on TSP, PCTSP, and CVRP across multiple problem sizes and TSPLIB instances.

2 Related Works

DRL routing research spans constructive heuristics, improvement heuristics, and hybrids with conventional solvers. The paper positions LCP as a DRL-only collaboration scheme that combines broad exploration with targeted revision.

  • DRL routing methods can generate solvers without ground-truth labels and apply to unexplored problems.
  • Constructive DRL heuristics build complete solutions sequentially, with attention-based models reporting strong results on several NP-hard routing problems.
  • LCP differs from multi-decoder diversity methods by increasing a single decoder’s entropy and correcting candidate mistakes through a reviser.
  • Improvement heuristics iteratively modify completed solutions, drawing on local-search methods such as 2-opt and large neighborhood search.
  • Improvement heuristics generally perform better than constructive heuristics but require more neural-network inferences and are usually slower.
  • Hybrid methods combine learned models with conventional solvers, but their expandability remains limited by the classical solvers they use.

3 Formulation of Routing Problems

The routing formulation represents a solution as a permutation generated sequentially by a constructive policy. The policy receives partial solutions, selects unserved nodes, and is rewarded by negative tour length.

  • For Euclidean TSP, the goal is to find the shortest Hamiltonian cycle over N nodes in two-dimensional space.
  • A TSP solution is represented as a permutation of the input nodes with no repeated selections.
  • The MDP state is the partial solution, represented by the sequence of previously selected actions.
  • At each step, the action selects one unserved node from the input set.
  • The cumulative reward for a solution is the negative of its tour length, −L(π|s).
  • The constructive policy p(π|s) generates a complete solution π from the TSP graph s.

4 Learning Collaborative Policies

Learning collaborative policies (LCP) is a hierarchical DRL strategy that first generates diversified candidate solutions and then repeatedly revises their segments to improve tour quality. The seeder explores the full combinatorial space with entropy-based rewards, while the reviser exploits reduced segment spaces in parallel.

  • 4 Learning Collaborative Policies: LCP uses two policies: a seeder generates diversified candidate solutions, and a reviser iteratively fine-tunes them.The final solution is selected from the revised candidates.
  • 4.1 Seeding Process: The seeder explores full trajectories and maximizes an entropy-based reward to encourage diverse candidate solutions.Because full-policy entropy is intractable over an N! search space, it is approximated by a weighted sum of segment-policy entropies.
  • 4.1 Seeding Process: Early decision steps receive higher entropy weights, promoting randomness when choices have greater influence on later full trajectories.The linear scheduler assigns larger weights at earlier stages.
  • 4.2 Revision Process: The reviser decomposes each candidate into K segments and simultaneously finds routing sequences for the segments, repeating this process I times.It conditions segment construction on the starting and destination nodes and uses a constructive policy.
  • 4.2 Revision Process: Compared with local-search baselines such as 2-opt, the reviser searches a larger space in one inference, potentially reducing the required number of iterations I.The paper contrasts O(N^2) search for 2-opt with O(MK × l!) for the reviser when segments are sufficiently large.
  • 4.2 Revision Process: The seeder and reviser are trained separately, with the reviser removing the entropy reward and optimizing its revised-tour objective.The reviser uses α = 0 during training.

5 Experiments

Experiments evaluate LCP on TSP, PCTSP, and CVRP against heuristic and DRL baselines under constrained time budgets. LCP improves DRL-based performance across these problems, with additional analyses examining speed–quality trade-offs and component contributions.

  • Target Problems and Baselines: LCP is evaluated on TSP, PCTSP, and CVRP using heuristic and DRL-based baselines.The study also includes real-world TSPLIB evaluation and ablation studies.
  • Target Problems and Baselines: Within a 10-second per-instance budget, Table 1 compares LCP configurations with baseline objective costs and flags out-of-budget or infeasible solvers.LCP notation reports the sampling width M and reviser iteration count I.
  • Performance Evaluation: LCP outperforms all DRL baselines and OR-Tools on TSP, PCTSP, and CVRP for N = 20, 50, 100.For TSP with N = 100, LCP and LCP* surpass DRL-2opt by 0.33%.
  • Performance Evaluation: In PCTSP, AM + LCP is faster than OR-Tools at N = 50 and N = 100, while trailing ILS by 1.0% but running 11× faster at N = 100.The reported OR-Tools speedups are 4× for N = 50 and 2× for N = 100.
  • Performance Evaluation: LCP achieves winner regions balancing speed and performance for PCTSP and CVRP, including t < 10 for PCTSP N = 100, 500 and CVRP N = 500.For CVRP N = 100, the reported winner region is t < 5.
  • Ablation Study: Ablations find the poorest performance for vanilla AM and the best performance when linearly scheduled entropy training and the reviser collaborate.These results empirically support both hierarchical policy collaboration and the entropy term.

6 Discussion

LCP combines reusable seeder and reviser policies to improve DRL routing across multiple NP-hard problems. Its implementations adapt decomposition, revision, and model reuse to TSP, PCTSP, and CVRP.

  • LCP outperforms conventional single-policy DRL frameworks, including AM, on TSP, PCTSP, and CVRP.
  • LCP is architecture-agnostic: its seeder and reviser can use AM, pointer networks, POMO, or MDAM architectures.
  • For CVRP, sub-tours begin and end at the depot, and padding depot nodes equalizes segment lengths for parallel revision.
  • For PCTSP, small-scale revision fixes the visited-node set and tunes only its order, while large-scale tasks reuse a trained seeder as reviser.
  • The LCP procedure samples M seeds, decomposes them into K segments, and iteratively revises the segments for I iterations.

A.5 Details of Experimental Setting

The experimental setting uses randomly generated routing datasets and reports runtime under explicitly constrained hardware and batching conditions. These choices reflect differences between CPU heuristics and GPU-based DRL parallelism.

  • Datasets for TSP, PCTSP, and CVRP are randomly generated following Kool et al.'s method and code.
  • Runtime experiments use one NVIDIA RTX 2080 Ti GPU and one Intel i7-9700K CPU, with some exceptions.
  • Runtime values are average time per instance, combining reproduced AM and DRL-2opt results with results from existing implementations.
  • Evaluation batch size is restricted to B ≤100 because GPU and CPU parallelization differ and many practical routing settings are sequential.
  • LCP has fast serial speed because the seeder uses one inference, while parallel revision processes decomposed seeds simultaneously.
  • Large-scale runtime experiments use B = 1 for most methods, while DRL-2opt and NLNS use B = 10.
  • AM uses T = 1 for N = 20, 50, 100 and T = 0.1 for N = 500; LCP temperatures are reported separately.

B Ablation Study of Scaled Entropy Regularization

The scaled-entropy ablation evaluates how the entropy-reward coefficient α and scaling type affect TSP performance after seeding and revision. Results favor different scaling types across α ranges.

  • For α = 0.2 and 0.3, uniform scaled entropy regularization exceeds linear scaling on TSP (N = 100).
  • For α = 0.4 and 0.5, linear scaled entropy regularization outperforms uniform scaling and achieves the best performances across tested cases.
  • Table 5 reports cost after seeding and after revision, with lower cost preferred and the best performances marked among equal α values.

C Ablation to SoftMax Temperature

The temperature ablation compares AM and LCP across TSP sizes and finds that LCP is more robust to temperature variation. LCP also performs best at a higher temperature range than AM in one example.

  • Figure 5 presents temperature-cost graphs for AM and LCP on TSP with N = 50, 100, and 500.
  • LCP is robust to temperature-scaling variations, whereas AM is vulnerable to high temperature.
  • In TSP (N = 50), AM performs best at T = 2.0, while LCP performs best at 2.0 < T < 3.5.

D Applying the LCP to Other DRL Frameworks

LCP extends beyond its original framework by pairing diverse seeding with iterative revision, improving sampled solutions and supporting fast, accurate heuristic improvement.

  • Framework adaptation: LCP applied to a pointer network uses the pointer network as seeder and reviser(10) with five iterations.The reviser setting remains similar to prior experiments.
  • Framework adaptation: Pointer-network sampling costs 7.33 versus 3.95 for greedy selection, but LCP reduces sampling cost below the greedy method.The result supports revising diverse seeds, even when sampled seeds are initially unreasonable.
  • Ablation study: The ablation study compares entropy regularization, linear scaling, default uniform scaling, and pointer-network selection variants on TSP N = 20.Optimal gaps are measured against state-of-the-art solvers.
  • Reviser comparison: Seeder+reviser outperforms Seeder+DRL-2opt in both time and performance.The experiment characterizes the reviser as a fast and accurate improvement heuristic.

F Experiments of Training Convergence in Different PyTorch Seeds

Training-curve experiments examine the seeder across TSP, PCTSP, and CVRP and the reviser separately, while testing convergence across four random PyTorch seeds.

  • Training graphs: The seeder’s training graph covers TSP, PCTSP, and CVRP at N = 100.
  • Training graphs: A separate training graph evaluates the reviser’s training behavior.
  • Random-seed convergence: Both seeder and reviser converge steadily across 4 random seeds.The experiment addresses instability that DRL algorithms can show with different random seeds.

G Details of Real World Experiments on TSP

Real-world TSP evaluation uses 35 TSPLIB instances to test transfer from training at N = 100 across varied scales, with LCP outperforming baselines in quality and speed.

  • Experimental setup: The evaluation uses 35 TSPLIB instances to test performance on real-world problems and transfer across varied scales after training at N = 100.
  • Experimental setup: The experiment uses reviser(20) with I = 25, reviser(10) with I = 20, and sample width M = 2560.
  • Baselines: AM uses sample width M = 40000, while DRL-2opt uses I = 2000 in the comparison.
  • Results: 22 out of 35 cases outperform the baseline solver, while the average optimal gap improves over DRL-2opt by 2.5%.The method also runs overwhelmingly faster than DRL-2opt and AM.
  • Reporting: Table 7 reports performance and time, selecting the best result across SoftMax temperatures T ∈ {0.1, 0.5, 1, 2} and multiplying time by 4.
Loading 2110.13987v1…