# Solving a Real-World Package Delivery Routing Problem Using Quantum
Annealers

Eneko Osaba  TECNALIA, Basque Research and Technology Alliance (BRTA), 48160
Derio, Spain<EMAIL_ADDRESS>0000-0001-7863-9910 Esther Villar-
Rodriguez  TECNALIA, Basque Research and Technology Alliance (BRTA), 48160
Derio, Spain  0000-0003-3343-3737 Antón Asla  Serikat - Consultoría y
Servicios Tecnológicos, 48009 Bilbao, Spain.

###### Abstract

Research focused on the conjunction between quantum computing and routing
problems has been very prolific in recent years. Most of the works revolve
around classical problems such as the Traveling Salesman Problem or the
Vehicle Routing Problem. Even though working on these problems is valuable, it
is also undeniable that their academic-oriented nature falls short of real-
world requirements. The main objective of this research is to present a
solving method for realistic instances, avoiding problem relaxations or
technical shortcuts. Instead, a quantum-classical hybrid solver has been
developed, coined Q4RPD, that considers a set of real constraints such as a
heterogeneous fleet of vehicles, priority deliveries, and capacities
characterized by two values: weight and dimensions of the packages. Q4RPD
resorts to the Leap Constrained Quadratic Model Hybrid Solver of D-Wave. To
demonstrate the application of Q4RPD, an experimentation composed of six
different instances has been conducted, aiming to serve as illustrative
examples.

###### keywords:

Routing Problem, Package Delivery, Logistics, Optimization, Quantum Computing,
Quantum Annealer, D-Wave

## Introduction

Introduction

Routing problems are extensively studied in the fields of transportation and
optimization [1, 2, 3]. The interest in this particular topic stems from two
main factors [4]: their high computational complexity, which makes them
challenging to address [5]; and their broad applicability scenarios [6]. Put
another way, improvements in the creation of effective routing algorithms have
positive effects on society and industry.

In this regard, it is crucial to emphasize that the majority of the algorithms
used to solve such problems require a significant amount of processing power.
In fact, for even relatively modest instances, many current computers are
incapable of running brute force methods. As a result, throughout the past few
decades, numerous time-efficient solving schemes have been proposed, with
heuristic and metaheuristic procedures being the most commonly used.

Most solvers developed so far have been designed with the intention of being
run on conventional computing resources. Quantum computing (QC [7]) has
nevertheless become a promising paradigm as an alternative to these
traditional devices for handling optimization and routing problems. Even
though it is not a mature technology, QC has gathered a lot of attention from
the scientific community as it offers researchers and practitioners a
revolutionary paradigm for tackling different kinds of practical optimization
problems [8, 9]. Specifically, a large range of problems coming from domains
such as healthcare [10], economics [11], industry [12], energy [13], or
logistics [14] have benefited from QC lately.

Research oriented towards routing problems solved by QC approaches has been
very prolific in recent years, with the Traveling Salesman Problem (TSP[15])
and Vehicle Routing Problem (VRP[16]) being the most studied cases. Specially
interesting for this analysis is the extensive review published by Osaba et.
al.[14], stating that this new paradigm has motivated 53 research publications
up to 2022. As concluded by the authors of that study, “it is noticeable that
the TSP engages most of the researchers (60,37% - 32 out of 53 papers), while
the VRP amounts to the 25,52% of the contributions (13 out of 53). The rest of
the papers deal with other routing problems, such as the Shortest Path Problem
or the Hamiltonian Cycle”. The trend follows a similar path with TSP [17, 18,
19, 20] and VRP [21, 22, 23, 24] being the problems that account for the vast
majority of the scientific production also in the years after 2022.

Some conclusions can be drawn by analyzing the current related work. On the
one hand, most of the works in the field pursue objectives such as unveiling
the potential of quantum technologies or checking the efficiency of a
particular method. This kind of work uses academic problems such as the TSP or
VRP for benchmarking purposes. On the other hand, several studies can be found
in the literature that present advances in the application of QC to real-
world-oriented routing problems, analyzing aspects such as traffic
congestion[25]. This second category of research focuses on getting the most
out of the current NISQ-era devices by implementing efficient and advanced
hybrid resolution methods [26].

In this context, the study of Weinberg et al. in 2023 [27] could be referred
to as the closest to solving a real routing problem using QC. The authors
elaborate on the multi-truck vehicle routing for supply chain logistics. Being
unable to solve the problem using a fully embedded approach, the authors
propose an algorithm that iteratively assigns routes to trucks. This
philosophy, which is also used in this research, allows the authors of that
work to consider restrictions such as pick-up and drop-off demands and
restricted driving windows.

The primary motivation of this research is to define a resolution method
capable of providing a good, if not the best, solution to a real-world problem
by making intelligent use of the capabilities offered by current quantum
devices. By maintaining all the characteristics and restrictions of the
original problem, it is “too complex to be fully embedded on any near-term
quantum hardware or simulator” [27]. For this reason, a hybrid workflow is
utilized, with routes iteratively assigned to trucks that comply with all the
existing restrictions. The solver implemented, which has been named as Quantum
for Real Package Delivery (Q4RPD), combines both quantum and classical
computing as follows:

  * •

