Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Prediction

1 Introduction

Vehicle routing problems (VRPs), represented by the travelling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP), appear in many real-world industrial scenarios, such as logistics planning [Sar and Ghadimi, 2023], circuit design [Brophy and Voigt, 2014], and robotic systems [Bullo et al., 2011]. Due to their NP-hard nature, solving VRPs (particularly at large scales) requires a trade-off between computational efficiency and solution quality. This challenge is traditionally tackled by heuristics or metaheuristics. However, designing high-quality heuristics typically requires considerable domain expertise and extensive parameter tuning, limiting their practical applicability.

∗Yaoxin Wu is the corresponding author

Recently, there has been a growing research interest in developing neural routing policies, which leverage neural networks to learn heuristics directly from data. Specifically, the Transformer architecture [Vaswani et al., 2017] is commonly used in constructive neural routing policies, which select nodes from the VRP instance sequentially and construct solutions (i.e., tours) in a step-by-step manner [Kool et al., 2019; Hua et al., 2025]. They offer high computational efficiency during inference and can match or even surpass the performance of some traditional algorithms [Hottung et al., 2025b].

Training neural routing policies is typically accomplished using either reinforcement learning (RL) [Kool et al., 2019; Kwon et al., 2020; Hottung et al., 2025a] or supervised learning (SL) [Luo et al., 2023; Drakulic et al., 2023]. Recent studies have shown that SL approaches exhibit significantly better generalizability on large-scale VRP instances compared to RL methods [Luo et al., 2023; Drakulic et al., 2023], highlighting the potential of SL in developing scalable and generalizable neural routing policies. Current SL-based methods, such as the Light-Encoder-and-HeavyDecoder (LEHD) model, are typically trained using crossentropy loss to predict the next node, conditioned on the previously selected node [Luo et al., 2023]. However, constructing VRP solutions constitutes a long-horizon planning task, often involving hundreds or thousands of nodes. The standard next-node prediction paradigm risks myopic decisions, as the model may fail to capture longer-range context crucial for route construction, thereby leading to a local optimum.

In this paper, we propose a multi-node lookahead prediction (MnLP) strategy for SL routing policies. Specifically, in addition to the standard decoding head that predicts next node, we introduce causal and discardable MnLP modules tasked with predicting future nodes. An auxiliary loss is designed for training these MnLP modules, thereby implementing the lookahead mechanism to enhance the representation learning of the main model. During the training stage, this mechanism encourages the model to account for long-term impact of its decisions by explicit multi-step predictions. At inference time, the MnLP modules are removed, and only the next-node head is used, ensuring no additional computational overhead compared to standard architectures. To demonstrate the effectiveness of MnLP, we conducted extensive experiments and proved its benefits in enhancing neural policies.

Our main contributions are summarized as follows: 1) We propose a novel architectural design for multi-node lookahead prediction in neural routing policies. The proposed MnLP modules operate exclusively during training, thereby introducing no additional computational overhead during inference; 2) We introduce a multi-depth auxiliary loss that guides the SL process to improve the model's long-horizon planning capability. This enables the learned policy to anticipate future decisions beyond next-node prediction; 3) We conduct extensive experiments demonstrating that our proposed training strategy can effectively enhance neural routing policies in terms of cross-size and cross-distribution generalization, as well as performance on real-world benchmarks.

2 RelatedWork

2.1 Neural Routing Policy

Neural routing policies constitute an important area within neural combinatorial optimization (NCO), and can be categorized into improvement and construction methods.

Improvement methods start from an initial solution and iteratively refine it through a neural network, which learns to optimize sub-problems, applies local search operators, or augments the existing solvers [Wu et al., 2021; Cheng et al., 2023; Kim et al., 2023]. In contrast, construction methods, pioneered by the Pointer Networks [Vinyals et al., 2015], directly generate problem solutions from scratch. By leveraging Transformer-like architectures and RL, the Attention Model (AM) proposed by [Kool et al., 2019] significantly advanced neural routing policies' performance. Building on AM, subsequent work has improved construction-based neural routing policies along several axes: test-time adaptation [Hottung et al., 2022; Kim et al., 2025], enhanced learning strategies [Wang et al., 2024], feature refinement [Li et al., 2024; Wang et al., 2025], and multi-task training [Berto et al., 2025; Jiang et al., 2024; Liu et al., 2025].

