丁 一 袁 浩 方懷瑾 田 宇

（1.上海海事大學(xué)物流工程與科學(xué)研究院 上海 201306；2.上海國際港務(wù)（集團）股份有限公司 上海 201306）

0 引 言

自動化導(dǎo)引車（automated guided vehicle,AGV）作為自動化集裝箱碼頭的水平運輸機械，對于提高整體碼頭作業(yè)效率有著至關(guān)重要的作用，因此AGV調(diào)度優(yōu)化問題一直是港航領(lǐng)域的熱點問題。AGV的調(diào)度有3個層面：AGV任務(wù)分配、AGV路徑規(guī)劃、AGV交通控制，在運籌優(yōu)化領(lǐng)域一般只考慮任務(wù)分配和路徑規(guī)劃[1]。

AGV 調(diào)度優(yōu)化問題一直是學(xué)者關(guān)注的熱點問題。早期對于該問題的研究只考慮任務(wù)指派或者路徑規(guī)劃中的1個方面。任務(wù)分配的目標(biāo)在于分配任務(wù)給合適的AGV 并決定作業(yè)順序。根據(jù)任務(wù)信息在調(diào)度周期內(nèi)是否可變分為靜態(tài)和動態(tài)2 種，靜態(tài)策略是在已知任務(wù)序列的前提下進行任務(wù)派發(fā)，以最小化成本或者最小化最末任務(wù)作業(yè)時間為目標(biāo)，考慮AGV作業(yè)限制如充電、載重等因素構(gòu)建混合整數(shù)規(guī)劃模型[2-3]求解出任務(wù)分配方案；動態(tài)策略是根據(jù)當(dāng)前AGV 的位置信息和新增任務(wù)信息進行任務(wù)派發(fā)，如基于競價概念的任務(wù)分配或是針對不確定環(huán)境的任務(wù)分配調(diào)整[4]。AGV調(diào)度除了決定作業(yè)序列，還需要規(guī)劃作業(yè)路徑，受自身體積、道路容量、碼頭布局和行駛路徑等因素的影響，作業(yè)過程中可能會出現(xiàn)沖突、死鎖等問題，因此AGV 路徑規(guī)劃的目標(biāo)在于尋找AGV 執(zhí)行任務(wù)的無碰路徑。根據(jù)環(huán)境信息是否已知可分為局部路徑規(guī)劃和全局路徑規(guī)劃。局部路徑規(guī)劃方法有粒子群算法，人工勢場法[5]，多應(yīng)用于倉庫或更開放的環(huán)境。自動化碼頭的AGV多是在已知碼頭環(huán)境下的全局路徑規(guī)劃，主要規(guī)劃算法有A*、Dijkstra、Floyd等[6]。除了路徑搜索，沖突規(guī)避問題也是AGV路徑規(guī)劃中的重點和難點，Lyu 等[7]將Dijkstra 算法與遺傳算法結(jié)合，規(guī)劃全局最短路徑的同時規(guī)避沖突，張中偉等[8]提出了不同沖突類型的時間窗模型并結(jié)合動態(tài)優(yōu)先級來解決路徑?jīng)_突問題。

早期的文獻中對AGV調(diào)度的研究多為AGV任務(wù)調(diào)度優(yōu)化，不考慮AGV 執(zhí)行任務(wù)的路徑規(guī)劃問題。因為任務(wù)分配和路徑規(guī)劃在AGV 調(diào)度的重要性和相關(guān)性，有一些學(xué)者在任務(wù)分配的約束條件中規(guī)避AGV 間的沖突，并提出了基于無沖突路徑的AGV 任務(wù)分配問題（dispatching and conflict-free route problem, DCFRP）。Krishnamurthy 等[9]基于該問題構(gòu)建了混合整數(shù)規(guī)劃模型，并使用了列生成算法求解。Correa 等[10]將柔性制造車間的調(diào)度主問題（即調(diào)度問題）建模為約束規(guī)劃問題，將子問題（即無沖突路由問題）建模為混合整數(shù)規(guī)劃問題，用CPLEX 求解了小規(guī)模的算例來驗證模型的有效性。余娜娜等[11]以最小化最末工作的完工時間為目標(biāo)，綜合考慮了自動分揀倉庫任務(wù)分配和路徑規(guī)劃，并提出了1 種在線協(xié)同算法實時調(diào)度AGV。Keisuke 等[12]考慮了AGV作業(yè)特點并基于時空網(wǎng)絡(luò)對AGV 進行調(diào)度，并提出了1 個有效的不等式來減少運算時間的算法，可以看到，目前對于AGV 綜合調(diào)度的研究多集中于柔性車間或者倉庫。

