Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem | #quantumsummit23

Maximilian Hess | PhD student quantum algorithms, Infineon Technologies

PD Dr. habil. Jeanette Miriam Lorenz | Head of Department Quantum-enhanced AI, Fraunhofer IKS

Modern-day transportation and logistics happen in increasingly smart environments. New data sources hold both an opportunity and a challenge. Vehicle routes need to be planned efficiently to exploit the new potential. For example, w aste management in large cities traditionally does not inhibit overflowing containers. Trucks follow a fixed route independent of the filling level which leads to inefficient routes. Containers can be equipped with sensors that provide real-time information on the filling level.

Optimal routes can then be computed dynamically to only visit full containers and utilize the truck’s capacity. Mathematically speaking, route planning for waste collection translates to a Capacitated Vehicle Routing Problem (CVRP). The CVRP is NP-hard, thus industry-sized problems with hundreds to thousands of nodes can only be solved heuristically. Quantum computing promises the potential to outperform classical solvers for several computational tasks. However, its practical application to industry-relevant optimization problems poses challenges such as finding good mathematical formulations, setting parameters of variational algorithms or measuring the solution quality. For the CVRP, we assess the viability of formulation, decomposition, and algorithmic options for noisy intermediate-scale quantum hardware with regards to problem-specific performance measures. Obtaining useful results with the Quantum Approximate Optimization Algorithm and its variants proves to be difficult even after reducing the CVRP to a set of Travelling Salesperson Problems, but the Variational Quantum Eigensolver shows more promise.

This work is part of the QuaST project funded by the Federal Ministry for Economic Affairs and Climate Action. QuaST aims to facilitate the access to quantum-based solutions for optimization problems and to bridge the gap between business and technology. Our work contributes to understanding the challenges therein for the CVRP.

More about #quantumsummit23: #quantumsummit23 | Quantum Summit (quantum-summit.com)

Видео Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem | #quantumsummit23 канала Bitkom Events