胡恩澤，賀建軍，申帥，吳仁超

(中南大學(xué) 自動(dòng)化學(xué)院，湖南 長(zhǎng)沙，410083)

隨著倉(cāng)儲(chǔ)物流技術(shù)的發(fā)展，許多大型工業(yè)倉(cāng)庫(kù)采用大規(guī)模的自動(dòng)引導(dǎo)車(AGV)編隊(duì)來(lái)實(shí)現(xiàn)物料自動(dòng)運(yùn)輸，其每天需要處理幾千起搬運(yùn)任務(wù)，如何優(yōu)化調(diào)度使AGV 更高效地執(zhí)行任務(wù)成為當(dāng)前提升物流效率和降低倉(cāng)儲(chǔ)成本的關(guān)鍵問題。AGV 調(diào)度最重要的目標(biāo)是最小化任務(wù)完成時(shí)間，其受到多項(xiàng)決策的影響[1]：

1) 任務(wù)定序分配。決定分配給每個(gè)AGV 的任務(wù)及執(zhí)行這些任務(wù)的順序。

2) 路徑規(guī)劃。為AGV 執(zhí)行被分配的任務(wù)時(shí)選擇最優(yōu)路徑，通常最優(yōu)路徑為耗時(shí)最少或距離最短的路徑。

3) 沖突管理。解決各AGV 之間可能發(fā)生的碰撞沖突。

以上3個(gè)問題是相互依存的[2]，確定AGV的任務(wù)分配是計(jì)算路徑規(guī)劃的先決條件，在選擇AGV的執(zhí)行路徑后才能判斷碰撞沖突是否會(huì)發(fā)生[3]。大多數(shù)研究針對(duì)調(diào)度優(yōu)化的3 個(gè)問題提出了求解的方法[4-5]：

首先，在不考慮碰撞沖突的情況下單獨(dú)求解任務(wù)定序分配問題，得到最優(yōu)方案[6]；

然后，為該方案選擇最優(yōu)的執(zhí)行路徑；

最后，考慮沖突管理問題，在發(fā)生沖突時(shí)建立“交通規(guī)則”等策略，指導(dǎo)AGV 停車等待或繞行來(lái)避免碰撞[7]。

然而，AGV 按照最優(yōu)的任務(wù)定序分配方案生成的最佳路徑去執(zhí)行任務(wù)時(shí)，很可能存在大量的碰撞沖突情況[8]，頻繁等待或繞行會(huì)降低AGV 整體系統(tǒng)運(yùn)行效率[9]。這些研究忽略了AGV 避免沖突的規(guī)避操作，導(dǎo)致存在計(jì)算之外的“延遲時(shí)間”[10]，無(wú)法實(shí)現(xiàn)系統(tǒng)整體的最優(yōu)調(diào)度。綜上分析，調(diào)度中的3個(gè)問題是內(nèi)在關(guān)聯(lián)的，任務(wù)定序分配結(jié)果會(huì)對(duì)路徑規(guī)劃中碰撞沖突情況造成直接影響[11]。因此，在AGV 優(yōu)化調(diào)度問題中，任務(wù)定序分配、路徑規(guī)劃和碰撞沖突問題需要經(jīng)一體化綜合處理，進(jìn)而得到系統(tǒng)整體的最優(yōu)調(diào)度方案[12]。

針對(duì)AGV 綜合調(diào)度問題，MAZA 等[13]提出了預(yù)先規(guī)劃算法和實(shí)時(shí)路由算法，在路徑規(guī)劃過程中生成無(wú)沖突路徑。LIAN等[14]提出一種基于交通控制方法的綜合調(diào)度方法，實(shí)現(xiàn)了基于時(shí)間窗的調(diào)度和沖突管理。然而，這些方法不能有效提高AGV 整體系統(tǒng)效率。SINGH 等[15]研究了電量約束下的異構(gòu)AGV 綜合求解任務(wù)分配和路徑規(guī)劃問題，并提出了一種自適應(yīng)大鄰域搜索算法。然而，該方法沒有考慮AGV 之間的碰撞沖突。此外，一些基于精確算法的綜合調(diào)度優(yōu)化方法[16-17]被用于一體化求解任務(wù)定序分配和無(wú)沖突路徑問題，但任務(wù)定序分配結(jié)果對(duì)路徑規(guī)劃中造成的碰撞沖突情況無(wú)法確定，這些方法對(duì)每一種情況進(jìn)行分析時(shí)，需要消耗不合理的計(jì)算時(shí)間，無(wú)法應(yīng)用于大型工業(yè)倉(cāng)庫(kù)實(shí)例。

