  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.