與車間或者倉庫比，自動化碼頭水平運輸作業(yè)區(qū)域廣，AGV 數(shù)量多且作業(yè)量大，因此涉及到的作業(yè)順序安排和隨機路徑?jīng)Q策問題更為復(fù)雜，僅考慮AGV 任務(wù)分配而不規(guī)劃路徑會導(dǎo)致AGV 作業(yè)路徑存在大量沖突。部分學(xué)者針對自動化碼頭的AGV綜合調(diào)度問題進行了研究。Hu 等[13]結(jié)合預(yù)規(guī)劃算法和實時規(guī)劃算法的優(yōu)點，提出了1 種三階段分解算法，將A*算法與時間窗原理相結(jié)合，按時間順序規(guī)劃每個AGV 的路徑并規(guī)避沖突。李靜等[14]以最小化AGV能耗為目標(biāo)設(shè)計了兩階段算法，第一階段基于最短路徑優(yōu)化AGV調(diào)度，第二階段基于沖突更新集裝箱AGV調(diào)度。Ji等[15]先建立集成調(diào)度問題的雙級編程模型，上層模型是3種設(shè)備的集成調(diào)度，下層模型是AGV的無沖突路徑規(guī)劃，接著基于沖突解決策略設(shè)計了2種雙級優(yōu)化算法。然而目前針對自動化碼頭AGV調(diào)度的研究仍舊較少。

梳理AGV調(diào)度相關(guān)研究，目前對于自動化碼頭AGV 調(diào)度系統(tǒng)相研究存在如下問題：①多數(shù)AGV調(diào)度的研究未能綜合考慮任務(wù)分配和路徑規(guī)劃問題；②未能考慮路徑規(guī)劃和任務(wù)分配的相互影響，路徑規(guī)劃沖突規(guī)避后未能考慮調(diào)整不合理的任務(wù)分配；③缺少對于自動化碼頭等待區(qū)域的研究；④缺少對于AGV集中作業(yè)的擁堵情況下AGV調(diào)度策略和路徑規(guī)劃的研究。

鑒于此，對考慮沖突規(guī)避的自動化碼頭AGV調(diào)度問題進行研究，結(jié)合AGV作業(yè)流程和自動化碼頭布局特點，綜合考慮了AGV任務(wù)分配和路徑規(guī)劃的相互影響，保證AGV 資源和路網(wǎng)資源配置的合理性，在追求作業(yè)成本最小化的同時確保多AGV間路徑無沖突。

1 問題描述

AGV 作業(yè)環(huán)境有倉庫和集裝箱碼頭。自動化碼頭對比倉庫或者車間具有車道數(shù)多，AGV 數(shù)量多，作業(yè)繁忙等特點。自動化碼頭布局見圖1，由堆場作業(yè)箱區(qū)，陸側(cè)裝卸區(qū)，AGV等待區(qū)，海側(cè)裝卸區(qū)等組成。AGV作業(yè)分為進口箱作業(yè)和出口箱作業(yè)，出口箱作業(yè)由堆場機械抓取指定集裝箱到AGV 上由AGV運輸?shù)胶?cè)，橋吊將AGV上的集裝箱裝載到指定貝位，進口箱作業(yè)則相反。為了避免AGV和橋吊或堆場機械相互等待的情況，在堆場和岸橋處均設(shè)有緩沖區(qū)暫時存放集裝箱。為了避免作業(yè)沖突，若AGV的目標(biāo)橋吊位置有AGV在進行裝卸作業(yè)，在從海側(cè)到陸側(cè)或陸側(cè)到海側(cè)時在等待區(qū)等待前1輛AGV作業(yè)完成。

圖1 自動化碼頭布局Fig.1 The layout of automatic port

任務(wù)分配和路徑規(guī)劃均會影響AGV 作業(yè)效率。任務(wù)分配不合理會增加AGV行駛距離；路徑規(guī)劃不合理會使得AGV 作業(yè)時需要頻繁的等待以規(guī)避沖突，嚴(yán)重時甚至?xí)霈F(xiàn)“死鎖”問題。因此對AGV 的調(diào)度需要合理的任務(wù)分配和路徑規(guī)劃減少總作業(yè)時間和路徑?jīng)_突帶來的等待時間。

