在看matlab的時候發現了這篇文章https://www.frontiersin.org/articles/10.3389/fict.2019.00013/full

仔細閱讀一下。(英語渣渣，自學用)

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.

D-Wave的量子退火器是一臺旨在解決優化問題的機器。與經典計算機相比，這臺機器利用量子效應加快計算速度。在量子退火器上解決CVRP問題的問題在于優化問題的特定表述。

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.為此，必須將其映射到二次無約束二進制優化（QUBO）問題上。像CVRP這樣的復雜優化問題可以轉化為較小的子問題，從而實現分階段解決問題。這項工作提出了一種用于CVRP的量子-經典混合解決方法。它闡明了這種方法的實施是否值得，相較于現有的經典解決方法，無論是在計算時間還是解決方案質量方面。詳細闡述了解決CVRP問題的幾種方法，討論了出現的問題，并根據解決方案質量和計算時間對結果進行評估。

1.Introduction

Optimization problems can be found in many different domains of applications, be it economics and finance (Black and Litterman, 1992), logistics (Caunhye et al., 2012), or healthcare (Cabrera et al., 2011). Their high complexity engaged researchers to develop efficient methods for solving these problems (Papadimitriou and Steiglitz, 1998). With D-Wave Systems releasing the first commercially available quantum annealer in 20111, there is now the possibility to find solutions for such problems in a completely different way than classical computation does. To use D-Wave's quantum annealer the optimization problem has to be formulated as a quadratic unconstrained binary optimization (QUBO) problem (Boros et al., 2007), which is one of two input types acceptable by the machine (alternative: the Ising model?Glauber, 1963). Doing this, the metaheuristic quantum annealing seeks for the minimum of the optimization function, i.e., the best solution of the defined configuration space (McGeoch, 2014). There has been recent research about solving real world problems on a quantum annealer, like Volkswagen's Traffic Flow Optimization (Neukart et al., 2017) or the recently announced Tsunami Evacuation Optimization project by Tohoku University.

優化問題可以在許多不同的應用領域中找到，無論是經濟和金融（Black and Litterman，1992），物流（Caunhye et al.，2012）還是醫療保健（Cabrera et al.，2011）。它們的高度復雜性促使研究人員開發解決這些問題的有效方法（Papadimitriou和Steiglitz，1998）。2011 年，D-Wave Systems 發布了第一臺商用量子退火爐1，現在有可能以與經典計算完全不同的方式找到此類問題的解決方案。為了使用D-Wave的量子退火器，優化問題必須表述為二次無約束二元優化（QUBO）問題（Boros et al.， 2007），這是機器可接受的兩種輸入類型之一（替代：Ising 模型?Glauber，1963）。這樣做，元啟發式量子退火尋求優化函數的最小值，即定義的配置空間的最佳解（McGeoch，2014）。最近有關于在量子退火器上解決現實世界問題的研究，如大眾汽車的交通流優化（Neukart et al.， 2017）或東北大學最近宣布的海嘯疏散優化項目。

The paper at hand regards the Capacitated Vehicle Routing Problem (CVRP), an NP-optimization problem that plays a major role in common operations research and is excessively studied since its proposal in?Dantzig and Ramser (1959). The classic CVRP can be described as the problem of designing optimal routes from one depot to a number of geographically scattered customers subject to some side constraints (see?Figure 1). It can be formulated as follows:

本文討論了有能力車輛路徑問題（CVRP），這是一個np優化問題，在普通作戰研究中起著重要作用，自Dantzig和Ramser（1959）提出以來得到了廣泛的研究。經典的CVRP可以被描述為設計從一個倉庫到許多地理上分散的客戶的最優路線的問題，但會受到一些側邊的約束（見圖1）。其可表述如下：

?圖1所示，CVRP和兩階段啟發式的概述:(A)初始狀態有9個客戶和1個倉庫(B)聚類階段產生3個集群(C)路徑由每個集群的最短路徑確定。

Let?G?= (V, E) be a graph with?V?= {1, …,?n} being a set of vertices representing?n?customer locations with the depot located at vertex 1 and?E?being a set of undirected edges. With every edge (i, j) ∈?E, i?≠?j?a non-negative cost?cij?is associated. This cost may, for instance, represent the (geographical) distance between two customers?i?and?j. Furthermore, assume there are?m?vehicles stationed at the depot that have the same capacity?Q. In addition, every customer has a certain demand?q?(Laporte, 1992). The CVRP consists of finding a set of vehicle routes such that

? each customer in?V?\ {1} is visited exactly once by exactly one vehicle;

? all routes start and end at the depot;

? the sum of customer demand within a route does not exceed the vehicles' capacity;

? the sum of costs of all routes is minimal given the constraints above;

設?G?= （V， E） 是一個圖，V ={1，…，n}是代表n個客戶位置的頂點集合，其中倉庫位于頂點1,E是一組無向邊。對于每條邊 （i， j）?∈ E，i?≠?j?一個非負成本?cij是關聯的。例如，此成本可能表示兩個客戶?i?和?j?之間的（地理）距離。此外，假設有?m?輛車輛駐扎在倉庫中，其容量為 Q。此外，每個客戶都有一定的需求q（Laporte，1992）。CVRP 包括查找一組車輛路線，以便

??V?\ {1} 中的每個客戶正好被一輛車訪問一次;

? 所有路線的起點和終點都在停車場;

? 路線內的客戶需求總和不超過車輛的容量;

? 鑒于上述限制，所有路線的成本總和是最小的;

