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

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

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

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

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

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

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

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

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

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

AGV調(diào)度模型

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

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

MIP：

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

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

QUBO 和 Ising 模型

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

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

數(shù)值實(shí)驗(yàn)

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

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

經(jīng)典計(jì)算機(jī)

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

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

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

量子計(jì)算機(jī)

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

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

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

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

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

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

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

結(jié)論

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

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

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

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