基于量子計算技術(shù)的AGV調(diào)度問題研究

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

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

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

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

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

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

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

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

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

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

AGV調(diào)度模型

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

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

MIP：

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

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

QUBO 和 Ising 模型

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

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

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

點模型和弧模型具體構(gòu)造形式可見論文。

數(shù)值實驗

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

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

經(jīng)典計算機

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

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

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

量子計算機

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

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

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

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

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

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

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

結(jié)論

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

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

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

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