11institutetext: Maastricht University, Maastricht, The Netherlands
TNO, The Hague, The Netherlands
11email<EMAIL_ADDRESS>
# Quantum Computing in Logistics and Supply Chain Management - an Overview

Frank Phillipson

(March 2024)

###### Abstract

The work explores the integration of quantum computing into logistics and
supply chain management, emphasising its potential for use in complex
optimisation problems. The discussion introduces quantum computing principles,
focusing on quantum annealing and gate-based quantum computing, with the
Quantum Approximate Optimisation Algorithm and Quantum Annealing as key
algorithmic approaches.

The paper provides an overview of quantum approaches to routing, logistic
network design, fleet maintenance, cargo loading, prediction, and scheduling
problems. Notably, most solutions in the literature are hybrid, combining
quantum and classical computing. The conclusion highlights the early stage of
quantum computing, emphasising its potential impact on logistics and supply
chain optimisation. In the final overview, the literature is categorised,
identifying quantum annealing dominance and a need for more research in
prediction and machine learning is highlighted. The consensus is that quantum
computing has great potential but faces current hardware limitations,
necessitating further advancements for practical implementation.

###### Keywords:

Quantum Computing Logistcs Supply Chain Management Optimisation

##  1 Introduction

Quantitative optimisation is integral to logistics and supply chain
management, driving efficiency, cost reduction, and overall performance
improvement. Various challenges underscore the need for this field. These kind
of challenges and the corresponding optimisation problems are often divided
into multiple levels, like operational, tactical and strategic
brouer2018optimisation ; de2017framework , see Fig. 1. On an operational
level, there is efficient route planning, as seen in vehicle routing problems
(VRP), minimising transportation costs while meeting demand and adhering to
constraints. Also problems like stowage and cargo loading have to be solved on
an operational level. Next, in inventory management, a balance is sought
between over-stocking and under-stocking, employing models like Economic Order
Quantity (EOQ) for optimal order quantities. Production schedule optimisation
addresses job scheduling, employee and machine scheduling, and production
planning, minimising lead times and costs. Last, accurate demand forecasting
is needed to optimise inventory, production, and transportation planning. On a
tactical level, we have problems like fleet deployment, timetabling and hub
site design. On a strategic level, decisions on facility location, fleet size
and mix, and network design, impact logistics costs.

Next to these pure optimisation problems, there are two issues we also have to
address in quantitative optimisation in this field. First, supply chain
objectives often conflict, requiring multi-objective optimisation for informed
decisions. Supplier selection involves balancing factors like cost, quality,
lead times, and reliability. Risk management minimises disruptions from
natural disasters or political events, ensuring operational continuity.
Second, in logistics we have to cope with the dynamic behaviour of the system.
Dynamic optimisation adapts to real-time changes, crucial in a dynamic supply
chain environment. Green supply chain optimisation focuses on sustainability,
reducing environmental impact through carbon emission and energy usage
minimisation.

Figure 1: Three levels of problems.

These issues make decision-making processes even more complex and consider
various variables and constraints, ensuring a smooth flow of goods while
maximising operational efficiency and minimising costs. Advanced techniques,
including mathematical modelling and metaheuristics, are commonly used to
tackle these challenges, which are computationally hard in most cases.

Currently, there is a burgeoning computing paradigm known as quantum
computing, which holds the potential to transform the contemporary computing
landscape. Quantum computers, the devices central to this paradigm, leverage
principles from quantum mechanics to achieve computational speeds and
efficiencies that surpass the inherent capabilities of current classical
computers for specific problems. The notable advancements attributable to
quantum computing include a quadratic improvement in searching unstructured
databases Grover_1996  and an exponential enhancement in integer factorisation
Shor_1994 ; Shor_1997 . Beyond these examples, quantum computing is expected
to provide advantages across various domains, such as simulating chemical
processes Cao2019 , solving optimisation problems jaderberg2022solving ;
Symons_2023 , and advancing quantum machine learning phillipson2020quantum ;
schuld2021machine .

Quantum computing has the potential to also revolutionise the field of
computational logistics and supply chain management by offering advantages in
solving complex optimisation problems. Some of these problems include solving
combinatorial optimisation problems, which are prevalent in logistics as we
saw before: vehicle routing, facility location, and network design problems,
which involve finding the best routes, locations, and structures to minimise
costs and improve efficiency, and scheduling problems, such as production
scheduling, job sequencing, and workforce management.

Also the Quantum Technology and Application Consortium (QUTAC)
bayerstadler2021industry  acknowledges that optimisation and simulation
problems are prevalent in the domain of production and logistics across
industries, such as manufacturing, chemical and pharmaceutical production,
insurance, and technology.. They state that real-world problems often involve
numerous variables and constraints that classical algorithms struggle to
address effectively, and that quantum optimisation approaches, such as quantum
annealing and hybrid algorithms like the Quantum Approximate Optimisation
Algorithm, are promising for their potential to provide higher quality
solutions and faster solution times. Also Yarkoni et al. yarkoni2022quantum
recognise scheduling and logistics as an important application area of quantum
computing in their overview of industry applications.

By reducing computation time significantly, quantum computing can help model
and optimise the supply chain in real time, making it (more) resilient to
disruptions, by finding alternative routes and sources during unexpected
events, thus minimising the impact of disruptions. Quantum computers are also
expected to be able to efficiently process and analyse vast amounts of data in
the future, which is essential for demand forecasting, inventory management,
and making real-time decisions in the supply chain. Lastly, quantum algorithms
can help tackle multi-objective optimisation problems by simultaneously
considering multiple conflicting objectives. This is beneficial for balancing
cost reduction, service level improvement, and environmental sustainability.
This is a great benefit for the two issues mentioned before.

While quantum computing offers great promise for addressing logistics and
supply chain optimisation problems, it is important to note that the
technology is still in its early stages, and practical, large-scale
implementations are limited. However, quantum hardware is evolving rapidly,
and researchers are working on developing both the software stack needed and
quantum algorithms for specific problems. Also quantum computing based
approaches specifically tailored to logistics and supply chain management are
studied and developed. A combination of classical and quantum computing
techniques may be the most practical approach for solving logistics and supply
chain challenges based on the current state of quantum computing hardware.
This can be seen reflected in literature. A lot is happening in different
research groups around the world. To get grip on this, in this paper an
overview is given of over 80 published papers on this topic, both in detail
and in the form of a compact overview. Next, conclusions from this overview
are drawn and blind spots are recognised for further research. We continue the
paper in Section 2 with an introduction to quantum computing and optimisation.
Next, in Section 3, we will dive into the various areas on quantitative
optimisation within the logistic and supply chain world and give an overview
of the quantum approaches for the problems in those areas. As indicated we
will end with a concise summary and recommendations for further research.

##  2 Quantum computing and optimisation

We can currently distinguish two paradigms in quantum computing: digital or
gate-based computers/computing (GBC) and analog quantum computing, of which
quantum annealers (QA) are an important example. GBC is most similar in
operation to the current generation of computers. They are capable of
performing operations (gate operations, such as AND, OR) on specific qubits or
on multiple qubits at the same time. This allows for actual programming, which
is often visualised via circuit diagrams. The QA, on the other hand, are
single-purpose machines. Quantum annealing started with the work of Kadowaki
and Nishimori kadowaki1998quantum . QA can basically do one thing only: find a
minimum value of a specific function. This function is encoded in the qubits,
after which a quantum mechanical evolution will lead to a solution that
minimises the energy. In this section we will present GBC and QA in more
detail and explain how they can be used in quantitative optimisation. First,
we introduce some fundamental concepts in quantum computing.

###  2.1 Fundamental Concepts

Superposition, entanglement, interference and tunnelling are fundamental
concepts in quantum mechanics, that underpin the power of quantum computing.
Superposition refers to the ability of a quantum system to exist in multiple
states simultaneously. Quantum computing uses qubits, or, quantum bits. Unlike
classical bits, which can only represent either 0 or 1, a qubit can be in a
superposition of both states. Mathematically, a qubit can be represented as a
linear combination of the basis states $\ket{0}$ and $\ket{1}$, often denoted
as $\alpha\ket{0}+\beta\ket{1}$, where $\alpha$ and $\beta$ are complex
numbers that describe the probability amplitudes of each state. This notation
is further explained in Section 2.2. When a measurement is made, the qubit
collapses into one of the basis states with a probability determined by the
square of the amplitudes, so it should hold that $|\alpha|^{2}+|\beta|^{2}=1$.
Quantum parallelism is related to superposition. Quantum computational
advantage is achieved by leveraging superposition in order to perform parallel
computations on multiple qubits.

Entanglement describes a strong correlation that can exist between two or more
qubits. When qubits become entangled, the state of one qubit becomes
intrinsically linked to the state of the other qubits. This entanglement
persists even if the qubits are physically separated. Entangled qubits can
exhibit highly non-classical behaviour and can be used to perform quantum
operations that are not possible with classical systems. Superposition and
entanglement are fundamental resources in quantum computing, enabling the
execution of powerful quantum algorithms and the potential for exponential
computational speedup.

Quantum interference is the third fundamental phenomenon in quantum mechanics,
where the amplitudes of different quantum states combine in such a way, that
they can reinforce or cancel each other out. It occurs when two or more
quantum states, such as wave functions or probability distributions, overlap
and interact with each other. Quantum interference is best understood through
the concept of superposition. When superposed states interfere, the resulting
probability distribution is not simply the sum of the individual
probabilities. Instead, it depends on the relative phase of the states.

Lastly, quantum tunnelling is a phenomenon in quantum mechanics where a
particle can pass through a potential barrier even when its energy is lower
than the energy of the barrier. In classical physics, if a particle does not
have enough energy to overcome a barrier, it would be reflected back or
stopped by the barrier. However, in the quantum realm, particles such as
electrons and protons can exhibit wave-like behaviour and have a non-zero
probability of “tunnelling” through the barrier.

###  2.2 Gate based quantum computing

The first paradigm is digital or gate-based quantum computing. GBC rely more
directly on qubits and gate operations. As said before, unlike classical bits,
which can only represent 0 or 1, qubits can exist in a superposition of
states, simultaneously representing multiple values. Through the application
of quantum logic gates, which are analogous to classical logic gates, quantum
computations are executed. These gates manipulate the quantum states of
qubits, enabling operations such as superposition, entanglement, and
interference. By leveraging a sequence of carefully crafted gate operations,
quantum algorithms can be executed, allowing for the solution of problems that
are intractable for classical computers. The precise control and manipulation
of qubits, as well as the mitigation of errors due to decoherence, pose
significant challenges in the practical implementation of gate-based quantum
computing systems. The qubit states can be represented by matrices (vectors):

$\ket{\psi}=\ket{0}=\binom{1}{0}\textrm{ and
}\ket{\psi}=\ket{1}=\binom{0}{1}.$

This means that a one-qubit quantum gate can be depicted as a unitary operator
acting on a single qubit, which is represented as a two-dimensional system. A
quantum gate acting on $n$ qubits is represented by a $2^{n}\times 2^{n}$
matrix. The state vector $\ket{\psi}$ belongs to a Hilbert space
$\mathcal{H}$, called the state space with vectors of length 1, using complex
numbers. This state is given in Dirac notation: a quantum object state is
represented by $\ket{\psi}$, the ket of quantum state $\psi$. The bra of the
same state vector, represented by $\bra{\psi}$ is the conjugate transpose of
the ket. If the vector contains only real numbers, the conjugate transpose is
the same as the regular transpose, for a vector with complex entries, the
conjugate transpose replaces each complex entry with its complex
conjugate111if you have a complex number $z=a+bi$, where $a$ is the real part
and $b$ is the imaginary part, then the complex conjugate of $z$, denoted as
$\bar{z}$, is defined as $\bar{z}=a-bi.$ and then transposes the resulting
matrix.

To give an example we look at the following. Figure 2 shows a quantum circuit
for encoding the data: it encodes two data points in two qubits.

$\ket{0}$ & H 1 X 1
$\ket{0}$ R_y(θ_1) R_y(θ_2)

Figure 2: Amplitude encoding: two-qubit circuit for data encoding of two
normalised two-dimensional data points.

A quantum circuits must be read from left to right. Each line in represents a
qubit, in this case we have two qubits. Each rectangle is a gate operation,
operating on one or two qubits. First, a Hadamard gate is applied to the first
qubit to bring that qubit in a superposition state. Then a controlled rotation
is used to encode the two data points $x_{i}=(x_{i0},x_{i1})$ for $i=0,1$ in
the amplitudes of the second qubit. The angles of the rotations $\theta_{i}$
are chosen such that $\alpha_{i}=x_{i0}$ and $\beta_{i}=x_{i1}$. The initial
state is now rotated to the desired state what can be expressed by:

$\ket{0}\ket{0}\rightarrow\frac{1}{\sqrt{2}}\big{(}\ket{0}\ket{x_{1}}+\ket{1}\ket{x_{2}}\big{)}.$

Note that the first qubit acts as a counter, while the two features of the
data point are encoded in the second qubit. Another option is to encode a
single data point with four features, using just two qubits. Quantum
programming languages can be used to construct and apply these circuits to
quantum hardware. Examples of such languages are PyQuil koch2019introduction ,
QCL omer2005classical  and Q# tolba2013q . These quantum programming languages
only focus on that specific part of the quantum software stack van2019vision ;
piattini2020talavera , whilst tools for other layers are also in development.

###  2.3 The QUBO

Many approaches on quantum computer devices that are related to optimisation
use the QUBO, Quadratic Unconstrained Binary Optimisation, formulation as
standardised input. This QUBO, or the equivalent Ising formulation, represents
the function that can be minimised by the quantum algorithm. The Ising
formulation defines the energy of electron spins via a Hamiltonian and enables
it to minimise this energy. The QUBO formulation is its binary representation
and is often used for combinatorial optimisation:

$\text{QUBO:}\min\mathbf{x}^{T}Q\mathbf{x}$

