Skip to content

Latest commit

 

History

History
243 lines (170 loc) · 16.1 KB

README.md

File metadata and controls

243 lines (170 loc) · 16.1 KB

RouteFinder

arXiv OpenReview Slack License: MITTestOpen In Colab

Towards Foundation Models for Vehicle Routing Problems

RouteFinder Overview

📰 News

  • Feb 2025: A new version (v0.3.0) of RouteFinder has been released. We have added several improvements, among which increasing the number of VRP variants from 24 to 48! See details on the release notes
  • Oct 2024: A new version (v0.2.0) 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]
                  [--variants_finetune VARIANTS_FINETUNE]
                  [--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
                        Experiment type
  --variants_finetune VARIANTS_FINETUNE
                        Variants to finetune on
  --checkpoint CHECKPOINT
  --lr LR
  --num_runs NUM_RUNS

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

🚚 Available Environments

VRP Problems

We consider 48 VRP variants. All variants include the base Capacity (C). The $k=5$ features O, B, L, TW, and MD can be combined into any subset, including the empty set and itself (i.e., a power set with $2^k = 32$ possible combinations. The Mixed (M) global feature creates new Mixed Backhaul (MB) variants in generalization studies, adding 16 more variants. We have the following environments available:

VRP Variant Capacity (C) Open Route (O) Backhaul (B) Mixed (M) Duration Limit (L) Time Windows (TW) Multi-depot (MD)
CVRP ✔
OVRP ✔ ✔
VRPB ✔ ✔
VRPL ✔ ✔
VRPTW ✔ ✔
OVRPTW ✔ ✔ ✔
OVRPB ✔ ✔ ✔
OVRPL ✔ ✔ ✔
VRPBL ✔ ✔ ✔
VRPBTW ✔ ✔ ✔
VRPLTW ✔ ✔ ✔
OVRPBL ✔ ✔ ✔ ✔
OVRPBTW ✔ ✔ ✔ ✔
OVRPLTW ✔ ✔ ✔ ✔
VRPBLTW ✔ ✔ ✔ ✔
OVRPBLTW ✔ ✔ ✔ ✔ ✔
VRPMB ✔ ✔ ✔
OVRPMB ✔ ✔ ✔ ✔
VRPMBL ✔ ✔ ✔ ✔
VRPMBTW ✔ ✔ ✔ ✔
OVRPMBL ✔ ✔ ✔ ✔ ✔
OVRPMBTW ✔ ✔ ✔ ✔ ✔
VRPMBLTW ✔ ✔ ✔ ✔ ✔
OVRPMBLTW ✔ ✔ ✔ ✔ ✔ ✔
MDCVRP ✔ ✔
MDOVRP ✔ ✔ ✔
MDVRPB ✔ ✔ ✔
MDVRPL ✔ ✔ ✔
MDVRPTW ✔ ✔ ✔
MDOVRPTW ✔ ✔ ✔ ✔
MDOVRPB ✔ ✔ ✔ ✔
MDOVRPL ✔ ✔ ✔ ✔
MDVRPBL ✔ ✔ ✔ ✔
MDVRPBTW ✔ ✔ ✔ ✔
MDVRPLTW ✔ ✔ ✔ ✔
MDOVRPBL ✔ ✔ ✔ ✔ ✔
MDOVRPBTW ✔ ✔ ✔ ✔ ✔
MDOVRPLTW ✔ ✔ ✔ ✔ ✔
MDVRPBLTW ✔ ✔ ✔ ✔ ✔
MDOVRPBLTW ✔ ✔ ✔ ✔ ✔ ✔
MDVRPMB ✔ ✔ ✔ ✔
MDOVRPMB ✔ ✔ ✔ ✔ ✔
MDVRPMBL ✔ ✔ ✔ ✔ ✔
MDVRPMBTW ✔ ✔ ✔ ✔ ✔
MDOVRPMBL ✔ ✔ ✔ ✔ ✔ ✔
MDOVRPMBTW ✔ ✔ ✔ ✔ ✔ ✔
MDVRPMBLTW ✔ ✔ ✔ ✔ ✔ ✔
MDOVRPMBLTW ✔ ✔ ✔ ✔ ✔ ✔ ✔

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

A tip for you!

Do you want to improve the performance of your model with no effort? Use our Transformer structure, based on recent models such as Llama and DeepSeek ;)

VRP Problems

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

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