分2 個階段研究自動化碼頭AGV 調(diào)度問題，第一階段根據(jù)任務(wù)位置和作業(yè)時間分配任務(wù)給AGV并決定作業(yè)順序，第二階段根據(jù)任務(wù)分配的結(jié)果在規(guī)避沖突的基礎(chǔ)上規(guī)劃路徑，針對擁堵問題，規(guī)避沖突后重新計算任務(wù)執(zhí)行的代價矩陣輸入第一階段模型再次進行任務(wù)分配，不斷迭代直到生成路徑規(guī)劃無沖突的任務(wù)分配方案。

2 模型構(gòu)建

2.1 基于自動化碼頭作業(yè)特點的AGV 任務(wù)分配模型

任務(wù)分配模型為AGV 決定任務(wù)序列。自動化碼頭作業(yè)中，AGV 1 次可裝載1 個40FEU 和2 個20TEU。AGV 作業(yè)流程見圖2，AGV 在完成上一任務(wù)后根據(jù)目前的電量和載重情況決定是否執(zhí)行下一階段的作業(yè)任務(wù)。部分文獻為了簡化模型不考慮AGV的多載和電量等因素，將任務(wù)分配看成m：n的指派問題。為了貼合自動化碼頭AGV的作業(yè)特點，將單個運輸任務(wù)精確到裝載和交付的具體操作，同時考慮了AGV多載和電量約束，因此該模型會比一般的任務(wù)分配模型復(fù)雜，可以看成是帶時間窗的裝卸貨問題（pickup and delivery problem with time window，PDPTW）求解。第一階段的模型為各個AGV決定任務(wù)序列，以最小作業(yè)成本為目標(biāo)完成所有水平運輸任務(wù)。任務(wù)用最早開始時間ai，最晚完成時間ei，生成節(jié)點i和目標(biāo)節(jié)點n+i來描述。

圖2 AGV作業(yè)流程圖Fig.2 AGV operation flowchart

模型假設(shè)如下。

1）AGV運行速度恒定。

2）AGV從充電站出發(fā)，電量不夠完成任意1組取送貨任務(wù)時返回充電站。

3）AGV在裝載交付任務(wù)中不消耗電量。

4）AGV 耗電恒定，滿電狀態(tài)下運行總距離、總時間相同。

5）AGV0時刻從充電站o出發(fā)。模型參數(shù)見表1。

表1 任務(wù)分配模型參數(shù)表Tab.1 Theparameters ofthe task allocation model

決策變量：xijk表示當(dāng)AGVk訪問任務(wù)節(jié)點i后是否訪問任務(wù)節(jié)點j，訪問時為1，否則為0。

目標(biāo)函數(shù)

約束條件

目標(biāo)函數(shù)式（1）是最小化AGV 總運行時間，本文用作業(yè)時間來衡量作業(yè)成本；式（2）保證完成裝載任務(wù)i后必須進行交付任務(wù)n+i；式（3）保證所有車輛從初始節(jié)點充電站出發(fā)；式（4）保證所有車輛最后回到充電站；式（5）是流量守恒約束；式（6）保證每個任務(wù)必須被執(zhí)行且僅執(zhí)行1次；式（7）為時間平衡約束；式（8）保證裝載任務(wù)必須在交付任務(wù)之前；式（9）為電量平衡約束；式（10）表示只有當(dāng)AGV的電量至少可以滿足裝載和交付任務(wù)才會被分配任務(wù)；且AGV 完成某一項任務(wù)后的電量應(yīng)該大于安全電量即可以返回充電站；式（11）為任務(wù)時間窗約束；式（12）為載重量約束。

2.2 基于時空網(wǎng)絡(luò)的AGV路徑規(guī)劃

上述任務(wù)分配模型決定AGV的任務(wù)序列，路徑規(guī)劃模型為AGV執(zhí)行任務(wù)規(guī)劃的路徑，并保證路徑間無沖突。路徑規(guī)劃需要對車間環(huán)境建模，常見的方法有：柵格圖和拓?fù)鋱D。作為高效的電子地圖建模方法，拓?fù)鋱D將AGV 的裝卸作業(yè)位置，停車位置等抽象成點，路徑抽象成邊。傳統(tǒng)碼頭或者倉庫的路網(wǎng)拓?fù)鋱D見圖3（a），其中黑色區(qū)域表示堆場或者貨架，AGV 可以深入堆場和貨架，在路徑上的任意點進行裝卸作業(yè)。自動化碼頭構(gòu)建路網(wǎng)拓?fù)鋱D見圖3（b），自動化碼頭主要作業(yè)區(qū)域集中在碼頭前沿，較少涉及堆場。