針對(duì)以上問題，本文提出一種綜合優(yōu)化調(diào)度方法，體現(xiàn)在：

1) 建立一個(gè)混合整數(shù)線性規(guī)劃模型來(lái)描述異構(gòu)多AGV 的綜合調(diào)度問題，采用柵格法構(gòu)建倉(cāng)庫(kù)地圖，定義任務(wù)執(zhí)行過程，提出路徑專家?guī)斓母拍?，即所有候選路徑的集合。針對(duì)現(xiàn)實(shí)工業(yè)倉(cāng)庫(kù)對(duì)于AGV在速度與物料搬運(yùn)能力的異構(gòu)性和AGV需要在適當(dāng)時(shí)間充電等問題，制定相應(yīng)的約束條件。

2) 提出一種基于分層規(guī)劃的綜合優(yōu)化調(diào)度方法，將綜合調(diào)度問題分解為聚合的上層任務(wù)定序分配問題和下層路徑規(guī)劃問題，在不考慮沖突的情況下生成上層問題的精英解集合，依次對(duì)集合中每個(gè)解在下層進(jìn)行基于路徑專家?guī)斓穆窂揭?guī)劃計(jì)算，記錄碰撞沖突結(jié)果并生成禁忌列表，將禁忌列表作為碰撞沖突的約束條件融入上層問題尋優(yōu)過程，最后通過迭代搜索得到滿足整體性能最優(yōu)的調(diào)度方案。

3) 提出一種混合離散狀態(tài)轉(zhuǎn)移算法(HDSTA)，設(shè)計(jì)一種精英種群生成方法，引入路徑選擇程序和禁忌列表，提升算法搜索過程的多樣性能力與強(qiáng)化搜索能力。同時(shí)，為了在任務(wù)定序分配結(jié)果中合適的位置插入充電請(qǐng)求，提出2種插入算子。

1 調(diào)度模型

2 基于分層規(guī)劃的綜合調(diào)度方法

本文提出一種基于分層規(guī)劃的綜合優(yōu)化調(diào)度方法，將調(diào)度問題分解為聚合的上層主問題和下層子問題。上層問題決定AGV 任務(wù)定序分配決策，下層子問題計(jì)算執(zhí)行任務(wù)的最優(yōu)路徑，同時(shí)，在2層問題的計(jì)算過程中考慮碰撞沖突問題。綜合優(yōu)化調(diào)度方法首先在不考慮沖突的情況下生成上層問題的精英解集合；然后，依次對(duì)集合中的每個(gè)精英解在下層進(jìn)行基于路徑專家?guī)斓穆窂揭?guī)劃計(jì)算，計(jì)算碰撞沖突并生成禁忌列表；最后，將禁忌列表作為碰撞沖突的約束條件融入上層問題的尋優(yōu)過程中，通過迭代搜索得到滿足整體性能最優(yōu)的調(diào)度方案。

AGV可以通過硬件和“交通規(guī)則”避免碰撞，因此，無(wú)沖突路徑不是強(qiáng)制性的，但規(guī)避沖突造成的延遲時(shí)間(避免碰撞的等待或繞道時(shí)間)需要被量化，同時(shí)，在上層問題和下層問題求解過程中減少碰撞沖突，目標(biāo)是最小化AGV 運(yùn)輸時(shí)間，即最小化所有AGV執(zhí)行任務(wù)時(shí)間和延遲時(shí)間(避免碰撞的等待或繞道時(shí)間)的總和。此外，為了避免死鎖，不允許2 輛以上AGV 在同一位置發(fā)生沖突，存在這種情況的調(diào)度方案在計(jì)算過程中會(huì)被定義為不可行解。綜合優(yōu)化調(diào)度方法執(zhí)行步驟如下。

