Insider Brief:
- A collaboration between Volkswagen Data:Lab and the University of Innsbruck highlights how QUBO can effectively model and address the Ride Pooling Problem.
- Quantum computing has been used for solving QUBO formulations and has the potential to deliver high-quality approximations effectively for complex, highly-connected problems.
- While QUBO-based solutions show promise, the paper notes that the quadratic scaling of variables remains a challenge for current quantum devices.
A recent study in Nature, conducted by Volkswagen Data: Lab and the Institute for Theoretical Physics at the University of Innsbruck, explored QUBO as a framework to model the Ride Pooling Problem (RPP). The RPP captures the optimization challenge that arises when pooling multiple customer requests for on-demand pickups and drop-offs with only a limited fleet of shared vehicles.
Modeling the Problem Using QUBO:
In a time of increased appeal of convenient doorstep delivery and shared transportation, the Ride Pooling Problem defines a commonly encountered scenario where multiple customers can create on-demand requests from a limited quantity of shared vehicles. The number of variables to optimize for makes this problem computationally intensive–the requests must be optimized for maximum efficiency, with minimum travel time, and within the constraints of the fleet.
To effectively explore solutions to this problem, Researchers from Volkswagen Data:Lab and the University of Innsbruck defined the RPP within the framework of QUBO, as QUBO models have been studied extensively in NP-hard real-world optimization problems. The versatility of QUBO comes from its ability to represent complex problems with binary variables, where the goal is to minimize or maximize a quadratic objective function.
Among previous methods presented in the literature to solve QUBO problems, quantum computing has shown strong potential. For instance, a paper by Silva et al. implements QUBO for minimizing losses in electrical distribution networks using quantum annealing. Similarly, another study by Tang et al. on the scheduling of automated guided vehicles demonstrated that using a coherent Ising machine to solve QUBO formulations can reduce computation times by up to 92% compared to classical methods.
According to the paper, quantum computing is a valuable tool for solving problems related to optimization. The quantum mechanical nature of quantum computing allows it to explore relationships between highly connected variables effectively. Even though quantum algorithms may not always succeed in finding the absolute most optimal solution, they still have the potential to deliver high-quality approximations much faster than classical algorithms. This becomes especially relevant where classical methods struggle due to a problem’s complexity or size.
In studying QUBO formulations for the RPP, the researchers from Volkswagen Data:Lab experimented with various methods, each chosen to find the most efficient and scalable solution. The paper emphasizes the importance of finding the most minimal QUBO representations in order to reduce the number of variables and constraints. This becomes highly relevant when considering quantum computing implementations as increased variables in a QUBO formulation directly contribute to deeper quantum circuits. As noted in the paper, deeper circuits are not ideal on current quantum processors due to limited qubit connectivity and coherence times.
The team notes that while the overall results of this study are directly applicable to modern routing challenges, such as those encountered by ride-sharing services, its significance does not end there. Exploring QUBO in the context of the RPP is not only relevant for routing and logistics problems, but also in further understanding how quantum computing will play a role in complex, real-world optimization challenges.
Future Outlook for Quantum Optimization:
While the QUBO formulations presented in the study are promising, the paper acknowledges that the quadratic scaling of variables would be not be ideal for implementation on current quantum devices. This limitation speaks to the need for further research and development to make these methods viable on today’s quantum hardware.
As quantum technology continues to scale, the practical application of QUBO-based solutions such as the one proposed for RPP will expand, offering optimization methods that have the potential to surpass classical approaches.
The scientists involved in the study include Michele Cattelan, associated with Volkswagen Data:Lab and the University of Innsbruck, as well as Sheir Yarkoni with the Volkswagen Data:Lab.
