Imagine a world where packages are delivered with unparalleled efficiency, even in the face of complex constraints. That’s precisely what researchers from TECNALIA and Serikat-Consultoría y Servicios Tecnológicos have achieved through their innovative use of quantum computing to solve a real-world package delivery routing problem. Their breakthrough, known as the Quantum for Real Package Delivery (Q4RPD) system, combines classical and quantum computing to tackle a problem that has long plagued the logistics industry: optimizing delivery routes while accounting for factors like vehicle capacity, delivery priorities, and even the dimensions of the packages themselves.
Unlocking the Power of Quantum Computing
The world of logistics is full of complex challenges, and the task of optimizing package delivery routes is no exception. Traditional methods have often struggled to keep up with the ever-evolving demands of modern supply chains, leaving companies scrambling to find more efficient solutions. Enter quantum computing, a revolutionary technology that has the potential to transform the way we approach optimization problems.
Tackling the 2-Dimensional and Heterogeneous Package Delivery with Priorities (2DH-PDP) Problem
The researchers at TECNALIA and Serikat-Consultoría y Servicios Tecnológicos set out to tackle a real-world routing problem faced by a Spanish logistics company, Ertransit. This problem, dubbed the 2-Dimensional and Heterogeneous Package Delivery with Priorities (2DH-PDP) problem, involves a fleet of heterogeneous vehicles (both owned and rented) tasked with delivering packages with varying weight and dimensional characteristics. Adding to the complexity, some packages are designated as “top priority,” requiring delivery within a specific time frame.
The Q4RPD Solving Scheme: A Quantum-Classical Hybrid Approach
To address this challenge, the researchers developed the Quantum for Real Package Delivery (Q4RPD) system, a hybrid approach that combines the power of classical and quantum computing. The key components of this system include:
Classical Computing: The classical computing aspect of Q4RPD is responsible for managing the overall workflow, splitting the problem into manageable sub-problems, and ensuring that all constraints and preferences are properly handled. This includes prioritizing the use of owned vehicles over rented ones and minimizing the number of vehicles used, even if it means a slightly longer overall distance.
Quantum Computing: The quantum computing component of Q4RPD leverages the D-Wave Leap Constrained Quadratic Model (CQM) Hybrid Solver to calculate the optimal route for each individual truck or sub-route. By formulating the problem as a CQM, the system can take advantage of the unique capabilities of quantum annealing to explore a vast solution space and identify the most efficient routes.
Fig. 2
Tackling Real-World Complexity
One of the standout features of the Q4RPD system is its ability to handle the real-world complexities of package delivery. Unlike many previous studies that focused on simplified or “toy” problems, the researchers worked closely with Ertransit to develop a system that could address the company’s actual day-to-day challenges.
This included accounting for factors such as:
• A heterogeneous fleet of vehicles, including both owned and rented trucks
• Prioritized deliveries, with certain packages requiring timely delivery
• Two-dimensional package descriptions, considering both weight and dimensions
By incorporating these real-world constraints, the Q4RPD system demonstrates its potential to deliver tangible benefits to logistics companies grappling with the complexities of modern package delivery.
Fig. 3
Experimental Validation and Promising Results
To validate the performance of the Q4RPD system, the researchers conducted a series of experiments using six different instances, each with varying levels of complexity and size. The results were impressive, with the system consistently meeting all the imposed constraints and delivering solutions that were highly competitive with those generated by a classical optimization algorithm, Google OR-Tools.
In cases where there were no prioritized deliveries, the Q4RPD system was able to find optimal solutions. Even in instances with time-sensitive “top priority” packages, the system was able to keep the deviation from the optimal distance to less than 6.3%.
Paving the Way for the Future of Logistics
The success of the Q4RPD system demonstrates the immense potential of quantum computing in solving real-world optimization problems, particularly in the realm of logistics and supply chain management. By combining classical and quantum approaches, the researchers have created a powerful tool that can tackle the complexities of package delivery, opening up new possibilities for increased efficiency, cost savings, and customer satisfaction.
As quantum computing technology continues to evolve, the impact of solutions like Q4RPD is likely to grow, with the potential to revolutionize various industries beyond logistics. The future of optimized package delivery is here, and it’s being driven by the innovative intersection of classical and quantum computing.
Author credit: This article is based on research by Eneko Osaba, Esther Villar-Rodriguez, Antón Asla.
For More Related Articles Click Here