步驟1：在上層主問題中去除碰撞約束條件，定義AGV 每個(gè)任務(wù)的運(yùn)輸時(shí)間為從起始節(jié)點(diǎn)到交付節(jié)點(diǎn)的最短時(shí)間，計(jì)算任務(wù)定序分配最優(yōu)解，并將最優(yōu)解和計(jì)算過程中其他精英解放入1個(gè)集合φi中。φi中的每個(gè)解用pn表示，其中，pn在集合φi中按照目標(biāo)函數(shù)值升序排列。

步驟2：在下層問題中，對(duì)于φi中每一個(gè)解pn進(jìn)行沖突約束下的路徑規(guī)劃，同時(shí)生成一個(gè)帶有記憶的碰撞沖突約束列表，稱為禁忌列表。若路徑規(guī)劃可以找到無(wú)沖突路徑，則調(diào)度優(yōu)化結(jié)束；否則，將碰撞沖突結(jié)果記錄到禁忌列表中。在每一個(gè)pn計(jì)算碰撞沖突過程中，將具有最小目標(biāo)函數(shù)值的解記為暫定最優(yōu)解pt，其碰撞沖突造成的延遲時(shí)間用td表示。

步驟3：定義最大允許延遲時(shí)間為ε，若步驟2中推導(dǎo)的td小于ε，則調(diào)度優(yōu)化完成。

步驟4：重新求解上層主問題，在這過程中從φi中去除被記錄在禁忌列表中的解。若k次迭代后目標(biāo)函數(shù)值沒有降低，則調(diào)度優(yōu)化結(jié)束。否則，更新精英集合φi并跳轉(zhuǎn)到步驟2。

本文提出一種引入路徑搜索和禁忌列表的混合狀態(tài)轉(zhuǎn)移算法(HDSTA)對(duì)任務(wù)定序分配、路徑規(guī)劃和碰撞沖突問題進(jìn)行一體化求解，算法流程如圖1所示。首先，在考慮當(dāng)前禁忌列表下，針對(duì)任務(wù)定序分配問題求解出候選精英解并添加到精英解集中，再依次對(duì)新生成的精英解執(zhí)行基于路徑專家?guī)斓穆窂揭?guī)劃計(jì)算。然后，通過碰撞檢測(cè)程序確定沖突延遲時(shí)間并獲得最終的任務(wù)完成時(shí)間。最后，更新禁忌列表，并將其作為沖突判斷指導(dǎo)求解下一代候選精英解。

混合離散狀態(tài)轉(zhuǎn)移算法流程如圖1 所示，其中，Xbest代表當(dāng)前最優(yōu)解，fbest表示歷史最優(yōu)解，SE為種群數(shù)量，n，ma，mb和mc為0到1之間的小數(shù)。HDSTA 的偽代碼見算法1。算法開始于由不考慮沖突的DSTA(I)算法生成上層初始精英解集Q0，對(duì)于其中每一個(gè)解pn，通過路徑選擇程序(SP)生成下層路徑解p，計(jì)算運(yùn)輸時(shí)間T、延遲時(shí)間tp和沖突次數(shù)，并生成禁忌列表Tlist。HDSTA設(shè)計(jì)了3個(gè)終止條件：

圖1 混合離散狀態(tài)轉(zhuǎn)移算法流程Fig. 1 Flow chart of hybrid discrete state transition algorithm

1) 精英解集中存在1個(gè)解，在路徑規(guī)劃中可以生成無(wú)沖突路徑，算法結(jié)束，輸出最優(yōu)解；

2) 精英解集在路徑規(guī)劃中的最優(yōu)解，其延遲時(shí)間tbest小于目標(biāo)值ε，算法結(jié)束，輸出最優(yōu)解；

