RouteFinder

Towards Foundation Models for Vehicle Routing Problems

---

📰 News

• Oct 2024: The latest version of RouteFinder has been released! We have added the latest contributions from our preprint and much improved codebase
• Jul 2024: RouteFinder has been accepted as an Oral presentatation at the ICML 2024 FM-Wild Workshop!

🚀 Installation

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]'

🏁 Quickstart

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

Generating Data

Data may be generated by running the following command:

python generate_data.py

and will be saved under the data/ directory. Note that if data is generated correctly, the BKS solutions from PyVRP will automatically be loaded and you will be able to see the gaps as well while training and testing.

Running

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

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

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

Testing

You may use the provided test function:

python test.py --checkpoint checkpoints/100/rf-transformer.ckpt   

or with additional parameters:

usage: test.py [-h] --checkpoint CHECKPOINT [--problem PROBLEM] [--size SIZE] [--datasets DATASETS] [--batch_size BATCH_SIZE]
               [--device DEVICE] [--remove-mixed-backhaul | --no-remove-mixed-backhaul]

options:
  -h, --help            show this help message and exit
  --checkpoint CHECKPOINT
                        Path to the model checkpoint
  --problem PROBLEM     Problem name: cvrp, vrptw, etc. or all
  --size SIZE           Problem size: 50, 100, for automatic loading
  --datasets DATASETS   Filename of the dataset(s) to evaluate. Defaults to all under data/{problem}/ dir
  --batch_size BATCH_SIZE
  --device DEVICE
  --remove-mixed-backhaul, --no-remove-mixed-backhaul
                        Remove mixed backhaul instances. Use --no-remove-mixed-backhaul to keep them. (default: True)

We also have a notebook to automatically download and test models on the CVRPLIB here!

🔁 Reproducing Experiments

Main Experiments

The main experiments on 100 nodes are (rf=RouteFinder) RF-TE: rf/rf-transformer-100, RF-POMO: rf/rf-100, RF-MoE: rf/rf-moe-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 additional Hydra options as described here. For instance, you can add +trainer.devices="[0]" to run on a specific GPU (i.e., GPU 0).

Ablations and more

Other configs are available under configs/experiment directory.

EAL (Efficient Adapter Layers)

To run EAL, you may use the following command:

python run_eal.py

with the following parameters:

usage: run_eal.py [-h] [--model_type MODEL_TYPE]
                  [--experiment EXPERIMENT]
                  [--checkpoint CHECKPOINT]
                  [--lr LR] [--num_runs NUM_RUNS]

options:
  -h, --help            show this help message
                        and exit
  --model_type MODEL_TYPE
                        Model type: rf, mvmoe,
                        mtpomo
  --experiment EXPERIMENT
  --checkpoint CHECKPOINT
  --lr LR
  --num_runs NUM_RUNS

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

🚚 Available Environments

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:

	Capacity (C)	Open Route (O)	Backhaul (B)	Mixed (M)	Duration Limit (L)	Time Windows (TW)
CVRP	✔
OVRP	✔	✔
VRPB	✔		✔
VRPL	✔				✔
VRPTW	✔					✔
OVRPTW	✔	✔				✔
OVRPB	✔	✔	✔
OVRPL	✔	✔			✔
VRPBL	✔		✔		✔
VRPBTW	✔		✔			✔
VRPLTW	✔				✔	✔
OVRPBL	✔	✔	✔		✔
OVRPBTW	✔	✔	✔			✔
OVRPLTW	✔	✔			✔	✔
VRPBLTW	✔		✔		✔	✔
OVRPBLTW	✔	✔	✔		✔	✔
VRPMB	✔		✔	✔
OVRPMB	✔	✔	✔	✔
VRPMBL	✔		✔	✔	✔
VRPMBTW	✔		✔	✔		✔
OVRPMBL	✔	✔	✔	✔	✔
OVRPMBTW	✔	✔	✔	✔		✔
VRPMBLTW	✔		✔	✔	✔	✔
OVRPMBLTW	✔	✔	✔	✔	✔	✔

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

Known Bugs

• 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!

🤗 Acknowledgements

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

🤩 Citation

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}}
}

---