Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems

In plain words

Routing problems ask for the shortest or cheapest way to visit a set of places, such as a delivery round or a fleet of vehicles serving customers. They are hard to solve exactly, so this paper trains a neural network to build a route one stop at a time. Earlier learned builders used a single policy, so their candidate routes tended to look alike. Here several decoders are trained together and pushed to disagree with each other, so the pool of candidate routes is more varied and more likely to contain a good one.

A search keeps a separate set of partial routes for each decoder. The paper also adds a shortcut to the encoder: after some steps, the stops that have already been visited are hidden from the attention layer at the top, so later decisions are based only on the stops that still matter. The authors report better routes than earlier learned methods, with more run time spent when the search is wider.

TL;DR

• Learns construction heuristics for routing problems (TSP, CVRP and four variants) with reinforcement learning, using a Transformer encoder and M = 5 attention decoders §3.1.1 §4.
• Each decoder is trained with its own REINFORCE term; a KL term between the first-step decoder distributions encourages diverse tours §3.3 eq. 11.
• The Embedding Glimpse (EG) layer approximates re-embedding of unvisited nodes by masking visited nodes in the top attention layer every p steps §3.2.
• Author-reported: MDAM with 50-wide beams reaches 0.38% (TSP100) and 2.23% (CVRP100) optimality gap. On CVRP100 it beats AM sampling (1,280 samples) with less time: 31 min (bs30) and 53 min (bs50) against 2 h tab. 1.

Problem

Exact solvers for routing are exponential in the worst case, and heuristics have to be designed by hand §1. Learned construction policies (pointer networks, the Attention Model of Kool et al.) produce solutions one node at a time, but the authors identify two weaknesses §1:

1. Low diversity. Sampling or beam search from one policy yields partly or completely repeated solutions, so few distinct candidates are explored §1 §3.1.2.
2. Stale embeddings. Node embeddings are computed once for the full instance, although visited nodes no longer matter for future choices. Full re-encoding after every step is too expensive §1 §3.2.

The paper assumes Euclidean instances with node coordinates (and demands or prizes for variants), trained on random uniform instances §4.

Method

Overview. One shared Transformer-style encoder embeds the nodes. M decoders with identical structure but separate parameters each generate a complete tour from the same embeddings §3.1.1 fig. 1. Training uses REINFORCE with a rollout baseline and a KL diversity term §3.3. At test time, each decoder keeps its own beam and the shortest finished tour is returned §3.1.2. The encoder's top attention layer is replaced by the EG layer, which is recomputed with visited nodes masked every p steps §3.2.

Encoder §3.1.1. Node inputs are projected to d = 128 §4. Each encoder block is multi-head self-attention (H = 8 heads, key size d/H) followed by a skip connection, batch normalisation, and a two-layer feed-forward network with ReLU and hidden size 512 §4 eq. 1-5. The depot (for VRP variants) has its own linear embedding attention_model.py. The encoder has three blocks in total §4; the first l-1 are computed once, and the last one is the EG layer graph_encoder.py.

Decoder §3.1.1 eq. 6-10. Each decoder m builds a context vector from the mean node embedding, the start node embedding, and the current node embedding, with trainable placeholders at the first step eq. 6. A glimpse attention over valid nodes updates the context eq. 7. Compatibilities between the query and node keys are clipped with tanh, using D = 10 eq. 9, and a softmax over valid nodes gives the step distribution eq. 10. The decoders have identical structure but unshared parameters §3.1.1.

Diversity term §3.1.1 eq. 11. The KL divergence between the output distributions of every ordered pair of decoders enters the objective with a negative sign, so training maximises the divergence. The formula sums over states, but training applies it only at the first step, where all decoders share the same empty partial solution; the authors argue that the first choice has a strong effect on the tour pattern §3.3.

Training loss §3.3 eq. 16-19. Each decoder samples one tour pi_m. The REINFORCE gradient is summed over decoders eq. 16, with a shared baseline b(x) equal to the smallest greedy-rollout tour length among decoders of the previous best model eq. 17-18. The KL term is subtracted with coefficient k_KL eq. 19.

# Training step  [§3.3] [eq. 16-19]
# Input:  batch of instances; baseline model (greedy, frozen)
# Output: one gradient update of the MDAM parameters

def train_step(instances, baseline_model):
    # Shared baseline: best greedy tour of the frozen model per instance
    # [§3.3] [eq. 17]
    baseline = best_greedy_tour_cost(baseline_model, instances)

    # Encode the nodes once; decoders share this embedding  [§3.1.1]
    embeddings = encoder(instances)                  # (B, N, d)

    # Each decoder samples its own tour and log-likelihood  [§3.3]
    for each decoder m in 1..M:
        tour, log_likelihood = sample_tour(decoder_m, embeddings)
        cost = tour_length(instances, tour)
        # REINFORCE term for decoder m  [§3.3] [eq. 16]
        reinforce_m = mean((cost - baseline) * log_likelihood)

    # Diversity term: KL between first-step distributions of all
    # ordered pairs of decoders, maximised  [§3.3] [eq. 11]
    diversity = sum_over_pairs(kl(first_step_m, first_step_n))

    # Total objective: summed REINFORCE minus weighted KL  [eq. 19]
    loss = sum_m(reinforce_m) - k_kl * diversity
    gradient_step(loss)                              # Adam, lr 1e-4 [§4]