3) 迭代l次后目標(biāo)函數(shù)值沒有減少，算法結(jié)束，輸出當(dāng)前最優(yōu)解。精英解集通過融合禁忌列表約束的DSTA(II)迭代過程進(jìn)行更新，直到其中一個(gè)終止條件被滿足，生成包含定序分配解D和執(zhí)行路徑解Pbest的綜合調(diào)度解S。

2.1 生成精英解集

在搬運(yùn)任務(wù)序列中插入定位充電請(qǐng)求對(duì)AGV調(diào)度問題至關(guān)重要。當(dāng)AGV 當(dāng)前電量無(wú)法完成所有被分配的任務(wù)時(shí)，必須在中途充電，此時(shí)，需要在搬運(yùn)任務(wù)序列中合理的位置插入充電請(qǐng)求，并規(guī)定AGV 在距離先前服務(wù)任務(wù)位置最近的充電站進(jìn)行充電[18]。針對(duì)AGV 可能需要多次充電問題，定義AGV 完成所有搬運(yùn)任務(wù)需要的充電次數(shù)為Nk，設(shè)計(jì)臨界插入算子和非臨界插入算子。當(dāng)決定了1 個(gè)搬運(yùn)任務(wù)定序分配解時(shí)，對(duì)Nk＞1 的AGV 用臨界插入算子插入充電請(qǐng)求，對(duì)Nk=1 的AGV用非臨界插入算子插入充電請(qǐng)求。

算法1：HDSTA偽代碼輸入：AGVK，任務(wù)T，路徑專家?guī)霳s輸出：S 1：用DSTA(I)算法生成初始精英解集Q0 2：while (y1=1 or y2=1 or y3=1)3：for每一精英解pn ∈Q0 4：[p，T，tD，SD]←SP(pn)5：if tp=0 then 6：D ←pn;Pbest ←p;Tbest ←T;y1 ←1 7：break for;8：end if 9：if tp ＜tbest then 10：tbest ←tp;Pbest ←p;Tlist ←[pn，Sp];Tbest ←T 11：end if 12：end for 13：if tbest ＜ε then 14：y2 ←1 15：end if 16：if y1=0 or y2=0 then 17：采用DSTA(II)算法更新精英解集Q0 18：更新計(jì)數(shù)器l 19：if l ＞5 20：y3 ←1 21：end if 22：end if 23：end while 24：S ←(D，Pbest)

臨界插入算子(CI)：按順序確定AGV 電量低于臨界閾值bl的任務(wù)位置，并在該任務(wù)前插入充電請(qǐng)求。

非臨界插入算子(NCI)：按順序確定AGV電量低于臨界閾值bl的任務(wù)位置。在該任務(wù)前找到離充電站最近且不會(huì)增加充電次數(shù)的位置，將充電請(qǐng)求插入該最佳位置，使AGV提前充電。

DSTA采用群體中的最優(yōu)解在鄰域內(nèi)迭代搜索直到找到全局最優(yōu)解。為了保證任務(wù)定序分配結(jié)果對(duì)路徑規(guī)劃過程具有多樣選擇性，需要生成包含多個(gè)精英解的集合。在DSTA迭代過程中，下一代種群的生成只與上一代的最優(yōu)解相關(guān)，用于生成種群的3 種特殊狀態(tài)變換算子見文獻(xiàn)[19]。每一代種群中的解具有高度相似性，其包含的解不滿足精英性和多樣性要求，因此，不能作為精英解集。針對(duì)上述問題提出一種精英解集Q0生成方法。初始化解集Q0并定義集合中解的數(shù)量上限為m，按照目標(biāo)函數(shù)值升序存放。在迭代過程中，將每一代搜索的所有精英解與Q0中存放的解進(jìn)行比較，若存在更優(yōu)的解則進(jìn)行替換，從而保證精英解集Q0包含搜索過程中所有精英個(gè)體。引入插入算子的精英解集生成方法見算法2，其中，Se為種群數(shù)量，Sbest為種群中最優(yōu)解，Q0為精英解集，Ci與Ni分別為臨界插入算子和非臨界插入算子。