圖3 傳統(tǒng)碼頭和自動化碼頭路網(wǎng)示意圖Fig.3 Schematic diagram of traditional wharf and automated wharf road network

現(xiàn)有文獻大多將車間環(huán)境如碼頭或倉庫抽象成二維路網(wǎng)進行路徑規(guī)劃，在不考慮其他AGV路徑的前提下找到A點到B點的最短路徑，規(guī)劃完所有路徑后針對不同的沖突類型解決沖突。然而，這種方式不適用于自動化碼頭。自動化碼頭AGV 作業(yè)位置集中在海側(cè)和陸側(cè)，水平運輸區(qū)域空曠，路徑上的障礙多為來自其他AGV 的動態(tài)障礙。因此需要實時檢測路徑?jīng)_突并進行規(guī)避。如圖4 所示，將自動化碼頭離散成路網(wǎng)采用普通A*或Dijkstra算法得到的路徑在網(wǎng)格圖A點到B點中只有1 和2 這2 種路線，C點到D點只有3和4這2種路線。因此傳統(tǒng)算法下，AGV 路線會存在同質(zhì)化，作業(yè)時易出現(xiàn)大量路徑?jīng)_突。同時作業(yè)區(qū)域集中在兩側(cè)，AGV停留作業(yè)在此處集中會帶來“擁堵”問題。

圖4 普通A*或Dijkstra路徑規(guī)劃結(jié)果Fig.4 Result of Dijkstra orA*path planning

時空網(wǎng)絡(luò)（TSN），是在空間信息的基礎(chǔ)上添加時間信息構(gòu)建的網(wǎng)絡(luò)，見圖5。TSN由節(jié)點及節(jié)點之間連接的邊組成，每個節(jié)點代表特定時間的特定位置，每條邊對應(yīng)時間和可能的空間轉(zhuǎn)換。時空網(wǎng)絡(luò)記錄了AGV 在不同時段能到達的多個位置和多個可行路段。時間線連接不同的節(jié)點以表示AGV 整個運行路徑，每個時間線都包含開始節(jié)點和到達節(jié)點，上一時間線的到達節(jié)點是下1個時間線的開始節(jié)點，通過多個時間線不間斷連接來表示AGV運行的時間連續(xù)性，由此可以對AGV路徑進行時空分析。

圖5 時空網(wǎng)絡(luò)模型Fig.5 Spatiotemporal network model

時空網(wǎng)絡(luò)可以實時檢測AGV 的狀態(tài)信息和沖突路段，因此基于時空網(wǎng)絡(luò)的路徑規(guī)劃可以使AGV在規(guī)避沖突的前提下規(guī)劃路徑。因為時空網(wǎng)絡(luò)每1個節(jié)點和邊包含時間屬性，避免不同AGV遍歷相同節(jié)點和邊達到了規(guī)避多AGV 間的路徑?jīng)_突的目標(biāo)。模型參數(shù)見表2。

表2 路徑規(guī)劃模型參數(shù)表Tab.2 The parameters of the path planning model

決策變量：zkmnt表示AGVk在t時刻是否開始經(jīng)過弧mn，經(jīng)過為1，否則為0；ykmt表示AGVk在t時刻是否在節(jié)點m，在為1，否則為0。

目標(biāo)函數(shù)

約束條件

因為模型需要找到可行解，所以目標(biāo)函數(shù)式（13）是常數(shù)，旨在尋找無沖突路徑規(guī)劃的可行解；式（14）保證所有的AGV最初均在初始節(jié)點；式（15）保證所有AGV最后回到初始節(jié)點；式（16）保證每個時刻AGV 只處于1 個位置；式（17）為避免相向碰撞約束;式（18）為流量守恒約束；式（19）為所有的任務(wù)都在正確的時間節(jié)點被執(zhí)行；式（20）確保同1個時刻1個位置只有1臺AGV。

3 算法設(shè)計

3.1 任務(wù)分配和路徑規(guī)劃算法設(shè)計

3.1.1 任務(wù)分配求解算法

