# QUBO Resolution of the Job Reassignment Problem

Iñigo Perez Delgado1, Beatriz García Markaida2, Alejandro Mata Ali3, Aitor
Moreno Fdez. de Leceta4 1i3b Ibermatica, Parque Tecnológico de Bizkaia,
Ibaizabal Bidea, Edif. 501-A, 48160 Derio, Spain
Email<EMAIL_ADDRESS>2i3b Ibermatica, Parque Tecnológico de
Bizkaia, Ibaizabal Bidea, Edif. 501-A, 48160 Derio, Spain
Email<EMAIL_ADDRESS>3i3B Ibermatica, Quantum Development
Department, Paseo Mikeletegi 5, 20009 Donostia, Spain
Email<EMAIL_ADDRESS>4i3b Ibermatica, Unidad de Inteligencia
Artificial, Avenida de los Huetos, Edificio Azucarera, 01010 Vitoria, Spain
Email<EMAIL_ADDRESS>
###### Abstract

We present a subproblemation scheme for heuristical solving of the JSP (Job
Reassignment Problem). The cost function of the JSP is described via a QUBO
hamiltonian to allow implementation in both gate-based and annealing quantum
computers. For a job pool of $K$ jobs, $\mathcal{O}(K^{2})$ binary variables
-qubits- are needed to solve the full problem, for a runtime of
$\mathcal{O}(2^{K^{2}})$. With the presented heuristics, the average variable
number of each of the $D$ subproblems to solve is $\mathcal{O}(K^{2}/2D)$, and
the expected total runtime $\mathcal{O}(D2^{K^{2}/2D})$, achieving an
exponential speedup.

###### Index Terms:

Simulation and Modeling; Intelligent Logistics; Management of Exceptional
Events: Incidents, Evacuation, Emergency Management

##  I Introduction

QUBO (Quadratic Unconstrained Binary Optimization) problems [1], which can be
solved both by quantum annealing devices and gate-based quantum computers,
have been already used to give answer to relevant NP-hard problems [2] such as
the Travelling Salesperson Problem [3, 4] or the Hamiltonian Cycle problem
[5]. In this paper we will treat one of these QUBOs named the Job Reassignment
Problem (JRP). In tha JRP a number $J$ of agents - which can take the form of
workers, machines, vehicles- have to be reallocated to a new configuration of
jobs due to some unexpected circumstance such as a shift on the production
priority or the incapacitation of some of the originally assigned agents. Due
to those unexpected causes, there exist a number $I$ of relevant jobs with
high priority score which do not have a paired agent. The resolution of the
JRP implies finding the agents which better suit those jobs, moving them from
their current low-priority jobs to those unassigned high-priority ones. This
is done by taking into account some $\mathcal{S}_{ij}$ scores defined between
each vacant job $i$ and each agent $j$. The goal of the optimization problem
will be to choose the $i,j$ pairs such that the sum of their
$\mathcal{S}_{ij}$ is maximized, with the full problem using $N=J\times I$
binary variables.

At first glance the number of variables required to solve the complete JRP
grows linearly with each of two independent parameters $J$ and $I$. However,
if typically a fraction $p$ of the total number $K=J+I$ of jobs are emptied,
meaning that $I=pK$ and $J=(1-p)K$, both the number $J$ of agents ready to
perform the jobs and the number $I$ of unexpectedly empty jobs would escalate
equally. Then, $N=J\times I=\mathcal{O}(K^{2})$. The search space of possible
solutions, and thus the time required to find its optimum, has size
$2^{J\times I}=\mathcal{O}(2^{K^{2}})$.

In this paper we present a heuristical approach to the JRP, with several
variable-reduction methods that aim to paliate the $N=\mathcal{O}(K^{2})$
scaling of the full problem. This scheme divides the full
$\mathcal{O}(K^{2})$-variable problem into $D$ different
$\mathcal{O}(K^{2}/2D)$-variable subproblems, reducing the search space of
each subproblem to size $\mathcal{O}(2^{K^{2}/2D})$ and thus the total runtime
of the $D$ subproblems to $\mathcal{O}(D2^{K^{2}/2D})$.