Beyond the typical Transformer-like modeling, some efforts have also explored alternative architectures. For example, LEHD [Luo et al., 2023] introduced a design with a light encoder and a heavy decoder to improve generalizability. Meanwhile, there are also studies that apply large language models (LLMs) to solve VRPs [Jiang et al., 2025; Yin et al., 2026], leveraging the power of large generative models to tackle routing challenges.

2.2 Training Paradigm

The training paradigms of neural policies broadly fall into two categories: RL and SL. RL-based approaches have achieved strong performance but typically suffer from sparse, delayed rewards and low sample efficiency (particularly on large-scale instances) [Kim et al., 2024]. To alleviate these limitations, prior work refines the RL pipeline via policy optimization with multiple optima (POMO) [Kwon et al., 2020], meta-learning [Zhou et al., 2023], and preference-based optimization [Liao et al., 2025].

In parallel, SL-based methods have gained traction for their strong cross-scale generalization [Drakulic et al., 2023; Luo et al., 2023]. By constructing partial solutions, they restrict training to a reduced solution space and shift from fullsolution construction to high-quality partial routes, thereby complementing RL by trading exploration for data efficiency and transfer. Empirically, SL markedly improves the generalizability of neural routing solvers [Luo et al., 2023]. However, despite recent refinements [Yao et al., 2024; Luo et al., 2025], most SL methods still use teacher-forced next-node cross-entropy, which optimizes local decisions rather than sequence-level quality and remains prone to exposure bias and error accumulation. We address this issue by extending standard next-node SL to predict multiple future nodes. This process equips the neural policy with stronger foresight during solution construction, thereby improving both performance and generalizability of SL-based routing policies.

2.3 Multi-token Prediction

Multi-token prediction (MTP) is a training framework for LLMs in which the model predicts a block of future tokens at each step rather than only the next token, building on prior work in blockwise decoding and non-autoregressive sequence modeling [Stern et al., 2018]. Increasing evidence suggests that pure next-token prediction underfits objectives requiring multi-step planning and long-horizon credit assignment [Bachmann and Nagarajan, 2024]. By supervising multiple future steps jointly, MTP encourages planful intermediate representations, mitigates myopic yet globally suboptimal behaviors induced by teacher forcing, and serves as a regularizer against overfitting to short-range patterns [Qi et al., ]. Empirically, MTP outperforms next-token prediction for LLM pre-training across diverse scales and tasks [Gloeckle et al., 2024; Gerontopoulos et al., 2025].

DeepSeek-V3 is a prominent real-world deployment of MTP, using it as an auxiliary pre-training objective [DeepSeek-AI et al., 2025]. Inspired by this design, we develop MnLP for SL-based routing policies. While conceptually related, we target VRPs rather than language modeling: MnLP omits heavy transformer blocks in MTP and trains over a feasible set that shrinks as nodes are visited instead of a fixed vocabulary, enabling the policy to anticipate multi-step decisions under an evolving decoding process.

3 Preliminaries

3.1 VRP Formulation

A VRP instance of size n is defined on a weighted graph G = (V, E), where V = {vi}ni=1 denotes node features (including the depot and customers) and E = {ei,j | i, j ∈ {1, . . . , n}, i ̸= j} is the set of edges. Without loss of generality, the depot is v1. Each edge ei,j has cost ci,j ≥ 0, forming a cost matrix C = [ci,j]. A feasible solution is represented as a node sequence τ = (x1, . . . , xk), where each xℓ ∈ [1, n] indexes node vxℓ ∈ V. The total travel cost is:

where we add the wrap-around term cxk, x1 because a closed tour is required. Given the feasible set Ψ, the objective is:

The feasible set Ψ encodes all problem-specific constraints. For the TSP, Ψ consists of Hamiltonian cycles that visit each node exactly once. For the CVRP, Ψ comprises a set of routes {τr}Rr=1 , each starting and ending at v1, such that every customer i ∈ V \ {v1} with demand di is served exactly once and the capacity constraint holds on every route:

We consider Euclidean VRPs, where each node has coordinates zi ∈ R2 and edge costs are ci,j = ∥zi - zj∥2.

3.2 LEHDmodel with SL

