摘要：由于自動化和智能化的普及，AGV（自動導引車）調度問題在物流、運輸和生產(chǎn)領域有著廣泛的應用。隨著AGV數(shù)量的增加，經(jīng)典計算方法難以滿足大規(guī)模調度的需求，而玻色量子自研的相干光量子計算技術具有強大的計算能力，特別是在組合優(yōu)化問題的求解上表現(xiàn)出無可比擬的性能優(yōu)勢，大大提高了AGV調度的效率和自動化水平。

真機測試結果表明，與經(jīng)典計算方法相比，基于玻色量子自研的100計算量子比特相干光量子計算機真機，平均可節(jié)省92%的計算時間。顯然，量子計算在AGV調度問題上的應用，不僅展示了相干光量子計算機的巨大潛力，也為物流自動化的未來發(fā)展指明了方向，具有重大的實際應用前景與里程碑式突破意義。

交通物流行業(yè)作為勞動密集型產(chǎn)業(yè)之一，提高該行業(yè)的自動化和智能化水平已成為工業(yè)界和學術界的重要課題。正因如此，AGV調度問題在交通物流行業(yè)有著廣泛應用。

近年來，一些行業(yè)龍頭企業(yè)已經(jīng)進行了技術改造。例如，零售巨頭亞馬遜以及中國電子商務公司京東等都建立了龐大的智能倉庫，其中使用了大量AGV執(zhí)行貨物的運輸作業(yè)。此外，AGV還廣泛應用于自動化碼頭、智能工廠等應用場景，極大地提升了作業(yè)效率，降低物流成本。

為了滿足應用場景的需求，AGV的并行工作量不斷增加，這給AGV調度帶來了很大的難度。AGV調度問題是十分困難的組合優(yōu)化問題，使用目前的普通臺式電腦與超級計算機來求解，精確算法可以生成好的解決方案，但其計算時間非常長，使其無法用于大規(guī)模問題。非精確算法表現(xiàn)出良好的效率，但經(jīng)常收斂到局部最優(yōu)，在短時間內(nèi)提供高質量的調度解決方案成為一項重大挑戰(zhàn)。

這類組合優(yōu)化問題卻是量子計算的擅長領域。

國際上，德國量子計算硬件公司Quantum Brilliance，曾與量子軟件公司Quantum-South合作，共同開發(fā)并銷售航運物流優(yōu)化配套產(chǎn)品和技術。這兩家公司與航空和海運運輸公司從量子計算概念驗證出發(fā)，以挖掘量子計算在解決經(jīng)典計算機范圍之外的高度復雜計算問題方面的潛力為主要研發(fā)方向。

此前，北京玻色量子科技有限公司（簡稱“玻色量子”）聯(lián)合大連海事大學交通運輸工程學院唐亮教授團隊，在“量子計算+AGV調度”領域實現(xiàn)的重要研究成果以《Quantum computing for several AGV scheduling models》為題（量子計算應用于多種AGV調度模型）在中科院SCI期刊2區(qū)《Scientific Reports》期刊上重磅發(fā)布。

論文主要介紹通過量子計算技術如何來解決自動導引車（AGV）的調度問題。玻色量子自研的相干光量子計算技術具有強大的計算能力，特別是在組合優(yōu)化問題的求解上表現(xiàn)出無可比擬的性能優(yōu)勢，大大提高了AGV調度的效率和自動化水平。這項研究具有重大的實際應用前景，突出表現(xiàn)玻色量子聯(lián)合大連海事大學在 “量子計算+AGV調度”領域率先實現(xiàn)實用化場景應用成果，并具有里程碑式突破意義。

下面我們將給出完整真機測試報告：從AGV調度模型的二次無約束二值優(yōu)化（QUBO）模型和Ising模型構建方法入手，給出了優(yōu)化問題目標函數(shù)、等式和不等式約束對應 QUBO 模型懲罰項的轉換方式，依托玻色量子團隊自主研發(fā)的“天工量子大腦100”開展了應用測試，驗證了相干光量子計算機在解決AGV調度問題和類似組合優(yōu)化問題方面具備了實用量子優(yōu)越性。

AGV調度模型

