Skip to content
Attention based model for learning to solve different routing problems
Branch: master
Clone or download
wouterkool Merge pull request #6 from wouterkool/v3
Updated code with major refactoring and included additional problems
Latest commit 3c51e65 Feb 7, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
images Major refactoring of code, added VRP model, added Pointer Network Jun 22, 2018
nets Updated code with major refactoring and included additional problems … Feb 6, 2019
pretrained
problems Updated code with major refactoring and included additional problems … Feb 6, 2019
utils Updated code with major refactoring and included additional problems … Feb 6, 2019
.gitignore Updated code with major refactoring and included additional problems … Feb 6, 2019
LICENSE Initial commit Mar 22, 2018
README.md Updated code with major refactoring and included additional problems … Feb 6, 2019
environment.yml Updated code with major refactoring and included additional problems … Feb 6, 2019
eval.py Updated code with major refactoring and included additional problems … Feb 6, 2019
generate_data.py Updated code with major refactoring and included additional problems … Feb 6, 2019
options.py Updated code with major refactoring and included additional problems … Feb 6, 2019
plot_vrp.ipynb Updated code with major refactoring and included additional problems … Feb 6, 2019
reinforce_baselines.py Updated code with major refactoring and included additional problems … Feb 6, 2019
run.py Updated code with major refactoring and included additional problems … Feb 6, 2019
train.py Updated code with major refactoring and included additional problems … Feb 6, 2019

README.md

Attention, Learn to Solve Routing Problems!

Attention based model for learning to solve the Travelling Salesman Problem (TSP) and the Vehicle Routing Problem (VRP), Orienteering Problem (OP) and (Stochastic) Prize Collecting TSP (PCTSP). Training with REINFORCE with greedy rollout baseline.

Paper

For more details, please see our paper Attention, Learn to Solve Routing Problems! which has been accepted at ICLR 2019. If this code is useful for your work, please cite our paper:

@inproceedings{
    kool2018attention,
    title={Attention, Learn to Solve Routing Problems!},
    author={Wouter Kool and Herke van Hoof and Max Welling},
    booktitle={International Conference on Learning Representations},
    year={2019},
    url={https://openreview.net/forum?id=ByxBFsRqYm},
}

Dependencies

Quick start

For training TSP instances with 20 nodes and using rollout as REINFORCE baseline:

python run.py --graph_size 20 --baseline rollout --run_name 'tsp20_rollout'

Usage

Generating data

Training data is generated on the fly. To generate validation and test data (same as used in the paper) for all problems:

python generate_data.py --problem all --name validation --seed 4321
python generate_data.py --problem all --name test --seed 1234

Training

For training TSP instances with 20 nodes and using rollout as REINFORCE baseline and using the generated validation set:

python run.py --graph_size 20 --baseline rollout --run_name 'tsp20_rollout' --val_dataset data/tsp/tsp20_validation_seed4321.pkl

Multiple GPUs

By default, training will happen on all available GPUs. To disable CUDA at all, add the flag --no_cuda. Set the environment variable CUDA_VISIBLE_DEVICES to only use specific GPUs:

CUDA_VISIBLE_DEVICES=2,3 python run.py 

Note that using multiple GPUs has limited efficiency for small problem sizes (up to 50 nodes).

Warm start

You can initialize a run using a pretrained model by using the --load_path option:

python run.py --graph_size 100 --load_path pretrained/tsp_100/epoch-99.pt

The --load_path option can also be used to load an earlier run, in which case also the optimizer state will be loaded:

python run.py --graph_size 20 --load_path 'outputs/tsp_20/tsp20_rollout_{datetime}/epoch-0.pt'

The --resume option can be used instead of the --load_path option, which will try to resume the run, e.g. load additionally the baseline state, set the current epoch/step counter and set the random number generator state.

Evaluation

To evaluate a model, you can add the --eval-only flag to run.py, or use eval.py, which will additionally measure timing and save the results:

python eval.py data/tsp/tsp20_test_seed1234.pkl --model pretrained/tsp_20 --decode_strategy greedy

If the epoch is not specified, by default the last one in the folder will be used.

Sampling

To report the best of 1280 sampled solutions, use

python eval.py data/tsp/tsp20_test_seed1234.pkl --model pretrained/tsp_20 --decode_strategy sample --width 1280 --eval_batch_size 1

Beam Search (not in the paper) is also recently added and can be used using --decode_strategy bs --width {beam_size}.

To run baselines

Baselines for different problems are within the corresponding folders and can be ran (on multiple datasets at once) as follows

python -m problems.tsp.tsp_baseline farthest_insertion data/tsp/tsp20_test_seed1234.pkl data/tsp/tsp50_test_seed1234.pkl data/tsp/tsp100_test_seed1234.pkl

To run baselines, you need to install Compass by running the install_compass.sh script from within the problems/op directory and Concorde using the install_concorde.sh script from within problems/tsp. LKH3 should be automatically downloaded and installed when required. To use Gurobi, obtain a (free academic) license and follow the installation instructions.

Other options and help

python run.py -h
python eval.py -h

Example CVRP solution

See plot_vrp.ipynb for an example of loading a pretrained model and plotting the result for Capacitated VRP with 100 nodes.

CVRP100

Acknowledgements

Thanks to pemami4911/neural-combinatorial-rl-pytorch for getting me started with the code for the Pointer Network.

This repository includes adaptions of the following repositories as baselines:

You can’t perform that action at this time.