算法2：DSTA(II)輸入：AGVK，任務(wù)T輸出：Q0 1：隨機(jī)生成初始化解Best 2：fbest ←fitness(Sbest)3：k ←0 4：repeat 5：[Q0，fbest，Sbest]←swap(Q0，fbest，Sbest，Tlist，Se，Ci，Ni)6：[Q0，fbest，Sbest]←shift(Q0，fbest，Sbest，Tlist，Se，Ci，Ni)7：[Q0，fbest，Sbest]←symmetry(Q0，fbest，Sbest，Tlist，Se，Ci，Ni)8：k ←k+1 9：until達(dá)到最大迭代次數(shù)

2.2 路徑選擇

基于路徑專家數(shù)據(jù)庫(kù)的AGV 路徑選擇程序SP，其偽代碼見算法3。路徑選擇過程根據(jù)當(dāng)前任務(wù)定序分配方案，從路徑專家數(shù)據(jù)庫(kù)中找到?jīng)_突最少的執(zhí)行路徑Pbest，計(jì)算延遲時(shí)間tp并記錄沖突信息生成禁忌列表Tlist。為了求解路徑規(guī)劃方案P，定義dk為AGVk被分配的所有搬運(yùn)任務(wù)，其執(zhí)行路徑由rk表示。每個(gè)任務(wù)搬運(yùn)任務(wù)tn∈dk由1 個(gè)取貨請(qǐng)求和1 個(gè)送貨請(qǐng)求組成，代表執(zhí)行任務(wù)tn的路徑，其中，分別表示取貨路徑和送貨路徑。此外，當(dāng)任務(wù)為充電請(qǐng)求時(shí)，則只有1 條路徑。在路徑專家?guī)熘?，從站點(diǎn)i到站點(diǎn)j的路線rij中第n條路徑用p(i，j，n)∈Ns表示。

在選擇程序中，沖突檢測(cè)程序(Con)是一個(gè)基于三維時(shí)空模型的沖突檢測(cè)程序[20]，它能計(jì)算沖突路徑位置Sp與延時(shí)時(shí)間ti。當(dāng)路徑之間存在沖突時(shí)，替換程序(Replace)在路徑專家數(shù)據(jù)庫(kù)中用其他平行路徑替換當(dāng)前路徑，替代方式是從路徑候選解集中自上而下搜索，直到為每個(gè)AGV 從路徑庫(kù)中找到延遲時(shí)間最少的路徑。在找到無(wú)沖突執(zhí)行路徑后停止搜索，否則，替換程序?qū)⑺阉髀窂綄＜規(guī)熘袥_突路線的替換路徑，選擇延遲時(shí)間最小的路徑集合記為當(dāng)前最優(yōu)路徑解Pbest。

算法3：路徑選擇程序輸入：任務(wù)定序分配方案Pn，路徑專家?guī)霳s輸出：Pbest，tp，Tlist 1：TC←0 2：for 每一個(gè)dk ∈pn 3：for 每一個(gè)tn ∈dk 4：rnu←P(ot u,1)；rnu'←P(otd,1)5：rn(1:)←rnu；rn(1:)←rnu′；rk(n)←rn 6：end for 7：P(k)←rk 8：end for 9：[ti，Sp]←Con(P)10：if ti≠ 0 11：for 每一個(gè)Sp 12：repeat 13：P′ ← Replace(SP，P)14：t′i ← Con(P')15：if t′i ＜ti 16：Sp′←Sp ti ←t′i P ←P′17：end if 18：until 路徑庫(kù)中所有的路徑都被查詢19：end for 20：tp ←ti 21：else 22：tp ←ti；Pbest ←P 23：end if 24：if tp滿足被禁忌列表記錄的條件25：Tlist ←[pn，Sp]26：end if