It is important to note that these proportionality figures are expected
values, and the true scaling will vary between instances of the problem.
Moreover, these methods, being of heuristical nature, do not guarantee an
acceptable solution for all cases of the problem. This does not mean, as it is
the case of other heuristics, that no advantage is to be expected from their
usage. In fact, the subproblemation allows for agents to be reallocated to
originally non-vacant jobs, which is not the case of the original full
problem. This expanded answer space suggests that, in some cases, the optimum
of the approximated problem can be of better quality than the optimum of the
original full hamiltonian.

The presented methods have been tested in the real context of a joint project
between i3b (Instituto de Innovación Ibermática) and the ONCE (Organización
Nacional de Ciegos Españoles).

##  II Problem description

The $\mathcal{S}_{ij}$ coefficients of the cost function of the problem that
relate each agent with each vacant job are given by the combination of several
values. The first term to take into account is the priority gain
$\Delta^{\mathcal{P}}_{ij}\equiv\mathcal{P}^{V}_{i}-\mathcal{P}^{C}_{j}$
between the priority of the vacant job $\mathcal{P}^{V}_{i}\in(0,1]$ and the
priority of the job the agent is currently covering
$\mathcal{P}^{C}_{j}\in(0,1]$. These priority values are known for each job,
being given by the statement of the problem. However, it is allowed for these
values to be changed between instances of the resolution of the problem, since
a certain job can have different priorities in different contexts. In any
case, none of the considered jobs should have a priority of $0$, because in
that case the job could just not be considered part of the problem. Priority
can have a discrete range of values when each job is ranked in one of $D$
priority categories. In that case, all jobs of the same category will have the
same $\mathcal{P}^{V}_{i}$ or $\mathcal{P}^{C}_{j}$ value, usually
$\in\\{1,2,...,D\\}$.

The second term of $\mathcal{S}_{ij}$ is the affinity gain
$\Delta^{\mathcal{A}}_{ij}\equiv\mathcal{A}^{V}_{ij}-\mathcal{A}^{C}_{jj}$
between the personal affinity of agent $j$ with the vacant job $i$,
$\mathcal{A}^{V}_{ij}\in[0,1)$, and the personal affinity of that agent with
the job they are currently covering $\mathcal{A}^{C}_{jj}\in[0,1)$. These
affinities are noted collectively as $\mathcal{A}_{kj}$, where $k$ encompasses
all $K=I+J$ jobs, vacant or assigned.

The total score is then calculated as

$\mathcal{S}_{ij}=c^{\mathcal{P}}\Delta^{\mathcal{P}}_{ij}+c^{\mathcal{A}}\Delta^{\mathcal{A}}_{ij}$
(1)

where $c^{\mathcal{P}}$ and $c^{\mathcal{A}}$ are the two positive constants
that give the relative weight of the optimization terms. They are given by the
statement of the problem.

A simple way to model the $\mathcal{A}_{kj}$ personal affinities is by
counting the number of times the agent $j$ was assigned to a particular job
$k$ in a historical record and mapping that count to a monotonically ascending
function such as

$\mathcal{A}_{kj}=1-\frac{1}{1+M_{kj}}\;,$ (2)

where $M_{kj}$ is the number of times agent $j$ has been assigned to job $k$.
Note that, since an assigned agent has been assigned to their current job at
least for the current instance, in this model
$\mathcal{A}^{C}_{jj}\in[0.5,1)$.

##  III Variable selection

In order to solve this optimization problem one binary variable
$x_{ij}\in\\{0,1\\}$ will be assigned to each ‘vacant job - agent’ pair. If
$x_{ij}=1$, then agent $j$ will be reassigned to the vacant job $i$, leaving
vacant their current assigned job. If $x_{ij}=0$, then agent $j$ will not be
reassigned to job $i$, but could be reassigned for other vacant job. This
means that

$\text{if }\sum_{j}x_{ij}=0\text{ then vacant job $i$ remains vacant,}$ (3)

and

$\text{if }\sum_{i}x_{ij}=0\text{ then agent $j$ is not reassigned.}$ (4)

For $J$ agents with assigned jobs and $I$ vacant jobs, the number of binary
variables needed to solve the full problem is $N=J\times I$. In Fig. 1 each of
the $x_{ij}\in\\{0,1\\}$ variables of the full problem is represented with a
grey line: if the agent from job $a_{j}$ has been reallocated to the vacant
job $v_{i}$, then $x_{ij}=1$ and the line is colored black. Else, $x_{ij}=0$
and the line remains grey.