where $\mathbf{x}$ is a vector with binary decision variables and $Q$ is a
square matrix with constant values. Many (constrained) combinatorial
optimisation problems can easily be described in a QUBO formulation
glover2019quantum . Take for example the problem

$\min\mathbf{c}^{T}\mathbf{x}\textrm{, under the constraints
}A\mathbf{x}=\mathbf{b},$

then we can place the conditions in the objective function using a penalty
$\lambda$:

$\min\mathbf{c}^{T}\mathbf{x}+\lambda(A\mathbf{x}-\mathbf{b})^{T}(A\mathbf{x}-\mathbf{b}).$

If we define $P=I\mathbf{c}$ being the matrix having the values of
$\mathbf{c}$ on the diagonal, then this equals:

$\operatorname{argmin}\mathbf{x}^{T}P\mathbf{x}+\lambda(A\mathbf{x}-\mathbf{b})^{T}(A\mathbf{x}-\mathbf{b})=\mathbf{x}^{T}P\mathbf{x}+\mathbf{x}^{T}R\mathbf{x}+d=\mathbf{x}^{T}Q\mathbf{x},$

where the matrix $R$ and the constant $\mathbf{d}$ are the result of the
multiplication and constant $\mathbf{d}$ can be neglected in the optimisation.
Matrix $Q$ now depends on the penalty $\lambda$. The QUBO can then be reduced
in a pre-processing step glover2018logical  to create a smaller problem.

###  2.4 Quantum Annealing

The QUBO is given as input to the QA, which is an important representative of
the second paradigm, analog quantum computing. The premise here is to create
an equal superposition over all possible states of a collection of qubits.
Then a problem-specific magnetic field, based on the QUBO formulation, is
turned on, causing the qubits to interact with each other. Now the qubits move
to the lowest energy state, from which the optimal solution of the original
problem can be derived. Quantum annealing has similarities with the well-known
Simulated Annealing (SA). However, where SA can only make thermal jumps, QA
also uses thermal fluctuations and quantum fluctuations (like tunnelling,
entanglement, etc). The most advanced QA is the version of D-Wave Systems
(from now called D-Wave). They claim that their devices are practical
implementations of adiabatic evolution farhi2000quantum . The evolution of a
quantum state on the quantum processor of D-Wave is described by a time-
dependent Hamiltonian ($H(t)$), consisting of the original Hamiltonian
($H_{0}$), whose ground state is easy to create, the equal superposition, and
the final Hamiltonian ($H_{1}$), whose ground state encodes the solution of
the current problem, via the QUBO. One specific linear annealing schedule is
expressed by:

$H(t)=(1-\frac{t}{T})H_{0}+\frac{t}{T}H_{1}.$

This system is initialised to the ground state of the original Hamiltonian,
i.e. $H(0)=H_{0}$. The adiabatic theorem states that if the system evolves
according to the Schrödinger equation, and the minimum spectral aperture of
$H(t)$ is not zero, $H(T)$, for $T$ large enough, will converge to the ground
state of $H_{1}$. Although we will not go into the technical details here, it
is good to know that it is usually not possible to estimate an adequate time T
for which the evolution to the desired state is assured. For some classes of
problems, the optimal annealing time has been determined experimentally
albash2018demonstration . There is therefore no guarantee of optimality.
Furthermore, it is not trivial to find a good value for the penalty $\lambda$
and the so-called chainstrength; the QA is very sensitive to these parameters.
Chainstrength is a parameter that results in a penalty if multiple qubits
representing one variable do not have the same value in the solution. In
addition, D-Wave’s state-of-the-art QA now has 5640 qubits with a connectivity
of up to 15. This can model a fully connected clique problem with $n=177$. For
problems with a lower dependency between the variables, larger problems can be
solved. Problems that cannot be placed on a chip of this size will have to be
broken into pieces, at the expense of the quality of the solution. D-Wave does
offer a standard function that takes care of this decomposition automatically
as well as offering hybrid computing pipelines. Note that in the remainder of
this paper we use the term Quantum Annealing (QA) also if we actually mean the
implemented Adiabatic Quantum Computing approach by D-Wave.

###  2.5 QAOA

There exists an algorithm that translates quantum annealing to the gate-based
quantum computer: QAOA, Quantum Approximate Optimisation Algorithm
farhi2014quantum , which is a type of variational quantum eigensolver (VQE)
algorithm. The VQE is a quantum algorithm that is used often for quantum
chemistry, quantum simulations and optimisation problems. It is a hybrid
algorithm that uses both classical computers and quantum computers to find the
ground state of a given physical system. In QAOA, the adiabatic evolution is
approximated by a discretised function that yields an approximation of the
ground state of the desired Hamiltonian. The goal of the QAOA algorithm is to
find the lowest possible upper bound for the ground state. Here too, we start
with an equal superposition over all solutions $\ket{s}$. The algorithm then
alternately applies the following two operations, operators, to this state:

$U(H_{0},\beta)=e^{-i\beta H_{0}}\textrm{ and }U(H_{1},\gamma)=e^{-i\gamma
H_{1}},$

where $\beta$ in $[0,2\pi]$ and $\gamma$ in $[0,4\pi]$. If we apply these
operators $p$ time, the QAOA produces the following quantum state:

$\ket{\gamma,\beta}=U(H_{0},\beta_{p})U(H_{1},\gamma_{p})…U(H_{0},\beta_{1})U(H_{1},\gamma_{1})\ket{s}.$

Using a QC, the expected value
$F_{p}=\bra{\gamma,\beta}H_{1}\ket{\gamma,\beta}$ can then be calculated,
which gives an upper limit for the ground state. If $p\rightarrow\infty$ and
given the right choice of angels $\beta_{p}$ and $\gamma_{p}$, this
approximation will converge to the optimal solution - the exact ground state
of the underlying problem. However, finding the right angles is not trivial
and if p must be large for a good approximation, the effectiveness of the
algorithm is still an uncertain factor. The QAOA has more freedom than QA in
this regard. Another choice for the so-called mixing operator
$U(H_{0},\beta)$, is the Quantum Alternating Operator Ansatz (Hadfield et al.
2019), which can limit the search space, by, for example, setting hard
constraints. The QAOA is an example of a variational or hybrid algorithm.
Classical parameters are optimised to create a quantum circuit that solves a
problem. This class of algorithms are seen to possess the first practical
application to gated quantum computers. After all, it only needs a limited
number of qubits and the depth of the circuit (the time factor) is also
limited if p is not chosen too large. In addition, variational algorithms are
fairly resistant to noise, the limited stability of the qubits.

Figure 3: Overview of the six problems areas together with the discussed
mathematical problem formulations.

##  3 Problem overview

In this section, we delve into the realm of quantum optimisation techniques,
focusing on their applications to six pivotal categories of logistics
problems: routing, network design, fleet optimisation, cargo loading,
prediction and scheduling, see Fig. 3. We will dive into all these categories
and discuss the quantum algorithms and approaches suggested for underlying
quantitative optimisation problems in literature.

###  3.1 Methodology

For this work we created an overview that is as complete as possible until
2023. We used Google Scholar and Scopus as source and used the index terms
‘quantum algorithm’ and the category names of the logistic problems. Note that
there exists also a lot of literature on ‘quantum inspired’ algorithms like
quantum genetic algorithms xihuai2007application , quantum evolutionary
algorithm xu2009using  and regular simulated annealing, not using the QUBO
formulation, such as chibeles2012simulated ; mousavi2013hybrid . The first
quantum annealing work we found is from 2013 and 2015, with the works from
chooinvestigating ; crispin2013quantum ; venturelli2015quantum . The main flow
of research starts around 2020, as shown in Fig. 4.

Figure 4: Distribution of the papers over the years, per category: fleet
optimisation, cargo loading, prediction and inventory control, scheduling,
routing and network design network

###  3.2 Routing problems

These problems involve determining the most efficient routes for transporting
goods from suppliers to manufacturers and then to customers. It includes the
Vehicle Routing Problem (VRP) and the Travelling Salesman Problem (TSP), where
you aim to minimise transportation costs while meeting customer demand and
satisfying constraints.

####  3.2.1 VRP and TSP quantum solutions

Several studies explore the application of quantum computing to address
various aspects of Vehicle Routing Problems (VRP). The following paragraph
provides an overview of these works, highlighting their methodologies,
findings, and future implications.

One of the earlier works is by Crispin et al. crispin2013quantum . They
propose an approach to solve the Capacitated Vehicle Routing Problem (CVRP)
using a quantum annealing algorithm. CVRP is a variant of the VRP where
vehicles have limited capacity. The paper discusses the design of a spin
encoding scheme for CVRP and an empirical approach for tuning parameters in
the quantum annealing algorithm. QA is introduced as a metaheuristic that
utilises quantum tunnelling in the annealing process. Experiments are
conducted on CVRP benchmark instances, and the results are compared with a
simulated annealing algorithm. The quantum annealing algorithm is found to
match or outperform simulated annealing in terms of success rate for various
instances. The paper analyses the quantum annealing algorithm’s performance
and discusses the impact of parameters such as population size, temperature,
and acceptance ratio.

Srinivasan et al. srinivasan2018efficient , introduce a quantum algorithm to
solve the TSP. It utilises the quantum phase estimation technique
jiang2021survey , encoding distances between cities as phases. Unitary
operators are constructed based on these phases, and the phase estimation
algorithm is applied to estimate eigenvalues representing total distances for
all possible routes. Quantum search algorithms are then employed to find the
minimum distance and corresponding route, providing a quadratic speedup over
classical brute force methods. The algorithm is illustrated with an example of
TSP involving four cities, and simulations are conducted using IBM’s quantum
simulator.

The work by Feld et al. feld2019hybrid  also investigates the CVRP using
D-Wave’s quantum annealer. They propose a quantum-classical hybrid solution,
incorporating a 2-Phase-Heuristic that divides CVRP into clustering and
routing phases. Results indicate that the hybrid method can compete with
classical construction and 2-phase heuristics in terms of solution quality.
However, challenges arise, particularly in finding the ‘best known solution’
for certain datasets, emphasising the need for larger quantum hardware. The
study anticipates future improvements in D-Wave’s technology, expecting
increased qubit connectivity and quantity.

Borowski et al. borowski2020new  also delve into (C)VRP, introducing four
quantum annealing-based algorithms. Their Full QUBO Solver (FQS), Average
Partition Solver (AVS), DBSCAN Solver (DBSS), and Solution Partitioning Solver
(SPS) showcase promising results. The study employs D-Wave’s Leap framework,
comparing quantum algorithms with classical metaheuristics. The experiments
use established benchmark datasets and custom scenarios with realistic road
networks. The authors outline future research directions, including extending
quantum formulations to address more realistic variants of VRP.

Weinberg et al. weinberg2023supply  focus on practical quantum algorithm use,
considering the limitations of Noisy Intermediate-Scale Quantum (NISQ)
hardware. They adopt a hybrid workflow for solving the CVRP, breaking down
problems into smaller instances suitable for quantum annealing. Simulated
annealing and the D-Wave Hybrid solver are used as quantum substitutes. While
not claiming clear advantages over classical methods, they emphasise the
sensible application of quantum algorithms to specific bottlenecks,
anticipating future advancements.

This study by Sinno et al. sinno2023performance  focus on the performance of
commercial QA solvers for the CVRP. The research challenges assumptions made
in theoretical studies and simulations on classic hardware, emphasising the
need for empirical measurements on real quantum platforms to assess commercial
capabilities accurately. The study evaluates the quality of solutions provided
by the D-Wave CQM solver for CVRP, considering problem size and complexity.
The study suggests that, more than problem size, model complexity
significantly affects solution quality, highlighting the importance of
minimising constraint density in practical applications.

Sales et al. sales2023adiabatic  address the VRP in last-mile logistics,
proposing a hybrid solution combining quantum annealing and classical
techniques. Their analysis, using Amazon Braket and D-Wave’s QA, demonstrates
the superiority of the hybrid algorithm over full Quantum Annealing,
suggesting potential advantages in scenarios with lower data “clusterability.”
Despite current challenges, the study identifies a cost-effective relationship
between running quantum algorithms and result quality, indicating quantum
computing’s theoretical advantage in solving constrained clustering problems.

The thesis by Palmieri palmieriquantum  explores the application of quantum
optimisation techniques to address the (C)VRP. Here, a heuristic two-phase
approach is explored. Nodes are first clustered into disjoint groups, and
routing is performed individually within each cluster. Various classical
methodologies for the clustering phase are investigated. An alternative
approach models the clustering phase as a Modularity Maximization problem,
which is tackled using quantum algorithms. The routing phase is modelled as a
Travelling Salesman Problem (TSP), and subtour elimination constraints are
adaptively added using the Dantzig-Fulkerson-Johnson (DFJ) strategy. This
adaptive approach reduces the number of qubits, making the models suitable for
both gate-based and annealing-based quantum devices. Various quantum
algorithms, such as QA, quantum GAVA (Graver Augmented Multi-seed Algorithm),
QAOA and VQE are investigated for quantum optimisation. Gurobi is used as a
classical benchmarking method. QA and quantum GAMA outperfom the VQE
approaches here.

Until here, all works use Quantum Annealing as their solver for the VRP. Rana
et al. rana2022quantum  explore employee transport route and agri-tech
logistics optimisation using both a quantum gate-based variational algorithm
and QA. Here again, quantum hardware limitations lead to problem
simplifications, using problem-specific decomposition techniques, such as
distance-based clustering. The study utilises real-world data and anticipates
extending quantum methods to more complex scenarios, acknowledging ongoing
improvements in the D-Wave’s system for addressing larger, intricate logistics
optimisation problems.

Azad et al. azad2022solving  explore the application of the QAOA for the VRP
within Intelligent Transportation Systems (ITS). The paper provides an Ising
formulation for the VRP and its variants, adapting them for quantum
processing. Despite the limitations of NISQ devices, having 15 qubits, QAOA
holds promise for solving combinatorial optimisation problems like VRP.
However, they conclude that there is a need for a multi-faceted approach to
enhance its performance. Working on aspects such as initialisation techniques,
optimising parameter values, exploring different mixer Hamiltonians, and
addressing noise-related challenges are essential for realising the full
potential of QAOA in practical applications.