禁忌列表在HDSTA 中的作用是從搜索空間移除曾經(jīng)訪問的解，從而進(jìn)行更廣泛探索。在路徑選擇中，禁忌列表記錄并更新存在沖突較多的任務(wù)定序分配精英解。HDSTA 在迭代過程中更新精英解集時(shí)受到禁忌列表約束，并刪除被記錄的解，從而防止循環(huán)回到之前搜索過的解決方案。禁忌列表能存儲(chǔ)解的數(shù)量上限為h，當(dāng)新的解延遲時(shí)間更大時(shí)，禁忌列表才會(huì)更新。需要強(qiáng)調(diào)的是，本文考慮的沖突問題具有時(shí)序性，優(yōu)先被執(zhí)行的任務(wù)不受靠后被執(zhí)行任務(wù)的影響，禁忌列表中記錄的信息對(duì)于任務(wù)分配結(jié)果的約束可以被擴(kuò)展，如當(dāng)AGV1被分配執(zhí)行任務(wù)(2-1-3-5)且AGV2被分配行任務(wù)(8-7-6-4)時(shí)，若記錄AGV1在執(zhí)行任務(wù)1 會(huì)與執(zhí)行任務(wù)7 的AGV2發(fā)生沖突，則沖突信息可以被擴(kuò)展為AGV1(2-1-X-X)與AGV2(8-7-X-X)，其中，X表示任意一個(gè)任務(wù)。

3 工業(yè)倉(cāng)庫(kù)實(shí)例驗(yàn)證

3.1 工業(yè)倉(cāng)庫(kù)案例

湖南長(zhǎng)沙的某科技公司是本項(xiàng)研究的合作單位和實(shí)驗(yàn)應(yīng)用場(chǎng)所，某倉(cāng)庫(kù)的布局如圖2所示，包括40個(gè)預(yù)分揀站和9個(gè)充電站。采用1個(gè)包含背負(fù)式AGV和托盤式AGV的異構(gòu)車隊(duì)集群，2種AGV的速度分別為0.8 m/s 和1.0 m/s。根據(jù)從業(yè)者反饋，在1 個(gè)時(shí)間段內(nèi)，等待分配的平均任務(wù)數(shù)約為50個(gè)，繁忙期，等待分配的任務(wù)超過80個(gè)。

圖2 倉(cāng)儲(chǔ)布局Fig. 2 Warehouse layout

3.1.1 參數(shù)設(shè)定

在實(shí)驗(yàn)案例中對(duì)參數(shù)進(jìn)行設(shè)定，首先確定種群數(shù)量、精英解集中解的數(shù)量和禁忌列表長(zhǎng)度的上限分別為S e=20，m=30，h=120。然后，確定算法的終止條件參數(shù)，允許的最大延遲時(shí)間ε=85 s，HDSTA 迭代計(jì)數(shù)值為5 次，DSTA 最大迭代計(jì)數(shù)值為50次。路徑專家?guī)霳s在離線階段被提前預(yù)設(shè)，每一條站點(diǎn)之間的路線都包含10 條以上優(yōu)秀的候選路徑。

3.1.2 案例分析

基于實(shí)際倉(cāng)庫(kù)案例的背景，通過處理不同規(guī)模的問題驗(yàn)證方法的有效性。在實(shí)驗(yàn)中，待調(diào)度的AGV數(shù)量分別6、9和15輛，案例中待分配的任務(wù)數(shù)分別為20、30、40、50、60、70 和80 個(gè)，每一個(gè)案例隨機(jī)生成5 組任務(wù)，并運(yùn)行10 次，共運(yùn)行50 次程序，取平均值作為結(jié)果。當(dāng)前工業(yè)倉(cāng)庫(kù)中先進(jìn)AGV 系統(tǒng)普遍采用依次優(yōu)化的調(diào)度方法，其中LIAN 等[14]提出的方法最具有代表性，因此，在現(xiàn)實(shí)倉(cāng)庫(kù)案例分析中選擇該方法進(jìn)行對(duì)比驗(yàn)證。在案例分析中，綜合優(yōu)化調(diào)度方法和依次優(yōu)化調(diào)度方法的任務(wù)完成時(shí)間和延遲時(shí)間的對(duì)比結(jié)果如圖3至圖5所示。

