动态共享出行问题的量子建模：量子弯曲分解方法的发展

《Expert Systems with Applications》：Quantum modeling of the dynamic ride-sharing problem: Development of quantum benders decomposition methods

量子计算在动态 ride-sharing 问题建模与优化中的应用研究

　　

埃尔凡·阿马尼·巴尼（Erfan Amani Bani）|库鲁什·埃什吉（Kourosh Eshghi）

伊朗德黑兰沙里夫理工大学工业工程系

摘要

数学建模及其后续的优化算法开发一直是运筹学研究的核心焦点。然而，快速解决复杂模型的挑战始终推动了该领域的众多创新。几十年来，量子计算一直被提出作为二进制计算的替代方案。近年来，运筹学者特别关注将这种逻辑应用于优化问题。具体而言，已经开发了许多基于量子的优化算法；然而，使用量子变量对优化问题进行建模的研究却很少。在本文中，我们重新定义了一个实际问题——动态拼车问题，并借助量子变量对其进行了建模。基于量子变量的模型与量子算法完全兼容。随后，我们开发了基于本德斯分解（Benders’ decomposition）的量子算法。尽管受限于量子计算硬件的可用性，但从计算复杂性和解决简单示例的角度来看，这些算法的性能已经得到了验证。

引言

受第四次工业革命和互联网推动，打车服务通过连接司机和乘客成为城市交通的重要组成部分。这些服务提供了公平的价格，使双方受益，但较高的单次乘车成本限制了其市场渗透率。拼车服务允许前往相似方向的乘客共享乘车，从而降低了乘客成本并促进了环境可持续性（通过减少车辆数量）。然而，优化乘客分配和确定司机的最佳路线顺序仍然是一个挑战。传统的二进制计算算法在处理现实世界的复杂问题时效率低下，而非精确算法又存在不足。这凸显了需要更先进方法来提升拼车服务的需求。

量子计算为解决拼车问题开辟了新的途径。凭借其在更短时间内解决优化问题的潜力，量子计算为这一领域带来了新的可能性。然而，仅仅应用量子方法而不改变基于二进制的建模方式是无法取得有效结果的。因此，要实现效率最大化，建模和算法都必须过渡到量子计算领域。

动态拼车是一种高级形式，它利用实时数据和算法按需匹配司机和乘客。与传统拼车不同，动态系统会根据位置、目的地和交通状况持续优化行程匹配。这种灵活性使得具有相似路线的乘客能够共享乘车，从而提高效率并降低成本（Di Febbraro, Gattorna, & Sacco, 2013）。图1展示了该问题的一个示意图。

目前，关于打车服务的文献和行业研究涵盖了多种基于不同假设的模型，其中大多数模型仍依赖于经典计算框架中的二进制变量。针对这些模型，已经提出了多种精确、启发式和元启发式的解决方法，这些方法将在后续章节中进行讨论。这些方法的共同特点是：要么试图确定性地解决问题（这非常慢且不适用于实际应用），要么只是近似求解（尽管速度较快，但在大规模问题中准确性不足）。

该问题的量子建模涉及使用量子比特（qubits）作为决策变量，而不是传统的二进制比特。与传统比特不同，量子比特具有独特的性质，能够在模型中更细致地表示不确定性。这些特性将在第3节中详细阐述。过渡到量子计算原理需要重新配置经典建模框架。然而，仅构建基于量子的模型是不够的，还需要制定量子算法，这些算法的工作原理与传统方法有根本区别。第3节概述了量子计算与传统图灵机范式之间的关键差异。本质上，由于量子算法是在量子电路上执行的，当设计得当时，它们在处理大型复杂问题时具有显著的计算优势。

本文所讨论的主题的重要性可以归纳为三点：首先，通过量子建模探索了动态拼车问题；其次，开发了量子优化算法来解决该问题；最后，将量子优化的结果与经典优化方法的结果进行了比较。不过，本文的价值不仅限于这些方面，其意义远不止于此。

本文共分为七个部分。第2节回顾了现有的拼车问题研究以及量子优化方面的进展；第3节介绍了量子计算的基础概念，有助于更深入地理解这一问题；第4节构建了拼车问题的经典和量子模型；第5节专注于开发用于解决问题的量子算法；第6节报告了数值实验，并比较了量子算法和经典算法的性能；第7节总结了研究的主要发现并得出了结论。

章节摘录

文献综述

拼车一直是交通优化研究中的一个重要主题，其建模框架包括一对一、一对多、多对一和多对多等多种形式。研究工作从基本问题的提出发展到实际应用的实现以及新解决策略的创建。同时，量子物理学和力学（在扩展我们的认知方面起着历史性作用）也为此领域做出了贡献。

量子计算基础

本节概述了量子计算的关键要素，以便更好地理解本文探讨的量子原理。经典比特只能处于0或1这两种状态之一，而量子信息的基本单位——量子比特（qubit）则可以表示为复数空间中的单位向量。由于该空间中有无限多个单位向量，量子比特可以取无限多个可能的值。

数学建模

本节首先介绍了对动态拼车问题进行经典建模的方法。接下来，我们探讨了使用量子变量对该问题进行重新建模的方法。这里介绍的量子模型将为后续讨论的量子解决技术奠定基础。

解决方法

在接下来的解决方案部分，我们介绍了本德斯分解算法（Benders decomposition）的量子版本。经典的本德斯分解方法将混合整数优化问题分解为一个线性规划子问题和一个整数规划主问题（BnnoBRs, 1962）。如前所述，动态拼车问题被归类为NP难问题。即使仅考虑二进制变量部分，该问题仍保持NP难的性质。

数值结果

在撰写本文时，全球已有几家公司提供了量子计算资源，包括微软（Microsoft）、亚马逊（Amazon）、IBM、D-Wave和谷歌（Google）。其中一些量子系统支持量子退火（quantum annealing），这对于GAMA算法至关重要；而其他系统则能够执行变分算法（如QAOA）。需要注意的是，由于地理限制，某些量子计算资源的访问受到限制，有些提供商已停止对特定量子计算的支持。

结论

本文通过应用量子计算技术解决了动态拼车问题。我们首先使用经典方法对问题进行了建模，然后开发了包括本德斯分解、QAOA和GAMA在内的量子模型来解决主问题和线性子问题。我们利用现有的量子计算资源（如谷歌的Cirq平台和IBM的量子计算硬件）解决了一个小规模问题实例，展示了量子算法的潜力。

CRediT作者贡献声明

埃尔凡·阿马尼·巴尼（Erfan Amani Bani）：概念化、方法论设计、形式分析、软件开发、数据收集、初稿撰写、可视化。库鲁什·埃什吉（Kourosh Eshghi）：指导、验证、审稿与编辑、项目管理、资源协调。