On Distributional Dependent Performance of Classical and Neural Routing Solvers

Daniela Thyssens, Tim Dernedde, Wilson Sentanoe, Lars Schmidt-Thieme · 2025

Read On Distributional Dependent Performance of Classical and Neural Routing Solvers by Daniela Thyssens, Tim Dernedde, Wilson Sentanoe, Lars Schmidt-Thieme (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-02510.txt.

Introduction

Daniela Thyssens and three co-authors study how the training data's shape decides routing solver performance in this 2025 paper. Neural solvers learn delivery style problems from examples. They still trail hand built heuristics on open benchmarks. The authors change the game: they build one large base distribution of stops, then sample both training and test problems from it. The test cases are new, but they share the base's hidden structure. Classical meta-heuristics and leading neural solvers faced the same task.

Under this planted structure, the gap between neural solvers and the specialists shrank. Learning pays when the world has a stable shape to learn. The authors argue benchmark design has been unfair to learners: random instances erase the very regularity learning exploits. Real fleets do have such regularity, since cities and depots persist.

Catalog record

CREATORDaniela Thyssens, Tim Dernedde, Wilson Sentanoe, Lars Schmidt-Thieme
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-02510

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Distributional Dependent Performance of Classical and Neural Routing Solvers Daniela Thyssens, Tim Dernedde, Wilson Sentanoe, Lars Schmidt-Thieme Abstract Neural Combinatorial Optimization aims to learn to solve a class of combinatorial problems through data-driven methods and notably through employing neural networks by learning the underlying distribution of problem instances. While, so far neural methods struggle to outperform highly engineered problem specific meta-heuristics, this work explores a novel approach to formulate the distribution of problem instances to learn from and, more importantly, plant a structure in the sampled problem instances. In application to routing problems, we generate large problem instances that represent custom base problem instance distributions from which training instances are sampled. The test instances to evaluate the methods on the routing task consist of unseen problems sampled from the underlying large problem instance. We evaluate representative NCO methods and specialized Operations Research meta heuristics on this novel task and demonstrate that the performance gap between neural routing solvers and highly specialized meta-heuristics decreases when learning from sub-samples drawn from a fixed base node distribution. 1 Introduction The research field of Neural Combinatorial Optimization (NCO), predominantly in the subfield of routing problems, is concerned with learning a parametrized policy to solve a class of combinatorial optimization problems (COPs), thereby saving development effort as well as finding near-optimal solutions faster than traditional algorithms. To train NCO methods, training samples of a particular problem class are randomly generated according to some underlying distribution. For routing problems, this underlying distribution consists in most cases of uniformly at random sampled coordinate values between 0 and 1 (and, in case of the classical vehicle routing problem (VRP) also of uniformly at random distributed integer demand values between 1 and 10) [ 2 ] . Although NCO has seen substantial advancements, notable performance gaps remain when compared to state-of-the-art meta-heuristics from Operations Research (OR) [ 28 , 9 , 11 , 34 ] . We contend that the prevailing conceptualization of the underlying instance distributions in routing tasks is not only misaligned with real-world conditions, but also suboptimal for the development and evaluation of data-driven approaches. The training and test instances concurrently used in the literature constitute instance attributes that are sampled independently from each other and thus make for problem instances that are not directly linked through reoccurring attribute patterns. While the currently employed data generation scheme presents a non-trivial challenge, we argue that it hinders effective learning and pattern recognition, thereby limiting the ability of neural methods to exhibit their full potential. Figure 1 : Overview Subsampling Approach. The Base Node Distribution \mathcal{G}_{\text{base}}^{\text{X}} follows the underlying Random-Clustered (R-C) coordinate distribution introduced in Uchoa et al. 2017 . Moreover, we demonstrate that traditional solvers, although generally more robust to distributional assumptions, are nonetheless influenced by them. Our experimental results indicate that, under more structured instance distributions, machine learning-based methods can narrow the gap to — and in some cases even surpass the performance of — classical meta-heuristics . Rather than sampling entirely new instances from an underlying distribution, we construct large seed instances — referred to as the Base Node Distribution — based on varying underlying distributions (see Fig. 2 ). From each seed instance, both training samples and the final test set are obtained via subsampling . This setup induces the reocurrence of nodes across instances within a problem class, thereby encouraging NCO methods to internalize and exploit the structural properties of the seed distribution. From a real-world perspective, the reocurrence of specific nodes reflects many practical scenarios, such as those encountered by logistics service providers who regularly serve established customers, but in varying configurations influenced by seasonal and other periodic trends. For instance, a logistics company may consistently deliver goods to a set of regular retail clients, but the specific delivery schedules, routes, or quantities might vary depending on factors such as holiday shopping seasons, promotional events, or annual sales cycles. We train three representative NCO methods (POMO [ 28 ] , BQ [ 11 ] , and NeuOpt [ 34 ] ) on two routing tasks and evaluate them against the two leading state-of-the-art OR algorithms, LKH-3 [ 16 ] and HGS-CVRP [ 39 ] , to demonstrate that by reconfiguring the data generation process, ML-based methods can effectively learn the underlying distribution and, in some cases, outperform established OR meta-heuristics. In summary, we make the following contributions: • Novel NCO Learning Task : We reformulate the NCO learning task by having neural methods learn from subsamples of a given Base Node Distribution , enabling them to capture the underlying problem structure and distribution of problem instances through the reocurrence of nodes across instances. • New Datasets : We introduce new routing problem datasets, providing subsampled training and test sets, along with the data generators used to generate these samples. • Evaluation and Insights : Through a series of experiments, we show that the proposed subsampling approach narrows the performance gap to state-of-the-art meta-heuristics and, in some cases, even outperforms them for specific problem distributions. 2 Related Work NCO Data Distributions. To effectively apply data-driven methods to combinatorial problems, NCO assumes the existence of an underlying distribution over the instances within a given problem class [ 25 , 3 ] . This assumption is crucial, as most combinatorial problems are NP-hard, meaning no single solver can be efficient across all possible instances. Even traditional heuristics implicitly rely on assumptions about the instances they address [ 46 ] . However, for evaluating the capabilities of a learned system, the instance distribution must exhibit sufficient structure to be discoverable [ 49 ] . For VRPs, the distribution is inherently defined by how the following attributes are sampled: (1) the node coordinates, which determine customer locations, (2) the demand from each customer, (3) the position of the depot, and (4) the vehicle capacity. Typically, the coordinates and demands are sampled independently and uniformly at random [ 36 ] , while the vehicle capacity is held fixed. This results in a distribution that exhibits minimal structural complexity. While recent works [ 43 , 49 ] have extended their evaluation to more complex distributions, such as Rotation and Explosion [ 6 ] (see Figure 2 ), all prior works have generated problem instance attributes independently from the underlying distribution. We propose sampling instances from a base node distribution specific to a problem class, where the base distribution itself follows a designated underlying distribution. This approach complements existing distributions. Our experiments show that sampling from a fixed set of base nodes reduces the performance gap between NCO and classical methods. By introducing structure in a distribution-independent manner, our approach can be easily integrated into existing evaluation protocols . Neural Methods for Routing Problems NCO methods can roughly be divided into two categories: improvement -based methods and constructive approaches. Constructive methods create solutions from scratch by sequentially picking nodes with a parameterized policy until a complete solution is constructed [ 7 , 10 , 11 , 22 , 23 , 29 , 28 , 33 , 36 , 37 , 41 , 42 , 44 ] . Different computational trade-offs have been explored. Some approaches compute the entire network at every decision [ 11 , 33 ] , some

Read the complete text