To solve the CVRP on D-Wave's quantum annealer, the formulated QUBO problem has to be mapped to the hardware. However, quantum computation compared to classical computation is still in its infancy and one of the major problems is that quantum hardware is limited regarding the number of quantum bits (qubits) and their connectivity on the chip. Generally, this leads to difficulties in mapping large QUBO problems to the hardware.為了解決D-Wave量子退火機上的CVRP問題，必須將公式化的QUBO問題映射到硬件上。然而，與經典計算相比，量子計算仍處于起步階段，其中一個主要問題是量子硬件在量子比特(量子位)數量及其在芯片上的連接方面受到限制。通常，這會導致將大型QUBO問題映射到硬件的困難。

With this paper we present an intuitive way to split the CVRP into smaller optimization problems by taking advantage of a classical 2-Phase-Heuristic (Laporte and Semet, 2002), see?Figure 1. This heuristic divides the CVRP into two phases, the clustering phase and the routing phase. The clustering phase itself can be mapped to the NP-complete Knapsack Problem (KP) (Karp, 1972), which tries to pack different sized items (here: customers) into capacity restricted knapsacks (here: vehicles). Doing this, the sum of the objective values of the items in a knapsack should be maximized, i.e., the euclidean distance between customers assigned to a vehicle should be minimized. The routing phase can be represented by the NP-hard Travelling Salesman Problem (TSP) (Biggs, 1986). Thus, the minimal tour in which all customers of a cluster are visited once is sought. Doing this, the tour starts and ends in one place, i.e., the depot.在本文中，我們提出了一種直觀的方法，通過利用經典的兩階段啟發式(Laporte和Semet, 2002)，將CVRP拆分為更小的優化問題，參見圖1。該啟發式算法將CVRP劃分為兩個階段，即聚類階段和路由階段。聚類階段本身可以映射到np完備的背包問題(KP) (Karp, 1972)，(6 封私信 / 56 條消息) 計算機科學中的「背包問題(Knapsack problem)」是什么，它有什么應用場景？ - 知乎 (zhihu.com)它試圖將不同大小的物品(這里是客戶)打包到容量有限的背包(這里是車輛)中。這樣做，一個背包中物品的客觀價值的總和應該是最大的，也就是說，分配給車輛的顧客之間的歐幾里得距離應該是最小的。路由階段可以用NP-hard旅行商問題(TSP)來表示(Biggs, 1986)。因此，尋求一次訪問集群中所有客戶的最小行程。這樣，旅行就在一個地方開始和結束，即倉庫。

Figure 1?shows a CVRP example with the 2-Phase-Heuristic. First the customers are grouped into clusters (b) before efficient vehicle routes in each cluster are searched (c).展示了一個帶有兩階段啟發式的CVRP示例。首先將顧客分組(b)，然后在每個分組中搜索有效的車輛路線(c)。

In this paper we investigate different quantum-classic hybrid approaches to solve the CVRP, expound their difficulties in finding good solutions, and finally propose a hybrid method based on the 2-Phase-Heuristic to solve the CVRP using D-Wave's quantum annealer. We map the optimization problems to a QUBO problem, and analyze performance from an application-specific perspective by using large benchmark datasets.

本文研究了求解CVRP的不同量子經典混合方法，闡述了它們在求解CVRP時存在的困難，最后提出了一種基于兩相啟發式的混合方法，利用D-Wave的量子退火器求解CVRP。我們將優化問題映射為QUBO問題，并通過使用大型基準數據集從特定于應用程序的角度分析性能。

The paper is structured as follows: section 2 gives an introduction to quantum annealing and the common QUBO problem. A brief overview of existing methods for solving the CVRP is given in section 3. In section 4, two approaches for solving the CVRP are briefly discussed before the concept of our hybrid method is presented. Section 5 first introduces the test setup, and subsequently presents and discusses the results with regard to solution quality and computational performance on commonly used CVRP datasets. Finally, we conclude this paper in section 6.

本文的結構如下:第2節介紹量子退火和常見的QUBO問題。第3節給出了解決CVRP的現有方法的簡要概述。在第4節中，在提出混合方法的概念之前，簡要討論了解決CVRP的兩種方法。第5節首先介紹了測試設置，隨后介紹并討論了在常用CVRP數據集上關于解決方案質量和計算性能的結果。最后，我們在第六節對本文進行總結。

2. Quantum Annealing on D-Wave Processor

Quantum annealing in general is a metaheuristic for solving complex optimization problems (Kadowaki and Nishimori, 1998). D-Wave's quantum annealing algorithm is implemented in hardware using a framework of analog control devices to manipulate a collection of quantum bit (qubit) states according to a time-dependent Hamiltonian, denoted?H(t), shown in Equation (1).

一般來說，量子退火是解決復雜優化問題的元啟發式方法(Kadowaki和Nishimori, 1998)。D-Wave的量子退火算法是在硬件中實現的，使用模擬控制設備框架來根據與時間相關的哈密頓量(表示為H(t))來操縱量子比特(qubit)狀態的集合，如式(1)所示。

The basic process of quantum annealing is to physically interpolate between an initial Hamiltonian?HI?with an easy to prepare minimal energy configuration (or ground state), and a problem Hamiltonian?HP, whose minimal energy configuration is sought that corresponds to the best solution of the defined problem. This transition is described by an adiabatic evolution path which is mathematically represented as function?s(t) and decreases from 1 to 0 (McGeoch, 2014). If this transition is executed sufficiently slow, the probability to find the ground state of the problem Hamiltonian is close to 1 (Albash and Lidar, 2018).