QC is applied to the calculation of each route to be integrated into the
complete solution. To build each of the routes, Q4RPD resorts to the Leap
Constrained Quadratic Model (CQM) Hybrid Solver (LeapCQMHybrid[28]) of D-Wave.
This device natively solves problems formulated as CQM, which refers to a
specific mathematical model defined by integer, real, and binary variables,
allowing the specification of linear and quadratic constraints and using a
quadratic objective function[28]. Also, CQM permits the definition of
inequality and equality restrictions. All these characteristics introduce an
advantage compared to the native formulation for the Quantum Processing Units
(QPUs), which is the Quadratic Unconstrained Binary Optimization (QUBO). Thus,
instead of requiring to translate a problem into a QUBO, both CQM and the
LeapCQMHybrid suppose a more user-friendly utilization of the quantum
resources.

  * •

Classical computing is used to manage the general workflow of Q4RPD, and to
conduct procedures such as intelligent allocation of resources and the merging
of subsolutions provided by the quantum device.

Finally, to demonstrate the application of Q4RPD, an experimentation with six
different instances has been conducted, aiming to serve as illustrative
examples.

The rest of the article is organized as follows: in the following section, the
Problem Definition is introduced. After that, in Solving scheme and
Fundamentals, the characteristics of the method implemented are described.
After that, in Single Routing Problem: Mathematical formulation, the
formulation of the problem addressed by the quantum device is presented. In
Experimental results, the applicability of the implemented system is
demonstrated employing a set of instances as input. Conclusions and future
work closes this paper by highlighting the main conclusions drawn from the
results obtained in the experimentation and the planned future work.

## Problem Definition

Problem Definition

First, it is noteworthy that the problem and its characteristics have been
defined by a Spanish company specializing in transport and logistics, named
Ertransit111https://www.ertransit.com.cn/ertransit-espana/. After conducting
several meetings among Ertransit and the research team, a set of real needs
were established, which have guided the developments detailed in this paper.

Having said that, the problem can be defined as follows: given a set of last-
mile deliveries to complete within the day (whose fulfillment in the daily
time-span is feasible), a depot, and a fleet of heterogeneous and available
owned and rental trucks, the main objective is to calculate a set of routes
that satisfy all of the predetermined demands while minimizing the total
costs. Exceptionally, a customer may have more than one order.

For this purpose, a route is defined as

> a trajectory associated with a single truck (driven by a designated single
> driver) that completes a group of deliveries and must start and end at the
> depot.

Furthermore, in this work, the total cost of a solution is the total distance
of the planned routes and the prices associated with the use of the truck. In
relation to the latter, if the truck is owned by Ertransit the cost is 0.
Otherwise, the use of rental vehicles incurs a cost for the service provided.

Additionally, the problem is subject to the following constraints:

  * •

R1: the capacity of each truck is measured in terms of weight (kgs) and
dimension ($cm^{3}$) which limits the load to be carried on each route. At the
same time, the deliveries to be distributed are also defined by these
parameters. We can say, thus, that the representation of the capacities is
two-dimensional.

  * •

R2: some of the packages must be delivered within a certain time frame
(priorities). These deliveries are labeled with a Top-Priority (TP) tag.

  * •

R3: the duration of a route must be less than the driver’s working day (which
is the same for all the available workers).

In this research, and for the sake of simplicity, distance and time of travel
share the same value. Lastly, the following business preferences are defined,
drawn from past real-world situations faced by Ertransit that became, over the
years, the operating protocol. Note that the preference order in the list
relates to their relevance (if two preferences clash, the one with the higher
ranking must prevail):

  * •

P1: a vehicle can only complete one route, meaning that the trucks cannot be
reused on that day, whether or not this decision has an impact on cost.

  * •

P2: the use of owned trucks must be prioritized, even if this implies a higher
overall cost in terms of distance. The motivation for this preference is
twofold: on the one hand, to avoid the transactions associated with renting a
vehicle, and on the other hand, to minimize the possibility of having an
accident with a non-company truck.

  * •

P3: preferential treatment must be given to solutions that use fewer vehicles,
even if this implies a higher overall cost in terms of the distance. The
purpose of this preference is to have as many trucks as possible in the depot
in order to handle potential incidents or unplanned extra-routine situations.

In light of this, this problem has been named 2-Dimensional and Heterogeneous
Package Delivery with Priorities (2DH-PDP).

## Solving scheme and Fundamentals

Solving scheme and Fundamentals

First of all, we introduce the different kinds of (sub-)routes that may be
calculated according to their origin and destination. This categorization is
the result of the hard-restrictions imposed by the TP deliveries. The
differentiated management of these TP-related types of routes makes it
impossible to violate this restriction, resulting in the subsequent generation
of an unfeasible solution for Ertransit:

Figure 1: A graphical step-by-step resolution of an instance composed of 14
different deliveries (D14_P1), being one of them a TP (surrounded by a red
circle).

  * •

Regular route: this is a route, completed by a single truck, that starts and
ends at the depot. A regular route route can be seen in STEP-4 of Fig.1.

  * •

Depot-TP sub-route: this is a sub-route that starts at the depot and finishes
at the location of a TP delivery. The main requirement for this kind of sub-
route is to arrive at the destination prior to its scheduled time. An example
of a Depot-TP sub-route is represented in STEP-1 of Fig.1.

  * •

TP-TP sub-route: in this kind of sub-route, both the origin and destination
correspond to the locations of different TP deliveries.

  * •

