RouteFinder: Towards Foundation Models for Vehicle Routing Problems
Authors:
Federico Berto,
Chuanbo Hua,
Nayeli Gast Zepeda,
André Hottung,
Niels Wouda,
Leon Lan,
Kevin Tierney,
Jinkyoo Park
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,…
▽ More
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 https://github.com/ai4co/routefinder.
△ Less
Submitted 21 June, 2024;
originally announced June 2024.
RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark
Authors:
Federico Berto,
Chuanbo Hua,
Junyoung Park,
Laurin Luttmann,
Yining Ma,
Fanchen Bu,
Jiarui Wang,
Haoran Ye,
Minsu Kim,
Sanghyeok Choi,
Nayeli Gast Zepeda,
André Hottung,
Jianan Zhou,
Jieyi Bi,
Yu Hu,
Fei Liu,
Hyeonah Kim,
Jiwoo Son,
Haeyeon Kim,
Davide Angioni,
Wouter Kool,
Zhiguang Cao,
Qingfu Zhang,
Joungho Kim,
Jie Zhang
, et al. (8 additional authors not shown)
Abstract:
Deep reinforcement learning (RL) has recently shown significant benefits in solving combinatorial optimization (CO) problems, reducing reliance on domain expertise, and improving computational efficiency. However, the field lacks a unified benchmark for easy development and standardized comparison of algorithms across diverse CO problems. To fill this gap, we introduce RL4CO, a unified and extensi…
▽ More
Deep reinforcement learning (RL) has recently shown significant benefits in solving combinatorial optimization (CO) problems, reducing reliance on domain expertise, and improving computational efficiency. However, the field lacks a unified benchmark for easy development and standardized comparison of algorithms across diverse CO problems. To fill this gap, we introduce RL4CO, a unified and extensive benchmark with in-depth library coverage of 23 state-of-the-art methods and more than 20 CO problems. Built on efficient software libraries and best practices in implementation, RL4CO features modularized implementation and flexible configuration of diverse RL algorithms, neural network architectures, inference techniques, and environments. RL4CO allows researchers to seamlessly navigate existing successes and develop their unique designs, facilitating the entire research process by decoupling science from heavy engineering. We also provide extensive benchmark studies to inspire new insights and future work. RL4CO has attracted numerous researchers in the community and is open-sourced at https://github.com/ai4co/rl4co.
△ Less
Submitted 21 June, 2024; v1 submitted 29 June, 2023;
originally announced June 2023.
