丁 一 袁 浩 方懷瑾 田 宇

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

0 引 言

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

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

早期的文獻(xiàn)中對(duì)AGV調(diào)度的研究多為AGV任務(wù)調(diào)度優(yōu)化，不考慮AGV 執(zhí)行任務(wù)的路徑規(guī)劃問題。因?yàn)槿蝿?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ī)模的算例來驗(yàn)證模型的有效性。余娜娜等[11]以最小化最末工作的完工時(shí)間為目標(biāo)，綜合考慮了自動(dòng)分揀倉(cāng)庫(kù)任務(wù)分配和路徑規(guī)劃，并提出了1 種在線協(xié)同算法實(shí)時(shí)調(diào)度AGV。Keisuke 等[12]考慮了AGV作業(yè)特點(diǎn)并基于時(shí)空網(wǎng)絡(luò)對(duì)AGV 進(jìn)行調(diào)度，并提出了1 個(gè)有效的不等式來減少運(yùn)算時(shí)間的算法，可以看到，目前對(duì)于AGV 綜合調(diào)度的研究多集中于柔性車間或者倉(cāng)庫(kù)。

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

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

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

1 問題描述

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

圖1 自動(dòng)化碼頭布局Fig.1 The layout of automatic port

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

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

2 模型構(gòu)建

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

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

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

模型假設(shè)如下。

1）AGV運(yùn)行速度恒定。

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

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

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

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

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

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

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

約束條件

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

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

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

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

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

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

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

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

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

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

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

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

約束條件

因?yàn)槟Ｐ托枰业娇尚薪?，所以目?biāo)函數(shù)式（13）是常數(shù)，旨在尋找無沖突路徑規(guī)劃的可行解；式（14）保證所有的AGV最初均在初始節(jié)點(diǎn)；式（15）保證所有AGV最后回到初始節(jié)點(diǎn)；式（16）保證每個(gè)時(shí)刻AGV 只處于1 個(gè)位置；式（17）為避免相向碰撞約束;式（18）為流量守恒約束；式（19）為所有的任務(wù)都在正確的時(shí)間節(jié)點(diǎn)被執(zhí)行；式（20）確保同1個(gè)時(shí)刻1個(gè)位置只有1臺(tái)AGV。

3 算法設(shè)計(jì)

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

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

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

1）初始解生成。從未被安排AGV的任務(wù)列表中隨機(jī)選出1 個(gè)組任務(wù)（裝載任務(wù)Pi和交付任務(wù)Di）插入現(xiàn)有AGV 任務(wù)序列中，使得執(zhí)行該組任務(wù)的代價(jià)最小且滿足載重約束和時(shí)間窗約束。若該任務(wù)沒有可插入的位置，則分配1 臺(tái)新的AGV 給該任務(wù)，L中刪除該任務(wù)；直到列表L為空時(shí)，輸出結(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ù)對(duì)于此臺(tái)AGV 時(shí)間過長(zhǎng)的任務(wù)(減少總行駛時(shí)間)以及任務(wù)數(shù)較少的AGV中的任務(wù)（減少車輛數(shù)），抽出的任務(wù)組成集合c1和c2。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算例分析

4.1 小規(guī)模算例

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

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

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

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

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

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

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

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

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

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

4.2 大規(guī)模算例

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

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

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

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

4.3 實(shí)驗(yàn)設(shè)置

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

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

4.4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5 結(jié)束語

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

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

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

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

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