$a_{1}$$a_{2}$$a_{3}$$\vdots$$a_{J}$$v_{1}$$v_{2}$$\vdots$$v_{I}$ Figure 1:
Representation of the full hamiltonian for a problem with $J$ agents -that is,
$J$ jobs with assigned agents- and $I$ vacant jobs, where the solution to the
problem has involved moving agent $a_{1}$ and $a_{3}$ from their original jobs
to the originally vacant jobs $v_{2}$ and $v_{I}$. Notice how not all vacants
are necessarily filled and not all agents are necesarily reallocated.

##  IV Hamiltonian construction

The cost function hamiltonian $H$ will be divided in two parts: the core
hamiltonian $H^{0}$, where we will encode the optimization problem, and the
restriction hamiltonian $H^{R}$ whose terms will effectively reduce the search
space to only physically plausible states. Then, $H\equiv H^{0}+H^{R}$.

The core hamiltonian takes into account the total score of all active
variables, and is composed of two terms, as shown in (5): the priority gain
and the affinity gain.

$H^{0}=-\sum_{ij}\mathcal{S}_{ij}x_{ij}=-c^{\mathcal{P}}\sum_{ij}\Delta^{\mathcal{P}}_{ij}x_{ij}-c^{\mathcal{A}}\sum_{ij}\Delta^{\mathcal{A}}_{ij}x_{ij}\;.$
(5)

Note how even though JRP is a maximization problem, the value of $H^{0}$ is
smaller for high $\Delta^{\mathcal{P}}_{ij}$ and $\Delta^{\mathcal{A}}_{ij}$.
This happens because the annealing systems decay towards the state of minimum
energy of their hamiltonian, so the original maximization cost function has to
be translated into its analogous minimization cost function by the
introduction of a $-1$ factor.

The restriction hamiltonian has two terms too, as shown in (6):

$H^{R}=H^{R}_{1}+H^{R}_{2}\;,$ (6)

where the first term

$H^{R}_{1}=\lambda_{1}^{R}\sum_{i}\left(\sum_{j}x_{ij}-0.5\right)^{2}$ (7)

ensures, for a large enough $\lambda_{1}^{R}>0$, that each job $i$ can be done
by at most one agent and the second term

$H^{R}_{2}=\lambda_{2}^{R}\sum_{j}\left(\sum_{i}x_{ij}-0.5\right)^{2}$ (8)

makes, for a large enough $\lambda_{2}^{R}>0$, each agent $j$ to be reassigned
to at most one job. Allowing the restriction coefficient to be the fractionary
number $0.5$ allows the number of active binary variables of the sums inside
the parentheses to be either $0$ or $1$, since those are the integer values
that are closer to $0.5$ [6], without introducing any dummy variables. Using
only integer restriction coefficients would force the introduction of $I+J$
dummy variables.

The complete hamiltonian is then, merging (5), (7) and (8),

$\begin{split}H=-\sum_{ij}&\bigg{[}c^{\mathcal{P}}\left(\mathcal{P}^{V}_{i}-\mathcal{P}^{C}_{j}\right)+c^{\mathcal{A}}\left(\mathcal{A}^{V}_{ij}-\mathcal{A}^{C}_{jj}\right)\bigg{]}x_{ij}\\\
&+\lambda_{1}^{R}\sum_{i}\bigg{(}\sum_{j}x_{ij}-0.5\bigg{)}^{2}\\\
&+\lambda_{2}^{R}\sum_{j}\bigg{(}\sum_{i}x_{ij}-0.5\bigg{)}^{2}\;,\end{split}$
(9)

summed over the $i,j$ pairs represented by the lines of the graph.

##  V Heuristical variable reduction and Problem segmentation

In order to diminish the needed number of qubits $N$, which in the full
problem of Fig. 1 equals $J\times I$, certain simplifications will be taken.

Firstly, only changes with $\mathcal{S}_{ij}>0$ will be taken into account.
Changes with a negative score will be ignored, even if they would allow a
second, positive-scored change which resulted in a net gain. It is assumed
that the initial distribution is already in a sensible state, and as such it
would be difficult to obtain a gain with that kind of second-order movement.

Secondly, changes with $\Delta^{\mathcal{P}}_{ij}<0$ will also be ignored,
since the ultimate goal of the optimization is to maximize the total priority
of the assigned jobs.

