Towards Foundation Models for Vehicle Routing Problems

News: RouteFinder has been accepted as an Oral presentatation at the ICML 2024 FM-Wild Workshop !

Install the package in editable mode:

pip install -e .

If you would like to install all dependencies including optional solvers, please install using pip install -e '.[dev,solver]'.

We recommend exploring this quickstart notebook to get started with the RouteFinder codebase!

Data may be generated by running the following command:

python routefinder/data/generate_data.py

and will be saved under the data/ directory.

Note that we provide the original testing data since the data may differ slightly across devices due to PyTorch's random number generator. The distribution will however be the same, so results should be comparable. To ensure full reproducibility and make sure the data is exactly the same, you may use the uploaded files under the data/ folder.

The main runner (example here of main baseline) can be called via:

python run.py experiment=main/rf/rf-100

You may change the experiment by using the experiment=YOUR_EXP, with the path under configs/experiment directory.

We consider 24 variants, which include the base Capacity (C). The $k=4$ features O, B, L, and TW can be combined into any subset, including the empty set and itself (i.e., a power set) with $2^k = 16$ possible combinations. Finally, we study the additional Mixed (M) global feature that creates new Backhaul (B) variants in generalization studies, adding 8 more variants.

We have the following environments available:

We additionally provide as baseline solvers for all baselines 1) OR-Tools and 2) the SotA PyVRP.

The main experiments on 100 nodes are (rf=RouteFinder) RF-POMO: rf/rf-100, RF-MoE-L: rf/rf-moe-L-100, MTPOMO mtpomo-100 and MVMoE mvmoe-100. You may substitute 50 instead for 50 nodes. Note that we separate 50 and 100 because we created an automatic validation dataset reporting for all variants at different sizes (i.e. here).

Note that for MVMoE-based models, one can additionally pass the model.hierarchical_gating=True to enable hierarchical gating (L, Light version) - and similarly, model.hierarchical_gating=False for the full version.

Note that additional Hydra options as described here. For instance, you can add +trainer.devices="[0]" to run on a specific GPU (i.e., GPU 0).

Other configs are available under configs/experiment directory.

To run EAL, you may use the following command:

python eal.py --path [MODEL_PATH]

with additional parameters that can be found in the eal.py file.

• For some reason, there seem to be bugs when training on M series processors from Apple (but not during inference somehow?). We recommend training with a discrete GPU. We'll keep you posted with updates!

• https://github.com/FeiLiu36/MTNCO/tree/main
• https://github.com/RoyalSkye/Routing-MVMoE
• https://github.com/yd-kwon/POMO
• https://github.com/ai4co/rl4co

If you find RouteFinder valuable for your research or applied projects:

@inproceedings{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},
    booktitle={ICML 2024 Workshop on Foundation Models in the Wild (Oral)},
    year={2024},
    url={https://openreview.net/forum?id=hCiaiZ6e4G},
    note={\url{https://github.com/ai4co/routefinder}}
}