RouteFinder

RouteFinder: Towards Foundation Models for Vehicle Routing Problems

¹KAIST ²Bielefeld University ³University of Groningen ⁴VU Amsterdam ⁵OMELET AI4CO^†

Abstract

Vehicle Routing Problems (VRPs) are optimization problems with significant real-world implications in logistics, transportation, and supply chain management. Despite the recent progress made in learning to solve individual VRP variants, there is a lack of a unified approach that can effectively tackle a wide range of tasks, which is crucial for real-world impact. This paper introduces RouteFinder, a framework for developing foundation models for VRPs. Our key idea is that a foundation model for VRPs should be able to model variants by treating each variant as a subset of a larger VRP problem, equipped with different attributes. We introduce a parallelized environment that can handle any combination of attributes at the same time in a batched manner, and an efficient sampling procedure to train on a mix of problems at each optimization step that can greatly improve convergence robustness. We also introduce novel Global Feature Embeddings that project instance-wise attributes efficiently onto the latent space and help the model understand different VRP variants. Finally, we introduce Efficient Adapter Layers, a simple yet effective technique to finetune pre-trained RouteFinder models to solve novel variants with previously unseen attributes outside of the original feature space. We validate our approach through extensive experiments on 24 VRP variants, demonstrating competitive results over recent multi-task learning models. We make our code openly available at this https URL.

Vehicle Routing Problems

We consider a collection of VRP variants that each consist of one or more attributes, resulting in a rich set of routing problems with practical relevance. Each of these variants offers a unique generalization task for RouteFinder. We consider in total 24 VRP variants. We divide the attributes we consider into node attributes, global attributes, and edge attributes. Node attributes are specific to the depot and customer nodes and local to specific nodes, such as (linehaul) demands, backhaul demands, and time windows. Global attributes represent structural aspects of the problem as a whole, e.g., open vs. closed routes, distance limits, and the type of backhaul.

Unified VRP Environment

We define an environment capable of modeling all of the previously discussed VRP attributes simultaneously, essentially building an OVRPBLTW environment: an open route vehicle routing problem with linehauls, backhauls, distance limit, and time windows. The environment supports subsets of the OVRPBLTW defining other VRP variants, i.e., some attributes can be “turned off.” In this way, all attributes characterizing a VRP variant can simply be turned “on” and “off”, allowing us to model up to 16 different problem types with one single environment. This approach can be easily extended (e.g., by including different location sampling mechanisms, backhaul classes, etc.), allowing for even more future problem variants to be modeled with the same environment.

Mixed Batch Training

We introduce a flexible approach which we coin Mixed Batch Training (MBT) to efficiently reuse a single dataset to generate multiple problem variants, optimizing data storage and processing capabilities. We observe that the OVRPBLTW problem variant is the most general problem variant we study in this paper, and can be used to generate any of the other variants by selectively removing the (O), (B), (L), or (TW) attributes. MBT is flexible and scalable, capable of adapting to any problem where different constraints or features might be selectively activated or deactivated.

Efficient Adapter Layers

We propose Efficient Adapter Layers (EAL), a simple yet effective approach for few-shot learning for VRP foundation models. Consider a linear projection layer \(\mathbf{W}\in\mathbb{R}^{k\times d}\) as the original weight matrix for the projection from the raw attribute to latent space, where \(k\) is the number of attributes and \(d\) is the hidden dimension. In this work, for simplicity, we consider unbiased linear projections to the latent space. This can be trivially extended to general affine projections using a bias term. To accommodate \(l\) new attributes, EAL augments \(\mathbf{W}\) with zeros. The new matrix \(\mathbf{W}^{\prime}\in\mathbb{R}^{(k+l)\times d}\) can be written as

where \(\mathbf{0}\in \mathbb{R}^{l\times d}\) is a matrix of zeros. Thus, the augmented matrix \(W^{\prime}\) retains the original \(k\) attributes and adds \(l\) new attributes, which are initialized to zero. Note that doing so does not affect the model as the new \(l\) dimensions are muted until fine-tuning on new variants occurs, enabling many new attributes to be included in virtually any part of the model via EAL.

Main Results

RouteFinder can scale better than the neural baselines in real-world settings. Moreover, training on any possible attribute combination (either with our MBT sampling or without) greatly improves the performance of RouteFinder and baselines, even for tasks such as CVRP, both in distribution and real-world benchmarks.

BibTeX

@article{berto2024routefinder,
  title={RouteFinder: Towards foundation models for vehicle routing problems},
  author={Berto, Federico and Hua, Chuanbo and Zepeda, Nayeli Gast and Hottung, Andr{\'e} and Wouda, Niels and Lan, Leon and Tierney, Kevin and Park, Jinkyoo},
  journal={arXiv preprint arXiv:2406.15007},
  year={2024}
}