量子退火的基本過程是在具有易于制備的最小能量構型(或基態)的初始哈密頓量HI和尋找與所定義問題的最佳解對應的最小能量構型的問題哈密頓量HP之間進行物理插值。這種轉變由絕熱演化路徑描述，該路徑在數學上表示為函數s(t)，從1到0遞減(McGeoch, 2014)。如果這種轉換執行得足夠慢，那么找到問題哈密頓量的基態的概率接近于1 (Albash和Lidar, 2018)。

The just described concept of adiabatic quantum computing is the source of inspiration for the design of D-Wave's quantum annealing hardware. While the machine's functioning is based on following an adiabatic evolution path, the dynamics describing its working is not adiabatic. This is because the machine is strongly coupled to the environment resulting in the performance being affected by dissipative effects (Marshall et al., 2017). Nonetheless, the hardware is known to be capable of solving a specific optimization problem called a quadratic unconstrained binary optimization (QUBO) problem (Boros et al., 2007). QUBO is a unifying model which can be used for representing a wide range of combinatorial optimization problems. However, in order to use quantum annealing on D-Wave's hardware the CVRP has to be formulated as a QUBO problem. The functional form of the QUBO the quantum annealer is designed to minimize is:

剛才描述的絕熱量子計算概念是D-Wave量子退火硬件設計的靈感來源。雖然機器的功能是基于遵循絕熱演化路徑，但描述其工作的動力學不是絕熱的。這是因為機器與環境強耦合，導致性能受到耗散效應的影響(Marshall等人，2017)。盡管如此，已知硬件能夠解決稱為二次無約束二進制優化(QUBO)問題的特定優化問題(Boros等人，2007)。QUBO是一種統一的模型，可用于表示廣泛的組合優化問題。然而，為了在D-Wave的硬件上使用量子退火，CVRP必須被表述為QUBO問題。量子退火爐設計的QUBO的功能形式最小化為:

with?x?being a vector of binary variables of size?n, and?Q?being an?n?×?n?real-valued matrix describing the relationship between the variables. Given the matrix?Q, the annealing process tries to find binary variable assignments to minimize the objective function in Equation (2).

其中x是大小為n的二元變量的向量，Q是描述變量之間關系的n × n實值矩陣。給定矩陣Q，退火過程試圖找到二值變量賦值以最小化式(2)中的目標函數。

The quantum processing unit (QPU) is a physical implementation of an undirected graph with qubits as vertices and couplers as edges between them. These qubits are arranged according in a so-called chimera graph, as illustrated in?Figure 2. In relation to the QUBO problem, each qubit on the QPU represents such a QUBO variable and couplers between qubits represent the costs associated with qubit pairs, mathematically described in matrix?Q. If the problem structure can not be embedded directly to the chimera graph, auxiliary qubits may be introduced to augment the available couplings.

量子處理單元(QPU)是一個無向圖的物理實現，量子比特作為頂點，耦合器作為它們之間的邊。這些量子位按照所謂的嵌合體圖排列，如圖2所示。對于QUBO問題，QPU上的每個量子位代表這樣一個QUBO變量，量子位之間的耦合器代表與量子位對相關的成本，在數學上用矩陣q描述。如果問題結構不能直接嵌入到嵌合體圖中，可以引入輔助量子位來增加可用的耦合。

一個嵌合拉圖的結構摘錄。完整的2048量子位圖擴展到一個8個量子位群的16×16格。圖參考Biswas等人。

If—like in this paper—large data sets are used, the size of the resulting QUBO problem may exceed the limited number of available qubits on the QPU and the problem cannot be put on the chip altogether anymore. For this case, D-Wave provides a tool called QBSolv that splits the QUBO into smaller components and solves them sequentially on the D-Wave hardware3. A detailed view on the QBSolv algorithm is given in section 5.1.

如果像本文中那樣使用大型數據集，那么由此產生的QUBO問題的大小可能會超過QPU上可用量子位的有限數量，并且問題無法完全放在芯片上。對于這種情況，D-Wave提供了一個名為QBSolv的工具，它將QUBO拆分為更小的組件，并在D-Wave硬件上依次解決它們。第5.1節給出了QBSolv算法的詳細視圖。

In this paper we used the D-Wave 2000Q model located in Vancouver, Canada, and we accessed the machine using D-Wave's cloud interface. The instance at hand has got a working graph with 2,038 qubits and 5,955 couplers out of the full graph with 2,048 qubits and 6,016 couplers.在本文中，我們使用位于加拿大溫哥華的D-Wave 2000Q模型，我們使用D-Wave的云接口訪問機器。當前實例的工作圖包含2,038個量子位和5,955個耦合器，而完整圖包含2,048個量子位和6,016個耦合器。

3. Related Work

Over the last decades several families of heuristics have been proposed for solving the CVRP. They can be divided into construction heuristics, improvement heuristics and metaheuristics (Laporte and Semet, 2002).

在過去的幾十年里，人們提出了幾種啟發式方法來解決CVRP問題。它們可以分為構建啟發式、改進啟發式和元啟發式(Laporte和Semet, 2002)。

Construction heuristics?try to generate a good solution gradually. In every step, they insert customers into partial tours or combine sub-tours considering some capacities and costs to generate a complete solution. One of the most fundamental construction heuristics is the Clarke and Wright savings algorithm (Clarke and Wright, 1964), which first constructs a single tour for each customer, calculates the saving that can be obtained by merging those single customer tours, and iteratively combines the best sub-tours until no saving can be obtained anymore.

構建啟發式試圖逐步產生一個好的解決方案。在每一步中，他們將客戶插入到部分行程中，或者結合考慮一些容量和成本的子行程，以生成完整的解決方案。最基本的構造啟發式方法之一是Clarke and Wright節省算法(Clarke and Wright, 1964)，該算法首先為每個客戶構建一個單獨的行程，計算合并這些單個客戶行程所能獲得的節省，并迭代地組合最佳子行程，直到無法再獲得節省。