TP-Depot sub-route: this is a sub-route which origin and destination are a TP
delivery location and the depot, respectively. An instance of a TP-Depot sub-
route sub-route is depicted in STEP-2 of Fig.1.

Figure 2: General workflow of Q4RPD.

Focusing on the Q4RPD solving scheme, as previously mentioned, it is based on
an iterative process that, at each iteration, (1) picks a truck out and (2)
calculates one route or sub-route. Fig.2 represents the general workflow of
Q4RPD. Having said that, and before starting the iterative process, Q4RPD
begins its execution with a pair of sorting heuristics:

  * •

Vehicle ordering heuristic: once the data for the problem is introduced, Q4RPD
starts by gathering information about the available trucks. To satisfy
preference P2 introduced in Problem Definition, vehicles are ordered and hence
served by the following criterion: owned trucks, sorted by their global
capacity, first; and rental trucks, ordered by their capacity, second.

  * •

Delivery ordering heuristic: the hard constraint R2 listed in Problem
Definition, which regards TP deliveries, is managed by this procedure in
charge of forcing the treatment of the restrictive deliveries first. It
involves sorting all the deliveries according to their scheduled time (if
any), i.e., the one with the earliest scheduled time at the top of the list.

From this initialization onwards, an iterative solving scheme is in charge of
partially solving the problem via a three-step procedure until the complete
set of deliveries is satisfied:

  1. S1.

Routing problem setup. This first step, which is executed using classical
computing, is devoted to preparing the problem instance for being subsequently
solved by the quantum device. This setup consists of the following methods:

     * •

Vehicle selection. Q4RPD starts an iteration by selecting an available truck
in order to calculate its most optimized route. If there is a sub-route to be
completed with an active truck already in use, this vehicle is chosen,
prioritizing the completeness of an unfinished route (i.e., a route without
the depot as its destination).

Figure 3: (Sub-)route selection procedure with the 4 scenarios.

     * •

(Sub-)route selection: four different scenarios, summarized in Fig.3, may
arise:

       1. (A)

If there is a half-completed sub-route and still prioritized deliveries to
attend, Q4RPD checks if further TP deliveries are still reachable. If
positive, a TP-TP should be calculated. Otherwise, a TP-Depot sub-route to
complete the trajectory will be the target (B in Fig.3). A TP delivery is
reachable if:

          * –

The active truck‘s capacity is enough to serve the new demand, i.e., R1 is
satisfied.

          * –

The active truck can arrive on time to both this intermediate destination and
the depot, and the driver´s working day will not be exceeded in completing the
whole route, i.e., the R2 and R3 constraints remain satisfiable after
accepting this new sub-route.

       2. (B)

If the selected vehicle has any sub-route already assigned and no TP remains
to be attended, a TP-Depot sub-route to complete the trajectory will be built.

       3. (C)

If there is no half-completed route but there are still TP deliveries to
complete, Q4RPD takes the first element out of the prioritized deliveries
queue to calculate a Depot-TP sub-route.

       4. (D)

If none of the previous conditions are met, a regular route will be
calculated.

It should be noted that, in the end, each complete route will be a regular and
cyclic path composed of a single regular route or a set of sub-routes.

     * •

Upperbound parameters update: due to the existence of sub-routes, the
upperbound parameters (summarized in Table 1) cannot be fixed in the problem
initialization but must be set at each iteration.

       * –

Maximum duration assignment: the $rt$ of the new (sub-)route is calculated,
embracing this criterion:

         1. (A)

For a TP-TP sub-route, with reachability already confirmed, $rt$ is calculated
as the difference between the destination’s TP scheduled time and the time
already spent since the beginning of the route, i.e., from the depot.

         2. (B)

For a TP-Depot route, $rt$ is the difference between the driver’s working day
and the time already spent since the beginning of the route.

         3. (C)

For a Depot-TP route, $rt$ is equal to the TP scheduled time.

         4. (D)

For a regular route, $rt$ is equal to the driver’s working day.

       * –

Usable truck capacity: if the truck is already in use, its capacities $W$ and
$D$ must be updated by deducting the load already assigned to the truck in
previous sub-routes from the vehicle’s tare and dimension specification.

Upperbound Parameters |
---|---
$rt$ |  the maximum possible duration of a (sub-)route.
$W,D$ |  maximum weight and dimension allowed for the (sub-)route.
Table 1: Upperbound parameters used in the formulation.

     * •

CQM problem formulation: since the employed LeapCQMHybrid natively solves
problems modeled as CQM, the last step of this classical phase is to build a
CQM with all the parameters above detailed, and following the formulation
described in the following section (Single Routing Problem: Mathematical
formulation).

  2. S2.

CQM problem resolution: after the CQM is built, this second step consists of
the resolution of this CQM through D-Wave’s LeapCQMHybrid. As pointed out
before, the problem faced can refer to any of the routes and sub-routes above
defined. It is in this step that the use of quantum computing is resorted to.

  3. S3.

Partial solutions storage: this last step, executed using classical computing,
is devoted to updating the whole problem. Two procedures engage in this phase:

     * •

Route storage with a previous concatenation of Depot-TP, TP-TP or TP-Depot
sub-routes, if applicable.

     * •

Update the list of pending deliveries, removing all the demands addressed in
the last solved (sub-)route.

## Single Routing Problem: Mathematical formulation

Single Routing Problem: Mathematical formulation