The proposed Indirect QAOA (IQAOA) by Bourreau et al. bourreau2023indirect ,
introduces a novel approach, targeting the Hamiltonian of a set of string
vectors. It utilises a Quantum Alternating Operator Ansatz with a
parameterised family of unitary operators, allowing for efficient modelling of
the Hamiltonian. This algorithm addresses the limitations of standard QAOA by
incorporating a classical meta-optimisation loop and estimating the average
cost of each string vector. The IQAOA approach includes the creation of a
quantum circuit with a limited number of gates suitable for current noisy
quantum machines. Numerical experiments demonstrate its efficacy in solving
the TSP, notably solving 8-customer instances, which are among the largest
TSPs solved using a QAOA-based approach.

The study by Mohanty at al. mohanty2023analysis  presents a VRP solver for
three and four cities using VQE on a fixed ansatz. The analysis extends to
assess the solution’s robustness in noisy quantum channels, considering
various noise models. The work contributes to understanding the impact of
noise on quantum algorithms for solving real-world optimisation problems. The
results highlight the importance of noise analysis for effective use of
quantum devices, emphasising the role of optimisers and the need for further
experimentation on physical quantum devices with larger VRP instances.

Bentley et al. bentley2022quantum  also introduce a QAOA based framework for
integrating quantum computing with the transport sector. They focus on a CVRP
and demonstrate a significant circuit performance enhancement (20 times error
reduction) using a real quantum device, emphasising problem decomposition,
mapping, and compilation for quantum advantage.

Next, Xie et al. xie2023feasibility  also use a QAOA approach for the CVRP.
This work explores the application of a variant of QAOA called Grover-Mixer
Quantum Alternating Operator Ansatz to solve CVRP. The paper introduces a
novel binary encoding for CVRP, focusing on minimising the shortest path while
bypassing vehicle capacity constraints. The search space is further
constrained using the Grover-Mixer. Experimental results indicate that the
proposed method outperforms conventional QAOA in terms of feasibility ratios,
optimality ratios, and optimality gaps. Despite promising results, the paper
acknowledges drawbacks, such as the requirement for multi-controlled Toffoli
gates, which may pose challenges for implementation on near-term quantum
devices with noise.

Also Palackal et al. palackal2023quantum  look at the CVRP and its relation to
the TSP. To facilitate experiments, the CVRP is reduced to a clustering phase
and a set of TSPs. The authors extensively test QAOA and VQE on TSP instances,
investigating the influence of hyperparameters like classical optimizer choice
and constraint penalisation strength. Results suggest that QAOA often falls
short in reaching the energy threshold for feasible TSP solutions, even with
extensions like recursive and constraint-preserving mixer QAOA. On the
contrary, VQE performs better, reaching the energy threshold and showing
improved performance. The study evaluates the challenges of quantum-assisted
solutions for real-world optimisation problems and proposes perspectives for
overcoming these obstacles. It also introduces a performance metric tailored
to the problem, focusing on solution quality from an application perspective.

Last in this category, the paper by Alsaiyari et al. alsaiyari2023variational
compare two quantum algorithms, general VQE and QAOA, for solving the VRP. The
study assesses the maximum VRP instance size that the current state-of-the-art
NISQ devices can handle, indicating that large VRP instances exceed current
quantum capabilities. While recognising the potential of quantum technology,
the study emphasises the need for advancements in both hardware and software
for broader adoption.

The next paradigm for solving routing problems optimisation is a mixture of
quantum computing and machine learning. Sanches et al. sanches2022short
explore the integration of quantum computing with reinforcement learning,
specifically addressing the VRP. Their model introduces quantum circuits in
place of classical attention head layers, showcasing competitive performance.
While acknowledging it as a proof of concept, the study emphasises the
potential symbiosis between quantum computing and machine learning, raising
questions about achieving quantum advantage for combinatorial optimisation
through (quantum) reinforcement learning agents.

Correll et al. correll2023quantum  take a different approach, employing
quantum neural networks with reinforcement learning for truck routing
logistics. The study uses real-world data, the same as Weinberg et al.
weinberg2023supply  we saw earlier, from the automotive sector and achieves
results comparable to human decision-making. While the quantum versions of
these neural networks offer theoretical speedups, the article acknowledges the
need to determine how much of this advantage can be practically realised.
Thus, it explores practical realisation methods by exploring methods for
tuning quantum circuits and workflow performance.

Slightly different and more general versions of the VRP problem are found in
the following papers. Ajagekar et al. ajagekar2020quantum ;
ajagekar2020quantum2  propose a Hybrid QC-IQFP Parametric Method for solving
the Inexact Quadratic Fractional Programming (IQFP) problem associated with
the VRP. The hybrid method combines an inexact parametric algorithm and
quantum computing techniques, demonstrating efficiency compared to classical
Mixed Integer Nonlinear Programming (MINLP) solvers for medium to large-sized
VRP instances. The authors highlight the heuristic nature of the method, its
potential for improvement with advancements in quantum computing, and its
competitive use in solving large-scale IQFP problems.

Masuda et al. masuda85optimisation  evaluate a quantum-classical hybrid
approach for the Time-Dependent Vehicle Routing Problem with Time Windows
(TDVRPTW). They employ a QUBO formulation using Fixstars Amplify Annealing
Engine (a classical, not quantum, Ising machine). The hybrid approach shows
potential efficiency for small-scale problems, emphasising the need for
further development to handle larger and more complex instances.

Also Leonidas et al. leonidasqubit  address the Vehicle Routing Problem with
Time Windows (VRPTW). They explore the application of a previously introduced
tan2021qubit  qubit encoding scheme to reduce the number of binary variables.
The study utilizes a quantum variational approach on a testbed of VRPTW
instances, ranging from 11 to 3964 routes, formulated as QUBO problems based
on realistic shipping scenarios. The authors compare their results with
standard binary-to-qubit mappings, employing simulators and various quantum
hardware platforms, including IBMQ, AWS (Rigetti), and IonQ. The benchmarking
is done against the classical solver, Gurobi. Despite the reduction in qubits
required, their approach demonstrates the capability to find approximate
solutions to the VRPTW comparable to those obtained from quantum algorithms
using the full encoding.

Harwood at al. harwood2021formulating  introduce various mathematical
formulations for VRPTW, suitable QAOA, VQE, and alternating direction method
of multipliers (ADMM). The formulations are compared from a quantum computing
perspective, considering metrics for evaluating the difficulty in solving the
underlying QUBO problems. Simulated quantum devices are employed to
demonstrate the relative benefits of different algorithms and their robustness
in practical scenarios.

Irie et al. irie2019quantum  introduce the idea of a time-table, capacity-
qubits, and the concept of state into the QUBO formulation. Time-tables are
incorporated to represent the temporal aspect of VRP, and capacity-qubits are
introduced to manage the capacity of vehicles dynamically. The concept of
state allows for the description of different traveling rules based on the
state of the vehicles. The paper includes a graphical view of a VRP instance
solution obtained using the D-Wave 2000Q. The results demonstrate the
effectiveness of the proposed formulation for small-size QUBO systems.

The work by Spyridis et al. spyridis2023variational , focuses on the Multiple
Travelling Salesman Problem (m-TSP). The study explores the use of the QAOA to
efficiently handle the m-TSP, formulating a QUBO problem. The authors
highlight potential applications in IoT systems, emphasising the need for
innovative error correction techniques to address limitations of NISQ devices.
An other variant of TSP is the selective travelling salesman problem (sTSP),
which is also known as the orienteering problem (OP), where each destination
is associated with a prize. Given a budget that must not be exceeded, the
salesperson is not necessarily required to visit all the cities, and his
mission is to collect as many prizes as possible. In Le et al. le2023quantum ,
the authors provide a QUBO formulation for this problem and perform
experimental results include an analysis of parameters such as annealing time,
chain strength, and solution quality for different instances of sTSP with
varying numbers of cities.

Salehi et al. salehi2022unconstrained  and Papalitsas et al.
papalitsas2019qubo  both look at the Travelling Salesman Problem with Time
Windows (TSPTW). The TSPTW involves finding a tour with the minimum cost,
where each city must be visited within a specified time window. Papalitsas et
al. give a first QUBO formulation of this problem. Salehi et al. introduce
three different formulations. The first formulation considers both earliest
start times and due times for each city. The second formulation presents a
higher-order binary model that is more space-efficient. The third formulation
is based on an alternative QUBO formulation derived from integer linear
programming. These formulations allow for multiple assignments of binary
variables to encode the optimal route without penalty, and they can be adapted
for other variants of the TSP. The study by Salehi et al. investigates the
efficiency of edge-based and integer linear programming (ILP) formulations
through experiments on the D-Wave Advantage quantum annealer. The results
indicate that the ILP model outperforms the edge-based model, particularly for
instances with four cities, showcasing a higher probability of obtaining
samples encoding the optimal route. The paper suggests a natural progression
for future work, involving a more nuanced exploration of penalty values for
time window constraints and the investigation of alternative techniques for
quadratisation in the node-based formulation.

Marsoit et al. marsoit2021quantum  address the VRP with uncertain data,
proposing a quantum computing approach. In real-world scenarios there are
uncertainties, which impact the effectiveness of VRP solutions, think of
varying travel times due to traffic congestion, uncertain customer demands,
service disruptions, or weather conditions. Failing to account for these
uncertainties may lead to inefficient route planning, missed time windows,
increased operational costs, and customer dissatisfaction. The study
formulates the problem, compares it with classical optimisation challenges,
and claims to demonstrate the effectiveness of the quantum approach through a
numerical example. However, it is not clear which quantum approach they use.
The research acknowledges current limitations of quantum hardware and calls
for further advancements.

Dixit et al. dixit2023quantum2  also discuss VRP with uncertainty, addressing
the Stochastic Time Dependent Shortest Path (STDSP) problem. In STDSP,
uncertainties arise from factors like demand and supply fluctuations, making
the representation of link travel time as a random variable necessary. The
study introduces a Quadratic Constrained Binary Optimisation Problem for the
STDSP. The research explores the efficiency of QA in comparison to classical
solvers, specifically CPLEX. The results indicate that quantum computing,
despite its current limitations in terms of qubit numbers and noise
susceptibility, exhibits linear computational efficiency.

Fitzek et al. fitzek2021applying  explore the use of QAOA for the
Heterogeneous Vehicle Routing Problem (HVRP). The HVRP involves determining
optimal routes for a fleet of vehicles with varying capacities to deliver
goods to customers. They formulate the HVRP as an Ising Hamiltonian,
showcasing scalability with increasing problem size. The study employs QAOA,
which requires defining a cost function and proposing an ansatz for
optimization. The study emphasises the trade-off between classical optimiser
performance and runtime, providing insights into the potential of quantum
computing for solving large instances of HVRP with advanced hardware.

Lo et al. lo2021genetic  introduce a quantum random number generator (QRNG) in
solving pollution-routing problems (PRPs) for sustainable logistics. The
hybrid model incorporates a modified k-means algorithm and a genetic
algorithm, showcasing the applicability of quantum random number generation in
optimising routes for emission reduction. The study suggests future research
directions involving metaheuristic algorithms and advancements in quantum
computing technology.

The work by Harikrishnakumar harikrishnakumar2020quantum  introduces a QA
approach to address the Multi-Depot Capacitated Vehicle Routing Problem
(MDCVRP). The MDCVRP involves assigning routes to vehicles from multiple
depots, each with varying capacities, to serve spatially distributed customer
locations while satisfying capacity constraints. The authors formulate the
MDCVRP and its dynamic version, the D-MDCVRP, as QUBO problems. The authors
discuss the complexity of the formulated problems, considering the total
number of decision variables. They also present a step-by-step solution
framework for solving QUBO formulations on quantum annealing hardware. The
authors outline future work, which includes solving the QUBO formulations on
D-Wave (here the 2000Q), comparing results against classical heuristic
algorithms like Tabu Search, and investigating the scalability of the quantum
annealing approach concerning the number of vehicles and depots.

The works of Warren warren2020solving  and Osaba et al.osaba2022systematic
gives an overview of VRP and TSP implementations. Warren conducts an analysis
of four software programs designed to solve the symmetric TSP, among which
D-Wave’s solutions and the work by Feld feld2019hybrid  we saw before. Osaba
et al give three main observations in the context of quantum optimisation and
routing problems. Regarding the current state of routing problems they
indicate that traditional routing problems like the TSP and VRP have been
extensively studied, but their formulations often fall short of addressing
advanced or realistic scenarios. Researchers face challenges in tailoring
problems to hardware capacities, leading to limitations in addressing complex
formulations. The second observation is the current state of the hardware.
current commercial quantum devices have inherent limitations such as noise and
decoherence. Researchers have worked on error correction and mitigation
strategies, but the focus on this aspect is relatively low. The last
observation is on the parameterisation sensitivity in quantum devices. Quantum
devices are highly sensitive to parameterisation in various aspects, including
problem formulation, algorithm tuning, and hardware specifications. Despite
this sensitivity, a majority of practical papers focus on solving specific
problems without deep exploration of parameter fine-tuning. Proper
parameterisation, especially the choice of (QUBO) penalty values in problem
formulation, is highlighted as a significant challenge.

Last, the work by Poggel et al. poggel2023recommending  introduces a framework
designed to automate and optimise the decision-making process in quantum-
assisted optimisation for real-world problems. Addressing the challenges of
formulating, encoding, and selecting algorithms and hardware options, the
proposed abstraction layer aims to make quantum-computing-assisted solution
techniques accessible to end-users without requiring in-depth knowledge of
quantum technologies. The framework incorporates state-of-the-art hybrid
algorithms, encoding, and decomposition techniques in a modular manner,
allowing evaluation using problem-specific performance metrics. Tools for
graphical analysis of variational quantum algorithms are developed, and
classical, fault-tolerant quantum, and quantum-inspired methods can be
included for a fair comparison. The approach is demonstrated and validated on
the CVRP.