Improvement heuristics?try to iteratively enhance a given feasible solution, which is often generated by a construction heuristic. A common methodology is to replace or swap customers between sub-tours taking capacity constraints into account. Popular improvement methods can be found in?Lin (1965)?and?Or (1976).?

改進啟發式嘗試迭代地增強給定的可行解決方案，這通常是由構造啟發式產生的。一種常見的方法是在考慮容量限制的情況下在子旅行之間替換或交換客戶。流行的改進方法可以在Lin(1965)和Or(1976)中找到。

Metaheuristics?can be thought of as top-level strategies which guide local improvement operators to find a global solution. Gro?r et al. describe a library of local search heuristics for the (C)VRP (Gro?r et al., 2010). In addition, Crispin and Syrichas propose a classical quantum annealing metaheuristic for vehicle scheduling (Crispin and Syrichas, 2013). To approximate quantum annealing on a classical computer, they use a stochastic variant called Path-Integral Monte Carlo (PIMC) to simulate the quantum fluctuations of a quantum system. In our work, the quantum annealing hardware is responsible for that. However, the complexity exists in mapping the CVRP to a format readable by the hardware.

元啟發式可以被認為是指導局部改進操作者找到全局解決方案的頂層策略。Gro?r等人描述了(C)VRP的本地搜索啟發式庫(Gro?r等人，2010)。此外，Crispin和Syrichas提出了一種經典的量子退火元啟發式車輛調度方法(Crispin和Syrichas, 2013)。為了在經典計算機上近似量子退火，他們使用一種稱為路徑積分蒙特卡羅(PIMC)的隨機變體來模擬量子系統的量子波動。在我們的工作中，量子退火硬件負責這一點。但是，將CVRP映射為硬件可讀的格式存在復雜性。

One of the most important classical 2-Phase-Heuristics is the Sweep algorithm (Gillett and Miller, 1974), where feasible clusters are formed by rotating a ray centered at the depot. After that the TSP is solved for each cluster. Fisher and Jaikumar also tried to solve the VRP with a cluster-first, route-second algorithm (Fisher and Jaikumar, 1981). They formulated a Generalized Assignment Problem (GAP) instead of using a geometry based method to form the clusters. Bramel and Simchi-Levi described a 2-Phase-Heuristic where the seeds were determined by solving capacitated location problems and the remaining vertices were gradually included into their allotted route in a second stage (Bramel and Simchi-Levi, 1995).最重要的經典兩階段啟發式算法之一是掃描算法(Gillett和Miller, 1974)，其中可行的集群是通過旋轉以倉庫為中心的射線形成的。然后求解每個集群的TSP。Fisher和Jaikumar也嘗試用集群優先，路由第二的算法來解決VRP (Fisher和Jaikumar, 1981)。他們提出了一個廣義分配問題(GAP)，而不是使用基于幾何的方法來形成聚類。Bramel和Simchi-Levi描述了一種兩階段啟發式算法，其中通過求解有能力定位問題來確定種子，剩余的頂點在第二階段逐漸被納入分配的路線(Bramel和Simchi-Levi, 1995)。

However, there are similar investigations performed by the quantum computing community. In?Rieffel et al. (2015), the authors have studied the effectiveness of a quantum annealer in solving small instances within families of hard operational planning problems under various mappings to QUBO problems and embeddings. While their study did not produce results competitive with state-of-the-art classical approaches, they derive insights from the results, useful for the programming and design of future quantum annealers. In our work we investigate larger routing problem instances using a classical quantum hybrid method and state the effectiveness and efficiency.?然而，量子計算社區也進行了類似的調查。在Rieffel et al.(2015)中，作者研究了量子退火器在各種映射到QUBO問題和嵌入的情況下解決硬操作計劃問題族中的小實例的有效性。雖然他們的研究沒有產生與最先進的經典方法競爭的結果，但他們從結果中獲得了見解，對未來量子退火爐的編程和設計有用。在我們的工作中，我們使用經典的量子混合方法研究了較大的路由問題實例，并說明了該方法的有效性和效率。

In?Tran et al. (2016), a tree-search based quantum-classical framework is presented. The authors use a quantum annealer to sample from the configuration space of a relaxed problem to obtain strong candidate solutions and then apply a classical processor that maintains a global search tree. They empirically test their algorithm and compare the variants on small problem instances from three scheduling domains. In general, one can see that many approaches have got a hybrid structure. That is, classical bottlenecks are outsourced to quantum computing devices that iteratively perform local quantum searches (Haddar et al., 2016;?Tran et al., 2016;?Chancellor, 2017).Tran等人(2016)提出了一種基于樹搜索的量子經典框架。利用量子退火器從松弛問題的組態空間中進行采樣，得到強候選解，然后應用經典處理器維護全局搜索樹。他們對算法進行了實證測試，并在三個調度領域的小問題實例上比較了算法的變體。一般來說，我們可以看到很多方法都有混合結構。也就是說，經典瓶頸被外包給迭代執行局部量子搜索的量子計算設備(Haddar等人，2016;Tran et al.， 2016;總理,2017)。

4. Concept of Hybrid Solution Method

There are numerous heuristics in the literature for solving the CVRP that all have an iterative approach. This makes it difficult to map them into a QUBO problem to be solved on a quantum annealer. In addition, there exists the classical 2-Phase-Heuristic that separates the CVRP into a clustering phase and a routing phase. Both phases can be seen as detached optimization problems, the Knapsack Problem (KP) with an additional minimization of distances between customers and the Travelling Salesman Problem (TSP), respectively. This division allows the mapping of the problems to one or two QUBO matrices.