任務(wù)分配問題類似于PDPTW問題，屬于典型的NP-Hard 問題。為了快速求解，根據(jù)問題特點提出了2 階段的快速模擬退火算法，該算法有效避免了無效插入，加速算法收斂[18]。模擬退火算法（SA）被證實有概率收斂到全局最優(yōu)，其結(jié)果不依賴于初始解的好壞，有較好的魯棒性，缺點在于收斂速度慢。為了保證解的質(zhì)量和多次迭代的穩(wěn)定性，這里采用模擬退火算法對初始解進行改進。

1）初始解生成。從未被安排AGV的任務(wù)列表中隨機選出1 個組任務(wù)（裝載任務(wù)Pi和交付任務(wù)Di）插入現(xiàn)有AGV 任務(wù)序列中，使得執(zhí)行該組任務(wù)的代價最小且滿足載重約束和時間窗約束。若該任務(wù)沒有可插入的位置，則分配1 臺新的AGV 給該任務(wù)，L中刪除該任務(wù)；直到列表L為空時，輸出結(jié)果，否則繼續(xù)插入任務(wù)。

2）生成新解。新解產(chǎn)生的方式采用的是Remove和Insert過程。

Remove 過程：設(shè)置當(dāng)前解為w，選取當(dāng)前解w中AGV 任務(wù)列表中的任意任務(wù)（Pi和Di）移除。優(yōu)先選取執(zhí)行該任務(wù)對于此臺AGV 時間過長的任務(wù)(減少總行駛時間)以及任務(wù)數(shù)較少的AGV中的任務(wù)（減少車輛數(shù)），抽出的任務(wù)組成集合c1和c2。

Insert 過程：將集合c中的任務(wù)重新插入形成新解w'。將任務(wù)數(shù)較少的AGV 序列c1中選出的任務(wù)分配給任務(wù)數(shù)較多的AGV；將c2中執(zhí)行代價高（行駛時間長）的任務(wù)分配給插入代價最小的AGV。

3）計算新解f(w'),若f(w')＜f(w),接受新解，否則以概率e(-ΔT/T)（Metropolis準(zhǔn)則）接受w'作為新的當(dāng)前解w。

4）判斷迭代次數(shù)是否達到該溫度下的最大迭代次數(shù)，未達到則繼續(xù)迭代，達到則降低溫度進行新一輪的迭代，直到降低到設(shè)定的溫度，輸出最優(yōu)解。模擬退火算法參數(shù)設(shè)置初始溫度T0=2 000 ℃，α=0.99，每個溫度迭代次數(shù)n為1 000，終止迭代溫度為0.01 ℃。

3.1.2 路徑規(guī)劃求解算法

時空網(wǎng)絡(luò)模型可以建成混合整數(shù)規(guī)劃模型求解，但隨著任務(wù)數(shù)量的增加會減慢計算速度。因此我們采用NETWORKX建立時空網(wǎng)絡(luò)進行路徑規(guī)劃的算法[19]，該算法可以顯著加快求解速度。時空網(wǎng)絡(luò)中，每個節(jié)點用坐標(biāo)x，y和時刻T表示，邊的權(quán)重屬性用該節(jié)點到達下1個節(jié)點時間表示。路徑規(guī)劃時根據(jù)任務(wù)的起始節(jié)點和目標(biāo)節(jié)點構(gòu)造t層時空網(wǎng)絡(luò)，基于該時空網(wǎng)絡(luò)執(zhí)行最短路徑算法進行路徑規(guī)劃。

對于沖突規(guī)避，目前文獻中對路徑規(guī)劃的研究是基于二維路網(wǎng)尋找起點到終點的最短路徑，完成所有任務(wù)的尋路后再處理路徑中可能出現(xiàn)的沖突[15-16]。如圖6所示，AGV路徑?jīng)_突的類型有相向沖突，節(jié)點沖突，占位沖突，追趕沖突4種，根據(jù)不同的沖突類型提出不同的規(guī)避方案。

圖6 AGV沖突類型Fig.6 AGV conflict type

時空網(wǎng)絡(luò)可以在實時檢測AGV 位置信息和沖突路段的基礎(chǔ)上規(guī)避沖突。一般情況下本文的度模型迭代求解1次就可以得到多AGV間路徑無沖突的調(diào)度方案。但是，當(dāng)任務(wù)分配不合理時，會出現(xiàn)路徑規(guī)劃無可行解的情況：在某一時間段路網(wǎng)的某一區(qū)域有多臺作業(yè)AGV，這個可以被稱為“擁堵”現(xiàn)象，映射在時空網(wǎng)絡(luò)上就是不存在起點到終點的無沖突路徑。傳統(tǒng)沖突處理策略在調(diào)整完路徑后沒有考慮后續(xù)影響，在這種“擁堵”情況下，沖突節(jié)點的前1個節(jié)點等待或重新調(diào)整路徑可能會使得AGV 發(fā)生2 次沖突，更無法解決多輛AGV在同一節(jié)點存在沖突的問題。

