Benchmarking and Solving Vehicle routing problem on various Quantum Computing (QPU's)

Last updated on Jun 23, 2023

Organization
- Qkrishi
Student
- Shisheer S Kaushik
Mentors
- Raghavendra V

Vehicle Routing Problem

The Vehicle routing problem (VRP) is an NP-hard optimization problem that has been an interest of research fordecades in science and industry. The gist of the project is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency. Classical tools and methods provide good approximations to reach the optimal global solution. Quantum computing and quantum machine learning provide a new approach to solving combinatorial optimization of problems faster due to inherent speedups of quantum effects. Many solutions of VRP are offered across different quantum computing platforms using hybrid algorithms such as quantum approximate optimization algorithm and quadratic unconstrained binary optimization. In this work, we build a basic VRP solver for 3 and 4 cities using the variational quantum eigensolver on a fixed ansatz. The Project work is further extended to evaluate the robustness of the solution in several examples of noisy quantum channels. The performance of the quantum algorithm depends heavily on what noise model is used. In general, noise is detrimental, but not equally so among different noise sources.

The overall workflow we demonstrate comprises:

Establish the client locations. Normally, these would be available ahead of the day of deliveries from a database. In our use case, we generate these randomly.
compute the pair-wise distances, travel times, or similar. In our case, we consider the Euclidean distance, “as the crow flies”, which is perhaps the simplest possible.
compute the actual routes. This step is run twice, actually. First, we obtain a reference value by a run of a classical solver (IBM CPLEX) on the classical computer. Second, we run an alternative, hybrid algorithm partly on the quantum computer.
visualization of the results. In our case, this is again a simplistic plot.
In the following, we first explain the model, before we proceed with the installation of the pre-requisites and the data loading.

The project procedure can be summarized as follows:

Initialization *Install pip install qiskit-optimization[cplex]
initializer class that randomly places the nodes in a 2-D plane and computes the distance between them.
Classical solution using IBM ILOG CPLEX
Instantiate the classical optimizer class
Solve the problem in a classical fashion via CPLEX
Visualize the solution
Quantum solution from the ground up
Instantiate the quantum optimizer class with parameters
Check if the binary representation is correct
Encode the problem as an instance of QuadraticProgram
Solve the problem via MinimumEigenOptimizer
Visualize the solution

Conclusion

The research work demonstrates the various results of the benchmarking with respect to the characteristics compared.

Variational Quantum EigenSolver (VQE)

Benchmarking results for 3 nodes + depot (1) & 2 vehicles tested on `ibmq_qasm_simulator

Comparison results of `ibmq_qasm_simulation` and `ibm_quito`

Benchmarking results for 4 nodes + depot (1) & 3 vehicles tested on ibmq_qasm_simulator

Comparison results of `ibmq_qasm_simulation` and `ibm_quito`

Benchmarking results when tested on various optimizers, using SPSA, L_BFGS_B and SLQSP

Comparison results obtained when 3 discreet optimizers were utilized and simulated on `ibmq_qasm_simulation`

Benchmarking results for 5 nodes + depot (1) & 4 vehicles tested on `ibmq_qasm_simulator

Comparison results of `ibmq_qasm_simulation` and `ibm_oslo`

Quantum Approximate Optimization Algorithm (QAOA)

Benchmarking results when tested on 2 different optimizers, using SPSA and COBYLA for 5 nodes + depot (1) & 4 vehicles

Comparison results obtained when 2 discreet optimizers such as `COBYLA` and `SPSA`were utilized and simulated on `ibmq_qasm_simulation`

Results

This result discusses, there is a drastic variation between classical {expected) cost and Quantum cost in few of the cases and some cases have a similar costs.

There were certain factors which might have caused the error:

Using a ‘qasm simulator’ it will use sampling (shots) from the ideal distribution so there will be shot (sampling) noise in any given value.
The type optimizer utilized, as it needs to find a minimum in this noise - some best optimizers which could be ufor VRP [ SPSA, L_BFGS, COBYLA, SLSQP ] which was designed to work in noise is a reasonable choice.
Also the type of algorithm matters, In case of variational - SamplingVQE. The anstaz is customisable [One has the freedom to can choose or make a difference too]. But, the QAOA comes with its default ansataz.

Solving VRP using Quantum Annealing technique

Similarly an attempt to to use Quantum Annealing technique is performed by using Dwave-ocean-sdk and the implementation data and its test results can be found here:

Comparison results obtained when 3 discreet test_input{graphs} were simulated on `D-wave CPU`

Comparison results obtained when 3 discreet test_input{graphs} were computed on `D-Wave 2000Q QPU`

As seen in the above results, there are many different vehicles which are travelling in accordance with the defined input{graph}, hence each fastest and cost efficient routes are highligted using different sets of color combination. The depot is highlighted with Blue color to distinguish with other nodes.

Note that there are two input formats:

Full input The full input needs a graph file and a test file. In a graph file, you need to provide edges description: each line should contain two nodes’ ids and cost. Cost is related to what you want to optimize, for example: distance or time. In a test file, you need to provide information about depots, destinations and vehicles. If you want to solve an instance of MDVRP (without capacities), you only need to provide depots’ and destinations’ ids and the number of vehicles. If you want to solve CMDVRP, you also need to provide destinations, weights and vehicles capacities.
Normal input It needs only a test file. You need to provide information about depots, destinations, vehicles and costs of travelling between depots and destinations. If you want to solve MDVRP (without capacities), you only need to provide depots and destinations ids, number of vehicles and costs. Similar to Full Input, its the same condition in case of CMVRP

Depots and destinations are enumerated with natural numbers. If you have n depots and m destinations, depots will have numbers 0, 1, 2, …, n - 1 and destinations will have numbers n, n + 1, n + 2, …, n + m - 1. You need to provide (n + m) x (n + m) matrix with costs.

The problem uses DBScanSolver for MDVRP. It also uses another solver (solver attribute) to solve problems like VRP and TSP, and then tries to divide the solution to consecutive parts that will be served by vehicles. There is also an attribute ‘random’ - bigger value should give better solutions with bigger execution time.Using this solver with DBScanSolver should give the best effect. On smaller tests (with the number of destinations up to 50), you can use it with FullQuboSolver to reduce the size of QUBO. Note that using this solver with AveragePartitionSolver is exactly the same as using it with FullQuboSolver.

Resources

Quantum Annealing

↑