Neural combinatorial optimization

Overview

A combinatorial problem asks for the best arrangement of discrete choices, such as the order in which vehicles visit stops. The approach here treats the solution as a sequence of decisions. A neural policy scores the feasible next choices, and reinforcement learning trains it on sampled instances. Once trained, the network produces a complete solution by repeating the choice step, with no search at answer time 2608.14156 §3.

The shared invariant is that every step must respect the problem's constraints. The policy only chooses among actions that break no rule, which is enforced with masks 2608.14156 §3. Hard feasibility is therefore built into the action set, not learned.

Variants

Attention-based route builder with parallel routes

The only variant covered so far builds several routes at once. The base model is JAMPR, an extension of the attention model of Kool et al., which adds encoders for each route and vehicle 2608.14156 §2.2, §3. Card: Attention-based pickup-and-delivery route builder.

The authors add two changes to JAMPR 2608.14156 §3:

• A pickup-order mask: a delivery is offered only after its pickup.
• A soft cost: a missed client adds a penalty instead of making the plan infeasible. The cost is 13 per unit of distance plus 10 per missed client. The authors chose both weights empirically.

The paper does not say how each delivery is linked to its pickup, whether routes return to the depot, or what units the coordinates use. Those points decide the scale of the penalty weights, so a reimplementation must fix them itself 2608.14156 §3, §4.

Not covered by this page: learned partitioning and destruction operators, which the paper lists as future work 2608.14156 §7.

When to use which

The choice below rests on one paper, with author-reported results against a single baseline, OR-Tools 2608.14156 §5.

Implementation sketch

The loop below is written from the description in 2608.14156 §3. The paper gives no algorithm block, so the details marked "not stated" must come from elsewhere or be chosen and tested by the implementer.

# Build one solution with a trained policy  [arxiv:2608.14156 §3]
# Penalty: 13 * distance + 10 * missed client  [arxiv:2608.14156 §3]

def build_solution(instance, policy, kappa):
    # Encode all nodes once; the depot index enters the context  [§3]
    node_emb = encoder(instance.node_features)
    # kappa routes grow in parallel; kappa is not stated  [§3]
    routes = [start_route(instance.depot) for _ in range(kappa)]
    while unvisited_nodes_remain(routes, instance):
        # Keep only (route, node) pairs that break no rule: capacity,
        # time window, visited, pickup before delivery  [§3]
        actions = feasible_actions(routes, instance)
        # Route and vehicle state (load, node, time) feed the context  [§3]
        context = build_context(routes, node_emb, instance.depot)
        # Greedy or sampled choice; decoding at test is not stated  [§3]
        chosen = select(actions, policy(actions, context))
        append_node(routes[chosen.route], chosen.node)
    return routes

Training, as the paper describes it, samples fresh instances from a fixed distribution and stops when the path cost stops falling over 10 optimization steps 2608.14156 §4, §5.2. The optimizer, learning rate, batch size, embedding size and baseline are not stated 2608.14156 §3.

Contradictions

None known across the cited papers. Only one paper is covered so far.

Within that paper, the abstract and conclusions call the small and medium solutions "optimal". The only reference is OR-Tools, and no exact solver is reported, so that wording is not verified 2608.14156 §5.1, §6.

Papers

• Attention-based pickup-and-delivery route builder: attention-based route builder (JAMPR) adapted to pickup-and-delivery routing with capacity and time windows, using a pickup-order mask and a soft penalty.