Embedding Glimpse layer §3.2 eq. 12-15 fig. 1. The lowest l-1 attention blocks are reused unchanged. The top attention layer recomputes attention with the attention weights to visited nodes set to minus infinity, followed by the same projection, skip, normalisation and feed-forward steps eq. 14-15. This is applied every p steps, not every step, because one node is removed per step and the embeddings change slowly §3.2. The paper gives p = 2, 4, 8 for TSP20, 50, 100 and p = 2, 6, 8 for CVRP20, 50, 100 §4.

# Embedding Glimpse re-embedding  [§3.2] [eq. 13-15]
# Input:  frozen lower-layer outputs, top-layer attention, visited mask
# Output: refreshed node embeddings for the next decision

def embedding_glimpse(frozen_lower, top_attention, visited):
    # Keep the first l-1 blocks fixed; only the top layer changes  [§3.2]
    scores = top_attention_scores(frozen_lower)  # (H, N, N)
    # Visited nodes get minus infinity, i.e. they are never attended  [§3.2]
    scores = where(visited, -inf, scores)
    # Re-run the attention output and feed-forward block  [eq. 14-15]
    refreshed = feed_forward_block(frozen_lower + attend(scores))
    return refreshed

Customised beam search §3.1.2 fig. 2. Given a total beam size, each decoder gets its own beam of size B = ceil(total / M), so beams never mix decoders. Partial tours inside one beam are merged when they are inferior to another: they share the start node, visited set and current node (the same remaining subproblem), and the other tour is not longer and has at least as much vehicle capacity left §3.1.2 fig. 2. When two partials are merged, the surviving one takes the larger probability of the two §3.1.2. The paper reports bs30 and bs50 as B = 30 and B = 50 per decoder, i.e. total beams of 150 and 250 with five decoders §4.1.

# Customised beam search, one beam per decoder  [§3.1.2]
# Input:  M decoders; per-decoder beam size B
# Output: the shortest complete tour found by any beam

def beam_search(decoders, beam_size):
    # Beams are kept separate per decoder, so their tours stay diverse
    # [§3.1.2]
    for each decoder m in decoders:
        beam = [empty partial tour]
        while some partial tour is unfinished:
            # Extend every partial tour with its valid next nodes
            candidates = expand(beam, decoder_m)
            # Merge candidates with the same remaining subproblem when
            # they are inferior  [§3.1.2] [fig. 2]
            candidates = merge_inferior(candidates)
            # Keep the B best by accumulated log-probability  [§3.1.2]
            beam = top_k(candidates, beam_size)
    return shortest(all finished tours)

Problem variants §4 [suppl.]. Capacities are fixed at 30, 40 and 50 for 20, 50 and 100 nodes, with integer demands from 1 to 9 §4. SDVRP, OP, PCTSP and SPCTSP follow the Attention Model setup and are described in the supplementary material; invalid nodes are masked at each step §4 [suppl.: "More details on the Comparative Study"].

Hyperparameters

Results

Author-reported. Setup: random uniform instances with 20, 50 and 100 nodes (TSP, CVRP, SDVRP, OP, PCTSP, SPCTSP) §4 §4.1. MDAM runs on one RTX 2080 Ti GPU; Concorde and LKH3 provide reference values for TSP and CVRP, run in parallel on 32 virtual CPUs; baseline numbers come from their original papers; Gurobi and OR Tools are run with time limits tab. 1 note. Times are for 10,000 test instances, following the Attention Model protocol tab. 1 note. "Bold" is best among learned methods; "*" is best overall (source convention, shown here as *). AM sampling uses 1,280 samples tab. 1 note.

tab. 1 Main comparison (Obj = mean tour cost; Gap vs reference; Time).

tab. 2 Architecture ablation, greedy decoding (TSP and CVRP).

[suppl. Table S.1] Temperature-tuned AM sampling (1,280 samples) vs MDAM beam search (CVRP; obj only).

[suppl. Table S.2] Generalisation to larger CVRP, trained on n = 100.

Other reported findings, all author-reported: the multi-decoder variant with greedy decoding improves on a single decoder tab. 2; each decoder wins the best-tour count in roughly similar amounts on CVRP20 fig. 3; merging in the beam search improves all instance sets, and more decoders help at fixed beam size [suppl.: "More Analysis of MDAM"] fig. S.1 fig. S.2. The figure values are not in the source text and are not reproduced here.

Paper vs code

Compared at code_commit 19b0bf8 (repository liangxinedu/MDAM, linked from the paper §4). The owner name matches the first author, and the README names the paper README.md. The comparison below covers the TSP and CVRP paths. The SDVRP, OP, PCTSP and SPCTSP code was not read in depth.