自動化碼頭裝卸作業(yè)集中在海陸兩側(cè)，因此該區(qū)域易發(fā)生擁堵現(xiàn)象。為了解決擁堵問題，提出了基于時空網(wǎng)絡(luò)和自動化碼頭布局特點的規(guī)避方式。圖7為基于時空網(wǎng)絡(luò)的路徑規(guī)劃示意圖，需要規(guī)劃A在t時刻經(jīng)過n個時間段到達C的路徑。若在時空網(wǎng)絡(luò)中不存在At到Ct+n的通路（路徑中的邊和節(jié)點被其他AGV遍歷），此時AGV需在到達Ct+n前在等待節(jié)點進行等待wt避免擁堵，此時AGV 到達的時間網(wǎng)絡(luò)的節(jié)點不再是Ct+n而是Ct+n+wt。

圖7 基于時空網(wǎng)絡(luò)的路徑規(guī)劃Fig.7 Path planning based on spatiotemporal network

針對不同的沖突類型，AGV規(guī)避沖突需要等待的時間不同。表3為不同沖突類型的等待時間計算方法。其中優(yōu)先級與電量相關(guān)，電量越低優(yōu)先級越高。

表3 不同沖突類型解決方法Tab.3 Different conflict types resolution methods

3.2 任務(wù)分配和路徑規(guī)劃算法設(shè)計

第一階段的任務(wù)分配模型會得到多個AGV 執(zhí)行任務(wù)的序列以及到達任務(wù)節(jié)點和離開任務(wù)節(jié)點的時間。將其輸入路徑規(guī)劃模型，任務(wù)節(jié)點的坐標(biāo)x，y加上時刻T為路徑規(guī)劃模型中構(gòu)建的時空網(wǎng)絡(luò)尋路的起點或者終點，路徑規(guī)劃模型基于起點和終點為AGV 作業(yè)規(guī)劃無碰撞的安全路徑。如果部分AGV 無法在時空網(wǎng)絡(luò)上找到起點到目標(biāo)節(jié)點的通路，則需要進行擁堵情況沖突規(guī)避和任務(wù)分配調(diào)整。時空網(wǎng)絡(luò)的優(yōu)點可以實時檢測沖突并進行規(guī)避，若仍舊存在沖突，本質(zhì)原因在于任務(wù)分配不均衡使得AGV 集中作業(yè)。因此需要針對沖突規(guī)避的結(jié)果將AGV 從作業(yè)點i到任務(wù)點j的等待作業(yè)時間wt加上原來執(zhí)行任務(wù)的時間tijk計算出新的任務(wù)執(zhí)行時間tijk+wt。在此基礎(chǔ)上形成新的代價矩陣再次輸入任務(wù)分配模型，不斷迭代，直到生成無沖突的路徑的AGV任務(wù)分配。算法流程見圖8。

圖8 算法流程圖Fig.8 Algorithm flowchart

4 算例分析

4.1 小規(guī)模算例

為了說明算法流程，基于碼頭作業(yè)特點隨機生成的小規(guī)模算例。算例由Python 隨機生成，整個算法由Python 3.7 的工具包GUROBI 求解器求解。實驗平臺在2.20 GHz PC，16 GB RAM，Windows10，64 位操作系統(tǒng)上運行。如表4 所示，最早開始時間和最遲完成時間組成任務(wù)時間窗，Pi以及Di分別為該任務(wù)相關(guān)的裝載或者交付任務(wù)。根據(jù)AGV 作業(yè)特點和地圖設(shè)定AGV 速度為1 m/s，1 次可托運1個40FEU或者2個20TEU，需求中用40和20代表集裝箱類型。以上為12個任務(wù)的小規(guī)模和5×5的小地圖，因為地圖較小，不另設(shè)等待節(jié)點，所有節(jié)點均可等待。

表4 小規(guī)模算例Tab.4 Small-scale study