Assuming about half of the $i,j$ pairs have $\mathcal{S}_{ij}>0$ or
$\Delta^{\mathcal{P}}_{ij}<0$ -since the two quantities are strongly
correlated, otherwise $\nicefrac{{3}}{{4}}$ of the pairs would be assumed-,
these simplifications reduce the expected number of qubits needed to
approximately $N\approx(J\times I)/2$, thus reducing the search space to a
size of $\sqrt{2^{J\times I}}$ and achieving a quadratical speedup.

Moreover, ignoring changes with $\Delta^{\mathcal{P}}_{ij}<0$ allows us to
divide the problem into smaller subproblems. These subproblems will be
generated in function of the $\mathcal{P}^{V}_{i}$ priorities of the vacant
values. If those values are discrete, being able to take $D$ different values,
then for each value one subproblem will be created. If the values are
continuous, they can be grouped in $D$ intervals of length $1/D$. Then for the
$d$th subproblem, only those vacant jobs with $\mathcal{P}^{V}_{i}\geq
1-\frac{d}{D}$ are considered. After having solved the $d=1$ subproblem, those
vacants which have been succesfully reassigned will not be included in the
$d=2$ subproblem. However, those jobs that have been emptied as a result of
their agent being reassigned will be included as vacant jobs. This means all
$\mathcal{A}_{kj}$ are potentially needed for the resolution, not only the
$\mathcal{A}^{V}_{ij}$ and $\mathcal{A}^{C}_{jj}$ of the original full
problem. Moreover, as $\Delta^{\mathcal{P}}_{ij}<0$ variables are ignored,
only those agents with jobs with
$\mathcal{P}^{C}_{j}\leq{\mathcal{P}^{V}_{d}}_{MAX}$ will be considered, where
${\mathcal{P}^{V}_{d}}_{MAX}$ is the maximum priority between all considered
$\mathcal{P}^{V}_{i}\geq 1-\frac{d}{D}$.

We can also estimate the effect of the subproblemation on the size of the
search space and time. It segmentates the $I$ vacant jobs of the complete
problem into $D$ subproblems, giving an average value of $\langle
I_{D}\rangle=I/D$ empty jobs for subproblem. As one can see in Fig. 2, The
number of available agents is also reduced with each step, with each step
having $\alpha\langle I_{D}\rangle$ less agents than the previous one, where
$\alpha$ is the average proportion of vacant jobs that are covered on each
subproblem. Then, the expected number of agents of the $d$th subproblem, for
$d\in\\{1,...,D\\}$, would be $J-\alpha D(d-1)$, for an average of $\langle
J_{D}\rangle=J-\alpha D(D-1)/2$ over the $D$ subproblems. In total, each
subproblem will have an expected size of $\langle N_{D}\rangle=\langle
J_{D}\rangle\times\langle I_{D}\rangle=JI/D-\alpha
I(D-1)/2=\mathcal{O}(K^{2}/D).$ This in turn makes the search space of each
subproblem size $\mathcal{O}(2^{K^{2}/D})$, and the total runtime of the $D$
subproblems $\mathcal{O}(D2^{K^{2}/D})$.

With all the heuristics combined, the search space of each subproblem is
expected to be reduced to size $\mathcal{O}(2^{K^{2}/2D})$, and the total
runtime of the $D$ subproblems to $\mathcal{O}(D2^{K^{2}/2D})$.

$a_{1}$$a_{2}$$a_{3}$$a_{4}$$v_{1}$$v_{2}$$v_{3}$$\big{\Downarrow}$$a_{2}$$a_{4}$$v_{4}$$v_{5}$$a_{3}$
Figure 2: Representation of the subproblem hamiltonians for a problem with
$J=4$ agents and $I=5$ vacant jobs, divided into $D=2$ subproblems. The first
solves for the high $\mathcal{P}^{V}_{i}$ vacants
$\\{v_{i}\\}_{1}=\\{v_{1},v_{2},v_{3}\\}$, and then a second subproblem takes
care of the remaining $\\{v_{4},v_{5}\\}$, as well as the newly-emptied
$\\{a_{3}\\}$, which makes $\\{v_{i}\\}_{2}=\\{v_{4},v_{5},a_{3}\\}$.
Meanwhile $\\{a_{1}\\}$, a specially low-priority job, is not even considered
for this playoff. After resolution, the list of jobs with assigned agents has
become $\\{v_{1},v_{4},v_{3},a_{3}\\}$.

