Data_Sheet_1_A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer.pdf

The Capacitated Vehicle Routing Problem (CVRP) is an NP-optimization problem (NPO) that has been of great interest for decades for both, science and industry. The CVRP is a variant of the vehicle routing problem characterized by capacity constrained vehicles. The aim is to plan tours for vehicles to supply a given number of customers as efficiently as possible. The problem is the combinatorial explosion of possible solutions, which increases superexponentially with the number of customers. Classical solutions provide good approximations to the globally optimal solution. D-Wave's quantum annealer is a machine designed to solve optimization problems. This machine uses quantum effects to speed up computation time compared to classic computers. The problem on solving the CVRP on the quantum annealer is the particular formulation of the optimization problem. For this, it has to be mapped onto a quadratic unconstrained binary optimization (QUBO) problem. Complex optimization problems such as the CVRP can be translated to smaller subproblems and thus enable a sequential solution of the partitioned problem. This work presents a quantum-classic hybrid solution method for the CVRP. It clarifies whether the implementation of such a method pays off in comparison to existing classical solution methods regarding computation time and solution quality. Several approaches to solving the CVRP are elaborated, the arising problems are discussed, and the results are evaluated in terms of solution quality and computation time.

容量车辆路径问题（CVRP）是一种NP优化问题（NPO），数十年来，对于科学和工业领域都引起了极大的关注。CVRP是车辆路径问题的一种变体，其特征在于车辆容量受限。目标是为车辆规划行程，以尽可能高效地供应特定数量的客户。该问题在于可能解的组合爆炸，其数量随客户数量的超指数增长。经典的解决方案为全局最优解提供了良好的近似。D-Wave的量子退火器是一种旨在解决优化问题的机器。该机器利用量子效应来加速计算时间，相较于经典计算机有显著优势。在量子退火器上解决CVRP的问题，是优化问题的特定表述。为此，它必须映射到二次无约束二进制优化（QUBO）问题。复杂的优化问题，如CVRP，可以被转化为较小的子问题，从而实现分割问题的顺序求解。本研究提出了一种针对CVRP的量子-经典混合解决方案。它阐明了相较于现有的经典解决方案，在计算时间和解决方案质量方面，此类方法的实施是否具有效益。详细阐述了多种解决CVRP的方法，讨论了由此产生的问题，并从解决方案质量和计算时间两方面对结果进行了评估。