From Comparison to Selection: Enhancing Cross-Scale Generalization of Pointer Networks Trained with Reinforcement Learning for for Capacitated Vehicle Routing Problem
Authors: Sofiene Lassoued, Devara Tertia, Stefan Lier, Andreas Schwung
Organizations: South Westphalia University of Applied Sciences, Automation Technology and Learning Systems Luebecker Ring 2, Soest, 59494, North Rhine-Westphalia, Germany · South Westphalia University of Applied Sciences, Logistik und Supply Chain Management Lindenstr.53, Meschede, 59872, North Rhine-Westphalia, Germany
Vehicle routing in delivery and logistics remains challenging as the number of clients varies. Classical approaches based on mixed-integer programming and heuristics can scale poorly or require problem-specific design, motivating learning-based alternatives. Reinforcement learning is particularly promising, provided a single policy can generalise across problem sizes without retraining. Although attention-based Pointer Networks are inherently size-agnostic, their solution quality degrades under both upscaling and downscaling. Using the Capacitated Vehicle Routing Problem (CVRP) as a controlled proxy, we investigate this degradation and identify three contributing factors: shifts in node density, attention dispersion, and dilution of the mean-pooled graph context. We systematically compare architecture-wide, encoder-side, and decoder-side modifications to address these limitations and propose a learned, permutation-invariant graph-context aggregation mechanism, implemented as a weighted average and as Set2Set. Results reveal distinct requirements for transfer in each direction: entropy-based attention scaling reduces the CVRP20-to-CVRP100 performance gap by 1.41 percentage points, while the proposed aggregation methods achieve the largest improvement on the more challenging CVRP100-to-CVRP20 transfer, approximately 0.9 percentage points. Exploiting this complementarity, we introduce an approach selector that chooses the best model for each training-target size pair. The selector reduces cost relative to the reference model across all nine seen train-test pairs and eight of nine pairs involving unseen sizes (CVRP35, CVRP75, and CVRP200), achieving improvements of up to 3.2%.
Figures & tables
Figure 1: Overview of the encoder-decoder attention-model policy: the reference architecture together with the architecture-wide, encoder-side and decoder-side approaches evaluated in this work.
Approach
Source
Origin
A
Entropy-based scaling (ESF)
S2
[ 44 ]
A
Learnable scaling (LSF)
S2
[ 44 ] (suggested)
E
GraphSAGE encoder
S2
[ 13 ]
E
Set Transformer encoder
S2, S3
[ 24 ]
D
Weighted-average context
S3
proposed
D
Set2Set context
S3
proposed
Table 1: Approaches, the degradation source they address and their origin. A: architecture-wide, E: encoder-side, D: decoder-side. Origin: citation, taken from the literature; proposed, contribution of this paper.
Train
CVRP20
CVRP50
CVRP100
CVRP20
6.480 (0.00)
13.692 (2.18)
25.408 (5.23)
CVRP50
6.649 (2.61)
13.400 (0.00)
24.277 (0.55)
CVRP100
6.984 (7.77)
13.611 (1.58)
24.145 (0.00)
Table 2: Reference attention-model policy: average solution cost and, in brackets, cross-size optimality gap (%). Rows are training size, columns are test size.
Figure 2: Entropy of the decoder action distribution of the reference policy at each decoding step, averaged over the test instances. Panels from left to right: test on CVRP20, CVRP50 and CVRP100 (note the different vertical scales); lines: models trained on CVRP20, CVRP50 and CVRP100.
Figure 3: Mean-pooled graph context of the CVRP100-trained reference policy for the individual test instances, projected on its first two principal components. Panels from left to right: test on CVRP20, CVRP50 and CVRP100; darker cells contain more instances.
Upscaling
Downscaling
Approach
20 → 50
20 → 100
50 → 100
50 → 20
100 → 20
100 → 50
A
ESF
↑ 0.48
↑ 1.41
↑ 0.03
↑ 0.37
↑ 0.24
↓ 0.04
A
LSF
↑ 0.23
↑ 0.34
↑ 0.06
↓ 0.16
0.00
↑ 0.43
E
GraphSAGE
↑ 1.43
↑ 3.07
↑ 1.84
↓ 2.07
↓ 5.42
↓ 1.78
E
Set Transformer
↑ 0.67
↑ 0.49
↓ 0.15
↓ 0.31
↓ 1.08
↑ 0.54
D
Weighted avg. †
↑ 0.16
↓ 0.41
↓ 0.09
↓ 0.09
↑ 0.91
↑ 0.33
Table 3: Gap gain Δ of every approach with respect to the reference (pp, Eq. ( 18 )). ↑ : smaller gap than the reference (improvement), ↓ : larger gap (degradation). A: architecture-wide, E: encoder-side, D: decoder-side; † proposed. Best gain per transfer in bold. The gains of GraphSAGE are read together with its weaker same-size models (Table 5 ).
Seen sizes
Unseen sizes
Train
20
50
100
35
75
200
CVRP20
↑ 0.20
↑ 0.47
↑ 0.56
↑ 0.26
↑ 0.49
↑ 3.20
CVRP50
↑ 0.08
↑ 0.25
↑ 0.40
↓ 0.03
↑ 0.35
↑ 0.46
CVRP100
↑ 1.07
↑ 0.41
↑ 0.43
↑ 0.49
↑ 0.41
↑ 0.35
Table 4: Approach selector on the fresh instance set (seed 6249): cost reduction relative to the reference (%), (zref−zsel)/zref×100 ; ↑ : cheaper than the reference, ↓ : more expensive. CVRP35, CVRP75 and CVRP200 are unseen sizes.
Approach
CVRP20
CVRP50
CVRP100
Reference / ESF
6.480
13.400
24.145
LSF
6.475
13.393
24.116
GraphSAGE
6.634
13.793
25.160
Set Transformer
6.474
13.423
24.115
Weighted avg. †
6.466
13.408
24.069
Set2Set †
6.487
13.374
24.050
Table 5: Same-size average cost (train = test) of the reference and of every approach; lower is better. ESF equals the reference by construction.
Department of Industrial Engineering, Tsinghua University, Beijing 100084, P.R. China · School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, P.R. China
Leicester International Institute, Dalian University of Technology, Panjin, 124221, Liaoning, China. · Department of Electronic and Information Technology, Dalian University of Technology, Panjin, 124221, Liaoning, China.