This section introduces the mathematical formulation of the problem addressed
by the LeapCQMHybrid, defined after the routing problem setup where the type
of route to calculate and the vehicle were determined by the Vehicle ordering
heuristic (Step S1 in Fig.2). As explained before and accordingly, the problem
faced by the quantum device at each iteration is not the complete 2DH-PDP, but
the calculation of a single (sub-)route of any of the types listed in Solving
scheme and Fundamentals. For this reason, this sub-problem has been coined the
Single Routing Problem (SRP) whose variables and parameters are displayed in
Table 2.

Upperbound Parameters |
---|---
$rt$ |  the maximum possible duration of a (sub-)route.
$W,D$ |  maximum weight and dimension allowed for the (sub-)route.
Static Parameters |
P |  set of deliveries.
$M$ |  number of deliveries.
$w_{i},d_{i}$ |  weight and dimension of delivery $i\in$ P.
$t_{i}$ |  the time limit for delivery $i$.
$c_{i,j}$, $d_{i,j}$ |  travel time and distance associated to going from the location of delivery $i$ to the location of delivery $j$.
Variables |
$x_{i,p}$ |  binary variable that represents if the location of delivery $i$ is visited at position $p$ of the (sub-)route, with $p\in[0,M]$.
Table 2: The complete set of parameters and variables used in our formulation.

### Codification and variables

Codification and variables

The binary codification used for the SRP is the one known as node-based, often
used in studies of quantum computing applied to routing problems [27, 29, 30].
A solution to the SRP is represented as a set $X=\\{X_{0},\dots,X_{M}\\}$ of
lists, in which each $X_{i}$ is associated with a single delivery $i$, where
$M$ is the total number of deliveries and 0 represents the origin location.
Furthermore, $X_{i}=\\{x_{i,0},\dots,x_{i,M}\\}$, where $x_{i,p}$ is a binary
variable used for representing the position of the delivery $i$ along the
trajectory. Thus, $x_{i,p}$ is 1 if the location of the delivery $i$ is
visited in position $p$ of the route, and 0 otherwise. A visual example
comprising five delivery locations is represented in Fig.4.

Figure 4: A SRP instance composed of five delivery locations, and a tentative
solution. Delivery location with $ID$=0 represents the starting point of the
route. Delivery location with $ID$=1 represents the destination, that is, the
delivery location that must be reached before a certain restricted time.

So, the challenge when solving SRP is to find the most appropriate values for
variables in $X$ in order to build the route that best optimizes the
established objectives (later described in Objectives).

### Problem initialization

Problem initialization

As part of the problem modeling, a slight initialization procedure is carried
out, which is comprised of two steps:

  * •

Firstly, the two first $X$ components, i.e., $X_{0}$ and $X_{1}$ are reserved
for the preset origin and the preset destination of the (sub-)route,
respectively.

  * •

Secondly, $x_{0,0}$ is set to 1 to assure that the sub-route begins at the
origin. In contrast, $X_{1}$, i.e., the set of variables identifying the
position of the destination in the (sub-)route, cannot be fixed in advance
since, at this stage, we do not know how many deliveries will eventually be
included in the (sub-)route and, therefore, what the last position of the
route will be.

### Objectives

Objectives

The SRP is an optimization problem that must be solved by minimizing a cost
function defined by two different objectives. By multiplying each of these
objectives by an appropriate weight, the user can determine the relevance
given to each of them. Hence, $\min\text{ }\sum_{i=1}^{2}\omega_{i}o_{i}$
represents the cost function, being $\omega_{i}$ the weight given to objective
$o_{i}$. For this specific research, $\omega_{1}$=1 and $\omega_{2}$=2 have
been applied.

  * •

$o_{1}$: minimizing the total distance of the route, which can be
mathematically formulated as follows:

$o_{1}=\min\sum_{i=0}^{M}\sum_{j=0}^{M}d_{i,j}x_{i,p}x_{j,p+1}\quad\forall
p\in\\{0,\dots,M-1\\},i\neq j.$ (1)

  * •

$o_{2}$: visiting the destination location as later as possible in the route,
that is, maximizing the number of deliveries carried out before reaching the
final destination. This objective is materialized by maximizing the value of
$p$ in $x_{1,p}=1$. This objective is formulated as follows:

$o_{2}=\min\sum_{p=0}^{M}(-x_{1,p}-\sum_{p^{\prime}=p}^{M}x_{1,p^{\prime}}).$
(2)

Finally, certain restrictions apply to the aforementioned objectives, which
are essential to solving a real-world-oriented problem. The next subsection
defines the entire pool of constraints (Problem constraints).

### Problem constraints

Problem constraints The above-described objectives are subjected to a set of
seven different restrictions, which are:

  * •

Delivery-consistency: a delivery may not be on the route or, if it is, at most
once.

$\sum_{p=0}^{M}x_{i,p}\leq 1\quad\forall i\in\\{0,\dots,M\\}.$ (3)

  * •

Location-consistency: each time slot of a truck schedule can be assigned to a
single order at most.

$\sum_{i=0}^{M}x_{i,p}\leq 1\quad\forall p\in\\{0,\dots,M\\}.$ (4)

  * •

Delivery-consecutiveness: a correct calculation of objectives $o_{1}$ and
$o_{2}$ requires that the deliveries served in the (sub-) route be
consecutive, which means that there must be as many consecutive zeros from
right to left in each $X_{0},X_{1},...X_{M}$ as there are surplus positions
$p$.