####  3.2.2 Other Routing problems

In addition to addressing the classic Vehicle Routing Problem (VRP) and
Travelling Salesman Problem (TSP), quantum computing has been applied to
various other routing problems, showcasing its potential in optimising complex
logistical scenarios. The first example is the shipment rerouting problem by
Yarkoni et al. yarkoni2021solving , addressing the challenge of partially
filled trucks transporting shipments between a network of hubs. The goal is to
minimise the total distance travelled by these trucks, thus reducing fuel
consumption and enhancing cost efficiency. The problem instances and
optimisation techniques are based on real-world data from an existing shipment
network in Europe. The authors create a QUBO formulation and then employ both
classical and hybrid quantum-classical algorithms to solve these QUBOs. The
quantum platforms, particularly D-Wave, are found to be promising for
addressing this logistics problem due to their qubit support, compared to
gate-based and quantum-inspired optimisers. The article mentions that due to
qubit limitations in current quantum hardware, the experiments are conducted
with minimal parameters. It anticipates that as quantum hardware improves,
more complex real-world problems can be solved using quantum computing.

Azzaoui et al. azzaoui2021quantum  extended the scope to smart logistics
systems, proposing Quantum Approximate Optimization Algorithm (QAOA) for route
optimisation. They emphasise the importance of considering, next to cost and
time, also carbon footprint in logistics operations. They propose the
deployment of QAOA to calculate and optimise travel paths, selecting the best
route to reduce costs, time and carbon footprint, in a multi objective
approach, in smart logistics systems. Next to this approach, they suggest
implementing a private blockchain network in smart logistics systems to ensure
secure and private communication between different tiers of the smart
logistics system, creating a trustworthy cluster. They then conduct
simulations, using IBM Quantum Lab and Qiskit, along with blockchain-based
secure communication simulations using IBM Hyperledger. The results show
promising outcomes, including a 91% success rate in route optimisation, a 10%
cost reduction, a 6% reduction in carbon footprint, and improved system
scalability. The paper concludes by highlighting the potential benefits of the
proposed framework, aiming to improve the scalability, reduce the carbon
footprint, and cut down transportation and logistics costs in smart logistics
systems.

The article by Atchade et al. atchade2021qrobot  introduces quantum computing
to the field of robotics, specifically focusing on optimising distance
travelled by the robots in warehouses and distribution centres where order
picking and batching is performed. The authors develop a real-time quantum
optimisation algorithm for this purpose, implemented on a Raspberry Pi 4 as a
proof of concept. The proposed system aims to minimise distance travelled and
optimise order batching. The system allows for hybrid computing, combining
quantum and classical processing. The environment developed enables the
execution of quantum algorithms on IBMQ, Amazon Braket (D-Wave), and
Pennylane, either locally or remotely. The study indicates that Amazon Braket
has better time performance than Qiskit or Pennylane. They discuss potential
improvements and considerations for applying the system to scenarios with
multiple robots and batches.

In the aviation sector, Makhanov et al. makhanov2023quantum  dive into the
complexities of optimising flight paths, emphasising the use of quantum
computing to overcome computational challenges associated with this crucial
aerospace engineering operation. The research introduces a customisable
modular framework designed to accommodate specific simulation requirements. It
also examines the application of quantum-enhanced algorithms using Grover’s
algorithm, on various quantum architectures and simulations using CPUs and
GPUs. The study presents results from running quantum algorithms on IBM
hardware, highlighting the potential advantages and challenges associated with
quantum computing in the aerospace industry and acknowledging the need for
further innovation to practically achieve the theoretical speedup promised by
quantum algorithms.

The paper by Neukart et al. neukart2017traffic  focuses on a real-world
application, namely traffic flow optimisation in dense road networks. The
authors describe the process of mapping a traffic flow optimisation problem
onto a QUBO formulation, to demonstrate the feasibility of using quantum
computing for real-time, time-critical optimisation tasks, such as continuous
redistribution of position data for cars in busy road networks. Due to the
limited size and connectivity of current D-Wave’s QPUs, a hybrid quantum and
classical approach is employed to address the traffic flow problem. The
quality of solutions is assessed by counting the number of congested roads
after optimisation. The study compares the outcomes against random assignments
of routes. The results indicate that the hybrid quantum approach redistributes
traffic in a way that reduces the number of congested roads compared to both
random assignments and the original route assignment.

Last example in the routing section, is the work by Phillipson et al.
phillipson2021multimodal . Also this study presents a real-world application
in multimodal container planning and demonstrates how to map this problem to a
QUBO formulation for practical implementation on the quantum annealer produced
by D-Wave. It describes the implementation of the formulation on both SA and
D-Wave’s QPU. Due to current limitations in the size of quantum computers, the
authors initially formulate the problem with a limited number of decision
variables and later propose expansions for larger-scale applications. The
conclusion emphasises the need for re-formulating real-world problems to match
the QUBO formulation and highlights the potential of quantum computing for
solving such problems as the technology matures. The implementation issues on
D-Wave’s QA, such as finding the right embedding, defining chain strength, and
penalty functions, are addressed through a parameter grid search. The paper
recommends further research on finding more general methods for these
parameters, extending the set with alternative paths, and introducing a
quantum variant of column generation for optimising paths.

###  3.3 Logistic Network Design

At the heart of logistical optimisation lies the strategic design of logistic
networks, a complex process that involves careful planning, analysis, and
decision-making. Logistic Network Design (LND) explores how organisations can
craft and refine their supply chain infrastructure to enhance efficiency,
reduce costs, and meet the ever-evolving demands of the market. From the
selection of distribution centres to the configuration of transportation
routes, this exploration aims to unravel the strategic considerations that
underpin a resilient and responsive logistical framework. One important
classical problem within this area is the Facility Location Problem. For this,
Mahasinghe mahasinghe2021qubo  gives a basic QUBO formulation.

The first work on LND by Ding et al. ding2021implementation ; ding2019logistic
discusses the application of quantum annealing to address logistic network
design problems (NDPs), which are described as abstract optimisation problems
aimed at finding the optimal configuration of supply chain infrastructures and
facilities based on customer demand, while minimising costs. They translate
the cost function with constraints into an Ising problem and benchmark their
results by measuring the accuracy of the solutions against optimal published
solutions, with an average error of less than 1%. Additionally, they compare
the performance of their quantum approach with classical algorithms and
observe a significant reduction in the number of iterations required. The
article emphasises that, even though current quantum annealers are not yet
achieving quantum supremacy, they can effectively address relevant supply-
chain problems. Following the authors, this demonstrates the potential for
state-of-the-art quantum annealers to encode and solve complex logistics
problems, despite limitations in quantum hardware. Furthermore, the authors
introduce an alternative approach called the combined quantum annealing
algorithm, which utilises two layers with feedback-control interaction between
them. This approach is tested on 12 NDP instances using both quantum annealer
simulators and the D-Wave QA, yielding positive results in terms of accuracy
and performance compared to classical algorithms.

The work by Dixit et al. dixit2023quantum  discusses the Transport Network
Design Problem (TNDP), involving optimising network capacities, scheduling
maintenance, and identifying new links under resource constraints.
Traditionally, meta-heuristic methods like Tabu Search are employed. The paper
formulates TNDP as a bi-level problem, with the upper level represented as a
QUBO problem, solved using quantum annealing on D-Wave’s QA. The results are
compared with Tabu Search, demonstrating significant computational benefits
using quantum annealing.

Next, Malviya et al. malviya2023logistics  explore the potential of quantum
annealing for a parcel distribution centre network optimisation using data
instances of different sizes. Using a small data instance that fits the
current technology, they use D-Wave’s built-in hybrid quantum-classical
Kerberos sampler via AWS Braket for solving the problem. An iterative hybrid
approach for improving the quality of solutions obtained from the Kerberos
sampler is used and then the solutions are compared to the random sampler, a
greedy heuristic, an exact solver and SA. Improvement in objective value over
random has been shown for different approaches over different data instance
sizes. Kerberos sampler performs better than greedy heuristic and at par with
exact solver for some data instances.

Gabbassov et al. gabbassov2022transit  address the challenge of balancing
service efficiency and accessibility in urban transit facility planning. The
focus is on transit facility consolidation as a cost-effective strategy to
enhance service quality. For this, they propose an optimisation framework that
integrates Geographical Information Systems (GIS), decision-making analysis,
and quantum technologies. The framework includes a mathematical model
capturing non-linear interactions between facilities, demand nodes, inter-
facility competition, ridership demand, and spatial coverage, solving the
Spatial Interaction Coverage (SIC) problem. The QUBO based model can, as they
suggest, be implemented on various quantum optimisation metaheuristics,
including QA, quantum-inspired Digital Annealing, Coherent Ising Machines, and
universal GBC. The framework is applied to the public transit facility
redundancy problem in the British Columbia Vancouver metropolitan area and
demonstrates a 40% reduction in the number of facilities while maintaining the
same service accessibility, thereby improving efficiency, using a D-Wave
Hybrid quantum-classical solver. Additionally, numerical experiments on a
synthetically generated dataset demonstrate that the Hybrid solver yields
statistically superior demand coverage compared to a SIC problem solved with
the APOPT222Advanced Process OPTimizer solver.

The paper by Klar et al. klar2022quantum  addresses the challenges of factory
layouts, emphasising their impact on operational costs. The problem involves
assigning functional units to positions, optimising transportation distances.
Manual layout planning is time-consuming due to the complexity of considering
multiple parameters simultaneously. The study introduces a QA-based approach
for factory layout planning, involving the formulation of the problem as a
QUBO problem. The results show that QA can solve layout planning problems of
different sizes within seconds, overcoming the trade-off between solution
quality and computation time.

We now shift from network design to location assignment problems (LAP). In the
first paper on this theme, Satori et al. satori2023quantum  propose a novel
approach for solving the LAP in an Automated Storage and Retrieval System
(AS/RS) using quantum annealing. The problem involves optimising the
assignment of product locations on shelves to improve picking efficiency. The
proposed method considers product pairs based on picking frequency and assigns
them to empty shelves in order of distance from an outlet, with the decision
variable being the swapping of positions within product pairs. The paper
introduces two formulations: the All-Layout formulation and the Swap
formulation. The former is formulated as a mixed-integer programming (MIP)
problem, while the latter is designed for iterative optimisation, reducing the
number of variables. The authors evaluate the performance of both formulations
using various solvers, including a MIP-solver (COIN-OR),SA, QA, and hybrid QA.
Numerical experiments validate the expected retrieve time as an objective
function and demonstrate the effectiveness of iterative optimisation in the
Swap formulation. The paper concludes that the proposed Swap formulation,
particularly when combined with quantum annealing, offers a promising approach
for solving this specific problem.

Next, the chapter by Guo guo2020quantum  discusses the application of QA to
solve, what they call, NP-hard spatial optimisation problems. Spatial
optimisation involves mathematical models to find the best solutions for
spatial decision problems, such as the FLP and NDP. The case study involves
programming a $p-$median model using the D-Wave QA and applying quantum
annealing to a biomass-to-biofuel supply chain optimisation problem. Numerical
results suggest a computational advantage of quantum annealing over classical
simulated annealing in certain scenarios. The authors suggest that quantum
computing, particularly quantum annealing, holds promise for solving complex
geospatial problems, but further research is needed to understand its full
potential and integrate it with modern High Performance Computing HPC
architecture. The authors envision a near-term future where QPUs could
supplement HPC for specific spatial optimisation problems, with a long-term
potential to be a game changer in solving computationally demanding geospatial
problems.

The paper by Giraldo et al. giraldo2022using  contributes to the integration
of quantum computing into urban and regional science, focusing on the maximal
covering location problem (MCLP). The MCLP involves optimising population
coverage within a specified service distance by locating a fixed number of
facilities. The paper outlines the process of transforming the MCLP into a
format suitable for two quantum computing paradigms: QA (D-Wave) and GBC
(IBM). The authors conduct computational experiments on real quantum devices
and classical quantum simulators, specifically applying QA and QAOA. The
results reveal the successful solution of MCLP instances using quantum
annealing technology. The paper compares the performance of QA and QAOA,
noting that quantum annealing shows great potential for solving this kind of
problems, while gate-based quantum technology faces (relatively more)
challenges.

Facility Location Problems have connections with the Quadratic Assignment
Problem. The quadratic nature of this problem makes it, expectedly, suited for
quantum computing. The paper by Khumalo khumalo2022investigation  discusses
the application of quantum computing to solve two specific problems: the TSP
and the Quadratic Assignment Problem (QAP). The TSP was already discussed
before. The authors explore again the potential of VQE and QAOA, in solving
instances of TSP and QAP. The paper extends previous benchmarks by including
the newest and largest IBM quantum devices. It introduces preliminary findings
for the QAOA on tractable instances and presents metrics to assess the
feasibility spectrum of quantum algorithms on IBM devices. The authors
investigate the impact of the conditional reset feature on IBM systems,
comparing it to previous results. The experimental results demonstrate that
classical optimisation algorithms outperform quantum algorithms in terms of
success rate, feasibility, and computational time for solving TSP and QAP
instances for now. The VQE algorithm performs better than QAOA in terms of
solution quality metrics. The conditional reset feature on IBM devices does
not show a noticeable improvement in computational performance. The paper
suggests that as quantum technology evolves, the performance of quantum
algorithms could improve. The authors highlight the need for further
exploration of quantum formulations, such as QUBO and Alternating Direction
Method of Multipliers (ADMM), and the potential advancements in higher-
performing processors with more qubits.

Also Tosun et al. tosun2022new  dive into the QAP. Their goal is to minimise
the total assignment cost in a scenario with $n$ facilities and $n$ locations.
This cost is calculated by summing the facility placement costs and
multiplying inter-location distances with flow amounts among facilities. The
paper discusses Quantum Bridge Analytics, Quantum Computing, and the
mathematical formulation of QAP as a QUBO model. It explores the challenges
and potential of combining metaheuristics with quantum computing for solving
optimisation problems efficiently. The authors propose a methodology to
transform large QAP instances into QUBO models and compare results with
classical robust tabu search methods. The study suggests that even with
current quantum computing limitations, QUBO transformation can be feasible for
difficult instances, paving the way for hybrid techniques that combine
classical and quantum computing. The authors acknowledge challenges such as
finding optimal penalty values and plan to automate this process in future
research.