圖3 使用6輛AGV的任務(wù)完成時(shí)間和延遲時(shí)間對(duì)比分析Fig. 3 Comparative analysis of task completion time and delay time with 6 AGVs

圖4 使用9輛AGV的任務(wù)完成時(shí)間和延遲時(shí)間對(duì)比分析Fig. 4 Comparative analysis of task completion time and delay time with 9 AGVs

圖5 使用15輛AGV的任務(wù)完成時(shí)間和延遲時(shí)間對(duì)比分析Fig. 5 Comparative analysis of task completion time and delay time with 15 AGVs

案例分析結(jié)果表明，本文所提出的綜合優(yōu)化調(diào)度方法具有更好的性能，在所有案例中都找到了更優(yōu)的解。具體表現(xiàn)為：相較于依次優(yōu)化調(diào)度方法，綜合優(yōu)化調(diào)度方法的任務(wù)完成時(shí)間縮短了10.56%，延遲時(shí)間減少了74.53%。值得注意的是，這2 種方法的延遲時(shí)間在任務(wù)數(shù)為20 時(shí)任務(wù)完成時(shí)間僅相差42.63 s，但當(dāng)任務(wù)數(shù)增大到80 個(gè)時(shí)，其任務(wù)完成時(shí)間相差1 281.13 s。因此，隨著任務(wù)規(guī)模增加，AGV 之間發(fā)生沖突的可能性也越大，依次優(yōu)化調(diào)度方法不能從任務(wù)分配過程中規(guī)避碰撞沖突的影響，而綜合優(yōu)化調(diào)度方法可以通過改變?nèi)蝿?wù)分配和具體執(zhí)行路徑，規(guī)避大多數(shù)沖突情況。

為了進(jìn)一步驗(yàn)證綜合優(yōu)化調(diào)度方法在大規(guī)模任務(wù)案例中減少碰撞沖突的作用，使用30輛AGV將2種方法在任務(wù)數(shù)分別為110～150個(gè)的案例中對(duì)碰撞沖突次數(shù)進(jìn)行對(duì)比。每一個(gè)案例隨機(jī)生成10組任務(wù)，每組運(yùn)行10次程序取平均值，結(jié)果如圖6所示。從圖6可以得到：綜合優(yōu)化調(diào)度方法能大幅度減少AGV 之間的碰撞次數(shù)，與依次優(yōu)化調(diào)度方法相比，平均碰撞次數(shù)降低73.3%。

圖6 平均碰撞次數(shù)對(duì)比分析Fig. 6 Analysis of conflicts number

3.2 對(duì)比驗(yàn)證分析

為了更全面地驗(yàn)證HDSTA 的性能，需要建立更大規(guī)模的案例范本。將20～100 個(gè)任務(wù)定義為小規(guī)模問題，待調(diào)度的AGV 從5 輛到15 輛不等；將100個(gè)任務(wù)以上定義為大規(guī)模問題，待調(diào)度的AGV從15輛到30輛不等。在對(duì)比實(shí)驗(yàn)中，對(duì)于不同規(guī)模的每個(gè)案例隨機(jī)生成10 組任務(wù)，每組運(yùn)行10次，共運(yùn)行100次程序，對(duì)比任務(wù)完成的時(shí)間。在每個(gè)案例中，將HDSTA與自適應(yīng)大鄰域搜索算法(HALNS)[15]、預(yù)先規(guī)劃算法(PPA)[13]和DS算法進(jìn)行對(duì)比。其中，HALNS 是一種混合了自適應(yīng)大鄰域搜索算法和線性規(guī)劃的算法，用于求解帶電量約束的異構(gòu)AGV 調(diào)度問題。但該方法沒有考慮沖突和死鎖問題，為了進(jìn)行比較，對(duì)其最優(yōu)解進(jìn)行沖突檢測(cè)并增加延遲時(shí)間。PPA是一種在路徑規(guī)劃過程生成無(wú)沖突最短路徑的算法，本文將綜合調(diào)度優(yōu)化方法與無(wú)沖突路徑策略進(jìn)行比較。DS 是基于離散狀態(tài)轉(zhuǎn)移算法的綜合求解方法，用于與本文提出的基于HDSTA的綜合求解方法作對(duì)比。算法的計(jì)算時(shí)間同樣是重要的性能指標(biāo)，因此，設(shè)定算法最大計(jì)算時(shí)間為120 s，對(duì)比結(jié)果如表1和表2所示。