$\sum_{i=0}^{M}x_{i,p}-\sum_{i=0}^{M}x_{i,p+1}\geq 0\quad\forall
p\in\\{0,\dots,M-1\\}.$ (5)

  * •

Destination-inclusion: the destination must be in the route.

$\sum_{p=0}^{M}x_{1,p}=1.$ (6)

  * •

Time-restriction: the duration of the route must not be longer than $rt$, that
is, the maximum possible duration of the route.

$\sum_{i=0}^{M}\sum_{j=0}^{M}c_{i,j}x_{i,p}x_{j,p+1}\leq rt\quad\forall
p\in\\{0,\dots,M-1\\},i\neq j.$ (7)

Note that, as aforementioned, in practice $c_{i,j}=d_{i,j}$.

  * •

Weight-restriction: the maximum allowed weight $W$ for the truck must not be
surpassed.

$\sum_{p=0}^{M}x_{i,p}w_{i}\leq W\quad\forall i\in\\{0,\dots,M\\}.,$ (8)

  * •

Dimension-restriction: the maximum permitted dimension $D$ for the route must
not be exceeded.

$\sum_{p=0}^{M}x_{i,p}d_{i}\leq D\quad\forall i\in\\{0,\dots,M\\}.$ (9)

## Experimental results

Experimental results

This section is devoted to analyzing the performance of Q4RPD. First, in
Quantum solver details, some details on the LeapCQMHybrid are provided. After
that, in Benchmark description, the data employed in the experimentation is
introduced. This section finishes in Performance analysis by showing the
obtained results and analyzing the performance of Q4RPD for the proposed
benchmark.

### Quantum solver details

Quantum solver details The QUBO solver used in this paper is the CQM model of
LeapCQMHybrid, implemented by D-Wave System. The LeapCQMHybrid workflow,
depicted in Fig. 5, applies parallel processing to the search for solutions to
eventually return the best solution found among the pool of threads. Each
thread consists of:

  * •

a classical heuristic module (CH) with cutting-edge heuristic methods
primarily aimed at solving the problem.

  * •

and a quantum module (QM) in charge of guiding HM into promising areas of the
search space and improving already-existing solutions by means of quantum
queries.

Figure 5: General scheme of LeapCQMHybrid solver. CH = Classical Heuristic
Module. QM = Quantum Module.

In this research, the quantum queries have been run on the Advantage_system6.4
architecture, which is the most recent at the time that this work was written.
This computer features 5616 qubits, arranged in a Pegasus topology. Regarding
the parameterization of the LeapCQMHybrid solver, the only configurable
parameter time_limit was set to the default value for each instance. For
additional details on LeapCQMHybrid, we refer to interested readers to the
D-Wave report [31].

### Benchmark description

Benchmark description With regard to the benchmark of Q4RPD, it is composed of
six different instances whose characteristics are summarized in Table 3. Each
instance is named DX_PY, where X represents the size of the problem in terms
of the number of deliveries and Y the amount of TP deliveries. The following
information per instance is also provided in Table 3: the number of owned and
rental trucks that compose the fleet of vehicles; and the number of variables
and constraints involved in the global problem formulation.

The characteristics of each instance and the main motivations for their
selection for benchmarking purposes are as follows:

  * •

D14_P1: this is the smallest scenario which is composed of 13 non-priority and
one priority delivery. The solution to D14_P1 can be seen in in Fig. 1.

  * •

D16_P1: the main difference between this case and the previous one is the use
of a drastically reduced working day (90 minutes) to push Q4RPD into a
narrower feasible solution space since in D14_P1 the length of the routes is
mostly restricted by the vehicle’s capacity. The resolution process of this
instance is shown in Fig. 6.

  * •

D14_P2 and D21_P2: the main characteristic of these scenarios is the existence
of two priority deliveries that are not reachable on the same route. In
addition, D14_P2 has two orders from the same customer, which must be served
by two distinct trucks to satisfy the restrictions while minimizing the
objective function. D21_P2, in turn, is the most demanding instance in terms
of quantum resources employed. The solutions to D14_P2 and D21_P2 are depicted
in Fig. 7 and Fig. 8, respectively.

  * •

D21_P0 and D29_P0: these instances are characterized by being fully composed
of non-priority deliveries, and their solutions are depicted in Fig. 9 and
Fig. 10. Regarding D29_P0, this instance unveils the potential of Q4RPD to
solve large and complex scenarios. In fact, this is the use case with the most
paths to be calculated.