As a last example, the work of Choo et al. chooinvestigating  explores the
feasibility of solving the FLP as a Quadratic Assignment Problem (QAP) on
D-Wave’s QA. The authors propose a method to convert the QAP into a QUBO
formulation and embed it onto D-Wave’s hardware. The study reveals that, in
the worst case, the current hardware can only handle QAPs with seven variables
due to the limitation of qubits. To address this, the authors demonstrate a
reduction in qubits required for QAPs with duplicate rows, potentially
allowing the solution of larger instances. Additionally, they introduce a
decomposition approach for solving generic QAPs on D-Wave’s QA. The work
emphasises the challenges and limitations of directly solving QAPs on D-Wave’s
hardware and provides insights into potential improvements as quantum
computing technology evolves.

###  3.4 Fleet maintenance and optimisation

In the field of fleet maintenance and optimisation, the application of quantum
algorithms emerges as a promising avenue for addressing complex logistical
challenges. Fleet management involves decisions on vehicle maintenance
schedules and resource allocation, which are integral to ensuring operational
efficiency and cost-effectiveness. The main problem in this area for which
quantum approaches are proposed is the Tail Assignment problem (TAP). The Tail
Assignment problem (TAP) is faced by airlines, where the objective is to
efficiently assign individual aircraft to a set of flights to minimise overall
costs. The TAP is part of the larger airline planning process, involving
complex optimisation problems with various constraints related to passengers,
crew, aircraft, maintenance, and ground staff.

The first work in this direction is the paper by Vikstaal et al.
vikstaal2020applying . They explore the application of the QAOA to instances
of this problem derived from real-world data. The instances are reduced to fit
on quantum devices with 8, 15, and 25 qubits, leaving only one feasible
solution per instance. The reduction allows mapping the Tail Assignment
problem onto the Exact Cover problem. The QAOA is simulated on an ideal
quantum computer to investigate its performance in solving the simplified Tail
Assignment problem. The study reveals that repeated runs of QAOA can identify
feasible solutions with close to unit probability for all instances. The
authors also observe patterns in the variational parameters, enabling the use
of an interpolation strategy that simplifies the classical optimisation part
of the QAOA. The study also highlights non-trivial properties in the
connectivity of the instances and raises questions about the performance of
QAOA compared to classical algorithms for larger instances of the problem. The
authors also mention an alternative method for optimising variational
parameters using the Gibbs objective function, leaving it for further study.

Next, the dissertation of Martins martins2020applying  aims to study the
feasibility of solving the TAP, considering operational restrictions and
costs, using Quantum Annealing. The main contributions of the dissertation
include detailing a model for the Tail Assignment Problem, analysing and
comparing the scalability of different modelling techniques, and presenting a
comparison of solutions obtained through classical and hybrid approaches. The
scalability analysis indicates that Direct QUBO modelling performs best, and
the comparison between solvers suggests that Hybrid Solvers outperform others
in terms of solution quality.

This paper by Willsch et al. willsch2022benchmarking  conducts a benchmark of
the QPUs of two prominent quantum annealers: the D-Wave Advantage (with 5000+
qubits) and its precursor D-Wave 2000Q (with 2000+ qubits). One of the
benchmarking problems used is the TAP. The benchmark set encompasses problems
of diverse sizes, connectivity levels, and complexities. Results of the study
are that the Advantage system exhibits superior performance across almost all
problems, showcasing a noteworthy increase in success rates and the ability to
handle larger problems compared to D-Wave 2000Q. The improved performance of
Advantage is attributed not only to the increased qubit count but also to
enhanced qubit connectivity. Advantage’s Pegasus topology, featuring 15
connections per qubit, surpasses D-Wave 2000Q’s Chimera topology with only 6
connections. The Advantage system demonstrates approximately twice the speed
of D-Wave 2000Q in terms of programming and readout times. It also displays
shorter time-to-solution and annealing times, along with consistently higher
success rates and smaller fluctuations over multiple repetitions. D-Wave 2000Q
may achieve better success rates for problems with sparse connectivity that do
not necessitate the many new couplers present on Advantage. Improved
connectivity does not universally enhance performance, depending on the
specific requirements of each problem instance.

###  3.5 Cargo-loading, knapsack and bin-packing problems

Efficient cargo loading is crucial for industries grappling with space
constraints and diverse load requirements. The knapsack problem involves
selecting the most valuable combination of items to fit a limited capacity,
while bin-packing focuses on optimising the allocation of items into
containers. Also here, classical algorithms encounter difficulties in swiftly
solving these problems, especially as the scale and complexity increase. This
section explores the application of quantum algorithms to approximately solve
cargo loading, knapsack, and bin-packing problems.

The paper by Nayak et al. nayak2022quantum  focuses on addressing challenges
in the aviation industry related to the optimisation of aircraft cargo loading
and the reduction of loading/unloading operations at multiple stopovers. The
primary goals are to maximise the payload capacity of aircraft, leading to
reduced fuel consumption and increased revenue, and to minimise the
operational and handling costs associated with loading and unloading cargo.
The paper presents a quantum approach for tackling these challenges,
experimenting with both QA-based and GBC algorithms. Among the quantum
platforms tested, D-Wave’s QA is identified as the most promising, as it
offers sufficient qubits to address realistic problems compared to gate-based
and quantum-inspired optimisers. The experiments are conducted on a Boeing
747-8F aircraft, one of the largest cargo carriers in the world. The model
used for the experiments manages the 2D/3D stacking of containers with and
without racks. Results obtained from quantum solvers, particularly D-Wave, are
said to outperform classical solvers, demonstrating the potential of quantum
computing in solving complex cargo loading problems. The authors emphasise
that due to the limitations of qubits in current quantum hardware, their
experiments had to be constrained to minimal parameters.

Also, Sotelo et al. hernandez2020application ; sotelo2021determination
created an application of quantum optimisation techniques to cargo logistics
on ships and airplanes. Their papers address the optimisation challenge of
determining the optimal configuration for maximising the loading of cargo
vehicles while adhering to specific constraints: maximum volume available and
maximum possible weight. The proposed solution, presented at the Airbus
Quantum Computing Challenge, employs the VQE algorithm. The Airbus Quantum
Computing Challenge consisted of 5 problems: 1. Aircraft Climb Optimisation,
2. Computational Fluid Dynamics, 3. Quantum Neural Networks for Solving
Partial Differential Equations, 4. Wingbox Design Optimisation and last 5.
Aircraft Loading Optimisation (ALO). The solution was implemented in the IBM
Qiskit platform, utilising a noise-free environment simulator. The problem set
comprises 200 different container arrangements for loading, with random
starting points and 1000 iterations for the VQE algorithm. Realistic weight
distributions are ensured by selecting weights with an expected value of 1/3
of the maximum weight of the problem instance. Results are evaluated using a
metric based on the logarithm of the median of normalised energies for 200
instances. The experiments compare the performance of seven classical
optimisers available in Qiskit. The findings indicate variations in the
convergence speed of classical algorithms, with the Nelder-Mead algorithm
demonstrating superior results. The convergence analysis reveals that over 70%
of problem instances achieve a convergence ratio of 0.01 for the Nelder-Mead
algorithm, while other classical algorithms exhibit varying degrees of
convergence efficiency. For instance, the COBYLA algorithm achieves a 50%
convergence ratio.

Also the work of Traversa traversa2019aircraft  and Pilon et al.
pilon2021aircraft  published a solution to the ALO problem as formulated by
Airbus. Unlike developing algorithms for future quantum computers, the
approach by Traversa formulates the ALO problem using Integer Programming (IP)
and explores its solution through the MemComputing paradigm (which is not
quantum). The ALO problem involves optimising the placement of containers with
different sizes and weights in an aircraft, considering constraints on maximum
weight, shear, and centre of gravity. The study proposes a two-objective IP
problem with binary variables, utilising the MemCPU software for efficient
solution strategies. The MemComputing approach, based on self-organising
algebraic gates, proves to be a non-algorithmic solution with promising
scaling properties, demonstrating its potential for solving large-scale ALO
problems efficiently. Pilon formulates this problem using a QUBO formulation.
The model’s performance is benchmarked on different solvers, including a
classical solver for QUBO functions and the D-Wave 2000Q Quantum Annealer. The
results indicate the feasibility of the QUBO formulation and highlight
comparisons between classical and quantum approaches in terms of computational
time and loaded weight.

There are several papers looking directly at the Bin Packing Problem (BPP).
The work of Romero et al. v2023hybrid  introduces a hybrid quantum-classical
framework, called Q4RealBPP, designed to solve real-world instances of the
three-dimensional Bin Packing Problem (3dBPP), involving efficient packing of
items into bins. The work in romero2023solving  adds to that framework in the
following way: i) the existence of heterogeneous bins, ii) the extension of
the framework to solve not only three-dimensional, but also one- and two-
dimensional instances of the problem, iii) requirements for item-bin
associations, and iv) delivery priorities. Q4RealBPP addresses realistic
characteristics such as package and bin dimensions, overweight restrictions,
affinities among item categories, and preferences for item ordering, making it
applicable to actual industrial and logistics scenarios. They successfully
apply Q4RealBPP to 12 instances of different nature, showcasing its capacity
to handle real-world constraints, based on (D-Wave’s) Leap Constrained
Quadratic Model (CQM). They outline the need for a thorough comparison between
Q4RealBPP and traditional artificial intelligence methods, considering factors
such as robustness of results and execution times.

Another work on the BPP is by De Andoin et al. de2022comparative ;
de2022hybrid . These papers explore the potential of quantum and hybrid
quantum-classical algorithms to provide advantageous solutions for the one-
dimensional BPP (1dBPP). The proposed hybrid approach integrates a quantum
annealing subroutine for sampling feasible solutions, followed by a classical
optimisation subroutine for problem solution construction. To assess its
performance, the paper compares this hybrid strategy with classical
alternatives, specifically random sampling and a random-walk-based heuristic.
The focus is on evaluating the quantum approach’s ability to avoid stagnation,
a common issue in classical algorithms. The benchmark comprises 18 instances
with 10 and 12 packages, incorporating various weight distributions. Results
indicate that the quantum annealing strategy avoids stagnation observed in
classical algorithms, enabling a faster full sampling of feasible partial
solutions. The hybrid approach outperforms the random walk in a majority of
cases. To measure the performance of the sampling strategy, a metric counting
the number of iterations needed to measure the full feasible partial solution
space is proposed. The paper emphasises the importance of hyperparameter
optimisation, acknowledging that a more refined selection could further
enhance algorithm performance.

The study bu Cellini et al cellini2023qal  introduces QAL-BP, a novel QUBO
approach specifically for BPP. QAL-BP stands for Quantum Augmented Lagrangian
approach for Bin Packing problem. It utilises an augmented Lagrangian method
to incorporate the bin packing constraints into the objective function while
also facilitating an analytical estimation of heuristic, but empirically
robust, penalty multipliers. This approach leads to a more versatile and
generalisable model that eliminates the need for empirically calculating
instance-dependent Lagrangian coefficients, a requirement commonly encountered
in alternative QUBO formulations for similar problems. To assess the
effectiveness of the proposed approach, they conduct experiments on a set of
bin-packing instances using D-Wave’s Advantage system. Additionally, they
compare the results with those obtained from two different classical solvers,
namely simulated annealing and Gurobi. The experimental findings confirm the
correctness of the proposed formulation and also demonstrate the potential of
quantum computation in effectively solving the bin-packing problem,
particularly as more reliable quantum technology becomes available.

The next related problem is the Knapsack Problem (KP). Van Dam et al.
van2021quantum  introduces enhancements to the QAOA, to make it more suitable
for Knapsack Problem (KP). The KP involves selecting items with weights and
values to maximise the total value under a weight constraint. The
contributions of the paper are two techniques applied to QAOA. They first use
the outcome of a classical greedy algorithm to define an initial quantum state
and mixing operation for QAOA. Next they use quantum exploration to avoid
local minima around the greedy solutions obtained from the classical
algorithm. The study compares the performance of constant-depth quantum
optimisation heuristics with similarly shallow classical greedy and simulated
annealing algorithms. Despite the likelihood that more sophisticated classical
algorithms may outperform quantum algorithms, the comparison is considered
fair as it involves algorithms of equal simplicity. The paper suggests that
the quantum algorithms perform well with weak dependency on instance-specific
fine-tuning.

The same problem, however in a slightly different application area, is studied
in the work by Benson et al. benson2023cqm . This paper demonstrates the use
of D-Wave’s Leap Hybrid solver for solving a KP, specifically selecting meal
combinations from a fixed menu that fit certain constraints. The optimisation
problem is formulated as a Constrained Quadratic Model and uses D-Wave’s CQM
solver. The paper also discusses the generalisation of this model for finding
optimal drug molecules within a large search space with complex and
contradictory structures and property constraints. The CQM-solver is shown to
solve multi-object optimisation problems on an expedited timescale, making it
a valid choice for molecular drug design. While the presented problem has a
manageable number of combinations, the authors discuss the scalability of
quantum annealing for larger optimisation problems, highlighting potential
advantages over classical computing.

A variation of the KP that is even more likely to benefit from quantum
computing is the Quadratic Knapsack Problem (QKP). Bontekoe et al.
bontekoe2023translating  recognise that, in general, constrained quadratic
binary optimisation problems can be translated into QUBOs in several ways,
which can have a large impact on the performance when solving the QUBO. They
show six different QUBO formulations for the QKP and compare their performance
using simulated annealing. The best performance is obtained by a formulation
that uses no auxiliary variables for modelling the inequality constraints.

###  3.6 Prediction and Inventory Control