In Fig. 2 a representative example of such a subproblemation secheme is shown,
for a $D=2$ case. Notice how, in the example, $a_{j}$ jobs emptied in the
first subproblem can be taken by other agents in the second, lower-priority
subproblem. In this case, subproblemation has reduced a size $J\times
I=4\times 5=20$ problem down to a $4\times 3=12$ and a $2\times 3=6$ problem:
not only the total size is smaller $(18<20)$, but each of the subproblems can
be executed in a machine with a significantly lower number of logical qubits.
Moreover, applying our first variable-reduction criterion, only $x_{ij}$
variables whose $\mathcal{S}_{ij}$ score are positive are taken into account.
This is represented by the omission of some of the gray connections on the
figure, In this example, this reduces the needed number of qubits of the two
subproblems to $7$ and $4$ respectively.

##  VI Summary of the quantum algorithm

Inputs:

  * •

The $\\{a_{j}\\}$ list of the $J$ jobs with assigned agents -including the
identity of the assigned agent $j$.

  * •

The $\mathcal{P}^{C}_{j}$ priorities of the $\\{a_{j}\\}$ jobs,

  * •

The $\\{v_{i}\\}$ list of the $I$ vacant jobs.

  * •

The $\mathcal{P}^{V}_{i}$ priorities of the $\\{v_{i}\\}$ jobs,

  * •

The $\mathcal{A}_{ik}$ affinities between each agent $j$ and each job $k$.
These affinity scores will be used in the form of the affinity of agent $j$
with the vacant job $i$, $\mathcal{A}^{V}_{ij}$ and the affinity of of agent
$j$ with the job they are covering $\mathcal{A}^{C}_{jj}$.

  * •

The $c^{\mathcal{P}}$ and $c^{\mathcal{A}}$ coefficients regulating the
relative weights of the priority and affinity terms.

Procedure:

  1. 1.

Decide, depending on the caracteristics of $\\{v_{i}\\}$ and
$\mathcal{P}^{V}_{i}$, the number $D$ of subproblems:

    1. (a)

If the values of $\mathcal{P}^{V}_{i}$ are discrete, then for each value one
subproblem will be created.

    2. (b)

If the values of $\mathcal{P}^{V}_{i}$ are continuous, the elements of
$\\{v_{i}\\}$ can be grouped into $D$ intervals of average length $1/D$.

  2. 2.

Divide $\\{v_{i}\\}$ into the $D$ different sublists $\\{v_{i}\\}_{d}$, with
$d$ ordered from high to low $\mathcal{P}^{V}_{i}$. Each $\\{v_{i}\\}_{d}$
will contain vacant jobs with priorities
$\mathcal{P}^{V}_{i}\in[{\mathcal{P}^{V}_{d}}_{min},{\mathcal{P}^{V}_{d}}_{MAX}]$.

  3. 3.

For $\delta\in\\{1,...,D\\}$, repeat iteratively steps a) $\rightarrow$ e):

    1. (a)

Knowing only $\Delta^{\mathcal{P}}_{ij}>0$ changes can happen, create a
sublist $\\{a_{j}\\}_{\delta}$ with only those assigned jobs with
$\mathcal{P}^{C}_{j}<{\mathcal{P}^{V}_{\delta}}_{MAX}$.

    2. (b)

Create a graph connecting all elements of $\\{a_{j}\\}_{\delta}$ with all
elements of $\\{v_{i}\\}_{\delta}$, and then remove all $i,j$ connections with
$\mathcal{S}_{ij}\leq 0$.

    3. (c)

Find the minimum of the $H$ hamiltonian described by the graph, which has the
QUBO form given by (9), taking into account that each connection is a
representation of one $x_{ij}$ binary variable.

    4. (d)

Update the $\\{a_{j}\\}$ list of jobs which have an assigned worker, taking
into account the new locations of the reallocated workers by removing new
vacants and adding newly filled jobs. Note that the elements of the list
change and thus the $j$ indices refer to different jobs in different
iterations. However, the number of elements $J$ does not change.

    5. (e)

Update all the $\\{v_{i}\\}_{d}$ to include the jobs the reallocated agents
have just left vacant. Only $\\{v_{i}\\}_{d}$ with $d\in\\{\delta+1,...D\\}$
will need an update.

      1. i.