Instance |  Fleet Description | #Variables | #Constraints
---|---|---|---
D14_P1 | 2o,3r | 420 | 111
D16_P1 | 0o,4r | 631 | 157
D14_P2 | 2o,3r | 398 | 124
D21_P2 | 3o,2r | 834 | 209
D21_P0 | 2o,2r | 702 | 138
D29_P0 | 0o,4r | 1602 | 232
Table 3: Characteristics of the six instances. The fleet is represented using Xo,Yr format, where X and Y are the number of owned and rental trucks, respectively. Instance | Problem solution | Validation | Objectives of the SRP
---|---|---|---
#Full routes |  #(Sub-)routes | R1 | R2 | R3 | $\sum o_{1}$ |  $o_{2}$ fulfillment
D14_P1 | Fig. 1 | 2 | [1,1,0,1] | $\checkmark$ | $\checkmark$ | $\checkmark$ | 210.43 (+ 4.3%) | $\checkmark$
D16_P1 | Fig. 6 | 3 | [2,1,0,1] | $\checkmark$ | $\checkmark$ | $\checkmark$ | 223.74 (+0.0%) | $\checkmark$
D14_P2 | Fig. 7 | 2 | [0,2,0,2] | $\checkmark$ | $\checkmark$ | $\checkmark$ | 245.30 (+ 6.3%) | $\checkmark$
D21_P2 | Fig. 8 | 3 | [1,2,0,2] | $\checkmark$ | $\checkmark$ | $\checkmark$ | 309.99 (+3.5%) | $\checkmark$
D21_P0 | Fig. 9 | 3 | [3,0,0,0] | $\checkmark$ | $-$ | $\checkmark$ | 381.46 (+0.0%) | $\checkmark$
D29_P0 | Fig. 10 | 4 | [4,0,0,0] | $\checkmark$ | $-$ | $\checkmark$ | 562.11 (+0.0%) | $\checkmark$
Table 4: Summary of the results obtained by Q4RPD. Number of (sub-)routes is
represented as [A,B,C,D] where A=regular routes; B: Depot-TP sub-routes; C:
TP-TP sub-routes and D: TP-Depot sub-routes. In Validation
section:$\checkmark$=restriction fulfilled; $\times$=restriction broken; and
$-$: constraint not present in the instance. In Objectives of the SRP section:
value in brackets represent the distance difference of the sums of $o_{1}$
when using our solver Q4RPD from the optimal result found by Google OR-Tools;
while $\checkmark$ in last column represents the optimality in all the $o_{2}$
computed. Figure 6: Step-by-step resolution of D16_P1, consisting of non-
priority 15 deliveries and one priority demand (surrounded by a red circle).
Also, two non-priority demands belong to the same client (surrounded by a
green circle), which are served by the same truck. Figure 7: Step-by-step
resolution of D14_P2, composed non-priority 12 deliveries and two priority
demands (surrounded by a red circle). Also, two non-priority demands
correspond to the same client (surrounded by a green circle), which must be
served separately. Figure 8: Step-by-step resolution of D21_P2, with 19 non-
priority deliveries and two priority ones (surrounded by a red circle). Figure
9: Step-by-step resolution of D21_P0, composed of non-priority 21 deliveries.
Figure 10: Step-by-step resolution of D29_P0, composed of no-priority 29
deliveries.

### Performance analysis

Performance analysis With respect to the Q4RPD performance, it is important to
mention that the stage S1 (described in Problem Definition) involved in the
pre-selection of the (sub-)route and truck reduces the search space and
therefore may affect the global performance of the solver. This means that by
attending to the business preferences indicated by Ertransit, the heuristics
may hinder or even prevent the optimal solution from being reached.
Nevertheless, this stage must be computed in advance to fix the upperbound
parameters that complete the mathematical formulation that eventually sets in
motion the (sub-)route construction. In addition, this classical processing
forces the application of the preferences P1 (i.e., one truck for each
complete route) and P2 (i.e., owned trucks have been prioritized to minimize
the cost associated with the rental of trucks.). Lastly, and after the conduct
of this experimentation, we have found that P3 is not always covered by the
currently proposed scheme. Even though this setback only occurs in rare cases,
future versions of the scheme will introduce more intelligent resource
allocation schemes aiming to meet this preference.

Having said this, the Q4RPD performance in relation to the objective function
and constraints for the six instances is summarized in Table 4. Along with the
reference to the figure in which the best-found solution by instance is
represented, the following information can be found in this table divided into
three main blocks:

  * •

Problem solutions: the amount of complete routes that compose the best
solution found by Q4RPD; and the number and type of (sub-)routes of that
solution.

  * •

Validation: in this second section, the 2DH-PDP constraints fulfillment R1
(i.e., respect truck capacities), R2 (i.e., meet time constraints of TP
deliveries), and R3 (i.e., respect the length of the working day) is assessed.

  * •

Objectives of the SRP: concerning the efficiency of the solutions found, and
for comparison purposes, a classic TSP has been selected as the baseline
algorithm to assess the performance of our solution. Concretely, each route
built by Q4RPD is evaluated against a TSP solution obtained through Google OR-
Tools. It is important to note that Google OR-Tools only calculates the
canonical TSP. Our solver Q4RPD, in turn, is forced to meet the TPs schedule
imposed by R1, which causes tweaks in the path that increase the distance but
avoids violating this constraint. Specifically, the sum of all the $o_{1}$
objectives calculated by Q4RPD is displayed with a percentage representing the
difference with respect to the sum of the costs of the solutions obtained by
Google OR-Tools. In addition to that, we also represent in Table 4 if all
$o_{2}$ calculated by Q4RPD have been optimized, i.e., if all the built
(sub-)routes maximize the number of deliveries attended while meeting
restrictions R1 and R3.

Two main conclusions can be drawn from the results. First, Q4RPD has
demonstrated to be a promising solver for dealing with 2DH-PDP. Regarding the
performance of the solver in terms of constraint fulfillment and its
capability to minimize the objective function:

  * •

