implementation of MDVRP solver

• Deep Reinforcement Learning(Policy Gradient, model architecture has Multi-Head Attention layer)
• GA(Genetic Algorithm)
• Google OR-Tools(https://developers.google.com/optimization/routing)

├── Csv -> mean of cost and time during test 
├── Png -> plot images during test
│
├── GA
│   └── data
│
├── Ortools
│   └── data
│
└── Torch
    ├── data
    ├── Nets -> python codes for neural network
    ├── Pkl -> pickle files contaning hyperparameter
    ├── Weights -> pt files of pre-trained weights 
    └── Csv -> csv files of train log

I leave my own environment below. I tested it out on a single GPU.

• OS:
  • Linux(Ubuntu 18.04.5 LTS)
• GPU:
  • NVIDIA® GeForce® RTX 2080 Ti VENTUS 11GB OC
• CPU:
  • Intel® Xeon® CPU E5640 @ 2.67GHz
• NVIDIA® Driver = 455.45.01
• Docker = 20.10.3
• nvidia-docker2(for GPU)

• Python = 3.6.10
• PyTorch = 1.6.0
• scipy
• numpy
• plotly(only for plotting)
• matplotlib(only for plotting in GA code)
• pandas(only for mean of test score)

Make sure you've already installed Docker

docker version

latest NVIDIA® Driver

nvidia-smi

and nvidia-docker2(for GPU)

1. build or pull docker image

build image

./docker.sh build

pull image from dockerhub

docker pull docker4rintarooo/mdvrp:latest

2. run container using docker image(-v option is to mount directory)

./docker.sh run

If you don't have a GPU, you can run

./docker.sh run_cpu

• train
• inference(with 10 data)
• inference(with 1 data)
  
  

First move to Torch dir.

cd Torch

Then, generate the pickle file contaning hyperparameter values by running the following command.

python config.py

you would see the pickle file in Pkl dir. now you can start training the model.

python train.py -p Pkl/***.pkl

set parameter(n_depot, n_car_each_depot, n_customer, capa) by editing test.sh and run it.
g option generates 10 test data in Torch/data, Ortools/data and GA/data dir.

./test.sh g

If you create data by mistake, you can remove them with rm option

./test.sh rm

Now you can test with or, to and ga option.
You can see the result score by running cd Csv/ && ./run.sh dir.

Generate test data

(GA -> txt file, Torch and Ortools -> json file).

python dataclass.py

Plot prediction of the pretrained model

cd Torch && python plot.py -p Weights/***.pt -t data/***.json -b 128

Compare the results

cd GA && python main.py data/***.txt

cd Ortools && python main.py -p data/***.json

• https://github.com/Rintarooo/VRP_DRL_MHA
• https://github.com/wouterkool/attention-learn-to-route
• https://github.com/d-eremeev/ADM-VRP
• https://qiita.com/ohtaman/items/0c383da89516d03c3ac0 (written in Japanese)

• https://github.com/skatsuta/vrp-solver

• https://github.com/Lagostra/MDVRP

• https://github.com/mathiasaap/Multi-Depot-Routing---Genetic-algorithm

• https://neo.lcc.uma.es/vrp/vrp-instances/multiple-depot-vrp-instances/