=Paper=
{{Paper
|id=Vol-3132/Short_9.pdf
|storemode=property
|title=Solving the Problem of Vehicle Routing on Modern Quantum-Classical Cloud Services
|pdfUrl=https://ceur-ws.org/Vol-3132/Short_9.pdf
|volume=Vol-3132
|authors=Leonid Hulianytskyi,Vyacheslav Korolyov,Oleksandr Khodzinskyi
|dblpUrl=https://dblp.org/rec/conf/iti2/HulianytskyiKK21
}}
==Solving the Problem of Vehicle Routing on Modern Quantum-Classical Cloud Services==
https://ceur-ws.org/Vol-3132/Short_9.pdf
Solving the Problem of Vehicle Routing on Modern Quantum-
Classical Cloud Services
Leonid Hulianytskyi, Vyacheslav Korolyov and Oleksandr Khodzinskyi
V.M. Glushkov Institute of Cybernetics of Ukrainian National Academy of Sciences, 801 box, 1 build., 40
Glushkov prosp., Kyiv, 03680, Ukraine
Abstract
Hybrid quantum-classical services for solving optimization problems are already used by
leading international corporations in competition, and achieving "quantum superiority" is
an absolute global trend. The use of quantum computing allows accelerating the solution
of several economic problems, logistics, virology, and many high technologies, which
determines the financing of this area's basic research around the world. The goal of the
article is to study algorithms for solving routing problems on quantum computers.
It should be noted that modern quantum computers have significant limitations on both
the number of qubits and the number of connections between qubits or the limited depth
of the circuit. In addition, modern quantum computers can give only approximate solu-
tions to combinatorial optimization problems, which is a consequence of the imperfec-
tion of technologies for creating and maintaining the stability of quantum states and
many other physical limitations. This means that many routing algorithms will not soon
be able to run on quantum computers.
Therefore, the authors limited the review of quantum algorithms for solving the problem
of vehicle routing to a list of algorithms that have been tested on real quantum computers
and for which the source code for programs is given by their developers. Algorithms and
computational schemes for solving the problem of vehicle routing on modern hybrid
quantum-classical cloud services of IBM and D-wave, as well as quantum computer
simulators, are studied and discussed.
Keywords 1
Quantum computer, quantum computer mathematics, qubit, vehicle routing problem, travel-
ing salesman problem
1. Introduction
Quantum computers (QC) have the potential advantage over classical processors because, in addi-
tion to arithmetic and logic operations, quantum superposition is used in algorithms. The computing
power of modern quantum processors, also known as "noisy quantum devices of intermediate scale",
is significantly limited due to the small number of qubits and connections between them, imperfect
control of qubit states, short coherence time, and poor error correction. The noise of quantum compu-
ting devices creates errors that affect both the state of qubits and the stability of the global minimum,
prepared by the procedure of mapping the optimization problem to the quantum system. Another
characteristic of QC is the ratio of the time of stability of qubits and couplings between them to the
time of computational operations. This characteristic allows us to estimate how many arithmetic and
logic operations can be performed during the existence of qubits. Hence, it shows the computational
performance of a quantum system for performing algorithms.
Solving combinatorial optimization problems by the method of quantum annealing is widely used
in materials science, chemistry, logistics, pharmaceuticals, bioinformatics, computational biology, in-
Information Technology and Implementation (IT&T-2021), December 01-03, 2021, Kyiv, Ukraine
EMAIL: leonhul.icyb@gmail.com (A. 1); korolev.academ@gmail.com (A. 2); okhodz@gmail.com (A. 3)
ORCID: 0000-0002-1379-4132 (A.1); 0000-0003-1143-5846 (A. 2); 0000-0003-4574-3628 (A.3);
©️ 2022 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
281
depth training for neural network training, and in the financial sector. Solving optimization problems
on hybrid quantum-classical computers and simulators (models) of QCs allows accelerating the solu-
tion of many known problems on graphs, clustering, optimization of an investment portfolio, vehicle
routing, protein folding, scheduling, modeling of chemical reactions, drug research, etc.
QCs are evolving in the following directions:
increasing the number of qubits and the connections between them [1, 2] (up to 7,000 cubic
meters in 2023);
development of a complex of computer systems and information technologies [1, 3], which
can simultaneously perform arithmetic and logic operations on quantum circles and annealing;
creation of universal QCs [4], which combine several physical qubits into logical ones to
reduce calculation errors due to noise;
building hybrid cloud services from quantum and classical computers [1, 3, 4, 5].
The article studies common approaches to the use of quantum computing to solve certain types of
combinatorial optimization problems [2, 7 - 10].
2. Physical principles for solving combinatorial optimization problems on
quantum computers
Quantum annealing based on cloud services is based on some metaheuristic algorithms for solving
combinatorial optimization problems using adiabatic quantum calculations [11, 12, 13]. Solving NP-
complex problems on quantum computers is based on the use of adiabatic quantum optimization and
mapping the problem to the states of the quantum system according to the functional of the Hamilto-
nian H(t) [11]. Technologically, quantum annealing is performed by changing the state of the qubit
system from the initial quantum state to the final quantum state by evolution within the model of
Hamiltonian dynamics following the problem of combinatorial optimization [13]. The prepared quan-
tum system then adiabatically changes to the required state for solving the problem in time T accord-
ing to the formula [11]:
t t
H t 1 H 0 H P ,
T T
when T is large enough, and H0 is the state of the system with minimal energy, HP is the state of the
system with the problem built into the qubit problem; then the system will remain in a state with min-
imum energy according to the adiabatic theorem of quantum mechanics. Problem-solving time for a
system with N spins [11]:
T O exp N ,
where α, β are positive coefficients, N → ∞. It is unlikely that any NP-complete problems can be
solved in polynomial time using adiabatic quantum optimization (AQO). However, if we construct a
quantum system where the coefficients α, β are small values, then there is a possibility that the AQO
algorithm will be faster than classical algorithms for some classes of problems.
3. Solving routing problems on quantum computers by the annealing meth-
od
Construction of algorithms for solving routing problems based on quantum computers is based on
the use of the Hamilton-Ising model for NP-complex optimization problems [10, 11], which in the
presence of many N spins si = ± 1 can be written as a special quadratic function the set N of spins si =
± 1. Variables are "turns up" spin (↑) and "turn down" spin (↓), i.e. states that correspond to the values
+1 and −1. Relationships between spins are called couplings and from the point of view of probability
theory can reflect correlations or anticorrelations. The objective function, expressed as a classical
Ising model, has the form:
N
H s1 ,K , s N J ij si s j hi si ,
ij i 1
282
where si, sj, i = 1,…, N, are linear coefficients corresponding to the displacement of qubits - hi, (spin
rotations), and square coefficients Ji,j correspond to the forces of connection between qubits. Compu-
tational quantum schemes for solving combinatorial optimization problems are based on the model of
quadratic unconstrained binary optimization (QUBO), which is isomorphic to the Hamilton-Ising
model:
N N
H x Qi ,i xi Qi , j xi x j ,
i 1 i j
where Qi,i are the linear coefficients and Qi,j are the quadratic coefficients, i = 1,…, N. The QUBO
model, which uses binary 02 and 12, is more convenient for writing code on traditional computers. The
hardware and software of quantum computer developers convert the code of the algorithm for solving
the optimization problem into the state of the quantum system.
The structure of the quantum processor is a physical implementation of an undirected graph with
qubits as vertices and couplers (connectors) as edges between them. From the standpoint of solving
the problems in formulation QUBO each qubit in the quantum processor represents the variable
QUBO, and the connectors between the qubits represent the costs or edge weight associated with pairs
of qubits mathematically described in the matrix Q.
3.1. Vehicle routing problem statement
Formulation of the problem.
Vehicle Routing Problem (VRP) tasks are determined by the set of customers to be serviced, their
location and requirements, as well as other primary information such as the distance between two cus-
tomers, the distance between each customer and the depot, the number of vehicles and their carrying
capacity. This class of routing tasks combines several types of logistics problems [14, 15, 16].
Let M be the number of available vehicles and N be the number of customer orders. A complete
weighted graph G = (V, A) is considered given. The set V = {v1, ..., vN+1} are vertices, the first N of
which correspond to the clients, and vN+1 represents the depot.
The depot often represents the supplier and the customers the retailers. The weight of each edge of
set A is related to the inherent cost of travel between incident vertices. Denote the cost of direct travel
from vertex i to the vertex j as Ci,j. We can also determine Ci , N 1 and Ci,N+1 for i ∈ {1,2,...,N} as the
cost of direct travel from the depot to the destinations of customers and from the destination of cus-
tomers to the depot, respectively.
3.2. An example of solving a TSP test problem on a D-wave QC
Consider the computational scheme of the Traveling Salesman Problem (TSP) algorithm on a D-
wave quantum computer. To do this, as input we use the weighted graph presented on Figure 1.
Initially, the problem is displayed as QUBO (Figure 2). To solve the problem with more than 40-
50 vertices, the company has developed procedures for decomposing problems; also, independent de-
velopers of algorithms have proposed several algorithms that take into account the load, delivery time,
and schedule [17]. The solution of the TSP problem (Figure 1) is a route on vertices: 0→1→2→3.
The data obtained is transmitted to a quantum computer company D-wave and displayed on the
qubits and couplings (Figure 3) with the next set of QC parameters [1, 2, 17]:
Parameters of the process of solving Timing
NUMBER OF READS 1000 QPU ACCESS TIME (μs) 249811.1
ANSWER MODE histogram QPU PROGRAMMING TIME (μs) 10871.1
Solution QPU SAMPLING TIME (μs) 238940
NUMBER OF SOURCE VARIABLES 16 TOTAL POST PROCESSING TIME (μs) 4133
NUMBER OF TARGET VARIABLES 79 POST PROCESSING OVERHEAD TIME (μs) 4133
MAX CHAIN LENGTH 6 SOLVER DETAILS NAME (CHIP ID) DW_2000Q_6
CHAIN STRENGTH 2 majority_vote
CHAIN BREAK RESOLUTION METHOD
283
Figure 1. A weighted non-directional graph for the TSP problem
a b
Figure 2. TSP problem in QUBO formulation (a - linear form; b - graph form)
According to the quantum annealing procedure, a set of solutions is obtained, from which the most
probable variant is chosen, which corresponds to the lowest energy level.
For the sample set histograms shown in Figure 4, the best solution has an energy level "-7". Other
samples, which match to higher energy levels, correspond to local minimums.
3.1. Examples of solving a TSP, VRP test problems on IBM QC simulator
The process of solving the traveling salesman problem and the vehicle routing problem was also
studied on the simulator of real IBM universal QC and also with the CPLEX library for solving
optimization problems on classical computers. Simulation quantum systems of classical systems may
require a large amount of random access memory. The solution of the TSP for four points on the IBM
QC simulator and IBM Qiskit quantum processing library required 64 gigabytes of random access
memory, which made it impossible to demonstrate it on a serial budget personal computer.
On Figure 5 it is shown the graph for the TSP test problem. The solution on an emulator of QC
gives two feasible solutions 0→2 →1; 0→1→2, shown in Figure 6, and gave an erroneous one:
2→0→1. Figure 7 is shown solving the vehicle routing problem on the simulator of IBM universal
QC (Figure 7 a) and also with the CPLEX library (Figure 7 b) for solving optimization problems on
classical computers.
A variational quantum eigenvalue solver [10] is essentially a heuristic algorithm based on the
quantum processing formulation of Ising Hamiltonian model. The local minimum in a quantum
processing formulation may be the same as the solution on a classical computer. Although in some
small-scale examples it is probable to find optimal solutions for the formulation of quantum
284
processing, which match the optimum solution on a classical computer. Finding optimal solutions for
integer linear programming is a more complicated task than finding local minimum for quantum
processing formulation at large, which sequentially is more difficult than finding feasible solutions for
integer linear programming. Variational quantum eigenmode solver is more dependable than integer
linear programming and promises feasible solutions for specific variational forms.
The depot is shown with a star, and the calculated routes for vehicles are shown with arrows. In
this particular case, one can find an optimal solution in quantum processing formulation, which
coincides with the optimal solution for integer linear programming.
Figure 3. Mapping the TSP problem to qubits and the coupling of a D-wave quantum computer
Figure 4. Histogram of the numbers of solutions of the TSP problem for different values of the ener-
gy of a quantum system
285
Figure 5. TSP problem unidirectional graph
Figure 6. TSP problem solutions in QUBO formulation on IBM QC simulator
3.2. An overview of algorithms for solving the problem of vehicle routing on
QC
3.2.1. Full QUBO Solver (FQS).
Proposed formulation [11, 12] for the problem of routing of loaded vehicles (CVRP) as a prob-
lem of quadratic unlimited binary optimization (QUBO). First, let's define the basic QUBO formula
that is used to solve VRP instances. Problem definition is based on a similar problem statement for
TSP in [12, 18]. We introduce the binary function:
n n n
A y1 ,..., yn 2 yi y j yi ,
i 1 j i 1 i 1
where yi ∈ {0, 1} for i ∈ {1 ,. . . , n}, n – number of vertices . It is easy to prove that the minimum
value of A(y1,...,yn) is “−1”, and this value can be achieved only if exactly one of y1,..., yn is equal to 1.
According to the definition of VRP, the problem of minimizing the total cost can be defined as
minimizing the function:
M N M N M N 1 N 1 N 1
C xm,n,1CN 1,n xm,n, N Cn, N 1 xm,i ,n xm, j ,n 1Ci , j . (1)
m 1 n 1 m 1 n 1 m 1 n 1 i 1 j 1
The first component in (1) of the sum C is the sum of all travel costs of vehicles from the depot -
the first part of the route of each vehicle. The second component is the cost of the last final part of the
routes (return to the depot) in a particular case, when one car serves all N orders (only in this case the
component can be greater than 0), the last part – this determines the total weight of the cost of all oth-
er sections of the ribs included in the route.
286
a b
Figure 7. VRP problem solution in QUBO formulation on IBM QC simulator (a) and VRP problem
solution in IBM CPLEX optimization library for classical computer (b)
To ensure that each delivery is serviced by one vehicle and only once and that each vehicle is
exactly in one place at a certain time, the next term (in which all components A are “-1” only in such
desirable cases) should be included in our QUBO formula:
N M N
Q A x1,k ,1 , x2,k ,1 ,K , x1,k ,2 , K , xM ,k , N A xm,k ,n , xm,2,n ,K , xm, N 1,n .
k 1 m 1 n 1
By definition, VRP, QUBO-representation of such an optimization problem can be
QUBOVRP = В1 ∙ C + В2 ∙ Q,
where the values of the constants B1 and B2 should be chosen so that the solution relationship found
by the quantum annealer would minimize Q (which should be "−N−NM") to meet the above re-
strictions (according to the results of tests [18]), constants acquired the following values: B1 = 1, B2 =
107).
A group of researchers from Poland proposed several algorithms and their modifications [18] for
solving VPR / CVRP problems based on the developed FQS computational scheme, as well as known
CVRP algorithms for classical and hybrid quantum-classical computers from D-Wave [18].
3.2.2. Average Partition Solver
Average Partition Solver (APS) - is a Full QUBO Solver variant that reduces the number of vari-
ables for each vehicle, assuming that each vehicle handles approximately the same number of orders.
3.2.3. DBSCAN Solver (DBSS)
DBSS allows you to use a quantum approach in combination with the classical algorithm. This
particular algorithm is inspired by recursive DBSCAN. DBSS uses recursive DBSCAN as a clustering
algorithm with a limited cluster size. The TSP problem is then solved for each cluster separately using
FQS. The DBSCAN algorithm can solve the CVRP if all the payloads of the vehicles are equal.
3.2.4. Algorithm for isolating solutions from TSP (Solution Partitioning Solv-
er - SPS)
Since adding vehicle capacity limitations to the model is not an easy task, it is possible [18] to
find a solution based on the results obtained by DBSS. The SPS algorithm divides the solution of the
TSP problem found by another algorithm (for example, DBSS) into successive intervals, which are
the solution to the CVRP problem. The effectiveness of algorithms from mediocre to the best of the
following: FQS, APS, DBSS, SPS [18].
287
3.2.5. CVRP routing algorithm with scheduling
Researchers from Japan have formulated a statement of the CVRP problem, which takes into ac-
count the schedule [19] and describes the changes in the status of the vehicle in time for each vehicle
during the trip [19]. There are restrictions on capacity (load), which are allowed to increase and de-
crease the load according to the cities (have not used this concept before) in which vehicles arrive.
Description of vehicle status allows you to set different travel rules depending on the condition of
each vehicle.
3.2.6. A hybrid method for solving the routing problem for vehicles with dif-
ferent capacities using a quantum annealer
A series of articles presents a way to decompose CVRP into smaller problems of the optimiza-
tion problem, which are solved sequentially [12]: clustering and routing. Vehicle clustering is formu-
lated in terms of the Knapsack problem. The Euclidean distance between the clients for the vehicle is
stated as minimal. Routing within the resulting clusters is seen as a problem by the traveling salesman
(TSP). The developed hybrid algorithm [12] uses a classic computer to solve the backpack problem
and a D-Wave quantum annealer to solve the TSP, but it is also possible to solve the whole problem
on the QC if the number of qubits is sufficient. The basis of the computational algorithm is the QUBO
scheme.
3.2.7. Routing algorithm based on a variational search of eigenvalues
Variational Quantum Eigensolver (VQE), implemented for IBM quantum computers [20], com-
bines classical and quantum optimization algorithms and quantum operators and logic gates, also
called quantum variation forms [10]. The limited number of qubits and connections in the existing
quantum computers and their imperfections make it difficult to determine the acceleration of the algo-
rithm because the resulting algorithm is essentially heuristic. Because IBM's quantum computer is
universal, not specialized, like D-wave, the developers built the Hamilton-Ising model using quantum
logic gates and operators and then translated it into the QUBO model. That is, they reduced the prob-
lem to the one already solved. The quality of the routing problem on an IBM quantum computer is
about the same as that of a D-wave quantum computer without a hybrid calculator.
4. Resume
Quantum approximate optimization algorithms belong to the class of quantum-classical hybrid
variational algorithms by the annealing method. Such calculators can run algorithms only with a lim-
ited depth of the quantum scheme, because the principle of operation of such annealers is based on ad-
iabatic evolution in time of the quantum system for a limited number of steps. The quantum ground
state is built on the Ising-Hamilton model used to solve combinatorial optimization problems.
Since the problem of the Ising problem is NP-complex, the integration of other combinatorial op-
timization problems into the corresponding system can also demonstrate a quantum advantage. An
approximate quantum optimization algorithm is used to solve the VRP problem with a finite number
of steps of adiabatic evolution and does not guarantee that the resulting solution corresponds to the
global optimal solution of the original problem.
This is because in an approximate quantum optimization algorithm, instead of gradually following
the evolution of the adiabatic state, it tries to guess it using a limited number of steps and heuristics.
On the other hand, inaccuracies in the operation of approximate quantum optimization algorithms at
higher values of the number of steps in the evolution of the adiabatic state form more local minima in
the energy landscape of the solution. This fact makes it difficult to find the minimum, so the required
number of steps should be selected according to the heuristic principle and empirical approaches. The
developed routing algorithms provide an approximate solution of TSP or VRP problems on D-wave
quantum computers in about 3 seconds. Algorithms may not find a solution or may provide a solution
with lost points to visit.
288
The direction of further development of solving the problem of routing on quantum computers is
to build new algorithms that are not based on the Ising model, but use other quantum principles or
models that can be implemented on universal quantum computers.
5. References
[1] Lardinois F. D-Wave plans to build a gate-model quantum computer
https://techcrunch.com/2021/10/05/d-wave-plans-to-build-a-gate-model-quantum-computer/
[2] Korolyov V.Yu., Khodzinskyi O.M. “Rozvʺyazuvannya zadach kombinatornoyi optymizatsiyi
na kvantovykh komp'yuterakh” [Solving combinatorial optimization problems on quantum
computers]. Cybernetics and Computer Technologies. 2020. 2. С. 5–13. (in Ukrainian)
https://doi.org/10.34229/2707-451X.20.2.1
[3] Moran C.C. Mastering Quantum Computing with IBM QX. Birmingham: Packt, 2019.
[4] Lucero E. Unveiling our new Quantum AI campus. URL:
https://blog.google/technology/ai/unveiling-our-new-quantum-ai-campus/
[5] List of quantum processors. URL: https://en.wikipedia.org/wiki/List_of_quantum_processors
[6] Moran C.C. Mastering Quantum Computing with IBM QX. Birmingham: Packt, 2019.
[7] Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information. Cambridge: Uni-
versity Press, 2012. https://doi.org/10.1017/CBO9780511976667
[8] Norlen H. Quantum Computing in Practice with Qiskit® and IBM Quantum Experience. Bir-
mingham: Packt, 2020.
[9] Kommadi B. Quantum Computing Solutions. Solving Real-World Problems Using Quantum
Computing and Algorithms. New York: Apress, 2020. https://doi.org/10.1007/978-1-4842-
6516-1
[10] Asfaw A. Learn Quantum Computation using Qiskit. URL: https://qiskit.org/textbook/ch-
applications/qaoa.html (accessed 06/21/2021).
[11] Lucas A (2014) Ising formulations of many NP problems. Front. Physics 2:5. doi:
10.3389/fphy.2014.00005
[12] Feld S., Roch C., Gabor T., Seidel C., Neukart F., Galter I., Mauerer W., Linnhoff-Popien C.
(2019) A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quan-
tum Annealer. Front. ICT 6:13. doi: 10.3389/fict.2019.00013
[13] Harikrishnakumar R., Nannapaneni S., Nguyen N.H., Steck J.E., Behrman E.C. A Quantum An-
nealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem.
http://arxiv.org/abs/2005.12478v2
[14] Toth P., Vigo D. (2014). Vehicle Routing: Problems, Methods, and Applications, Second Edi-
tion, MOS-SIAM Series on Optimization 18. SIAM, Philadelphia
[15] Golden, B.L., Raghavan, S., & Wasil, E. A. (Eds.). (2008). The vehicle routing problem: latest
advances and new challenges (Vol. 43). Springer Science & Business Media.
[16] Hulyanitskyi L.F. “Problema optimizatsii marshrutov transportnykh sredstv s vremennymi ok-
nami” [The problem of optimizing the routes of vehicles with temporary windows]. Computer
Mathematics. 2007. 1. P. 122–132. (in Ukrainian)
[17] D-Wave Hybrid Solver Service: An Overview. URL:
https://www.dwavesys.com/sites/default/files/14-1039A-A_D-
Wave_Hybrid_Solver_Service_An_Overview.pdf
[18] Borowski M. et al. (2020) New Hybrid Quantum Annealing Algorithms for Solving Vehicle
Routing Problem. In: Krzhizhanovskaya V. et al. (eds) Computational Science – ICCS 2020.
ICCS 2020. Lecture Notes in Computer Science, vol 12142. pp. 546-561. Springer, Cham.
https://doi.org/10.1007/978-3-030-50433-5_42
[19] Irie H., Wongpaisarnsin G., Terabe M., Miki A., Taguchi S. (2019) Quantum Annealing of Ve-
hicle Routing Problem with Time, State and Capacity. In: Feld S., Linnhoff-Popien C. (eds)
Quantum Technology and Optimization Problems. QTOP 2019. Lecture Notes in Computer
Science, vol 11413. pp. 145–156, 2019. Springer, Cham. https://doi.org/10.1007/978-3-030-
14082-3_13
[20] Vehicle Routing Optimization
https://qiskit.org/documentation/tutorials/optimization/7_examples_vehicle_routing.html
289