Q4RPD has emerged as a suitable solver to efficiently deal with the
constraints imposed on the problem, always providing solutions that meet the
imposed restrictions.

  * •

In terms of distance minimization, it can be seen that Q4RPD can compete with
a classical solver such as Google OR-Tools. On the one hand, in cases where
there are no TP deliveries, i.e., D21_P0 and D29_P0, the routes calculated by
Q4RPD have been demonstrated to be the optimal ones. On the other hand, in
those instances with TP deliveries, Q4RPD provide solutions with a deviation
of less than 6.3% in all cases. It should be noted that this deviation in the
objective $o_{1}$ is not attributed to the performance of the routing
algorithm but to the obligation of Q4RPD to comply with the restriction R2. In
fact, in those cases in which Google OR-Tools provides better results in terms
of $o_{1}$, the restriction R2 is not met. All this allows certifying the good
performance of Q4RPD for the scenarios tackled in this research.

Last but not least, the iterative nature of Q4RPD permits solving instances of
a larger size than usually seen in the current NISQ-era literature. While
Q4RPD can efficiently cope with problems such as D29_P0, composed of 30 nodes,
recent studies on routing problems through the QC perspective work with
significantly smaller problems [32, 18, 20, 17, 25, 21]. Finally, for the sake
of replicability, all the instances employed in this experimentation as well
as the detailed outcomes are openly available[33].

## Conclusions and future work

Conclusions and future work

In this paper, a quantum-classical system for solving a real-world logistic
problem is presented, named Quantum for Real Package Delivery (Q4RPD).
Specifically, this system deals with complex routing problems whose
specifications include constraints such as a heterogeneous fleet of vehicles,
priority deliveries, and package description and truck capacity according to
weight and dimensions. For this reason, the problem has been coined as
2-Dimensional and Heterogeneous Package Delivery with Priorities (2DH-PDP). To
demonstrate the applicability, six instances of different sizes and
characteristics have been utilized. Several inspiring challenges and
opportunities have been identified for future work, graphically summarized and
categorized in Fig.11:

  * •

As for the problem definition:

    * –

An extension of the mathematical formulation of 2DH-PDP to include further
real-world situations. Some examples of new features would add more realistic
and/or complex cost calculations with the cost of the node-to-node trip
subject to: a pre-calculated fuel consumption, the likelihood of road
congestion…

    * –

The use of 3D dimensions, i.e., depth, width, and height, to categorize
packages and truck capacities. This line would relate this work to other
branches of research, such as the bin packing problem [34].

    * –

The possibility of reusing the trucks so that they can complete more than one
route.

  * •

As for the future applications:

    * –

The extension of Q4RPD to companies with long-distance deliveries that would
exceed the one-day delivery time.

    * –

Consider other transportation options as possible means of transport, such as
cargo flights or ships.

  * •

With respect to technology and the solving approach:

    * –

The use of complexity reduction mechanisms with the intention of dealing with
larger scenarios in an efficient way by reducing the size of the problem while
maintaining all the constraints of the problem.

    * –

The design and implementation of hybrid methods incorporating another QC
paradigm or technology.

    * –

The development of more configurable solvers that could automatically handle
changes in company preferences or that could easily adapt to other companies
requirements. A very interesting avenue would be to grant the solver the
ability to transform heuristics, i.e., preferences, into constraints or sub-
objectives in the objective function, and the other way around.

Figure 11: A graphical summary of the planned future work.

## Data availability

Data availability

The data used, as well as the results discussed, are available at
http://dx.doi.org/10.17632/yv48pwk96y.1.