We select the LEHDmodel [Luo et al., 2023] as the backbone and use the proposed MnLP for its training, since: 1) LEHD is a neural policy that is typically trained by SL rather than RL; 2) unlike other SL models such as BQ-NCO [Drakulic et al., 2023], which learn an unconditional decision process, LEHD generates solutions in an auto-regressive manner, conditioning each decision on previous steps. This causal factorization matches MnLP's multi-step supervision: the node predicted by the (k - 1)-th MnLP module enters the decoding context of the k-th, yielding a coherent chain of future nodes. Thus, MnLP can supervise several future decisions at once, improving credit assignment across consecutive steps and reducing exposure bias compared with next-step SL paradigm.

LEHD consists of an encoder (e.g., the Shared Encoder in Figure 1), a decoder with L - 1 attention blocks (e.g., the Main Decoder), and an output head. Given node features V = (v1, . . . , vn) for an instance, a light encoder (a linear layer followed by an attention block) maps them to node embeddings H(E) = (h(0) 1 , . . . , h(0) n ). Each attention block comprises a multi-head self-attention layer (MultiHeadAttn) and a feed-forward network (FFN). Further computational details in the attention block are provided in Appendix A.

Instead of training for constructing the complete tour with n nodes, LEHD learns to sequentially construct the solution in np steps for a partial solution (x1, ..., xnp ), which is sampled from the optimal complete solution. In step t ∈ {1, ..., np}, the decoding process is conditioned on the embeddings of the first selected node h(0) x1 and the node selected in the previous step h(0) xt-1 , which together serve as the decoding context for the current step. More precisely, they interact with Ha through L - 1 attention blocks:

where Ha = {h(0) i | i ∈ {1, . . . , np} \ {x1, . . . , xt-1}} and W1, W2 are learnable matrices. The output head of the LEHD model incorporates an attention block, a linear layer with a learnable matrix WO, and a Softmax function to calculate the probabilities pt for selecting among all available nodes:

The SL paradigm employs a cross-entropy loss: Llehd = - ∑mi yi log(pt,i), where m is the number of available nodes; yi is a binary variable that denotes if vi is selected. However, if trained only with teacher-forced next-node SL, the model can be locally myopic because auto-regressive decoding weakens credit assignment and accumulates exposure bias, with generalization degrading as n grows.

4 Methodology

The MnLP framework (see Figure 1) consists of a shared encoder, a main decoder for next-node prediction, and K causal MnLP modules that predict K future nodes during training.

More specifically, each MnLP module k ∈ {1, . . . ,K} predicts node xt+k at decoding step t, leveraging the intermediate node representation produced by the preceding module. This design enforces causality across different prediction depths, meaning that each MnLP module receives contextual information from the previous one to predict the corresponding node. From these predictions, we obtain node-selection probabilities p(k) t and corresponding losses L(k) MnLP, which are combined with the main model loss to promote longhorizon planning. Notably, all MnLP modules are used solely during training and are discarded at inference time.

4.1 Model Architecture

The overall architecture of our model is illustrated in Figure 1. After encoding the VRP instance using the shared encoder, the main decoder and the MnLP modules perform depth-wise computation and apply task-specific output heads to select the node at depth k. The process is detailed below.

Encoder. The model uses a lightweight encoder that linearly projects raw node features V = (v1, ..., vn) (e.g., 2D coordinates for Euclidean TSP) and then applies a single Transformer-style attention block (MultiHeadAttn + FFN, as detailed in Appendix A) to produce the node-embedding matrix H(E) = (h(0) 1 , ..., h(0) n ), such that,

where WE denotes the learnable parameter of the linear layer. The node embeddings H(E) are shared by the decoder and all MnLP modules for depth-wise computation.

Depth-wise Computation. The main decoder and all the MnLP modules compute the representations used for node selection. As depicted by Figure 1, the k-th MnLP module comprises two LayerNorm (LN) operations, a linear layer with a learnable matrix W (k) I , an FFN layer, and a task-specific output head. At depth k = 0, the main model predicts xt at step t using the embedding of the previously selected node xt-1 as part of the decoding context. We generalize this process to a multi-node prediction setting: for any k > 0, the k-th MnLP module predicts node xt+k using an intermediate context representation h(k) t, obtained by combining 1) the representation from the (k - 1)-th module, h(k-1) t, and 2) the embedding of the ground-truth node xt+k-1, h(0) t+k-1 (for k = 1, h(k-1) t reduces to the embedding of xt-1). Following the normalization-then-projection design of DeepSeekV3 [DeepSeek-AI et al., 2025], we compute:

Note that Equation (8) is typically for TSP. In the case of other VRPs, we need to incorporate additional constraint information. For example, we introduce the updated vehicle capacity C (k) for CVRP, as the available vehicle capacity must be dynamically adjusted for each prediction depth k > 0. This is specified by: h′ (k) t = W (k) I concat(LN(h(k-1) t ), LN(h(0) t+k-1 ), WcC (k) ), where Wc is also a learnable matrix that projects C (k) to the embedding dimension. After that, we apply a FFN layer with LN to h′ (k) t for enriched representation learning, such that,

As shown in Figure 1, OutputHeadk takes input as h(k) t and generates probability p(k) t , which is introduced below.

Task-specific output head. The output head in k-th MnLP module predicts the (t + k)-th node (i.e., xt+k). Specifically, we use a task-specific output head OutputHeadk, which is also a parameterized and learnable component, to allow for an interaction between h(k) t and the available node embeddings H(E) . As a result, the probabilities of selecting each node at prediction depth k are calculated as below,

Considering the unique problem characteristics, we design task-specific output heads for different VRP variants. For the TSP, we compute the compatibility between the intermediate MnLP representation h(k) t at prediction depth k and the node embeddings H(E) simply via a dot-product operation:

where W (k) M and W (k) E are learnable matrices. This is followed by masking (as remarked below) and a Softmax operation imposed on the feasible set A(k) t at each depth k.

Remark 1 (Feasible set A(k) t at depth k). Let Sp be the node set of a sampled partial tour of length np. At each decoding step t, the available nodes (i.e., feasible set) for the depth-k prediction are A(k) t = { i ∈ Sp \ {x1, . . . , xt+k-1} }.

We ensure feasibility by assigning -∞ to the logits of all nodes not in A(k) t (same masking as in prior work [Kool et al., 2019]), including nodes visited by earlier MnLP depths. Consequently, the size of the feasible set |A(k) t | = np - (t + k-1) decreases with the increase of k. If t+k > np, we skip the computation of depth-k loss. Therefore, the final selection distribution is then computed only over A(k) t :

In contrast, the output head of CVRP requires a more elaborate mechanism due to the need to predict both the next customer and the possibility of returning to the depot [Luo et al., 2023]. To address this, we adopt an architecture similar to the decoder layer of the LEHD. Specifically, we first concatenate the representation h(k) t with H(E) (the embeddings of

Algorithm 1 Training with MnLP

Input: episodes per epoch E, batch size B Param: MnLP weight γ, warm-up epochs W, ratio α Output: trained model θ 1: for epoch e = 1, 2, . . . do 2: γe ← γ · min(1, e/(αW)) 3: for i = 1 to E/B do 4: Sample a batch of B instances and reset env 5: for decoding step t = 0, 1, . . . until termination do 6: if t ≤ 1 then 7: Select fixed nodes (e.g., depot/start) 8: else 9: (Lmain, LMnLP) ← FORWARD(θ) 10: L ← Lmain + γLMnLP 11: Update θ by backprop on L 12: end if 13: STEPENV() 14: end for 15: end for 16: end for 17: return θ

available nodes): ˜H(k) = concat(h(k) t ,H(E) ), which is then processed by an attention block to make the decoding context (i.e., h(k) t ) interact with the node embeddings. After that, the output ˜H(k) is used to compute the node selection probabilities at depth k, as formulated similarly by Equation (5).

4.2 MnLP Training

MnLP enhances policy learning with auxiliary supervision. As shown in Algorithm 1, each forward pass produces both the main logits for next-node prediction and lookahead logits for MnLP. The main loss Lmain and auxiliary loss LMnLP are computed in parallel (Figure 1), and parameters are updated using their weighted sum. Only the main decoder is used at inference, so test-time complexity remains unchanged.

More precisely, we extend the standard cross-entropy used in SL training to supervise predictions at multiple depths. Let mk = |A(k) t | be the size of the feasible set, p(k) t ∈ Rmk be the predicted distribution over A(k) t , and yk i ∈ {0, 1} be a one-hot indicator of the node selected at depth k (such that ∑i yk i = 1). For a given k, the depth-k MnLP loss is:

where np is the length of the teacher-forced partial solution. Note that when the lookahead would exceed the partial trajectory, the loss is masked out. To obtain the overall signal, we average the depth-wise losses across the K MnLP modules:

This auxiliary loss is then integrated into the training objective via a weighted sum with the main task loss:

Here, γ is the parameter that controls the contribution of the MnLP auxiliary supervision, and Lmain denotes the crossentropy loss of the main model. To prevent MnLP from dominating early training, we linearly ramp up γ over a warm-up period of W epochs (line 2 in Algorithm 1).

We train with L that augments the standard next-node head with K lookahead heads (k=1, . . . ,K). At depth k, supervision targets the node that would appear at step t+k under teacher forcing, but is applied already at t: the k-th MnLP module is conditioned on xt+k-1 and its cross-entropy is computed over A(k) t . This design shortens credit-assignment paths, strengthens long-range representations in the encoder, and provides multi-task regularization during training.

5 Experiments

We empirically evaluate our proposed MnLP training strategy on TSP and CVRP of various sizes and distributions, comparing it against the existing neural routing policies with different architectures and training algorithm designs.

Problem setting We follow standard data-generation protocols for TSP and CVRP in prior work [Kool et al., 2019]. In line with the settings used by LEHD [Luo et al., 2023], we use one million instances each for TSP100 (i.e., TSP instance with 100 nodes) and CVRP100 as the training sets. For evaluation, the TSP test set comprises 10,000 instances with 100 nodes, along with 128 instances each for problem sizes of 200, 500, and 1000 nodes. The CVRP test set mirrors this structure, containing the same number of instances across corresponding problem sizes. To obtain ground-truth labels, the optimal solutions for the TSP training set are computed using the Concorde solver [Cook et al., 2011], while optimal solutions for the CVRP training set are generated by the Hybrid Genetic Search (HGS) solver [Vidal, 2022].

Model and training setting We adopt the LEHD configuration from [Luo et al., 2023], which has a one-layer encoder and a decoder with 6 attention blocks. The node embedding dimension is set to 128. Each MultiHeadAttn layer uses 8 attention heads, while the dimension of FFN is 512. We set K = 4 for MnLP, while a sensitivity analysis of K is also conducted. The MnLP weight γ is 0.2 for TSP and 0.1 for CVRP, with W = 5 warm-up epochs and warm-up ratio α = 3. TSP and CVRP models are trained for 150 and 15 epochs, respectively, with a batch size of 1024. We use Adam with an initial learning rate 10-4 and decay rates 0.97 for TSP and 0.9 for CVRP. All experiments are run on a server with an AMD EPYC 7F72 CPU and an NVIDIA H100 GPU.

Baselines We compare with: (1) Classical solvers: Concorde [Cook et al., 2011], LKH3 [Helsgaun, 2017], HGS [Vidal, 2022], and OR-Tools [Furnon and Perron, 2024]; (2) Neural routing policies with architectural designs: ELG [Gao et al., 2024], LEHD [Luo et al., 2023], INViT [Fang et al., 2024], DGL [Xiao et al., 2025], and RELD [Huang et al., 2025]; (3) Neural routing policies with training algorithm designs: POMO [Kwon et al., 2020], which train using parallel solution trajectories, SADABL [Yao et al., 2024], which implements SL with data augmentation and bidirectional loss, and BOPO [Liao et al.,

2025], which uses best-anchored and objective-guided preference optimization. We retrain LEHD by following [Luo et al., 2023], and use the provided open-sourced models for other baselines. During evaluation, we measure: 1) average objective values (Obj.), 2) performance gap relative to baseline solvers (Gap), and 3) total inference time (Time).

5.1 Main Results

Table 1 reports results on uniformly distributed routing instances of various sizes. MnLP policies consistently outperform the original greedy LEHD, with gains increasing at larger scales. For example, on TSP1000, MnLP reduces the optimality gap from 3.563% to 2.852%-a 20% relative improvement, showing that multi-step supervision enhances long-horizon decision quality. These gains arise purely from training (MnLP modules are not used at inference), isolating the benefit to representation learning. Overall, the results support our claim that supervising multiple future steps yields richer long-range context and smaller gaps, especially on large instances where myopic errors accumulate.

More broadly, MnLP can also outperform other training strategies in the domain of NCO, including POMO, preference-based optimization (i.e., BOPO), and augmentation-driven SL (i.e., SA-DABL), especially when the instance size exceeds 100. The performance gain is more pronounced on n = 1000 instances, suggesting that MnLP training is particularly effective for large-scale problems. Meanwhile, compared to methods that introduce additional components and computationally intensive processes (e.g., INViT and DGL), MnLP achieves better efficiency while producing more optimal solutions across most task settings.