AGV調度問題根據(jù)不同的場景和考慮因素有多種分類。例如，考慮任務的時間窗口、調度和路徑的聯(lián)合優(yōu)化、與其他設備的配合、計費策略等。研究人員簡化了復雜場景下AGV調度問題規(guī)模，保留了AGV調度問題的本質。在此基礎上，構建了AGV調度模型。研究人員提出了基于混合整數(shù)規(guī)劃（MIP）的經(jīng)典AGV調度模型以及基于QUBO形式的點模型和弧模型。

AGV調度問題及可行解決方案。所有AGV從固定的起始節(jié)點出發(fā)，執(zhí)行運輸任務，完成所有任務后到達終點節(jié)點?！癝”表示運輸任務的起點，“E”表示運輸任務的終點。不同的顏色代表不同的AGV任務路線。

MIP：

目標函數(shù)（1）是最小化AGV的總行程時間。約束條件（2）和（3）確保所有AGV都需要完成虛擬啟動任務和虛擬結束任務，約束條件（4）保證所有實際任務都唯一分配給特定的AGV。約束條件（5）確保每臺AGV完成其任務時滿足流量平衡。然后，約束（6）保證虛擬啟動任務在時刻0開始和結束。約束（7）指出，到達任務結束的時間等于到達該任務開始的時間加上從開始到結束的運輸時間。約束（8）表示到達任務開始的時間晚于到達前一個任務結束的時間加上從前一個任務結束到達該任務開始所需的運輸時間，最后的約束（9）消除了任務自引用。約束（10）和（11）表示變量的范圍限制。

其中T表示任務完成時間makespan。目標函數(shù)是最小化T，約束條件（13）表示T必須不小于最后一個AGV完成任務所需的時間。

QUBO 和 Ising 模型

QUBO是優(yōu)化問題的表達式，其目標是找到二次二值變量多項式的最小值。Ising模型最早應用于統(tǒng)計物理學,它描述了一個由相互作用單元組成的系統(tǒng)，其中每個自旋粒子必須具有兩種可能的隨機狀態(tài)（例如+1和?1），然后將其作為模型引入數(shù)學領域，以描述一系列優(yōu)化問題。許多組合優(yōu)化問題可以用二次無約束二值優(yōu)化或Ising模型的形式表示，并且它們可以相互轉換，QUBO模型的一般表達式如式（14）所示。

其中x是z維二值變量，Q是二次系數(shù)矩陣，上述 QUBO 形式的模型可以很容易地轉換為 Ising 模型，優(yōu)化函數(shù)可以用以下形式表示

Ising 問題的解是找到哈密頓量的基態(tài)。CIM根據(jù)最小增益原理求解Ising問題，可以求出Ising哈密頓量的基態(tài)或低能態(tài)。該方法是將QUBO問題映射到具有可編程參數(shù)的全連接Ising哈密頓量中，并通過可控量子相變獲得問題的解。

點模型和弧模型具體構造形式可見論文。

數(shù)值實驗

研究人員使用 Gurobi求解器在經(jīng)典計算機上求解上述MIP模型，并展示其在不同問題尺度下的計算性能。并利用玻色量子的相干光量子計算機真機去求解不同尺度的節(jié)點模型和弧模型的問題案例，將計算性能與經(jīng)典計算機進行對比。

研究人員使用 Gurobi 求解了 AGV 調度的混合整數(shù)規(guī)劃模型，用于兩個優(yōu)化目標。在“任務數(shù)量”中，研究人員展示了計算時間隨任務數(shù)量變化的實驗，而在“AGV數(shù)量”中，研究人員展示了計算時間隨AGV數(shù)量變化的實驗。研究人員將每次運行的時間限制設置為1800 秒。

經(jīng)典計算機

一般來說，任務數(shù)量的增加會導致AGV調度解決方案的生成速度變慢。研究人員研究了任務數(shù)量變化對MIP模型的計算速度的影響。為了實現(xiàn)這一目標，研究人員生成了4個任務到12個任務的實例，其中固定數(shù)量的AGV為2，并獲得如圖所示的計算時間圖。其中左圖以最小化總時間為目標函數(shù)，右圖以最小化任務完成時間為目標函數(shù)。圖例部分表示模型編號。

