publications

The Capacitated Vehicle Routing Problem (CVRP) underpins modern last-mile logistics. Current Neural Combinatorial Optimization (NCO) methods construct CVRP solutions autoregressively, inheriting sequential decoding bottlenecks, sensitivity to spatial symmetries, and brittle out-of-distribution behavior. We revisit the classical Cluster-First-Route-Second (CFRS) paradigm – long known to be asymptotically optimal but largely overlooked by NCO – and argue that it is structurally aligned with the core strengths of deep learning: similarity and assignment over global context, rather than the construction of long sequential tours. We introduce Neural CFRS, the first purely non-autoregressive one-shot neural CFRS framework for the CVRP. It enforces global fleet-capacity constraints end-to-end via a differentiable entropic Optimal Transport layer, producing a continuous transport plan to sparsify an exact capacitated assignment solver. We provide formal theoretical guarantees that our architecture intrinsically abstracts away spatial, inter-route permutation, and intra-route traversal symmetries. By equipping the framework with a pre-trained spatial vocabulary, we unlock extreme parameter efficiency and zero-shot scaling. Designed primarily for real-world spatial distributions under a constant capacity setting, Neural CFRS scales robustly to out-of-distribution instances with a < 4% gap – retaining an approximate 5% gap at this scale even as an ultra-lightweight, single-layer architecture. Furthermore, when deployed out-of-the-box on standard benchmarks, we achieve a highly competitive 2.73% optimality gap on size-100 problems.

In this paper, we present the Foundation Model for the Montreal Capacitated Vehicle Routing Problem (FM-MCVRP), a novel Deep Learning (DL) model that approximates high-quality solutions to a variant of the Capacitated Vehicle Routing Problem (CVRP) that characterizes many real-world applications. The so-called Montreal Capacitated Vehicle Routing Problem (MCVRP), first formally described by Bengio et al. (2021), is defined on a fixed and finite graph, which is analogous to a city. Each MCVRP instance is essentially the sub-graph connecting a randomly sampled subset of the nodes in the fixed graph, which represent a set of potential addresses in a real-world delivery problem on a given day. Our work exploits this problem structure to frame the MCVRP as an analogous Natural Language Processing (NLP) task. Specifically, we leverage a Transformer architecture embedded in a Large Language Model (LLM) framework to train our model in a supervised manner on computationally inexpensive, sub-optimal MCVRP solutions obtained algorithmically. Through comprehensive computational experiments, we show that FM-MCVRP produces better MCVRP solutions than the training data and generalizes to larger sized problem instances not seen during training. Even when compared to near-optimal solutions from state-of-the-art heuristics, FM-MCVRP yields competitive results despite being trained on inferior data. For instance, for 400-customer problems, FM-MCVRP solutions on average fall within 2% of the benchmark. Our results further demonstrate that unlike prior works in the literature, FM-MCVRP is a unified model, which …

The Traveling Salesman Problem (TSP) is a problem that has been formally studied since the 1930s and attracts great theoretical and practical interest. The theoretical aspects are particularly interesting as the TSP is an NP-hard problem and exact solutions for large TSPs are difficult to obtain. On the practical side, the growth of e-Commerce has resulted in more deliveries and it is increasingly important to obtain higher quality routes to increase efficiency. To that end, we introduce a Human Inspired Heuristic (HIH) that converts a road network semantic map into a truncated distance matrix that can be passed to a traditional TSP solution algorithm. The HIH can be further augmented in the image domain with our proposed novel Convolutional Neural Network (CNN). Our proposed CNN takes as input this original road network semantic map and outputs a reduced road network of plausible paths that are learned from near-optimal route instances. Through extensive numerical experiments, we find that additional pre-processing done by the CNN does not improve the performance of the HIH. In the context of real-world applications, a HIH designed based on physical constraints already works well. While the CNN in its current form in general fails to outperform a HIH, we did find one instance where it outperformed. This suggests that there is potential for CNNs to outperform and a promising research direction is to predict semantic maps in an autoregressive manner and reduce the reliance or remove entirely, the HIH.