QC Ware Corp., Palo Alto, CA, USA.
Aisin Corporation, Tokyo Research Center, Chiyoda-ku, Tokyo, Japan.
Sci Rep. 2023 Mar 23;13(1):4770. doi: 10.1038/s41598-023-31765-8.
Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance which can have many variables and unwieldy objective functions. As a consequence, there is a growing body of literature that tests quantum algorithms on miniaturized versions of problems that arise in an operations research setting. Rather than taking this approach, we investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Such a problem is too complex to be fully embedded on any near-term quantum hardware or simulator; we avoid confronting this challenge by taking a hybrid workflow approach: we iteratively assign routes for trucks by generating a new binary optimization problem instance one truck at a time. Each instance has [Formula: see text] quadratic binary variables, putting it in a range that is feasible for NISQ quantum computing, especially quantum annealing hardware. We test our methods using simulated annealing and the D-Wave Hybrid solver as a place-holder in wait of quantum hardware developments. After feeding the vehicle routes suggested by these runs into a highly realistic classical supply chain simulation, we find excellent performance for the full supply chain. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest.
嘈杂的中等规模量子（NISQ）硬件几乎与具有许多变量和棘手目标函数的实际重要性的全规模优化问题完全不兼容。因此，越来越多的文献测试量子算法在操作研究环境中出现的问题的小型版本上。我们没有采取这种方法，而是研究了供应链物流中的多卡车车辆路线问题，这是一个具有重要商业价值的问题，其规模与公司在运营中使用的规模相当。这样的问题过于复杂，无法完全嵌入任何近期的量子硬件或模拟器中；我们通过采用混合工作流程方法来避免面对这一挑战：我们通过一次生成一个新的二进制优化问题实例来为卡车分配路线。每个实例都有 [公式：见文本] 个二次二进制变量，使其处于 NISQ 量子计算，特别是量子退火硬件可行的范围内。我们使用模拟退火和 D-Wave Hybrid 求解器来测试我们的方法，这些求解器是在等待量子硬件发展的过程中的占位符。在将这些运行建议的车辆路线输入到高度逼真的经典供应链模拟中后，我们发现整个供应链的性能非常出色。我们的工作提供了一组技术，可以在车辆路线之外的其他上下文中采用，以混合方式将 NISQ 设备应用于具有商业价值的大规模问题。
