Learning to Deliver: a Foundation Model for the Montreal Capacitated
  Vehicle Routing Problem
Samuel J. K. Chin Matthias Winkenbach Akash Srivastava
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 performs consistently and reliably on a range of
problem instance sizes and parameter values such as the vehicle capacity.