MIP 模型計算時間隨任務數(shù)量變化圖。（a）表示最小化總時間的目標下的MIP模型計算時間隨任務數(shù)量變化圖。（b）表示最小化任務完成時間的目標下的MIP模型計算時間隨任務數(shù)量變化圖。

在圖中，研究人員發(fā)現(xiàn)混合整數(shù)規(guī)劃模型的計算速度隨著AGV任務數(shù)量的增加而逐漸減慢，當任務數(shù)量達到一定臨界值時，計算時間急劇增加，這是兩個不同目標函數(shù)所體現(xiàn)的共同屬性。尤其是當任務數(shù)量增加到 12 個時，計算時間已經(jīng)超過 1800 秒，這反映了傳統(tǒng)模型在面對大規(guī)模問題時的弱點。

量子計算機

在節(jié)點模型中最小化總時間的目標函數(shù)下，哈密頓量隨時間的演化圖。（a）以4個任務為例表示哈密頓量隨時間變化的演化圖。（b）以5個任務為例表示哈密頓量隨時間變化的演化圖。（c）以6 個任務為例表示哈密頓量隨時間變化的演化圖。（d）以7個任務為例表示哈密頓量隨時間變化的演化圖。

在弧模型中兩個目標函數(shù)下哈密頓量隨時間變化的演化圖。（a）表示目標函數(shù)為最小化總時間情形下哈密頓量隨時間變化的演化圖，（b）表示目標函數(shù)為最小化任務完成時間情形下哈密頓量隨時間演化圖。

節(jié)點模型量子計算解決方案示意圖（以最大割問題形式展現(xiàn)）。（a）代表4個任務下的解決方案。（b）代表個項任務下的解決方案。（c）代表6個任務下的解決方案。（d）代表7個任務下的解決方案。

弧模型量子計算解決方案示意圖（以最大割問題形式展現(xiàn)）。（a）表示在最小化總時間的目標函數(shù)下4個任務的解。（b）表示在最小化任務完成時間的目標函數(shù)下4個任務的解。

經(jīng)典計算機V.S量子計算機

經(jīng)典計算機和CIM的計算時間（ms）對比

從上表可以看出，CIM得到的解都是最優(yōu)解，且計算時間比經(jīng)典計算機快得多。CIM與經(jīng)典計算機（求解器）相比具有明顯的性能優(yōu)勢。特別是當問題規(guī)模增加時，CIM所需的時間不會像經(jīng)典計算機那樣顯著增加。這表明CIM具有巨大的發(fā)展和應用潛力。

結論

1.在傳統(tǒng)的AGV調度研究中，隨著AGV和任務數(shù)量的增加，計算時間大大增加。將量子計算技術引入AGV調度問題研究中，構建了新的AGV調度QUBO模型。在實際場景中，調度員往往會根據(jù)工作性質設定不同的調度目標，其中最小化AGV總時間和最小化任務完成時間（makespan）是最常見的兩個目標。根據(jù)不同的目標，研究人員推導了不同的QUBO模型，并給出了兩個不同目標下的模型解和相關理論基礎。

2.研究人員利用經(jīng)典計算機和玻色量子的相干光量子計算機分別對所提出的傳統(tǒng)模型和QUBO模型進行了數(shù)值實驗。實驗結果表明，相干光量子計算機的計算速度遠快于經(jīng)典計算機，平均節(jié)省了92%的計算時間，證明相干光量子計算機在解決AGV調度問題和類似組合優(yōu)化問題方面已經(jīng)初步具備了實用量子優(yōu)越性，未來具有巨大的應用潛力。

量子計算在AGV調度問題上的應用，不僅展示了玻色量子的相干光量子計算機的巨大潛力，也為物流自動化的未來發(fā)展指明了方向。

隨著量子計算技術的不斷成熟，玻色量子將基于最新550計算量子比特相干光量子計算機——天工量子大腦550W，聯(lián)合各行業(yè)優(yōu)秀的合作伙伴探索并驗證更多“量子計算+”實用化場景，依托量子計算生態(tài)產(chǎn)業(yè)鏈，使它將在物流等更多領域發(fā)揮革命性的作用，推動社會進入一個更加智能和高效的新時代。