文獻中有許多用于求解 CVRP 的啟發式方法，它們都具有迭代方法。這使得很難將它們映射到要在量子退火器上求解的 QUBO 問題。此外，還存在經典的 2 階段啟發式方法，將 CVRP 分為聚類階段和路由階段。這兩個階段都可以看作是分離的優化問題，分別是背包問題（KP）和旅行推銷員問題（TSP），前者是客戶之間距離的最小化。這種劃分允許將問題映射到一個或兩個 QUBO 矩陣。

?We have investigated three different approaches for the 2-Phase-Heuristic using a quantum annealer, see?Figure 3. The insights of the preliminary exploration will be given in section 4.1. The concept of the most suitable approach—called Hybrid Solution (HS)—will be presented in detail in sections 4.2 and 4.3.

我們研究了使用量子退火器進行 2 相啟發式的三種不同方法，見圖 3。初步探索的見解將在第4.1節中給出。最合適的方法的概念（稱為混合解決方案 （HS））將在 4.2 和 4.3 節中詳細介紹。

?4.1Preliminary Exploration

第一種基于兩相啟發式的方法將CVRP劃分為兩個獨立的優化問題（圖3中的Q2Q）。聚類階段可以看作是背包問題，在要分組的客戶之間有額外的距離最小化。路由階段可以簡化為熟悉的旅行推銷員問題。因此，可以將 CVRP 拆分為兩個單獨的 QUBO 問題并按順序執行它們。路由階段的 QUBO 公式與 Lucas （2014） 中提出的 TSP 表示完全對應。然而，聚類階段的 QUBO 公式是對 Lucas （2014） 所述的背包問題的改編。它由 H = HA + HB + HC 組成，其中?

As the CVRP usually needs to fill several routes?m?(i.e., backpacks) with customers, the original formulation of?Lucas (2014), which takes only one backpack into account, has been adapted accordingly with?HA?(Equation 3). The first term of?HA?ensures that the backpack has only one capacity constraint. That is, as soon as two or more?yn?variables are set to 1, a penalty value?X?(very high value) is added to the solution what declares it as bad or invalid. The second term, in turn, ensures that the sum of packed objects does not exceed the specified backpack capacity from the first term.

由于CVRP通常需要用客戶填充幾條路線（即背包），因此Lucas（2014）的原始公式僅考慮一個背包，已相應地調整為HA（公式3）。HA 的第一個術語確保背包只有一個容量限制。也就是說，一旦將兩個或多個 yn 變量設置為 1，就會向解決方案中添加一個懲罰值 X（非常高的值），該值聲明它為錯誤或無效。反過來，第二項確保包裝物品的總和不超過第一項規定的背包容量。

As soon as the difference is not equal to 0, the squaring and the penalty value?A?also classify the solution as bad.?HB?(Equation 4) guarantees that every object or customer must be packed in just one backpack or route. Finally,?HC?(Equation 5) is an additional optimization function that tries to improve the clustering by grouping the customers that are close to each other. To do this, the distances between the customers of a cluster are summed up.

一旦差值不等于 0，平方和懲罰值 A 也會將解歸類為壞解。HB（公式 4）保證每個物品或客戶都必須裝在一個背包或路線中。最后，HC（公式 5）是一個額外的優化函數，它試圖通過對彼此接近的客戶進行分組來改進聚類。為此，需要將集群的客戶之間的距離相加。

Duv?corresponds to the Euclidean distance between customers?u?and?v. The solution with the shortest summed distances within the clusters is the optimum of a classical clustering. The penalty value?X?must be greater than?A?and?A?greater than?C. This ensures that in fact only one capacity limit per vehicle is set and each customer is assigned to exactly one vehicle. Experimental tests for different CVRP datasets and problem sizes yielded the following correlation of the penalty values:?X?=?A2?and?A?=?max(Duv) * number of customers.?C?corresponds to an edge weighting of the clustering, which is used to optimize the clustering.

Duv 相當于客戶 u 和 v 之間的歐氏距離。簇內距離總和最短的解就是經典聚類的最優解。懲罰值 X 必須大于 A，而 A 又必須大于 C。這就確保了事實上每輛車只設置了一個容量限制，并且每個客戶都被精確分配到一輛車上。針對不同的 CVRP 數據集和問題規模進行的實驗測試得出了以下懲罰值的相關性： X = A^2?和 A = max(Duv) * 客戶數量。C 相當于聚類的邊緣權重，用于優化聚類。第二種方法試圖同時而不是按順序解決每個 CVRP 子問題（圖 3 中的 Q1Q）。為此，必須將這些子問題映射為一個單一的 QUBO 問題。這個 QUBO 問題的整體解決方案如下：

?HA?corresponds to Equation (3) of the first approach. The first term also ensures that the?m?vehicles have a clear capacity constraint while the second term ensures that the vehicle capacity determined by the first term is not exceeded by the summed customer demand.

HA 相當于第一種方法的公式 (3)。第一項還確保 m 輛車有明確的容量限制，而第二項則確保第一項確定的車輛容量不超過客戶需求總和。