For discrete values of $\mathcal{P}^{V}_{i}$, each of the new vacants will
naturally be included in the $\\{v_{i}\\}_{d}$ group that corresponds to their
$\mathcal{P}^{C}_{j}$.

      2. ii.

For continuous values of $\mathcal{P}^{V}_{i}$ sometimes jobs with
$\mathcal{P}^{C}_{j}\in[{\mathcal{P}^{V}_{\delta}}_{min},{\mathcal{P}^{V}_{\delta}}_{MAX}]$
will be left vacant. In that case, they should be included into the
inmediately subsequent list of $\\{v_{i}\\}_{\delta+1}$, for them to be
included in the subproblem of the next iteration.
${\mathcal{P}^{V}_{\delta+1}}_{MAX}$ will then need to be updated, taking the
value of the highest $\mathcal{P}^{C}_{j}$ included.

Output: An updated version of the $\\{a_{j}\\}$ list with the jobs that have
ended up with an assigned agent -and the identity of that agent for each job.

##  VII Conclusions

In this paper we described the heuristical subproblemation scheme developed
for solving the Job Reassignment Problem posed in the joint project between
i3b (Instituto de Innovación Ibermática) and the ONCE (Organización Nacional
de Ciegos Españoles).

This algorithm, as all heuristical methods, does not guarantee a speedup or a
solution of quality for all possible instances of the problem. However, the
performance of the method for an average problem can be calculated, proving an
exponential speedup over the resolution of the full problem without
subproblemation. Moreover, the subproblemation scheme uniquely allows for
agents to be reallocated to originally non-vacant jobs, which means that in
some cases the given answer can be of better quality than the optimum of the
original full problem.

The presented algorithm works over a QUBO hamiltonian cost function to allow
resolution by both gate-based and annealing quantum computers, as well as
classical and quantum-inspired resolution methods. As it divides the QUBO
hamiltonian of the full problem into several smaller problems which are still
in QUBO form, the advantage of the subproblemation scheme is device-agnostic
and stacks with the advantages of other QUBO resolution methods. As usual, all
the advantages of the method remain when using the Ising forms of the
hamiltonians.

## Acknowledgments

We thank ONCE INNOVA for the project proposal which kickstarted this work.

The research leading to this paper has received funding from the Q4Real
project (Quantum Computing for Real Industries), HAZITEK 2022, no.
ZE-2022/00033.

© 2023 IEEE. Personal use of this material is permitted. Permission from IEEE
must be obtained for all other uses, in any current or future media, including
reprinting/republishing this material for advertising or promotional purposes,
creating new collective works, for resale or redistribution to servers or
lists, or reuse of any copyrighted component of this work in other works.

## References

  * [1] F. Glover, G. Kochenberger, and Y. Du, “A tutorial on formulating and using QUBO models,” 2019.
  * [2] M. R. Garey and D. S. Johnson, _Computers and Intractability: A Guide to the Theory of NP-Completeness_. San Francisco, CA, USA: W.H. Freeman and Company, 1979.
  * [3] E. Villar-Rodriguez, E. Osaba, and I. Oregi, “Analyzing the behaviour of D’wave quantum annealer: fine-tuning parameterization and tests with restrictive hamiltonian formulations,” 2022.
  * [4] A. Bonomi, T. D. Min, E. Zardini, E. Blanzieri, V. Cavecchia, and D. Pastorello, “Quantum annealing learning search implementations,” _Quantum Information and Computation_ , vol. 22, no. 3&4, pp. 181–208, feb 2022. [Online]. Available: https://doi.org/10.26421$%$2Fqic22.3-4-1
  * [5] J. Nüßlein, T. Gabor, C. Linnhoff-Popien, and S. Feld, “Algorithmic QUBO formulations for k-SAT and hamiltonian cycles,” in _Proceedings of the Genetic and Evolutionary Computation Conference Companion_. ACM, jul 2022. [Online]. Available: https://doi.org/10.1145$%$2F3520304.3533952
  * [6] I. P. Delgado, B. G. Markaida, A. M. F. De Leceta, and J. A. O. Uriarte, “Quantum hobbit routing: Annealer implementation of generalized travelling salesperson problem,” in _2022 IEEE Symposium Series on Computational Intelligence (SSCI)_ , 2022, pp. 923–929.