使用GUROBI 求解兩階段的混合整數(shù)規(guī)劃模型，得到AGV的作業(yè)順序和作業(yè)路徑。路徑由x坐標(biāo)，y坐標(biāo)和時刻T表示。模型的第1 次迭代結(jié)果見表5。

由表5可見：AGV3規(guī)劃路徑時出現(xiàn)了無可行解的情況。沖突見圖9，7 s時AGV3在（2，1）節(jié)點執(zhí)行任務(wù)后不存在到達下1 個任務(wù)節(jié)點（1，3）節(jié)點的通路。2 個方向的道路（2，3，9）和（1，2，9）均被AGV1和AGV2遍歷。

圖9 沖突示意圖Fig.9 Conflict diagram

表5 第1 次迭代結(jié)果Tab.5 Results of the first iteration

此時需要規(guī)避沖突，規(guī)避流程見圖10，AGV在（2，1）節(jié)點等待后時空網(wǎng)絡(luò)的目標(biāo)節(jié)點更改為（3，3，11）。

圖10 沖突規(guī)避示意圖Fig.10 ConflictAvoidance Diagram

調(diào)整后執(zhí)行任務(wù)2后執(zhí)行任務(wù)3的代價已變化，再次進行任務(wù)分配得到新的任務(wù)分配和路徑規(guī)劃方案見表6。

表6 AGV 調(diào)度結(jié)果Tab.6 AGV scheduling results

4.2 大規(guī)模算例

為了驗證模型在大規(guī)模問題下的求解速度表現(xiàn)和后續(xù)實驗對比?；谘笊礁鄣牟季衷O(shè)計AGV 的實驗環(huán)境。整個算法由Python 編程求解實現(xiàn)，其中時空網(wǎng)絡(luò)由Python 的工具包NetworkX 編譯構(gòu)建。路網(wǎng)基于洋山港岸橋，橋吊緩沖區(qū)等關(guān)鍵節(jié)點建立，設(shè)立等待區(qū)域供AGV 停留以規(guī)避沖突。路網(wǎng)參數(shù)設(shè)置見表7。

表7 路網(wǎng)參數(shù)Tab.7 Road network parameters

將本文提出的求解算法（FSA-TSN）與求解PDPTW常用的遺傳算法（GA）及求解器GUROBI的求解時間進行對比。根據(jù)上述路網(wǎng)參數(shù)隨機生成20組10，20，30，40，100個任務(wù)的算例，使用上述3種算法求解，不同任務(wù)規(guī)模下3 種算法平均求解時間見表8?？梢娦∫?guī)模任務(wù)下，求解速度是相近的。但隨著任務(wù)規(guī)模的提升，求解器的求解速度不斷降低，當(dāng)求解任務(wù)規(guī)模達到100時，求解時間超過1 h，因此無法適應(yīng)碼頭繁忙作業(yè)情況。與常見的啟發(fā)式算法GA相比，筆者提出的兩階段算法避免了無效的插入加速了算法收斂，提高了求解速度。綜上，本文的算法在求解速度上優(yōu)于求解器和傳統(tǒng)的啟發(fā)式算法。

表8 不同算法求解速度對比Tab. 8 The speed comparison of different algorithms

4.3 實驗設(shè)置

實驗1。不考慮多AGV間路徑?jīng)_突的調(diào)度模型默認(rèn)任務(wù)分配后以最短路徑執(zhí)行任務(wù)（TAP-SP）。對比不同任務(wù)規(guī)模下本文的調(diào)度模型（TAP-TSN）和TAP-SP的沖突數(shù)量和成本。

實驗2。針對擁堵情況，本文模型的調(diào)整方式是沖突規(guī)避后調(diào)整AGV 任務(wù)分配，追求AGV 路徑無沖突的前提下最小化作業(yè)成本。對比本文的AGV調(diào)度模型與傳統(tǒng)的三階段AGV調(diào)度模型，即任務(wù)分配后基于二維路網(wǎng)規(guī)劃路徑，并根據(jù)路徑規(guī)劃中的沖突類型解決沖突的三階段調(diào)度模型[13]。用任務(wù)延期時間和沖突數(shù)量及路網(wǎng)擁堵率3個指標(biāo)來衡量算法的優(yōu)劣。其中擁堵率的計算方式時總?cè)蝿?wù)延誤時間比上總?cè)蝿?wù)完成時間[22]。

4.4 實驗結(jié)果分析