## References

  * [1] Kucukoglu, I., Dewil, R. & Cattrysse, D.  The electric vehicle routing problem and its variations: A literature review.  _Computers & Industrial Engineering_ 161, 107650 (2021).
  * [2] Asghari, M., Al-e, S. M. J. M. _et al._ Green vehicle routing problem: A state-of-the-art review.  _International Journal of Production Economics_ 231, 107899 (2021).
  * [3] Konstantakopoulos, G. D., Gayialis, S. P. & Kechagias, E. P.  Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification.  _Operational research_ 1–30 (2020).
  * [4] Osaba, E., Yang, X.-S., Diaz, F., Lopez-Garcia, P. & Carballedo, R.  An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems.  _Engineering Applications of Artificial Intelligence_ 48, 59–71 (2016).
  * [5] Lenstra, J. K. & Kan, A. R.  Complexity of vehicle routing and scheduling problems.  _Networks_ 11, 221–227 (1981).
  * [6] Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D. & Juan, A. A.  Rich vehicle routing problem: Survey.  _ACM Computing Surveys (CSUR)_ 47, 1–28 (2014).
  * [7] Steane, A.  Quantum computing.  _Reports on Progress in Physics_ 61, 117 (1998).
  * [8] Gill, S. S. _et al._ Quantum computing: A taxonomy, systematic review and future directions.  _Software: Practice and Experience_ 52, 66–114 (2022).
  * [9] Yang, Z., Zolanvari, M. & Jain, R.  A survey of important issues in quantum computing and communications.  _IEEE Communications Surveys & Tutorials_ (2023).
  * [10] Ur Rasool, R. _et al._ Quantum computing for healthcare: A review.  _Future Internet_ 15, 94 (2023).
  * [11] Egger, D. J. _et al._ Quantum computing for finance: State-of-the-art and future prospects.  _IEEE Transactions on Quantum Engineering_ 1, 1–24 (2020).
  * [12] V. Romero, S., Osaba, E., Villar-Rodriguez, E., Oregi, I. & Ban, Y.  Hybrid approach for solving real-world bin packing problem instances using quantum annealers.  _Scientific Reports_ 13, 11777 (2023).
  * [13] Ajagekar, A. & You, F.  Quantum computing for energy systems optimization: Challenges and opportunities.  _Energy_ 179, 76–89 (2019).
  * [14] Osaba, E., Villar-Rodriguez, E. & Oregi, I.  A systematic literature review of quantum computing for routing problems.  _IEEE Access_ 10, 55805–55817 (2022).
  * [15] Gutin, G. & Punnen, A. P.  _The traveling salesman problem and its variations_ , vol. 12 (Springer Science & Business Media, 2006).
  * [16] Toth, P. & Vigo, D.  _Vehicle routing: problems, methods, and applications_ (SIAM, 2014).
  * [17] Delgado, I. P., Markaida, B. G., de Leceta, A. M. F. & Uriarte, J. A. O.  Quantum hobbit routing: Annealer implementation of generalized travelling salesperson problem.  _arXiv preprint arXiv:2309.16522_ (2023).
  * [18] Qian, W. _et al._ Comparative study of variations in quantum approximate optimization algorithms for the traveling salesman problem.  _Entropy_ 25, 1238 (2023).
  * [19] Tszyunsi, C. & Beterov, I.  A quantum algorithm for solving the travelling salesman problem by quantum phase estimation and quantum search.  _Journal of Experimental and Theoretical Physics_ 137, 210–215 (2023).
  * [20] 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_ , 2686–2691 (IEEE, 2023).
  * [21] 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).
  * [22] Poggel, B., Quetschlich, N., Burgholzer, L., Wille, R. & Lorenz, J. M.  Recommending solution paths for solving optimization problems with quantum computing.  In _2023 IEEE International Conference on Quantum Software (QSW)_ , 60–67 (IEEE, 2023).
  * [23] Leonidas, I. D., Dukakis, A., Tan, B. & Angelakis, D. G.  Qubit efficient quantum algorithms for the vehicle routing problem on quantum computers of the nisq era.  _arXiv preprint arXiv:2306.08507_ (2023).
  * [24] Bentley, C. D., Marsh, S., Carvalho, A. R., Kilby, P. & Biercuk, M. J.  Quantum computing for transport optimization.  _arXiv preprint arXiv:2206.07313_ (2022).
  * [25] Tambunan, T. D., Suksmono, A. B., Edward, I. J. M. & Mulyawan, R.  Quantum annealing for vehicle routing problem with weighted segment.  In _AIP Conference Proceedings_ , vol. 2906 (AIP Publishing, 2023).
  * [26] Osaba, E., Villar-Rodriguez, E., Gomez-Tejedor, A. & Oregi, I.  Hybrid quantum solvers in production: how to succeed in the nisq era?  _arXiv preprint arXiv:2401.10302_ (2024).
  * [27] Weinberg, S. J., Sanches, F., Ide, T., Kamiya, K. & Correll, R.  Supply chain logistics with quantum and classical annealing algorithms.  _Scientific Reports_ 13, 4770 (2023).
  * [28] D-Wave Developers.  Measuring Performance of the Leap Constrained Quadratic Model Solver.  Tech. Rep. 14-1065A-A, D-Wave Systems Inc. (2022).
  * [29] Feld, S. _et al._ A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer.  _Frontiers in ICT_ 6, 13 (2019).
  * [30] Salehi, Ö., Glos, A. & Miszczak, J. A.  Unconstrained binary models of the travelling salesman problem variants for quantum optimization.  _Quantum Information Processing_ 21, 67 (2022).
  * [31] D-Wave Developers.  Hybrid Solver for Constrained Quadratic Models.  Tech. Rep. 14-1055A-A, D-Wave Systems Inc. (2021).
  * [32] Mori, N. & Furukawa, S.  Quantum annealing for the adjuster routing problem.  _Frontiers in Physics_ 11, 1129594 (2023).
  * [33] Osaba, E. & Villar, E.  Datasets and results for the 2-dimensional and heterogeneous package delivery with priorities problem.  http://dx.doi.org/10.17632/yv48pwk96y.1 (2024).  Online at Mendeley Data.
  * [34] Romero, S. V., Osaba, E., Villar-Rodriguez, E. & Asla, A.  Solving logistic-oriented bin packing problems through a hybrid quantum-classical approach.  In _2023 IEEE 26th International Conference on Intelligent Transportation Systems (ITSC)_ , 2239–2245 (IEEE, 2023).

## Acknowledgements

Acknowledgements

This work was supported by the Basque Government through HAZITEK program
(Q4_Real project, ZE-2022/00033) and through Plan complementario comunicación
cuántica (EXP. 2022/01341) (A/20220551). The authors thank Miguel Angel Casla,
Ertransit’s Director of Operations, for his assistance throughout this
research.

## Author contributions statement

Author contributions statement

All authors conceived the research and defined the problem. All authors
conceived the experiments. E.O. and E.V.R design the solver. E.O. developed
the code and conducted the experimentation. E.O. and E.V.R. wrote the
manuscript. All authors reviewed the manuscript.

## Competing interests

Competing interests

The authors declare no competing interests.