论文标题
在QUBO中建模路由问题，并应用于乘车
Modeling routing problems in QUBO with application to ride-hailing
论文作者
论文摘要
许多新兴的商业服务基于共享或集合资源供共同使用，目的是降低成本。诸如交付，移动性或交通运输服务等企业在世界许多地方已成为标准，并满足了现场环境中客户的按需请求。但是，众所周知，这些问题中的许多都是NP-HARD，因此对它们进行建模和准确解决是一个挑战。在这里，我们专注于一个这样的路由问题，即乘车问题（RPP），其中多个客户可以在舰队内的共享车辆中要求按需接送和下车。组合优化任务是使用有限的车辆组合的车辆，类似于小规模的灵活巴士路线，以最佳的方式汇总客户请求。在这项工作中，我们提出了一个二次无约束的二进制优化（QUBO）程序，并引入了使用元启发式术，特别是新兴量子优化算法来求解的RPP的有效公式方法。
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.