Although some models (e.g., ELG) perform better on indistribution n = 100 cases, MnLP remains competitive and can be strengthened via the Random Re-Construct (RRC) process from LEHD [Luo et al., 2023]. With only 100 RRC steps, MnLP surpasses these compared policies. Meanwhile, we also present the comparative results between our method and LEHD with the same RRC steps in Appendix C, which shows that our model with RRC can also outperform the original model, particularly on large-scale instances, demonstrating compatibility with test-time refinement techniques.

5.2 Cross-distribution Generalization

Generalizability is essential for neural routing policies: models that overfit a single distribution have limited practical value [Zhou et al., 2023]. Beyond the performance on uniformly distributed instances reported in Table 1, we further evaluate the cross-distribution generalization performance of our model on two typical benchmark distributions of VRP: the rotation distribution (R) and the explosion distribution (E), both of which have been used extensively in prior work [Zhou et al., 2023; Jiang et al., 2023]. The precise generation protocols are given in Appendix B.

Specifically, we randomly generate 1,000 instances for each distribution with different sizes: n = 500 and 1000. The comparative results are summarized in Table 2. It shows that the model trained with MnLP consistently improves upon the LEHD baseline across distributions and problem sizes. Taking TSP as an example, MnLP yields substantial relative reductions in average gap: at n = 1000, R decreases from 5.937% to 4.458% (24.9% improvement) and E from 6.397% to 5.189% (18.9% improvement). These results indicate that MnLP can effectively enhance cross-distribution generalizability and robustness to distributional shift.

Furthermore, we evaluate the MnLP-trained model on the widely used real-world benchmark datasets, including TSPLib [Reinelt, 1991] and CVRPLib [Uchoa et al., 2017], which reflect real-world problem distributions. The performance is evaluated on instances with Euclidean distance, and is compared against POMO and the original LEHD model in Table 3. Empirically, we observe that the MnLP improves overall performance across the benchmark datasets, showing its effectiveness on instances with various distributions.

5.3 Ablation and Sensitivity Analyses

We conduct ablation and sensitivity analyses to identify the optimal MnLP training configuration.

Effect of the value of γ. The impact of different values of γ on model performance is shown in Figure 2. By varying γ from {0.05, 0.1, 0.2, 0.3}, we observe that appropriate values of γ lead to improved training outcomes. For instance, setting γ = 0.2 for TSP and γ = 0.1 for CVRP yields the best average performance across various problem sizes. In contrast, excessively large values (e.g., γ = 0.3) may degrade performance, as the training process becomes increasingly biased toward optimizing the MnLP modules, thereby hindering sufficient learning of the main model for next node prediction.

Effect of different MnLP implementations. To evaluate our design, we compare different architectural implementations. In our method, MnLP modules share the encoder with the main model. Alternatively, they can share high-level node representations by reusing the network components before the output head, where the first MnLP module takes input from the (L - 1)-th decoder layer. We denote our encodersharing design as MnLP-E and the decoder-based variant as MnLP-D, and report results in Table 4. MnLP-E consistently outperforms MnLP-D, while MnLP-D sometimes even degrades performance compared with the original LEHD. This is likely because decoder representations already contain the current decoding context (e.g., the node selected at the previous step), which introduces noise for future prediction.

Effect of other factors. We further analyze the computational cost of MnLP, the impact of using different numbers of MnLP modules, and the role of the warm-up phase. Detailed results and discussions are provided in Appendix C.

5.4 Versatility Study

We evaluate the effectiveness of MnLP on another SL-based policy (i.e., SIL [Luo et al., 2025]) in Appendix C, where we demonstrate its versatility on different neural architectures.

6 Conclusion

We propose MnLP, a training-only multi-depth supervision scheme for SL-based neural routing policies that adds a lookahead mechanism to predict future nodes, injecting longhorizon signals without changing inference or adding testtime cost. Experiments show consistent gains across crosssize, cross-distribution, and real-world benchmarks, highlighting the value of multi-step supervision for NCO.

Future work includes extending MnLP to RL for longhorizon credit assignment, applying it to other CO tasks (e.g., scheduling), and designing test-time retained multi-step predictors to improve efficiency and solution quality.