RL for Combinatorial Optimization: Pointer Networks and Learning to Route

TL;DR

Classical combinatorial optimization problems — the traveling salesman problem, vehicle routing, bin packing, job scheduling — are NP-hard, and the standard approach is hand-designed heuristics or exact solvers that scale poorly. RL reframes these as sequential decision problems: build a solution one piece at a time (e.g., one city visited at a time), treating each construction step as an action and the final solution quality as the (delayed) reward. Pointer Networks provide the key architectural trick — an attention mechanism that “points to” one of the input cities rather than generating from a fixed vocabulary, so the same network handles inputs of any size. Trained with REINFORCE against tour length as the reward, these models learn construction heuristics directly from data rather than from hand-designed rules. Used in vehicle routing, job-shop scheduling, and chip placement.

Constructing a Solution One Step at a Time

graph LR
    A[Problem Instance - e.g. city coordinates] --> B[Encoder]
    B --> C[Attention Over Unvisited Inputs]
    C --> D[Point to Next City]
    D -->|mask as visited, repeat| C
    D --> E[Complete Tour]

    style D fill:#6366f1,color:#fff

Problem Statement

The traveling salesman problem (TSP) — visit every city exactly once and return home, minimizing total distance — has no known efficient exact algorithm for large instances, and classical heuristics (nearest-neighbor, 2-opt, Lin-Kernighan) are hand-designed and don’t automatically improve as more solved instances become available. RL offers a different path: learn a construction policy directly from data, so the “heuristic” is whatever the network discovers works well, rather than whatever a human happened to design.

Pointer Networks: Attention That Points, Not Generates

Ordinary sequence-to-sequence models generate output tokens from a fixed vocabulary — but a TSP tour’s “vocabulary” is the input cities themselves, and there’s a different number of cities in every problem instance. Pointer Networks (Vinyals et al., 2015) solve this by using attention not to blend input representations into an output (as in standard attention), but to produce a probability distribution directly over the input positions, effectively pointing at which input city to visit next:

class PointerNetwork(nn.Module):
    def __init__(self, input_dim, hidden_dim):
        super().__init__()
        self.encoder = nn.LSTM(input_dim, hidden_dim, batch_first=True)
        self.decoder_cell = nn.LSTMCell(input_dim, hidden_dim)
        self.attention = nn.Linear(hidden_dim * 2, 1)

    def forward(self, city_coordinates, decoder_steps):
        encoder_outputs, (h, c) = self.encoder(city_coordinates)
        visited_mask = torch.zeros(city_coordinates.size(0), city_coordinates.size(1))
        tour = []

        decoder_input = city_coordinates[:, 0]   # start from an arbitrary first city
        for _ in range(decoder_steps):
            h, c = self.decoder_cell(decoder_input, (h, c))

            # Attention score against every input city, masking out already-visited ones
            scores = self.attention(torch.cat([encoder_outputs, h.unsqueeze(1).expand_as(encoder_outputs)], dim=-1))
            scores = scores.squeeze(-1).masked_fill(visited_mask.bool(), float("-inf"))

            probs = F.softmax(scores, dim=-1)
            next_city = torch.multinomial(probs, 1)   # sample which city to visit next
            tour.append(next_city)
            visited_mask.scatter_(1, next_city, 1)
            decoder_input = city_coordinates.gather(1, next_city.unsqueeze(-1).expand(-1, -1, city_coordinates.size(-1))).squeeze(1)

        return tour

Masking out already-visited cities at each step is what enforces the “visit every city exactly once” constraint directly in the architecture, rather than needing the network to learn that constraint purely from the training signal.

Training With REINFORCE Against Tour Length

Neural Combinatorial Optimization (Bello et al., 2016) trains a Pointer Network end-to-end with REINFORCE (covered in the companion policy gradient article), using negative tour length as the reward — a natural fit, since tour quality is only known once the full construction sequence is complete, exactly the kind of delayed, whole-episode reward REINFORCE was designed for:

def combinatorial_reinforce_loss(log_probs, tour_length, baseline):
    reward = -tour_length                      # shorter tours are better
    advantage = reward - baseline               # baseline: often a separate, exponential-moving-average critic
    return -(log_probs.sum(dim=-1) * advantage.detach()).mean()

The baseline here plays exactly the same variance-reduction role as in the companion policy gradient article — without it, tour-length-based rewards across different problem instances vary too much in absolute scale to provide a clean, low-variance gradient signal.

Attention-Based Construction: Beyond Recurrence

Attention, Learn to Solve Routing Problems! (Kool et al., 2019) replaces the Pointer Network’s recurrent encoder-decoder with a fully attention-based (transformer-style) architecture, letting the model attend directly over all cities’ embeddings without the sequential bottleneck of an LSTM encoder, which both improves solution quality and speeds up training on larger problem instances.

Improvement Heuristics: Learning to Refine, Not Just Construct

A separate line of work trains RL agents not to construct a tour from scratch, but to iteratively improve an existing solution — learning when and how to apply local search moves like 2-opt (reversing a segment of the tour) to a candidate solution, effectively learning a smarter, learned version of classical local-search metaheuristics rather than replacing them outright:

def learned_2opt_step(policy, current_tour, tour_length_fn):
    i, j = policy.select_segment_to_reverse(current_tour)   # learned action: which segment to reverse
    candidate_tour = reverse_segment(current_tour, i, j)
    improvement = tour_length_fn(current_tour) - tour_length_fn(candidate_tour)
    return candidate_tour if improvement > 0 else current_tour, improvement

Comparison Table

Approach	Solution Building Strategy	Architecture
Pointer Networks	Construct tour step-by-step from scratch	LSTM encoder-decoder with pointing attention
Attention-Based Construction	Construct tour step-by-step from scratch	Transformer-style full attention, no recurrence
Learned Improvement Heuristics	Iteratively refine an existing candidate solution	Policy selects local-search moves (e.g., 2-opt)

Applications

Vehicle routing and logistics — delivery route optimization, where the same learned construction policy generalizes across different customer location sets without needing per-instance re-optimization from scratch.
Job-shop and scheduling problems — sequencing tasks on machines to minimize completion time follows the same construct-a-solution-step-by-step framing.
Chip placement — treating the sequential placement of circuit components as a construction problem, closely related to Google’s AlphaChip work covered in the companion RL-for-scientific-discovery article.
Any NP-hard problem with a natural step-by-step construction process — bin packing, knapsack variants, and network design problems have all been approached with the same general Pointer Network-style framing.

Key Learnings

The key architectural insight — pointing at inputs instead of generating from a fixed vocabulary — is what makes one trained model handle problem instances of any size. This is a genuinely different requirement than standard sequence generation, since the “vocabulary” (the set of cities) changes with every new problem instance.
Delayed, whole-solution rewards make this a natural fit for REINFORCE and policy gradient methods specifically, since tour quality genuinely can’t be evaluated until construction is complete — there’s no natural per-step reward the way there is in many other RL domains.
Construction and improvement are complementary strategies, not competing ones. A learned construction policy provides a good starting solution quickly; a learned improvement policy can then refine it further — in practice, the strongest systems often combine both rather than relying on construction alone.

References

Vinyals, O., Fortunato, M., Jaitly, N. (2015). Pointer Networks.
Bello, I. et al. (2016). Neural Combinatorial Optimization with Reinforcement Learning.
Kool, W., van Hoof, H., Welling, M. (2019). Attention, Learn to Solve Routing Problems!