The next category of application is that of demand prediction. There are many
papers on Quantum Machine Learning (QML) and prediction, however only one on a
direct application within logistics and supply chain optimisation. Jahin et
al. jahin2023qamplifynet  focus on improving backorder prediction in supply
chain management (SCM) through the introduction of a novel hybrid quantum-
classical neural network called QAmplifyNet. Backorder prediction is used for
optimising inventory control, reducing costs, and enhancing customer
satisfaction. Traditional machine-learning models face challenges with large-
scale datasets and complex relationships. The proposed QAmplifyNet
demonstrates high accuracy in predicting backorders, particularly on short and
imbalanced datasets, outperforming classical models and quantum neural
networks. The study also addresses the scarcity of research on product
backordering, emphasising the challenges of class imbalance in datasets. While
classical machine learning models have been widely used, following the
authors, quantum-inspired techniques show superior performance, specifically
QAmplifyNet. The research integrates quantum and classical computing to
leverage the strengths of both, overcoming challenges in handling short,
imbalanced datasets common in SCM. The methodological framework involves
evaluating seven preprocessing techniques, selecting the best-performing one,
and enhancing the model’s interpretability using Explainable Artificial
Intelligence (XAI) techniques. Practical implications include improved
inventory control, reduced backorders, and enhanced operational efficiency.
QAmplifyNet achieves a high F1-score of 94% for predicting “Not Backorder” and
75% for predicting “Backorder”, along with the highest AUC-ROC score of
79.85%. The hybrid quantum-classical model shows promise for real-world SCM
applications, paving the way for further exploration of quantum-inspired
machine learning in supply chain management.

The work by Jiang jiang2022quantum  highlights the challenges in classic
computing related to large state and action spaces in supply chain problems.
They introduce a quantised policy iteration algorithm designed for inventory
control problems and demonstrate its effectiveness. They perform simulations
and experiments using IBM Qiskit and the qBraid system. They underscore the
practicality of variational algorithms for solving small-sized inventory
control problems.

###  3.7 Scheduling

In this section, we delve into the application of quantum algorithms to
address scheduling problems within the domains of logistics and supply chain
optimisation. Scheduling plays an important role in orchestrating the
efficient flow of resources, managing timelines, and optimising overall
operational processes. The research by Riandari et al. riandari2021quantum
explores the potential of quantum computing in production planning or
scheduling, using quantum algorithms like QAOA and VQE to minimise production
costs and address demand and resource constraints. They evaluate the potential
benefits, limitations, and difficulties associated with employing quantum
computing to production planning.

The work by Ajagekar et al. ajagekar2020quantum ; ajagekar2020quantum2
discusses multiple optimisation problems, including the job-shop scheduling
problem (JSP). They propose a hybrid approach to address this complex problem,
which involves determining an optimal schedule for a set of jobs on a set of
machines. The proposed MILP model incorporates due dates and sequence-
independent processing times, with decision variables representing start
times, assignments, and sequencing of jobs. The hybrid QC-MILP decomposition
method involves two phases: solving the MILP problem with a classical Gurobi
solver and employing QC for sequencing. The quantum processor, QA, is utilised
to determine feasible schedules, overcoming memory limitations of classical
solvers for larger instances. Computational results indicate competitive
performance, particularly for large-scale industrial problems, where classical
solvers face limitations. The approach says to guarantee a global optimal
solution but may require longer runtimes, showcasing the complementary
strengths of MILP and QC in tackling intricate scheduling problems
effectively. The other problem they study is the Manufacturing Cell Formation
(MCFP) problem. Cellular manufacturing involves organising equipment to
facilitate continuous flow production, enhancing efficiency. Here, they
propose a hybrid QC and Mixed-Integer Quadratic Programming (MIQP) approach to
solve the MCFP. The MIQP model is formulated to minimise costs associated with
intracellular movement, resource utilisation, and machine set-ups. The dual LP
model is solved classically, and its results guide the quantum step, solving a
QUBO problem. The hybrid method efficiently handles large instances,
outperforming conventional solvers. The proposed approach provides optimal or
near-optimal solutions, demonstrating again the complementary strengths of
classical and quantum computing in tackling complex manufacturing problems.

The article by Permin et al. permin2022simple  explores the application of
quantum computers to simplify the complexity of Job Shop Scheduling (JSP). The
study employs Grover’s algorithm in IBM Qiskit to translate a JSP into a
binary qubit format, effectively reducing the search space. By conducting
simulations, the research demonstrates a significant decrease in complexity

The article by Venturelli et al. venturelli2015quantum  also focuses on the
JSP. Here, QA is employed as a solver for JSP, with a detailed presentation of
the formulation and strategies used. The study discusses the challenges
associated with quantum annealing, including limitations in precision,
connectivity, and the number of variables. The quantum annealer’s performance
is compared with classical global-optimum solvers, particularly, as the
authors call them, algorithms B (based on Brucker et al. brucker1994branch )
and MS (based on Martin et al. martin1996new ). Results indicate that D-Wave 2
QA faces challenges in outperforming classical algorithms on small instances
of JSP, raising questions about its scalability and asymptotic advantage.
Motivated by these quantum annealing results, the study proposes a QA JSP
solver, addressing issues such as embedding, pre-processing, and running
strategies. The article introduces a solving process for a full JSP
optimisation solver, inclusive adapting classical algorithms as pre-processing
techniques. The proposed timespan discrimination is highlighted as a flexible
compromise between full optimisation and decision formulations, allowing for
immediate benefits from precision improvements.

Also Kurowski et al. kurowski2020hybrid  employ a QA approach for the JSP. The
mapping of the JSP to the QUBO formulation is detailed, considering the
constraints and the specific topology of the D-Wave 2000Q. The proposed
heuristic is explained, involving the decomposition of the JSP into smaller
optimisation problems and the tuning of QUBO parameters. Experimental studies
on a JSP test instance (ft06) are presented, including estimates of the number
of feasible solutions. The results obtained from the quantum annealing
heuristic are compared with optimal solutions generated by classical heuristic
methods for the JSP benchmark.

The study by by Amaro amaro2022case  explores the application of VQAs on IBM’s
superconducting quantum processors to solve the JSP. The four VQAs tested are
the QAOA, general VQE, variational quantum imaginary time evolution (VarQITE),
and the recently introduced filtering VQE(F-VQE). The study compares
convergence speed, scalability, and accuracy of the VQAs, with a focus on
practical applicability to non-fault-tolerant hardware. The results show that
F-VQE outperformed other algorithms in terms of convergence speed and
frequency of sampling the optimal solution, even on instances with five
qubits. VarQITE exhibited slower convergence but sampled optimal solutions
more frequently. VQE converged slowly and sampled optimal solutions less
frequently, while QAOA struggled with convergence due to the complexity of
circuits and optimiser choice. In a subsequent set of experiments, F-VQE was
further tested on larger instances with up to 23 qubits, showcasing its
promising performance and ability to handle larger combinatorial optimisation
problems. The study suggests that F-VQE is a step towards addressing
challenges associated with quantum hardware limitations, including sparse
connectivity and cross-talk noise.

Schworm et al. schworm2023solving  explore the application of QA as a
metaheuristic for solving the JSP, particularly the flexible job shop
scheduling problems (FJSP). QA utilises quantum mechanical effects to evaluate
multiple solutions simultaneously, potentially providing time-efficient
solutions for complex assignment problems. The study assesses QA’s efficiency,
scalability, solution quality, and computing time by solving FJSP instances of
various sizes. The results demonstrate QA’s potential in finding high-quality
solutions for the FJSP within seconds, even for large instances, making it a
promising approach for industry-scale applications. The evaluation includes a
scientific benchmark comparing QA with state-of-the-art algorithms,
highlighting QA’s efficiency in finding high-quality solutions in a short
time. While QA shows promise, challenges such as dynamic factors in industrial
settings and the need for multi-objective optimisation are acknowledged for
future research. The study concludes that QA can be a valuable tool for
intelligent transportation systems, emphasising the need for further
improvement and exploration of QA’s capabilities.

The paper by Denkena et al. denkena2021quantum  introduces a new method for
process-parallel Flexible Job Shop Scheduling (FJSP) using QA. The FJSP
requires continuous and process-parallel optimisation of machine allocation
and processing sequences. The proposed quantum annealing-based method
demonstrates results comparable to classical heuristics with reliably low
anneal times, especially for large problem instances. The approach is shown to
be robust against stochastic influences and hyper-parameter variations. In a
practical use case, the approach outperforms classical MES solutions and
combinations of MES with genetic algorithms in terms of makespan reduction.

This paper by Carugno et al. carugno2022evaluating  also investigates the
application of Quantum Annealing (QA) to the JSP. The study provides a
detailed analysis of applying QA to JSP, covering problem formulation, quantum
annealer fine-tuning, and comparison with classical solvers. The research
addresses often-overlooked aspects, such as computational costs, qubit
requirements, and mitigating chain breaks. Additionally, advanced tools like
reverse annealing are explored. Results reveal challenges at various stages,
highlighting important research questions and areas for improvement in quantum
annealing technology. The study contributes to a balanced discussion on QA’s
potential and limitations in solving JSP, emphasising open research directions
for further exploration.

A factory scheduling problem was presented by Yarkoni et al. yarkoni2021multi
, derived from a real-world optimisation problem involving re-ordering colour
sequences in a paint shop during the manufacturing of cars. The task is to
assign colours to sequences of cars such that all customer orders are
fulfilled while simultaneously minimising the number of colour switches within
the sequence. In this work, the authors investigated problem instances ranging
from 10–3000 cars in a single sequence. The multi-car paint shop problem
described in the paper has a simple Ising model representation, and instances
derived directly from real-world data were solved using D-Wave’s QPUs, hybrid
algorithms, and classical algorithms. The results showed that while the
quantum hardware and hybrid algorithms were able to provide adequate solutions
to the problem for smaller sizes, the performance of these algorithms
approached that of a simple greedy algorithm in the large size limit. However,
the analysis also concluded that QA is currently approaching the limit of
industrially-relevant problem scales. Partly the same authors look at the same
problem but then using the QAOA approach in streif2021beating . This research
combines numerical simulations with experimental data obtained from a trapped
ion quantum computer, presenting a comparison between the performance of QAOA
and classical heuristics, particularly in the infinite-size limit for
noiseless quantum computation. The experimental findings show the quick
degradation of the quantum algorithm’s efficiency as the problem size
increases.

Also Huang et al. huang2022paint  look at the paint shop problem. While
previous research primarily targeted minimising color changeovers between
vehicles, this study introduces a novel problem formulation considering not
only color transitions but also the impact on product quality. By
incorporating a machine learning model, which is not explained in the paper,
to predict quality defects and leveraging quantum computing, the paper
presents an approach for solving the generalised paint shop sequencing
problem. The paper concludes with a case study showcasing the potential of
QAOA in solving a small-scale sequencing problem, paving the way for future
exploration in real-world, industrial-sized scenarios.

The next problem coming from the aircraft industry, is the Aircraft Recovery
Problem (ARP), a crucial aspect of airline disruption management. Given the
financial pressures on airlines, aggravated by the recent pandemic, a swift
and efficient solution to recover from disruptions is essential to minimise
financial losses. Mori et al. mori2022replanning  develop a Two-Stage
algorithm to model ARP as a QUBO problem. Two experiments are conducted to
evaluate the model’s performance using QC in comparison to classical solvers.
The first experiment compares the proposed approach with a previous one
de2015evolutionary  based on evolutionary computation algorithms, showing
similar execution times and results. The second experiment compares a
classical solver with a hybrid solver using the proposed model, demonstrating
identical solutions but with faster execution times for the hybrid solver.

A more generic problem that also has applications in the aircraft industry is
the Quadratic Assignment Problem (QAP). Mohammadbagherpoor
mohammadbagherpoor2021exploring  explores the QAP in the application of
airline gate-scheduling . Here, the QAP involves optimising the allocation of
facilities (airline gates) to locations (flights) with known assignment costs.
The paper introduces the concept of using VQE and space-efficient graph
colouring, to enhance quantum computing algorithms for solving QAPs. The study
tests these enhanced quantum computing algorithms on an 8-airline gate and
24-flight test case using both the IBM quantum computing simulator and a
27-qubit superconducting transmon IBM quantum computing hardware platform. The
results suggest that smaller circuit size and efficient mapping to hardware
topology enable the application of variational quantum algorithms to larger
problem sets, a critical advancement in solving optimisation problems.

The work by Scherer et al. scherer2021oncall  discusses the application of
Grover’s algorithm, to solve the “on-call spacecraft operator scheduling”
problem at the German Space Operating Center (GSOC). The problem involves
scheduling operators for spacecraft missions, considering various constraints
and optimisation goals. The scheduling must allocate approximately 50
operators to 20 positions over 180 days, while satisfying constraints such as
operator availability, working preferences, and limiting consecutive working
days. Evaluation is done using Qiskit’s QASM simulator with up to 32 qubits.
The success rates are evaluated for different problem sizes and
configurations. The paper successfully demonstrates solving the scheduling
problem using Grover’s algorithm on a quantum simulator. Future work includes
testing on real quantum devices, improving qubit stability, and exploring
quantum-classical hybrid approaches. Emphasis on minimising the number of
qubits and optimising the algorithm’s width and depth is highlighted.

Adelomou et al. adelomou2020using  address personnel scheduling. They look at
the challenges faced by social workers in generating optimal visiting
schedules for patients. The problem involves a combination of routing and
planning issues. The article suggest the use of the Parameterised Quantum
Circuits (PQC) and the VQE algorithm in solving the problem. It explores the
potential of PQC as a basis for Machine Learning (ML) and delves into the
formulation of the social worker problem for quantum computing. The proposed
methodology aims to offer an efficient and intelligent system, capable of
learning by analogy and avoiding the need for recalculating from scratch.
Experimental results suggest the effectiveness of the Quantum Cases-Based
Reasoning (QCBR) approach, demonstrating potential benefits for optimising
worker schedules. The article concludes by emphasising the broader
applicability of the proposed formulation to solve various planning,
scheduling, and routing problems. It envisions the creation of hybrid and
intelligent systems that leverage quantum resources efficiently, reducing
costs and laying the foundation for generalised problem-solving in the field.

