Cattelan Michele, Yarkoni Sheir
Volkswagen Data:Lab, Volkswagen AG, Munich, 80805, Germany.
Institute for Theoretical Physics, University of Innsbruck, Innsbruck, A-6020, Austria.
Sci Rep. 2024 Aug 26;14(1):19768. doi: 10.1038/s41598-024-70649-3.
Many emerging commercial services are based on the sharing or pooling of resources for common use with the aim of reducing costs. Businesses such as delivery-, mobility-, or transport-as-a-service have become standard in many parts of the world, fulfilling on-demand requests for customers in live settings. However, it is known that many of these problems are NP-hard, and therefore both modeling and solving them accurately is a challenge. Here we focus on one such routing problem, the Ride Pooling Problem (RPP), where multiple customers can request on-demand pickups and drop-offs from shared vehicles within a fleet. The combinatorial optimization task is to optimally pool customer requests using the limited set of vehicles, akin to a small-scale flexible bus route. In this work, we propose a quadratic unconstrained binary optimization (QUBO) program and introduce efficient formulation methods for the RPP to be solved using metaheuristics, and specifically emerging quantum optimization algorithms.
许多新兴的商业服务基于资源共享或集中以供共同使用，目的是降低成本。诸如按需配送、出行即服务或运输即服务等业务在世界许多地区已成为标准模式，满足了客户在实际场景中的即时需求。然而，众所周知，其中许多问题是NP难问题，因此准确地对其进行建模和求解具有挑战性。在此，我们聚焦于一个此类路由问题，即拼车问题（RPP），在该问题中，多个客户可以请求从车队中的共享车辆进行按需接送。组合优化任务是使用有限的车辆集来最优地整合客户请求，类似于小规模的灵活公交线路。在这项工作中，我们提出了一个二次无约束二元优化（QUBO）程序，并引入了有效的公式化方法来求解使用元启发式算法，特别是新兴的量子优化算法来解决的RPP。
