Optimizing delivery routes can significantly reduce operational costs, lower emissions, and improve customer satisfaction for logistics and mobility businesses. Our Anaqor Quantum Fleet Planning Service demonstrates how quantum computing can tackle the complexities of route optimization, which is closely related to the well-known Travelling Salesperson Problem (TSP).
What is the Travelling Salesperson Problem? Finding the shortest path between a number of points and places that must be visited is the goal of the algorithmic problem known as the โtraveling salesperson problemโ (TSP) . The cities a salesperson might visit are the points in the problem statement. The salesperson wants to travel as little as possible, both in terms of distance, time and travel costs.
Focused on optimization, TSP is often used in computer science to find the most efficient route for data to travel between various nodes. The simplest method is to try all possible routes and calculate the associated cost, but this is also the most time consuming and expensive method.
So the challenge lies in finding the shortest route that visits all nodes (e.g. parcel drop-off points) while considering factors such as distance, traffic, and street type. Solving this problem involves evaluating a rapidly increasing number of possible routes, making it computationally demanding.
How to translate the TSP for quantum devices Today's quantum devices are suitable to tackle exactly such combinatorial optimization problems. In our consideration we assume a fleet (= several travel-persons), which together have to visit all nodes and afterwards have to return to the starting node. This variation of the general TSP problem is also known as vehicle routing problem (VRP).
For an optimal interplay of classical and quantum algorithms, our approach involves dividing the VRP into several subproblems. Namely, first the graph encoding the nodes and connections between them is partitioned into subgraphs by a classical method. This partitioning is based on the eigenvalue computation of a special matrix, called Laplacian , and is called Spectral Clustering. In simple terms, this procedure ensures that nodes with shorter connections to each other are grouped together into a subgraph (or cluster).
The number of required subgraphs corresponds to the number of available vehicles in the fleet and can be entered as a parameter in the algorithm. With this step, the VRP is split into several TSPs, which can be solved with quantum hardware.single TSP , it must be formulated properly. A possible encoding is achieved via binary variables in the following way:
Using this encoding, at the heart of the formulation of the TSP is the following term:
This states that if at two successive time steps along the route ๐ก and ๐ก+1 the nodes ๐ and ๐ are visited, the distance ๐๐๐ between the cities is added to the distance traveled. In this term, we also see that the variables occur quadratically. This allows the formulation of the TSP as a so-called quadratic unconstrained binary optimization problem (QUBO).
How to solve the TSP using quantum devices This kind of formulation is ideally suited in order to implement it on today's quantum devices and solve the optimization problem. As such, quantum annealers are a metaheuristic approach to solving exactly such QUBOs . Once the problem is transferred to the hardware, this architecture allows the natural evolution of the qubit states to find the global optimum (i.e., the perfect route).
There are also suitable algorithms for solving such problems on universal quantum computers, which, in contrast to the natural evolution of quantum systems in the quantum annealer, attempt to actively manipulate the state of the qubits. Among the best known representatives of so-called variational algorithms are the Variational Quantum Eigensolver (VQE) or the Quantum Approximate Optimization Algorithm (QAOA), which are used to solve such optimization problems.
In the Fleet Routing Service we have developed, we provide the presented methods, as well as other classical approaches to solve the VRP.
By leveraging quantum computing and machine learning, businesses in the logistics and mobility industry have the potential to optimize their fleet planning, driving efficiency and sustainability while enhancing customer satisfaction.
โ