##  4 Conclusions and Recommendations

The total overview of all the literature discussed in the previous section can
be found in Table 1 and Table 2. Here the paradigm, the main topic and the
discussed problem are listed. Also, in these tables is indicated whether the
solution is a pure quantum solution or a hybrid quantum solution. With hybrid
we mean ‘Horizontal Hybrid Quantum Computing’, following the classification of
phillipson2023classification . This means that the algorithm requires both a
quantum computer and a classical computer to perform an algorithm, in
sequential or parallel order. As we can see in the tables, most of the current
solutions use hybrid approaches. This is as expected, from two thoughts.
First, the current generation of quantum computers are still small, meaning
that solving real world use cases, which is what most articles in the
literature aim for, is limited and classical computers are needed to perform
at least part of the algorithm. Next, for many optimisation problems a hybrid
approach, using quantum computers as part of a (meta-) heuristic approach is
expected to last, where also classical algorithms break down the calculation
pipeline and the QC is not expected to solve NP-hard problems
aaronson2008limits . These meta-heuristic approaches, where a QC is combined
with a classical counterpart report the best performances. An other aspect
that is clearly visible in this overview is that the majority of publications
use QA as main quantum paradigm. This follows by the relative high number of
qubits and larger size of problems this technology allows for. Also the hybrid
approaches, as offered by D-Wave in their full stack approach, help with the
uptake here. The QAOA and other VQE approaches on the gate-based device are
the second most used approach, however they are still very much limited in
performance. More problem specific and machine learning approaches are still
limited in number. There is quite a bit of room for experimentation here. When
we look at the topics and problems covered, we see most attention to the
classical areas of routing and scheduling. Especially in predictions there is
again room for further research, potentially for QML approaches.

Generally, we can say that we endorse the conclusions reached in the work of
Osaba osaba2022systematic . Were we looked more general than only VRP and TSP
work, also we can conclude that the majority of the papers conclude that
current hardware is in the early stage: researchers face small number of
qubits and inherent limitations such as noise and decoherence, and challenges
in tailoring problems to hardware capacities. This leads to limitations in
addressing complex formulations. Only a small number of papers indicate that
their hybrid approach beats current classical approaches. Most of the work
indicate the potential advantages and benefits of their approach.

## Acknowlegements

This publication is part of the project Divide and Quantum ‘D&Q’
NWA.1389.20.241 of the program ‘NWA-ORC’, which is partly funded by the Dutch
Research Council (NWO). The author likes to thank Juan Boschero and Stan van
der Linde for their valuable input.

Work | Paradigm | Topic | Problem | Nature
---|---|---|---|---
Ajagekar ajagekar2020quantum2  | QA - QUBO | Routing | VRP | hybrid
Alsaiyari alsaiyari2023variational  | GBC - QAOA/VQE | Routing | VRP | hybrid
Atchade-Adelomou atchade2021qrobot  | QA and GBC - QUBO | Routing | picking | hybrid
Azad azad2022solving  | GBC - QAOA | Routing | VRP | hybrid
Azzaoui azzaoui2021quantum  | GBC - QAOA | Routing | TSP | hybrid
Bentleybentley2022quantum  | GBC - QAOA | Routing | CVRP | hybrid
Borowski borowski2020new  | QA - QUBO | Routing | VRP/CVRP | full and hybrid
Bourreau bourreau2023indirect  | GBC - QAOA | Routing | TSP | hybrid
Correll correll2023quantum  | GBC - QML | Routing | VRP | hybrid
Dixit dixit2023quantum2  | QA - QUBO | Routing | STDSP | full
Feld feld2019hybrid  | QA - QUBO | Routing | CVRP | hybrid
Fitzek fitzek2021applying  | GBC - QAOA | Routing | HVRP | hybrid
Harikrishnakumar harikrishnakumar2020quantum  | QA - QUBO | Routing | (D-)MDCVRP | full
Harwood harwood2021formulating  | GBC - QAOA | Routing | VRPTW | hybrid
Irie irie2019quantum  | QA - QUBO | Routing | CVRPTW | hybrid
Lo lo2021genetic  | QRNG | Routing | VRP | hybrid
Khumalo khumalo2022investigation  | GBC - QAOA/VQE | Routing | TSP | hybrid
Le le2023quantum  | QA - QUBO | Routing | sTSP | hybrid
Leonidas leonidasqubit  | GBC - QAOA | Routing | VRPTW | hybrid
Lo lo2021genetic  | QRNG | Routing | VRP | hybrid
Makhanov makhanov2023quantum  | GBC - Grover’s | Routing | SPP | hybrid
Marsoit marsoit2021quantum  | QA - QUBO | Routing | CVRP | hybrid
Masuda masuda85optimisation  | CA - QUBO | Routing | TDVRPTW | full
Mohanty mohanty2023analysis  | GBC VQE | Routing | VRP | hybrid
Neukart neukart2017traffic  | QA - QUBO | Routing | Flow opt. | hybrid
Palackal palackal2023quantum  | GBC - QAOA/VQE | Routing | TSP | hybrid
Palmieri palmieriquantum  | QA and GBC - QUBO | Routing | CVRP | hybrid
Papalitsas papalitsas2019qubo  | QA - QUBO | Routing | TSPTW | full
Phillipson phillipson2021multimodal  | QA - QUBO | Routing | Flow opt. | hybrid
Poggel poggel2023recommending  | Generic | Routing | CVRP | hybrid
Rana rana2022quantum  | QA and GBC - QUBO | Routing | CVRP | hybrid
Salehi salehi2022unconstrained  | QA - QUBO | Routing | TSPTW | full
Sales sales2023adiabatic  | QA - QUBO | Routing | CVRP | full and hybrid
Sanches sanches2022short  | GBC - RL | Routing | CVRP | hybrid
Sinno sinno2023performance  | QA - QUBO | Routing | CVRP | hybrid
Spyridis spyridis2023variational  | GBC - QAOA | Routing | m-TSP | hybrid
Srinivasan srinivasan2018efficient  | GBC - QPE | Routing | TSP | hybrid
Warren warren2020solving  | QA - QUBO | Routing | TSP | full and hybrid
Weinberg weinberg2023supply  | QA - QUBO | Routing | CVRP | hybrid
Xie xie2023feasibility  | GBC - QAOA | Routing | CVRP | hybrid
Yarkoni yarkoni2021solving  | QA - QUBO | Routing | SRP | hybrid
Choo chooinvestigating  | QA - QUBO | Network Design | FLP | hybrid
Ding ding2021implementation  | QA -QUBO | Network Design | NDP | hybrid
Ding ding2019logistic  | QA -QUBO | Network Design | NDP | full
Dixit dixit2023quantum  | QA -QUBO | Network Design | NDP | hybrid
Gabbassov gabbassov2022transit  | QA - QUBO | Network Design | UTP | hybrid
Giraldo giraldo2022using  | QA and GBC - QUBO | Network Design | MCLP | hybrid
Guo guo2020quantum  | QA - QUBO | Network Design | FLP | hybrid
Khumalo khumalo2022investigation  | GBC - QAOA/VQE | Network Design | FLP | hybrid
Klar klar2022quantum  | QA - QUBO | Network Design | FLP | hybrid
Mahasinghe mahasinghe2021qubo  | QUBO | Network Design | FLP | -
Malviya malviya2023logistics  | QA - QUBO | Network Design | NDP | hybrid
Satori satori2023quantum  | QA - QUBO | Network Design | LAP | hybrid
Tosum tosun2022new  | QUBO | Network Design | QAP | -
Table 1: Overview - Part I

Work | Paradigm | Topic | Problem | Nature
---|---|---|---|---
Martins martins2020applying  | QA - QUBO | Fleet opt. | TAP | hybrid
Vikstaal vikstaal2020applying  | GBC - QAOA | Fleet opt. | TAP | hybrid
Willsch willsch2022benchmarking  | QA - QUBO | Fleet opt. | TAP | hybrid
De Andoin de2022comparative  | QA - QUBO | Cargo | BPP | hybrid
De Andoin de2022hybrid  | QA - QUBO | Cargo | BPP | hybrid
Benson benson2023cqm  | QA - CQM | Cargo | KP | hybrid
Bontekoe bontekoe2023translating  | QA - QUBO | Cargo | QKP | full
Cellini cellini2023qal  | QA - QUBO | Cargo | BPP | full
Nayak nayak2022quantum  | QA - QUBO | Cargo | ALO | hybrid
Pilon pilon2021aircraft  | QA - QUBO | Cargo | ALO | full
Romero romero2023solving ; v2023hybrid  | QA - CQM | Cargo | BPP | hybrid
Sotelo hernandez2020application ; sotelo2021determination  | GBC - VQE | Cargo | ALO | hybrid
Van Dam van2021quantum  | GBC - QAOA | Cargo | KP | hybrid
Jahin jahin2023qamplifynet  | GBC - QML | Prediction | Prediction | hybrid
Jiang jiang2022quantum  | GBC - HHL/VQE | Prediction | Inventory | hybrid
Adelomou adelomou2020using  | GBC - VQE | Scheduling | Personnel | hybrid
Ajagekar ajagekar2020quantum2  | QA - QUBO | Scheduling | JSP | hybrid
Ajagekar ajagekar2020quantum2  | QA - QUBO | Scheduling | MCFP | hybrid
Amaro amaro2022case  | GBC - VQE | Scheduling | JSP | hybrid
Carugno carugno2022evaluating  | QA - QUBO | Scheduling | JSP | hybrid
Denkena denkena2021quantum  | QA - QUBO | Scheduling | FJSP | hybrid
Huang huang2022paint  | QA - QUBO | Scheduling | JSP | hybrid
Kurowski kurowski2020hybrid  | QA - QUBO | Scheduling | JSP | hybrid
Mohammadbagherpoor mohammadbagherpoor2021exploring  | QA - VQE | Scheduling | QAP | hybrid
Mori mori2022replanning  | GBC and QA - QAOA | Scheduling | ARP | hybrid
Permin permin2022simple  | GBC - Grover | Scheduling | JSP | hybrid
Riandari riandari2021quantum  | GBC - QAOA | Scheduling | Production opt. | hybrid
Scherer scherer2021oncall  | GBC - Grover | Scheduling | JSP | full
Streif streif2021beating  | GBC - QAOA | Scheduling | JSP | hybrid
Schworm schworm2023solving  | QA - QUBO | Scheduling | JSP | hybrid
Venturelli venturelli2015quantum  | QA - QUBO | Scheduling | JSP | full
Yarkoni yarkoni2021multi  | QA - QUBO | Scheduling | JSP | hybrid
Table 2: Overview - Part II

ALO | Aircraft Loading Optimisation
---|---
AP | Assignment Problem
ARP | Aircraft Recovery Problem
AS/RS | Automated Storage and Retrieval System
BPP | Bin Packing Problems
CA | Classical annealing
CQM | Constrained Quadratic Model
CVRP | Capacitated Vehicle Routing Problem
FJSP | Flexible Job Shop scheduling Problem
FLP | Factory Layout Planning
GBC | Gate Based Computer/Computing
HPC | High Performance Computing
HVRP | Heterogeneous Vehicle Routing Problem
JSP | Job Shop Problem
KP | Knapsack Problem
LAP | Location Assignment Problem
LND | Logistic Network Design
MCFP | Manufacturing Cell Formation Problem
(D-)MDCVRP | (Dynamic) Multi-Depot Capacitated Vehicle Routing Problem
MIP | Mixed-Integer Programming
MCLP | Maximal Covering Location Problem
NDP | Network Design Problem
NISQ | Noisy Intermediate-Scale Quantum (devices)
QA | Quantum Annealing
QAOA | Quantum Approximate Optimisation Algorithm
QAP | Quadratic Assignment Problem
QKP | Quadratic Knapsack Problem
QML | Quantum Machine Learning
QPE | Quantum Phase Estimation
QPU | Quantum Processing Unit
QRNG | Quantum Random Number Generator
QUBO | Quadratic Unconstrained Binary Optimisation problem
RL | Reinforcement Learning
SIC | Spatial Interaction Coverage
SPP | Shortest Path Problem
SRP | shipment rerouting problem
STDSP | Stochastic Time Dependent Shortest Path problem
TAP | Tail Assignment Problem
TDVRPTW | Time-Dependent Vehicle Routing Problem with Time Windows
TSP | Travelling Salesman Problem
TSPTW | Travelling Salesman Problem with Time Windows
m-TSP | multiple Travelling Salesman Problem
sTSP | selective travelling Salesman Problem
UTP | urban transit planning
VQE | Variational Quantum Eigensolver
VRP | Vehicle Routing Problem
VRPTW | Vehicle Routing Problem with Time Windows