實驗1 結(jié)果與分析。分別用TAP-TSN 和TAP-SP求解不同規(guī)模的算例，得到?jīng)_突數(shù)量與作業(yè)成本見表9。其中，規(guī)避前的TAP-SP 作業(yè)成本是不考慮沖突前提下以最小化AGV 作業(yè)總時間為目標(biāo)計算得出的，其結(jié)果存在大量沖突，且跟隨任務(wù)數(shù)的增長不斷增加。而實際的時間成本在規(guī)避沖突后平均增加了9.91%。與之相比，本文的算法在任務(wù)數(shù)到達600時仍舊不會出現(xiàn)沖突。同時該算法的成本與未考慮沖突規(guī)避的成本是相近的，最大成本增加不超過2.6%。綜上，對于自動化碼頭AGV的調(diào)度需要完成任務(wù)分配和路徑規(guī)劃2方面的調(diào)度。

表9 TAP-TSN 和TAP-SP 沖突數(shù)量對比Tab.9 Comparison of the number of conflicts between TAP-TSN and TAP-SP

實驗2結(jié)果與分析。分別用本文調(diào)度模型和三階段調(diào)度模型求解不同規(guī)模的算例，得到任務(wù)延期時間和數(shù)量及路網(wǎng)擁堵度見表10。由表10可見：本文的算法可以有效地避免多AGV 間的路徑?jīng)_突和任務(wù)延期。在算例中，不同任務(wù)規(guī)模下，本文提出的算法AGV路徑?jīng)_突均為0，而傳統(tǒng)避障策略在更改路徑或等待后仍存在沖突。任務(wù)延期方面，本文的算法最大降低任務(wù)延期時間2 895 s。同時該算法相較三階段的調(diào)度模型而言，降低了路網(wǎng)擁堵度，在任務(wù)箱數(shù)量為100，200，300，400個時分別降低5.73%，5.48%，8.47%，10.79%。因此本文提出的調(diào)度模型和沖突處理策略對于解決自動化碼頭AGV調(diào)度更為有效。

表10 三階段調(diào)度模型與本文模型對比Tab.10 Comparison between three-stage scheduling model and this model

5 結(jié)束語

本文針對AGV調(diào)度的2個子問題任務(wù)序列分配和路徑規(guī)劃提出了1 個兩階段的模型，結(jié)合自動化集裝箱碼頭布局和作業(yè)特點，構(gòu)建兩階段模型解決調(diào)度中的任務(wù)分配和路徑規(guī)劃問題，為AGV決定任務(wù)序列分配的同時規(guī)劃執(zhí)行任務(wù)的無沖突路徑。任務(wù)分配模型以最小化作業(yè)成本為目標(biāo)，路徑規(guī)劃模型以多AGV間路徑無沖突為目標(biāo)；采用改進的模擬退火算法確定AGV作業(yè)序列，在減少任務(wù)延期的前提下，利用時空網(wǎng)絡(luò)在規(guī)避沖突基礎(chǔ)上規(guī)劃AGV路徑。針對路徑規(guī)劃無可行解的擁堵情況，規(guī)避沖突后重新計算代價矩陣再次進行任務(wù)分配以調(diào)整AGV 任務(wù)分配不合理帶來的集中作業(yè)問題。在此基礎(chǔ)上，與其他調(diào)度模型對比，可以得出以下結(jié)論。

1）本文綜合考慮了AGV電量，多載和自動化碼頭的布局構(gòu)建模型，符合自動化碼頭AGV的實際作業(yè)過程，具有較強的實用性。

2）與本文的模型對比，在不考慮沖突規(guī)避的調(diào)度模型的實驗結(jié)果中沖突數(shù)量隨任務(wù)規(guī)模增大不斷增大，最大達到310個，因此針對自動化碼頭AGV調(diào)度的研究需要考慮沖突規(guī)避問題。

3）本文針對擁堵情況采取沖突規(guī)避后調(diào)整不合理任務(wù)分配的方式，避免了任務(wù)分配不均衡帶來的路徑?jīng)_突問題，從結(jié)果上看與不調(diào)整相比降低了任務(wù)延期時間和路網(wǎng)擁堵度。

本文的研究符合自動化碼頭AGV 實際作業(yè)過程，并在傳統(tǒng)調(diào)度模型的基礎(chǔ)上考慮了沖突規(guī)避問題，但還存在一些不足，兩階段模型需要多次迭代，利用啟發(fā)式算法求解會有不穩(wěn)定的問題，因此采用列生成算法求解本文的模型將作為未來的研究方向。