HB′?(等式 6）與第一種方法的等式 4 相似。不過，這里還需要考慮路線中的位置，因為在這種方法中，集群和集群內的路線都是同時解決的。

Thus, this term means that a customer can only be assigned exactly one route with exactly one position within this route.?HC?corresponds to Equation (5) of the first approach and is responsible for optimizing the clustering. That is, we try to assign customers who have a small distance from each other to a route.?HD?(Equation 7) ensures that each position?j?can only be assigned to exactly one customer α and one route?k. Finally, the shortest route within a cluster must be found. This is optimized with?HE?(Equation 8). Since each position is unique across all routes, the route subdivision can be neglected here. It should also be noted that in the Q1Q approach the depot needs to be mapped to each cluster in order to properly execute the TSP in each cluster. HF causes the depots that were inserted multiple times in the dataset to be assigned to different clusters each, where?d?corresponds to the number of depots or the number of vehicles.

因此，這個術語意味著一個客戶只能被分配到一條路線，而在這條路線中只能有一個位置。HC 與第一種方法的公式 (5) 相對應，負責優化聚類。也就是說，我們盡量將彼此距離較小的客戶分配到一條線路上。HD（等式 7）確保每個位置 j 只能分配給一個客戶 α 和一條線路 k。這可以通過 HE 進行優化（公式 8）。由于每個位置在所有路線中都是唯一的，因此可以忽略路線細分。還應注意的是，在 Q1Q 方法中，為了在每個集群中正確執行 TSP，需要將車廠映射到每個集群。高頻會導致在數據集中多次插入的車廠分別被分配到不同的集群，其中 d 相當于車廠數量或車輛數量。

However, in the second approach we observed that both optimization functions (HC?and?HE) seemed to hinder each other. Neglecting the clustering optimization function (HC) led to valid routes inside the clusters, but at the same time the clusters were very sparse. The other way round, i.e., neglecting the routing optimization function?HE, led to dense clusters but also to invalid routes inside the clusters. In summary, both efforts lead to invalid or unusable solutions.

然而，在第二種方法中，我們發現兩個優化功能（HC 和 HE）似乎相互阻礙。忽略集群優化功能（HC）會導致集群內的路線有效，但同時集群非常稀疏。反之，即忽略路由優化函數 HE，則會導致集群密集，但同時集群內的路由也無效。總之，這兩種方法都會導致無效或無法使用的解決方案。

The third approach (HS in?Figure 3) as a candidate for a CVRP solution method combines the positive aspects of the previous mentioned approaches. To achieve this, the clustering phase (KP) is solved using a classical algorithm while the routing phase (TSP) is mapped to a QUBO problem in order to solve it on the quantum annealer. The following Subsections will go into detail.作為 CVRP 解決方案候選方法的第三種方法（圖 3 中的 HS）結合了前幾種方法的優點。為此，聚類階段（KP）采用經典算法求解，而路由階段（TSP）則映射為 QUBO 問題，以便在量子退火器上求解。以下分節將詳細介紹。

4.2?Hybrid Solution—Clustering Phase(混合解決方案-聚類階段)

The clustering phase of the hybrid solution method we propose is inspired by?Shin and Han (2011). Based on their work, we add a characteristics called?clustering core point parameter?that will be presented below. The clustering phase can be subdivided: (1) cluster generation and (2) cluster improvement.

我們提出的混合求解方法的聚類階段受到了 Shin 和 Han（2011 年）的啟發。在他們工作的基礎上，我們添加了一個稱為聚類核心點參數的特征，將在下文中介紹。聚類階段可細分為：（1）聚類生成和（2）聚類改進。

Within the?cluster generation?the core stop of a cluster, i.e., the first customer in a cluster, is chosen.?Koenig (1995)?propose to select the core stop either based on the maximum demand of the customers, or based on the largest distance to the depot. The motivation behind choosing the customer with the highest demand is the assumption that this one is the most critical customer in relation to the vehicles' capacity constraint. After selecting that particular customer, the vehicle can be filled with goods for customers having a smaller demand.

在集群生成過程中，選擇集群的核心站點，即集群中的第一個客戶。Koenig （1995）建議根據客戶的最大需求量或與倉庫的最大距離來選擇核心站。之所以選擇需求量最大的客戶，是因為假定該客戶是與車輛運力限制相關的最關鍵客戶。選擇該客戶后，車輛可為需求量較小的客戶裝滿貨物。

The motivation behind choosing the customer with the largest distance to the depot is the assumption that this one is the most critical customer in relation to the routes' length constraint and that other customers may be supplied while approaching or receding that particular customer. Once the core stop?v?of a cluster has been selected, the geometric center CC(mk) of cluster?mk?is calculated using

之所以選擇與車廠距離最大的客戶，是因為假設該客戶是與路線長度限制相關的最重要客戶，而且在接近或離開該客戶時，可能會向其他客戶提供服務。一旦選定了集群的核心站點 v，集群 mk 的幾何中心 CC(mk) 的計算公式為

?

the customer with the smallest distance to the cluster center is selected from the set of unclustered customers and added to the cluster. After the cluster center is recalculated the steps are repeated until the demand of a customer to be added would exceed the vehicle's capacity. If this is the case, a new core stop is selected based on the previously explained criteria and the still unclustered customers are assigned to the new cluster. This procedure stops when each customer has been assigned to a cluster.

從未分類的客戶集合中選出與集群中心距離最小的客戶，并將其添加到集群中。重新計算集群中心后，重復上述步驟，直到要添加的客戶需求超過車輛的容量。如果出現這種情況，就會根據之前說明的標準選擇一個新的核心站，并將仍未聚類的客戶分配到新的聚類中。當每個客戶都被分配到一個群組后，該程序就會停止。

Once the clusters have been generated, the?cluster improvement?is executed to enhance the clusters. This step assigns a customer?vi?belonging to cluster?mk?to another cluster?mj, if that would reduce the distance to the cluster center, i.e., if the distance to?CC(mj) is smaller than the distance to?CC(mk). However, assigning a customer to a new cluster must not violate the capacity limitation. If the reassignment is possible and valid,?CC(mj) and?CC(mk) are recalculated and the improvement process begins again. The improvement step terminates if it is not possible to assign a customer to another cluster or when a certain stop criterion is reached (e.g., number of iterations).

聚類生成后，將執行聚類改進以增強聚類。這一步會將屬于簇 mk 的客戶 vi 分配到另一個簇 mj，前提是這樣能減少與簇中心的距離，即與 CC(mj) 的距離小于與 CC(mk) 的距離。但是，將客戶分配到新的群組不得違反容量限制。如果重新分配可行且有效，則重新計算 CC(mj) 和 CC(mk)，并重新開始改進過程。如果無法將客戶分配到另一個群組，或達到某個停止標準（如迭代次數），則改進步驟終止。

4.3?Hybrid Solution—Routing Phase(混合解決方案--路由階段)

After the clustering phase is completed, the goal is now to find the shortest route inside each cluster. Thus, the Travelling Salesman Problem (TSP) is executed for every generated cluster. The TSP can be reduced to the Hamiltonian Cycle Problem (HPC), which can be formulated as QUBO problem as follows (Lucas, 2014):

聚類階段完成后，現在的目標是找到每個聚類內部的最短路徑。因此，每個生成的集群都要執行旅行推銷員問題（TSP）。TSP 可以簡化為漢密爾頓循環問題（Hamiltonian Cycle Problem，HPC），可表述為如下 QUBO 問題（Lucas，2014）：

The binary variable?xi, j?is 1 if the customer with index?i?is located at position?j?in the Hamiltonian Cycle. The first term (constraint) requires that each customer must occur only once in the cycle, while the second term enforces that each position in the cycle must be assigned to exactly one customer. This defines the order of the customers within the tour. The squared differences of these terms ensure that exactly one customer has a unique position in the tour. Otherwise, a high penalty value?A?would be added to the solution energy, which states the solution itself as suboptimal or rather invalid.?

如果索引為 i 的客戶位于漢密爾頓循環中的位置 j，則二進制變量 xi, j 為 1。第一項（約束條件）要求每位顧客在循環中只能出現一次，而第二項則強制要求循環中的每個位置必須分配給一位顧客。這就定義了客戶在巡回中的順序。這些項的平方差確保了恰好有一位顧客在巡回中擁有唯一的位置。否則，解的能量中就會增加一個高懲罰值 A，從而說明解本身是次優的，或者說是無效的。

?Although different penalties are possible for the two terms, we choose the same value because we consider both constraints equally important. The third term ensures that the order of customers found is possible. That is, if?xu, j?and?xi, j+1?are both 1 and (ui) ??E?with?E?being the set of edges between the nodes representing the customers, then the penalty value?A?should also state the solution invalid (Lucas, 2014). In this work we have evaluated our algorithm using CVRP/TSP datasets with fully meshed vertices, i.e., customers are connected with undirected edges. That is why the third term can be neglected.雖然這兩個項可能有不同的懲罰，但我們選擇了相同的值，因為我們認為這兩個約束條件同樣重要。第三項確保找到的客戶順序是可能的。也就是說，如果 xu, j 和 xi, j+1 均為 1 且 (ui) ? E（E 是代表客戶的節點之間的邊集），那么懲罰值 A 也應說明解決方案無效（Lucas，2014 年）。在這項工作中，我們使用全網格頂點的 CVRP/TSP 數據集對算法進行了評估，即客戶是通過無向邊連接的。因此第三項可以忽略。

為了找到長度最短的哈密頓周期，需要使用以下最小化函數：

Here?Dui?is the euclidean distance between the customers?u?and?i. The minimization function sums all costs of the edges between successive customers. The total solution for the TSP QUBO problem is then composed of:Dui 是客戶 u 和 i 之間的歐氏距離。最小化函數將連續客戶之間邊的所有成本相加。因此，TSP QUBO 問題的總解由以下部分組成：

The penalty value?B?must be chosen sufficiently small so that it does not violate the constraint?HA. A possible choice would be 0 <?B?·?max(Dui) <?A?(Lucas, 2014). With?B?= 1,?A?has to be chosen larger than the greatest distance between two customers. In our experiments?B?was set to 1 and?A?was set to?n?·?max(Dui) with?n?being the number of customers.

懲罰值 B 必須選得足夠小，這樣才不會違反 HA 約束。可能的選擇是 0 < B - max(Dui) < A（盧卡斯，2014 年）。當 B = 1 時，A 必須大于兩個客戶之間的最大距離。在我們的實驗中，B 被設為 1，A 被設為 n - max(Dui)，n 為客戶數。

By multiplying the QUBO formulas, one obtains the coefficients for the QUBO problem matrix which can be written as a lower (or upper) triangular matrix to be mapped to the quantum annealing processor.?Figure 4?shows an excerpt of an exemplary QUBO problem in which only the coefficients are entered for simplification. As soon as several coefficients are noted on one cell of the matrix they must be added. In addition, every coefficient is multiplied with the penalty value?A?and the distance is multiplied with penalty value?B.

通過與 QUBO 公式相乘，可以得到 QUBO 問題矩陣的系數，該矩陣可以寫成下（或上）三角矩陣，并映射到量子退火處理器中。圖 4 顯示了一個示例 QUBO 問題的摘錄，其中只輸入了系數以簡化問題。一旦矩陣的一個單元格中出現多個系數，就必須將其相加。此外，每個系數都要乘以懲罰值 A，距離則乘以懲罰值 B。

?5. Evaluation

In this section we present the results of the hybrid solving method with regards to solution quality and computational results. First the preliminaries for the test setup are given, then the test results are shown.在本節中，我們將介紹混合求解方法在求解質量和計算結果方面的成果。首先介紹測試設置的初步情況，然后展示測試結果。

5.1Preliminaries

As already mentioned, the D-Wave quantum annealer can be regarded as a discrete optimization machine that accepts problems in QUBO formulation. The QUBO problem matrix increases with the problem size, i.e., with the number of problem variables used. For the TSP?n2?logical variables, with?n?being the number of customers, have to be used to describe it as a QUBO problem (see section 4.3). These variables have to be mapped to the qubits and the logical links between them to the couplers of the physical QPU. Because of the almost fully meshed dependencies between the logical variables it is not possible that the logical problem structure matches the physical one. For such issues D-Wave provides a minor embedding technique to find a valid embedding to the hardware, as described in?Cai et al. (2014). We have used this technique4?in combination with D-Wave's QBSolv tool to fit our large QUBO problems to the physical hardware.
如前所述，D-Wave 量子退火器可被視為一種離散優化機器，可接受 QUBO 格式的問題。QUBO 問題矩陣隨著問題規模（即使用的問題變量數量）的增加而增加。就 TSP 而言，必須使用 n2 個邏輯變量（n 表示客戶數量）才能將其描述為 QUBO 問題（見第 4.3 節）。這些變量必須映射到量子比特，而量子比特之間的邏輯鏈路必須映射到物理 QPU 的耦合器。由于邏輯變量之間存在幾乎完全網狀的依賴關系，因此邏輯問題結構不可能與物理問題結構相匹配。針對此類問題，D-Wave 提供了一種次要嵌入技術，以找到對硬件的有效嵌入，如 Cai 等人（2014 年）所述。我們將該技術4 與 D-Wave 的 QBSolv 工具結合使用，將大型 QUBO 問題與物理硬件相匹配。
QBSolv splits the QUBO into smaller components (subQUBOs) of a predefined subproblem size5, which are then solved independently of each other. This process is executed iteratively as long as there is an improvement and it can be defined using the QBSolv parameter?num_repeats. This parameter determines the number of times to repeat the splitting of the QUBO problem matrix after finding a better sample. With doing so, the QUBO matrix is split into different components using a classical tabu search heuristic in each iteration. QBSolv can be used in a completely classical way to solve the subQUBOs or as a quantum-classic hybrid method by solving the single subQUBOs on the quantum annealer.

QBSolv 將 QUBO 分解成預定義子問題大小5 的較小部分（子 QUBO），然后獨立求解。只要有改進，這個過程就會反復執行，可以使用 QBSolv 參數 num_repeats 來定義。該參數決定了在找到更好的樣本后，重復分割 QUBO 問題矩陣的次數。這樣，QUBO 矩陣就會在每次迭代中使用經典的塔布搜索啟發式分割成不同的部分。QBSolv 可用于以完全經典的方式求解子 QUBO，也可作為量子經典混合方法，在量子退火器上求解單個子 QUBO。

Besides embedding and splitting the QUBO into subQUBOs, QBSolv also takes care of the unembedding and the merging of the subproblems' solutions. We use the default configuration of D-Wave's QBSolv6?including the?auto_scale?function that automatically scales the values of the QUBO matrix to the allowed range of values for the biases and strengths of qubits and couplers. The single-shot annealing time is set to the default value of 20μs. For more details about QBSolv, see?Michael Booth and Roy (2017).除了將 QUBO 嵌入和拆分成子 QUBO 之外，QBSolv 還負責解嵌入和合并子問題的解。我們使用 D-Wave QBSolv6 的默認配置，包括自動縮放功能（auto_scale），該功能可自動將 QUBO 矩陣的值縮放至量子比特和耦合器偏置和強度的允許值范圍。單次退火時間設置為默認值 20μs。有關 QBSolv 的更多詳情，請參見 Michael Booth and Roy (2017)。

There exist many different benchmark datasets for the CVRP and the TSP, which can be downloaded from?Xavier (2014),?Reinelt (2013), and?Cook (2009). In addition, the?Best Known Solution?(BKS) of each dataset is noted. It gives information about the best solution, i.e., the shortest euclidean distance found by any solution method. In order to test and compare the proposed hybrid solution method with regard to the solution quality, various test datasets of Christofides and Eilon (Xavier, 2014) have been selected. Details about the CVRP datasets can be extracted from the name with the format?E-nX-kY. For example,?E-n22-k4?stands for a certain dataset?E,?n22 for the number of customers including the depot and?k4 for the minimal number of vehicles needed to solve the problem. The TSP datasets have the name format?CityX, which just indicates the number of customers which have to be visited in the TSP tour. As already mentioned, the customer and depot coordinates relate to a 2D euclidean space.

CVRP 和 TSP 有許多不同的基準數據集，可從 Xavier（2014 年）、Reinelt（2013 年）和 Cook（2009 年）下載。此外，每個數據集的最佳已知解（BKS）都有記錄。它提供了最佳解決方案的信息，即任何解決方案找到的最短歐氏距離。為了測試和比較所提出的混合求解方法的求解質量，我們選擇了克里斯托菲德斯和埃隆（Xavier，2014 年）的各種測試數據集。有關 CVRP 數據集的詳細信息可從名稱中提取，格式為 E-nX-kY。例如，E-n22-k4 代表某個數據集 E，n22 代表包括倉庫在內的客戶數量，k4 代表解決問題所需的最小車輛數量。TSP 數據集的名稱格式為 CityX，表示在 TSP 行程中必須訪問的客戶數量。如前所述，客戶和車廠坐標與二維歐幾里得空間有關。

（累了，過幾天再編輯）

?