• Gradient scale across decoders. Paper sums the REINFORCE term over decoders §3.3 eq. 16. Code adds each decoder's loss divided by the number of decoders attention_model.py. The effective learning rate of the REINFORCE part is therefore 1/M of the paper's sum, and the KL term is not divided attention_model.py.
• KL aggregation. Paper sums the KL over states, decoder pairs and nodes §3.3 eq. 11. Code takes the mean over decoder pairs and the batch attention_model.py and applies the first step only. With k_KL = 0.01 this changes the effective diversity weight; the paper does not say which convention k_KL refers to.
• Beam expansion width. The paper does not state how many successors a beam entry expands. The search code overwrites the expansion width with the constant 3, after computing it from the beam size [code: nets/model_search.py#L165-L166]. Each beam therefore considers 3 successors per entry, not beam-width many.
• Baseline replacement. Paper says the baseline is the best model among previous epochs §3.3. Code replaces the rollout baseline only if a paired, one-sided t-test on the validation set gives p < 0.05 [code: reinforce_baselines.py#L205-L214] options.py.
• Rollout baseline value. Matches the paper: the rollout takes the minimum cost over decoders train.py and the decoders are set to greedy train.py.
• EG defaults. Paper gives per-size interval values §4. The command-line default is 200, which effectively disables EG; the README's TSP20 example passes 2 options.py README.md.
• Gradient clipping. Code clips the global norm to 1.0 by default [code: options.py#L41-L42]. The paper does not mention clipping.
• Re-embedding. Paper masks visited nodes with minus infinity §3.2 eq. 13. Code multiplies the stored attention by the unvisited mask and renormalises graph_encoder.py; this is equivalent for softmax weights. Code adds 1e-9 to the denominator for VRP variants only graph_encoder.py.
• Merging criteria. Paper's inferiority rule §3.1.2 matches the code's checks for shared visited set, first and current node, and the distance and used-capacity comparisons model_search.py.
• Matches. Tanh clipping D = 10 attention_model.py; FF size 512 graph_encoder.py; Adam, lr 1e-4 [code: run.py#L96]; CVRP capacities and demands [code: problems/vrp/problem_vrp.py#L181-L193].
• Not verifiable from code. The CVRP100 batch size of 256 §4 is not set per problem in the code, and the README gives only the TSP20 command.

Pitfalls

• Equation and table numbers were counted from the LaTeX source (aaai.tex), not from the compiled PDF. Equations were numbered in order of appearance (eq. 1-19), tables as Table 1 and 2, supplementary as S.1 and S.2, figures as 1-3 and S.1-S.2. Check against the PDF before relying on them.
• Expansion width is missing from the paper. The code expands only 3 successors per beam entry, so a 30-wide beam sees at most 90 candidates per step model_search.py. Copy this constant if you want to reproduce the reported beam results.
• Learning-rate scale depends on M. Dividing the REINFORCE loss by M changes the step size relative to the summed form in the paper eq. 16. Pick one convention and keep the KL weight consistent with it.
• KL weight is not portable. k_KL = 0.01 was tuned on TSP20 only §4. Re-tune if you change M, the batch size, or the KL normalisation.
• The KL term can be infinite. First-step log-probabilities are floored at minus 1e9 before the KL is computed attention_model.py. Without this floor, masked actions give -inf and the KL is undefined.
• Batch normalisation at evaluation. The search script calls model.train() before evaluating search.py, so BatchNorm uses batch statistics. Results can depend on the evaluation batch size (default 1024 options.py). The paper does not discuss this.
• Depot location. The paper says cities are sampled uniformly but does not state where the depot is. The code samples it uniformly in the unit square as well problem_vrp.py. Treat this as the authors' choice, not as a paper requirement.
• Time columns mix scopes. Table 1 times are for 10,000 instances [tab. 1 note]; §4.1 gives 6.7 s per CVRP100 instance for bs50 without instance parallelism. The two numbers are not directly comparable §4.1.
• Figure 2 caption is copied from Figure 1. The source gives the same caption text to the search figure fig. 2, so the figure's own description is not in the source. Use the body text §3.1.2 instead.
• Supplementary sections are unnumbered. They are cited by title, e.g. [suppl.: "More Analysis of MDAM"].
• Repository license. The LICENSE file is MIT but its copyright line names Wouter Kool (2018), who is the upstream author; the README says MDAM is developed from the Attention Model code README.md. Record code_license: MIT as the license, and keep this note in mind when reusing code.

Lineage

• Builds on: the Attention Model of Kool et al. (Transformer encoder, pointer attention decoder, sampling baseline and 1,280-sample evaluation) §2 tab. 1. Not linked to a card in this wiki.
• Builds on: pointer networks and REINFORCE training of routing policies §2.
• Builds on: a prior routing paper's step-wise re-embedding idea, which EG generalises with better efficiency §3.2. The source cites it as 9226142; its title is not given in the source.
• Compared against: NeuRewriter (improvement heuristic) §4.1 tab. 1, REOPT, OR Tools, Gurobi, LKH3, Concorde and Compass tab. 1.