Solving the Vehicle Routing Problem

Exploring various quantum annealing-based approaches to solve the vehicle routing problem.

This project was part of the QOSF Quantum Computing Mentorship Program 2021 Cohort 4, mentored by Dr. Vesselin G. Gueorguiev
Mentees: The Qubit Players

Asish Kumar Mandoi
Junior Undergraduate at Indian Institute of Technology Kanpur, Department of Electrical Engineering
Website ~ LinkedIn ~ GitHub
Arya Bhatta
Junior Undergraduate at Indian Institute of Technology Kanpur, Department of Electrical Engineering
LinkedIn

This is now under development as part of a research group at QWorld.

Any usage of this code is free but do cite this code's authors and the organizations if you use it for research or commercial purposes. Please contact the authors for more information.

Introduction

Vehicle routing is a challenging logistics management problem. More precisely, it is an NP-hard combinatorial optimization problem.

Problem statement: What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?
Generalises The Travelling Salesman Problem (TSP).

Overview

The primary focus of the project has been on improving the applicability of quantum annealing-based solvers for the Vehicle Routing Problem (VRP) for large numbers of customers and vehicles by using a minimal number of qubits. It includes implementations of three solvers:

Route Activation Solver
GPS Solver (Guillermo, Parfait, Saúl) ~ [4]
DBSCAN Solver ~ [7]

The first two are non-clustering solvers that give exact solutions for the simplest variant of the VRP for small datasets and the third one is a clustering-based solver that gives approximate solutions for large datasets. The project also demonstrates the usage of the Binary Quadratic Model and Constrained Quadratic Model provided by D-Wave to formulate various other solvers including the above. The accuracy and runtimes of these solvers, calculated against the exact solutions obtained by classical implementations using Google's OR-Tools, are compared with each other.

The project was inspired from this video and this paper by Paweł Gora and others. A lot of initial ideas were borrowed from a project on the same topic by Shantom Borah and others.

Get started

You may start with the solve_vrp.ipynb notebook where you can choose to run any solver on any model and get the solutions to the Vehicle Routing Problem for any number of clients and vehicles. You can play with the time_limit parameter to see how the solver performs on different datasets, but make sure not to set it too high as you may exhaust your limited monthly resources on your D-Wave Leap account.

The quantum subfolder in the VRP folder further contains two more subfolders CQM_based and BQM_based. The first one contains the implementations of the solvers using the Constrained Quadratic Model (CQM) and the second one contains the implementations of the solvers using the Binary Quadratic Model (BQM).:

Constrained Quadratic Model is a new model recently released by D-Wave Systems that is capable of encoding Quadratically Constrained Quadratic Programs (QCQPs)
Binary Quadratic Model is a model that encodes Ising or QUBO problems.

Directory Structure

(click to expand)

VRP-explorations
├── _venv_                # (virtual python environment)
├── presentations
│   ├── notebook_1.ipynb
│   ├── .
│   ├── .
│   └── notebook_9.ipynb
├── datasets
│   ├── generate_dataset_for_vrp.ipynb
│   └── dataset.csv
├── results
│   ├── sol2.log
│   ├── .
│   ├── .
│   ├── sol11.log
│   ├── sol2.csv
│   ├── .
│   ├── .
│   ├── sol11.csv
│   └── results.png
├── TSP
│   ├── classical
│   │   └── gps.py
│   └── quantum
│       ├── fqs.py
│       └── gps.py
├── VRP
│   ├── classical
│   │   ├── ras.py
│   │   └── sps.py
│   └── quantum
│       ├── BQM_based
│       │   ├── full_qubo_solver.py
│       │   ├── route_activation_solver.py
│       │   ├── solution_partition_solver.py
│       │   ├── dbscan_solver.py
│       │   └── ...
│       └── CQM_based
│           ├── fqs.py
│           ├── gps.py
│           └── ras.py
├── utils.py
├── solve_tsp.py
├── solve_vrp.py
├── vrp_comparision_results.py
├── post_processing_results.py
├── requirements.txt
├── setup.sh
├── .gitignore
└── README.md

Results

The following is a concise comparision of results obtained by running (non-clustering) solvers for this dataset (generate_dataset_for_vrp.ipynb) using the ConstrainedQuadraticModel and LeapHybridCQMSampler provided by D-Wave.

The results for more instances can be found in the results folder.

It can be seen that these solvers give exact solutions for upto 7 nodes (6 clients and 1 depot) and are as good as classical ones in terms of accuracy and runtimes, and acceptable solutions till upto 15 nodes.

Run this repo

Locally

Requirements:

A bash terminal
Python version >= 3.9
D-Wave Leap account

# Clone this repo
git clone https://github.com/AsishMandoi/VRP-explorations.git

# Go into the project's main directory and setup the environment to run all codes
cd VRP-explorations && bash setup.sh

### The `setup.sh` script consists of the following steps:
# 1. Create a virtual environment (named '_venv_') if it doesn't exist
# 2. Install the required packages in the virtual environment
# 3. Run `dwave setup` to get access to the D-Wave backend solvers

The above process will also run the dwave setup command. This will require your authentication token from your account on D-Wave Leap. Learn more about how to set up your environment for using dwave-ocean-sdk.

On D-Wave Leap platform

Coming soon

Future work

Incorporate solutions for other more general variants of the problem (especially for the CVRPTW)
Make a circuit based algorithm from scratch (that does not use any application modules from any libraries) to solve VRP
Find potential real life applications for VRP (for e.g. Supply Chain, Traffic Flow Optimization)

References

Borowski, Michal, Gora, Pawel, "New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem" (2020)
Feld, Sebastian, et al. "A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer" (2019)
Fisher, Marshall L., Jaikumar, Ramchandran, "A generalized assignment heuristic for vehicle routing" (1981)
Gonzalez-Bermejo, Saul, et al. "GPS: Improvement in the formulation of the TSP for its generalizations type QUBO"
The QOSF cohort - 3 project by Shantom, Aniket and Avneesh based on this topic
Vehicle routing problem - Wikipedia
DBSCAN - Wikipedia
D-Wave's documentations on Binary Quadratic Model and Constrained Quadratic Model
Google's OR-Tools