## References

  * (1) Aaronson, S.: The limits of quantum. Scientific American 298(3), 62–69 (2008)
  * (2) Adelomou, A.P., Ribe, E.G., Cardona, X.V.: Using the parameterized quantum circuit combined with variational-quantum-eigensolver (vqe) to create an intelligent social workers’ schedule problem solver. arXiv preprint arXiv:2010.05863 (2020)
  * (3) Ajagekar, A.: Quantum computing for process systems optimization and data analytics. Master’s thesis, University of Porto (2020)
  * (4) Ajagekar, A., Humble, T., You, F.: Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems. Computers & Chemical Engineering 132, 106630 (2020)
  * (5) Albash, T., Lidar, D.A.: Demonstration of a scaling advantage for a quantum annealer over simulated annealing. Physical Review X 8(3), 031016 (2018)
  * (6) Alsaiyari, M., Felemban, M.: Variational quantum algorithms for solving vehicle routing problem. In: 2023 International Conference on Smart Computing and Application (ICSCA). pp. 1–4. IEEE (2023)
  * (7) Amaro, D., Rosenkranz, M., Fitzpatrick, N., Hirano, K., Fiorentini, M.: A case study of variational quantum algorithms for a job shop scheduling problem. EPJ Quantum Technology 9(1), 5 (2022)
  * (8) Andoin, M.G.d., Oregi, I., Villar-Rodriguez, E., Osaba, E., Sanz, M.: Comparative benchmark of a quantum algorithm for the bin packing problem. In: 2022 IEEE Symposium Series on Computational Intelligence (SSCI). pp. 930–937. IEEE (2022)
  * (9) Andoin, M.G.d., Osaba, E., Oregi, I., Villar-Rodriguez, E., Sanz, M.: Hybrid quantum-classical heuristic for the bin packing problem. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion. pp. 2214–2222 (2022)
  * (10) Atchade-Adelomou, P., Alonso-Linaje, G., Albo-Canals, J., Casado-Fauli, D.: qrobot: A quantum computing approach in mobile robot order picking and batching problem solver optimization. Algorithms 14(7), 194 (2021)
  * (11) Azad, U., Behera, B.K., Ahmed, E.A., Panigrahi, P.K., Farouk, A.: Solving vehicle routing problem using quantum approximate optimization algorithm. IEEE Transactions on Intelligent Transportation Systems (2022)
  * (12) Azzaoui, A., Kim, T.W., Pan, Y., Park, J.H.: A quantum approximate optimization algorithm based on blockchain heuristic approach for scalable and secure smart logistics systems. Human-centric Computing and Information Sciences 11(46), 1–12 (2021)
  * (13) Bayerstadler, A., Becquin, G., Binder, J., Botter, T., Ehm, H., Ehmer, T., Erdmann, M., Gaus, N., Harbach, P., Hess, M., et al.: Industry quantum computing applications. EPJ Quantum Technology 8(1), 25 (2021)
  * (14) Benson, B.M., Ingman, V.M., Agarwal, A., Keinan, S.: A CQM-based approach to solving a combinatorial problem with applications in drug design. arXiv preprint arXiv:2303.15419 (2023)
  * (15) Bentley, C.D., Marsh, S., Carvalho, A.R., Kilby, P., Biercuk, M.J.: Quantum computing for transport optimization. arXiv preprint arXiv:2206.07313 (2022)
  * (16) Bontekoe, T., Phillipson, F., Van der Schoot, W.: Translating constraints into QUBOs for the quadratic knapsack problem. In: International Conference on Computational Science. pp. 90–107. Springer (2023)
  * (17) Borowski, M., Gora, P., Karnas, K., Błajda, M., Król, K., Matyjasek, A., Burczyk, D., Szewczyk, M., Kutwin, M.: New hybrid quantum annealing algorithms for solving vehicle routing problem. In: International Conference on Computational Science. pp. 546–561. Springer (2020)
  * (18) Bourreau, E., Fleury, G., Lacomme, P.: Indirect quantum approximate optimization algorithms: application to the tsp. arXiv preprint arXiv:2311.03294 (2023)
  * (19) Van den Brink, R., Phillipson, F., Neumann, N.M.: Vision on next level quantum software tooling. Computation Tools (2019)
  * (20) Brouer, B.D., Karsten, C.V., Pisinger, D.: Optimization in liner shipping. Annals of Operations Research 271, 205–236 (2018)
  * (21) Brucker, P., Jurisch, B., Sievers, B.: A branch and bound algorithm for the job-shop scheduling problem. Discrete applied mathematics 49(1-3), 107–127 (1994)
  * (22) Cao, Y., Romero, J., Olson, J.P., Degroote, M., Johnson, P.D., Kieferová, M., Kivlichan, I.D., Menke, T., Peropadre, B., Sawaya, N.P.D., Sim, S., Veis, L., Aspuru-Guzik, A.: Quantum chemistry in the age of quantum computing. Chemical Reviews 119(19), 10856–10915 (2019). https://doi.org/10.1021/acs.chemrev.8b00803, pMID: 31469277
  * (23) Carugno, C., Ferrari Dacrema, M., Cremonesi, P.: Evaluating the job shop scheduling problem on a D-Wave quantum annealer. Scientific Reports 12(1), 6539 (2022)
  * (24) de Castro Moura, A.J.F.: Evolutionary Computation methods applied to Operational Control Centers. Master’s thesis, University of Porto (2015)
  * (25) Cellini, L., Macaluso, A., Lombardi, M.: QAL-BP: An augmented lagrangian quantum approach for bin packing problem. arXiv preprint arXiv:2309.12678 (2023)
  * (26) Chibeles-Martins, N., Pinto-Varela, T., Barbósa-Póvoa, A.P., Novais, A.: A simulated annealing algorithm for the design and planning of supply chains with economic and environmental objectives. In: Computer Aided Chemical Engineering, vol. 30, pp. 21–25. Elsevier (2012)
  * (27) Choo, J.: Investigating the feasibility of solving the quadratic assignment problem using quantum computing. Master’s thesis, University of London (2015)
  * (28) Correll, R., Weinberg, S.J., Sanches, F., Ide, T., Suzuki, T.: Quantum neural networks for a supply chain logistics application. Advanced Quantum Technologies 6(7), 2200183 (2023)
  * (29) Crispin, A., Syrichas, A.: Quantum annealing algorithm for vehicle scheduling. In: 2013 IEEE International Conference on Systems, Man, and Cybernetics. pp. 3523–3528. IEEE (2013)
  * (30) van Dam, W., Eldefrawy, K., Genise, N., Parham, N.: Quantum optimization heuristics with an application to knapsack problems. In: 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). pp. 160–170. IEEE (2021)
  * (31) De Juncker, M.A., Huizing, D., del Vecchyo, M.O., Phillipson, F., Sangers, A.: Framework of synchromodal transportation problems. In: Computational Logistics: 8th International Conference, ICCL 2017, Southampton, UK, October 18-20, 2017, Proceedings 8. pp. 383–403. Springer (2017)
  * (32) Denkena, B., Schinkel, F., Pirnay, J., Wilmsmeier, S.: Quantum algorithms for process parallel flexible job shop scheduling. CIRP Journal of Manufacturing Science and Technology 33, 100–114 (2021)
  * (33) Ding, Y., Chen, X., Lamata, L., Solano, E., Sanz, M.: Logistic network design with a D-Wave quantum annealer. arXiv preprint arXiv:1906.10074 (2019)
  * (34) Ding, Y., Chen, X., Lamata, L., Solano, E., Sanz, M.: Implementation of a hybrid classical-quantum annealing algorithm for logistic network design. SN Computer Science 2, 1–9 (2021)
  * (35) Dixit, V.V., Niu, C.: Quantum computing for transport network design problems. Scientific Reports 13(1), 12267 (2023)
  * (36) Dixit, V.V., Niu, C., Rey, D., Waller, S.T., Levin, M.W.: Quantum computing to solve scenario-based stochastic time-dependent shortest path routing. Transportation Letters pp. 1–11 (2023)
  * (37) Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)
  * (38) Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106 (2000)
  * (39) Feld, S., Roch, C., Gabor, T., Seidel, C., Neukart, F., Galter, I., Mauerer, W., Linnhoff-Popien, C.: A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Frontiers in ICT 6, 13 (2019)
  * (40) Fitzek, D., Ghandriz, T., Laine, L., Granath, M., Kockum, A.F.: Applying quantum approximate optimization to the heterogeneous vehicle routing problem. arXiv preprint arXiv:2110.06799 (2021)
  * (41) Gabbassov, E.: Transit facility allocation: Hybrid quantum-classical optimization. Plos one 17(9), e0274632 (2022)
  * (42) Giraldo-Quintero, A., Lalinde-Pulido, J.G., Duque, J.C., Sierra-Sosa, D.: Using quantum computing to solve the maximal covering location problem. Computational Urban Science 2(1), 43 (2022)
  * (43) Glover, F., Kochenberger, G., Du, Y.: Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models. 4or 17, 335–371 (2019)
  * (44) Glover, F., Lewis, M., Kochenberger, G.: Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems. European Journal of Operational Research 265(3), 829–842 (2018)
  * (45) Grover, L.K.: A Fast Quantum Mechanical Algorithm for Database Search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. p. 212–219. STOC ’96, Association for Computing Machinery, New York, NY, USA (1996)
  * (46) Guo, M., Wang, S.: Quantum computing for solving spatial optimization problems. High Performance Computing for Geospatial Applications pp. 97–113 (2020)
  * (47) Harikrishnakumar, R., Nannapaneni, S., Nguyen, N.H., Steck, J.E., Behrman, E.C.: A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem. arXiv preprint arXiv:2005.12478 (2020)
  * (48) Harwood, S., Gambella, C., Trenev, D., Simonetto, A., Bernal, D., Greenberg, D.: Formulating and solving routing problems on quantum computers. IEEE Transactions on Quantum Engineering 2, 1–17 (2021)
  * (49) Hernández, F., Díaz, K., Forets, M., Sotelo, R.: Application of quantum optimization techniques (QUBO method) to cargo logistics on ships and airplanes. In: 2020 IEEE Congreso Bienal de Argentina (ARGENCON). pp. 1–1. IEEE (2020)
  * (50) Huang, J., Fan, H.T., Xiao, G., Chang, Q.: Paint shop vehicle sequencing based on quantum computing considering color changeover and painting quality. arXiv preprint arXiv:2206.11204 (2022)
  * (51) Irie, H., Wongpaisarnsin, G., Terabe, M., Miki, A., Taguchi, S.: Quantum annealing of vehicle routing problem with time, state and capacity. In: Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1. pp. 145–156. Springer (2019)
  * (52) Jaderberg, B.: Solving optimisation problems on near-term quantum computers. Ph.D. thesis, University of Oxford (2022)
  * (53) Jahin, M.A., Shovon, M.S.H., Islam, M.S., Shin, J., Mridha, M., Okuyama, Y.: Qamplifynet: pushing the boundaries of supply chain backorder prediction using interpretable hybrid quantum-classical neural network. Scientific Reports 13(1), 18246 (2023)
  * (54) Jiang, D., Liu, X., Song, H., Xie, H.: An survey: Quantum phase estimation algorithms. In: 2021 IEEE 5th Information Technology, Networking, Electronic and Automation Control Conference (ITNEC). vol. 5, pp. 884–888. IEEE (2021)
  * (55) Jiang, H., Shen, Z.J.M., Liu, J.: Quantum computing methods for supply chain management. In: 2022 IEEE/ACM 7th Symposium on Edge Computing (SEC). pp. 400–405. IEEE (2022)
  * (56) Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Physical Review E 58(5), 5355 (1998)
  * (57) Khumalo, M.T., Chieza, H.A., Prag, K., Woolway, M.: An investigation of IBM quantum computing device performance on combinatorial optimisation problems. Neural Computing and Applications pp. 1–16 (2022)
  * (58) Klar, M., Schworm, P., Wu, X., Glatt, M., Aurich, J.C.: Quantum annealing based factory layout planning. Manufacturing Letters 32, 59–62 (2022)
  * (59) Koch, D., Wessing, L., Alsing, P.M.: Introduction to coding quantum algorithms: A tutorial series using pyquil. arXiv preprint arXiv:1903.05195 (2019)
  * (60) Kurowski, K., Weglarz, J., Subocz, M., Różycki, R., Waligóra, G.: Hybrid quantum annealing heuristic method for solving job shop scheduling problem. In: Computational Science–ICCS 2020: 20th International Conference, Amsterdam, The Netherlands, June 3–5, 2020, Proceedings, Part VI 20. pp. 502–515. Springer (2020)
  * (61) Le, T.V., Nguyen, M.V., Khandavilli, S., Dinh, T.N., Nguyen, T.N.: Quantum annealing approach for selective traveling salesman problem. In: ICC 2023-IEEE International Conference on Communications. pp. 2686–2691. IEEE (2023)
  * (62) Leonidas, I.D., Dukakis, A., Tan, B., Angelakis, D.G.: Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors. arXiv preprint arXiv:2306.08507 (2023)
  * (63) Lo, S.C., Shih, Y.C.: A genetic algorithm with quantum random number generator for solving the pollution-routing problem in sustainable logistics management. Sustainability 13(15), 8381 (2021)
  * (64) Mahasinghe, A., Fernando, V., Samarawickrama, P.: QUBO formulations of three NP problems. Journal of Information and Optimization Sciences 42(7), 1625–1648 (2021)
  * (65) Makhanov, H., Setia, K., Liu, J., Gomez-Gonzalez, V., Jenaro-Rabadan, G.: Quantum computing applications for flight trajectory optimization. arXiv preprint arXiv:2304.14445 (2023)
  * (66) Malviya, G., AkashNarayanan, B., Seshadri, J.: Logistics network optimization using quantum annealing. In: International Conference on Emerging Trends and Technologies on Intelligent Systems. pp. 401–413. Springer (2023)
  * (67) Marsoit, P.T., Zhang, L.W., Lakonde, D., Panjaitan, F.S.: Quantum computing approach in uncertain data optimization problem for vehicle routing problem. International Journal of Enterprise Modelling 15(3), 187–198 (2021)
  * (68) Martin, P., Shmoys, D.B.: A new approach to computing optimal schedules for the job-shop scheduling problem. In: International Conference on Integer Programming and Combinatorial Optimization. pp. 389–403. Springer (1996)
  * (69) Martins, L.N.: Applying quantum annealing to the tail assignment problem. Ph.D. thesis, University of Porto (2020)
  * (70) Masuda, K., Tsuyumine, Y., Kitada, T., Hachikawa, T., Haga, T.: Optimization of delivery plan by quantum computing. Optimization 85, 1 (2023)
  * (71) Mohammadbagherpoor, H., Dreher, P., Ibrahim, M., Oh, Y.H., Hall, J., Stone, R.E., Stojkovic, M.: Exploring airline gate-scheduling optimization using quantum computers. arXiv preprint arXiv:2111.09472 (2021)
  * (72) Mohanty, N., Behera, B.K., Ferrie, C.: Analysis of the vehicle routing problem solved via hybrid quantum algorithms in the presence of noisy channels. IEEE Transactions on Quantum Engineering (2023)
  * (73) Mori, A.M.: Replanning Flight Schedules Using Quantum Computing. Master’s thesis, University of Porto (2022)