表1 小規(guī)模案例對(duì)比分析Table 1 Results for the small-scale instances

表2 大規(guī)模案例對(duì)比分析Table 2 Results for the large-scale instances

任務(wù)完成時(shí)間與運(yùn)行成本成正比，可以直觀反映AGV 協(xié)同運(yùn)行效率，而計(jì)算時(shí)間是動(dòng)態(tài)調(diào)度的重要指標(biāo)，可以反映AGV系統(tǒng)的計(jì)算效率。從表1可見：當(dāng)任務(wù)數(shù)量為20個(gè)，AGV數(shù)量分別為5，8和10輛時(shí)，采用HDSTA算法優(yōu)化調(diào)度計(jì)算得出的方案任務(wù)完成時(shí)間分別為1 440、1 453 和1 485 s，計(jì)算時(shí)間分別為0.83、0.82 和0.89 s；通過20 個(gè)小規(guī)模案例類型的200組任務(wù)的結(jié)果分析發(fā)現(xiàn)，相較于PPA 和HALNS，本文提出的HDSTA 解的任務(wù)完成時(shí)間平均值分別縮短0.48%和1.16%，計(jì)算時(shí)間分別降低78.40%和69.74%。DS 求解時(shí)間與其他3 種綜合調(diào)度方法相差較大；在小規(guī)模問題中，幾種綜合調(diào)度方法求解時(shí)間相差不大，而HDSTA的求解時(shí)間更少。從表2 可見：當(dāng)任務(wù)數(shù)量為120個(gè)，AGV 數(shù)量分別為15、18 和19 輛時(shí)，采用HDSTA 算法優(yōu)化調(diào)度計(jì)算后任務(wù)完成時(shí)間分別為12 305、12 654 和13 147 s，計(jì)算時(shí)間分別為8.60、8.84 和8.92 s；通過10 個(gè)大規(guī)模案例類型的100 組任務(wù)的結(jié)果分析發(fā)現(xiàn)，與PPA 和HALNS 相比，HDSTA 可以在更短的時(shí)間內(nèi)求得質(zhì)量更高的解，任務(wù)完成時(shí)間分別縮短5.54%和9.73%，計(jì)算時(shí)間分別降低86.68%和84.19%。在大部分案例中，DS不能得到整體最優(yōu)的結(jié)果，HDSTA 雖然計(jì)算時(shí)間比DS的更長(zhǎng)，但仍在一個(gè)合理的范圍內(nèi)。

4 結(jié)論

1) 本文提出的基于分層規(guī)劃的綜合優(yōu)化調(diào)度方法比依次優(yōu)化調(diào)度方法平均任務(wù)完成時(shí)間減少10.56%，碰撞沖突造成的延遲時(shí)間減少74.53%。

2) 在所有案例中，DS 都不能得到整體最優(yōu)的結(jié)果。在100個(gè)任務(wù)內(nèi)的小規(guī)模問題中，本文提出的方法比HALNS 和PPA 任務(wù)完成時(shí)間分別減少1.16% 和0.48%，計(jì)算時(shí)間分別減少69.74% 和78.40%。在100個(gè)任務(wù)以上的大規(guī)模問題中，本文提出的方法比HALNS和PPA任務(wù)完成時(shí)間分別減少9.73%和5.54%，計(jì)算時(shí)間分別減少84.19%和86.68%。