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).
Sleek v2.0 public release is here
Lorem ipsum dolor sit amet, consectetur adipiscing elit lobortis arcu enim urna adipiscing praesent velit viverra sit semper lorem eu cursus vel hendrerit elementum morbi curabitur etiam nibh justo, lorem aliquet donec sed sit mi at ante massa mattis.
- Neque sodales ut etiam sit amet nisl purus non tellus orci ac auctor
- Adipiscing elit ut aliquam purus sit amet viverra suspendisse potent i
- Mauris commodo quis imperdiet massa tincidunt nunc pulvinar
- Adipiscing elit ut aliquam purus sit amet viverra suspendisse potenti
What has changed in our latest release?
Lorem ipsum dolor sit amet, consectetur adipiscing elit ut aliquam, purus sit amet luctus venenatis, lectus magna fringilla urna, porttitor rhoncus dolor purus non enim praesent elementum facilisis leo, vel fringilla est ullamcorper eget nulla facilisi etiam dignissim diam quis enim lobortis scelerisque fermentum dui faucibus in ornare quam viverra orci sagittis eu volutpat odio facilisis mauris sit amet massa vitae tortor condimentum lacinia quis vel eros donec ac odio tempor orci dapibus ultrices in iaculis nunc sed augue lacus
All new features available for all public channel users
At risus viverra adipiscing at in tellus integer feugiat nisl pretium fusce id velit ut tortor sagittis orci a scelerisque purus semper eget at lectus urna duis convallis. porta nibh venenatis cras sed felis eget neque laoreet libero id faucibus nisl donec pretium vulputate sapien nec sagittis aliquam nunc lobortis mattis aliquam faucibus purus in.
- Neque sodales ut etiam sit amet nisl purus non tellus orci ac auctor
- Adipiscing elit ut aliquam purus sit amet viverra suspendisse potenti
- Mauris commodo quis imperdiet massa tincidunt nunc pulvinar
- Adipiscing elit ut aliquam purus sit amet viverra suspendisse potenti
Coding collaboration with over 200 users at once
Nisi quis eleifend quam adipiscing vitae aliquet bibendum enim facilisis gravida neque. Velit euismod in pellentesque massa placerat volutpat lacus laoreet non curabitur gravida odio aenean sed adipiscing diam donec adipiscing tristique risus. amet est placerat in egestas erat imperdiet sed euismod nisi.
“Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum”
Real-time code save every 0.1 seconds
Eget lorem dolor sed viverra ipsum nunc aliquet bibendum felis donec et odio pellentesque diam volutpat commodo sed egestas aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod eu tincidunt tortor aliquam nulla facilisi aenean sed adipiscing diam donec adipiscing ut lectus arcu bibendum at varius vel pharetra nibh venenatis cras sed felis eget dolor cosnectur drolo.
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.
To solve a 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.
If you want more information about our fleet routing service or other product and services from our portfolio, get in contact with us!
