基于時(shí)空網(wǎng)絡(luò)的自動(dòng)化集裝箱碼頭自動(dòng)化導(dǎo)引車(chē)路徑規(guī)劃

高一鷺，胡志華

（上海海事大學(xué)物流研究中心，上海201306）（*通信作者電子郵箱zhhu@shmtu.edu.cn）

0 引言

自動(dòng)化導(dǎo)引車(chē)（Automated Guided Vehicle，AGV）是自動(dòng)化集裝箱碼頭（Automated Container Terminal，ACT）水平運(yùn)輸?shù)闹饕O(shè)備［1］，承擔(dān)岸邊與堆場(chǎng)之間集裝箱的搬運(yùn)任務(wù)，與岸橋和場(chǎng)橋互相協(xié)調(diào)共同完成碼頭的裝卸作業(yè)。AGV 路徑是指搬運(yùn)任務(wù)作業(yè)過(guò)程中，AGV 從任務(wù)起點(diǎn)（Origin，O）到終點(diǎn)（Destination，D）的行駛軌跡，而ACT 連續(xù)作業(yè)下，多輛AGV同時(shí)共享道路網(wǎng)絡(luò)并行完成大量裝卸任務(wù)，因此AGV 行駛軌跡可能發(fā)生交叉或重疊從而導(dǎo)致AGV 發(fā)生碰撞、擁堵等沖突問(wèn)題。AGV 路徑?jīng)_突若處理不當(dāng)，則導(dǎo)致AGV 單次作業(yè)時(shí)間延長(zhǎng)，作業(yè)成本增加，同時(shí)增加岸橋或場(chǎng)橋的等待時(shí)間，延長(zhǎng)ACT 整體裝卸時(shí)間，從而降低其運(yùn)作效率并大幅度增加碼頭作業(yè)成本。因此考慮沖突規(guī)避的多AGV 路徑規(guī)劃是ACT 運(yùn)作管理的關(guān)鍵問(wèn)題，相關(guān)的模型與算法研究為碼頭的運(yùn)營(yíng)和管理提供重要的理論依據(jù)［2-4］。

沖突規(guī)避的AGV 路徑規(guī)劃問(wèn)題已成為當(dāng)前研究的重點(diǎn)。Lyu 等［5］將帶時(shí)間窗的Dijkstra 算法嵌入遺傳算法中，搜索最短路徑同時(shí)檢測(cè)多車(chē)輛的碰撞情況；Fazlollahtabar等［6］建立混合整數(shù)規(guī)劃模型并提出兩階段優(yōu)化方法（搜索解空間和尋找最優(yōu)解）來(lái)規(guī)避AGV 之間的沖突；Nishi 等［7］提出動(dòng)態(tài)環(huán)境中雙向AGV 系統(tǒng)調(diào)度和路徑?jīng)_突規(guī)避的Petri網(wǎng)分解方法，整個(gè)Petri 網(wǎng)分解為任務(wù)子網(wǎng)和AGV 子網(wǎng)并在AGV 子網(wǎng)中嵌入避免死鎖的方法；Miyamoto 等［8］建立混合整數(shù)規(guī)劃模型，并提出局部隨機(jī)搜索方法求解容量限制的AGV 系統(tǒng)調(diào)度和沖突規(guī)避的路徑規(guī)劃問(wèn)題。以上研究同時(shí)考慮AGV 路徑規(guī)劃以及任務(wù)調(diào)度問(wèn)題，通過(guò)調(diào)整AGV 任務(wù)作業(yè)序列以規(guī)避路徑?jīng)_突。然而，大部分情況下AGV任務(wù)執(zhí)行順序是確定的。

在AGV 任務(wù)作業(yè)順序確定條件下，較多文獻(xiàn)關(guān)注于路徑搜索方法：Ma?opolski 等［9］用矩陣描述運(yùn)輸系統(tǒng)布局，將AGV的運(yùn)動(dòng)視為以固定的平均速度從矩陣到矩陣的運(yùn)動(dòng)，進(jìn)而提出一種防止AGV碰撞和死鎖的新方法；Antakly等［10］利用時(shí)間Petri 網(wǎng)進(jìn)行建模并提出三階段的啟發(fā)式算法，通過(guò)對(duì)AGV 施加適當(dāng)?shù)难舆t以避免與其他AGV 發(fā)生碰撞；Mohammadi 等［11］提出一種基于仿真的高級(jí)柔性工藝模型，通過(guò)預(yù)見(jiàn)機(jī)制以動(dòng)態(tài)預(yù)防AGV的碰撞和死鎖；Fanti等［12］通過(guò)區(qū)域控制分散協(xié)議協(xié)調(diào)AGV 運(yùn)動(dòng)以規(guī)避碰撞；郭興海等［13］考慮動(dòng)態(tài)環(huán)境下根據(jù)障礙物的運(yùn)動(dòng)情況，提出感應(yīng)轉(zhuǎn)向算法使AGV 規(guī)避障礙物；Nishi 等［14］考慮AGV 加速或減速條件下沖突規(guī)避的路徑規(guī)劃問(wèn)題，建立連續(xù)時(shí)間模型并提出基于列生成的啟發(fā)式算法；劉二輝等［15］提出路徑微調(diào)算子使路徑片段變短以避開(kāi)障礙物，實(shí)現(xiàn)基于遺傳算法的動(dòng)態(tài)路徑規(guī)劃；曹小華等［16］結(jié)合圖論提出一種基于頂點(diǎn)屬性和實(shí)時(shí)位置信息的沖突預(yù)測(cè)方法，建立混合整數(shù)規(guī)劃模型并提出一種適用于多AGV 系統(tǒng)避碰決策優(yōu)化的改進(jìn)粒子群優(yōu)化算法；李軍軍等［17］通過(guò)分析路段與節(jié)點(diǎn)沖突問(wèn)題建立混合整數(shù)規(guī)劃模型并提出一種誘導(dǎo)蟻群粒子群算法，在算法的狀態(tài)轉(zhuǎn)移規(guī)則中，增加誘導(dǎo)因子來(lái)引導(dǎo)AGV 規(guī)避沖突；鄭延斌等［18］針對(duì)多Agent 路徑規(guī)劃問(wèn)題，提出一個(gè)基于蟻群算法及博弈論的兩階段路徑規(guī)劃算法，為解決多Agent 之間的碰撞，利用博弈論構(gòu)建多Agent 之間的動(dòng)態(tài)避障模型并利用虛擬行動(dòng)法來(lái)求解多Nash 均衡的選擇問(wèn)題。以上研究通過(guò)設(shè)計(jì)和調(diào)整AGV 行駛路線或者采取等待措施以規(guī)避路徑?jīng)_突，然而，大部分沖突規(guī)避的路徑規(guī)劃研究主要面向生產(chǎn)制造系統(tǒng)。

自動(dòng)化碼頭與制造系統(tǒng)相比，運(yùn)輸區(qū)域面積更大且無(wú)障礙物，交通規(guī)則更靈活，并且AGV 尺寸更大且數(shù)量更多，碼頭全自動(dòng)連續(xù)作業(yè)要求AGV 與岸橋和場(chǎng)橋交互作業(yè)誤差盡可能小，因此對(duì)AGV 路徑進(jìn)行合理規(guī)劃具有一定難度。Xin等［19］提出一種層次控制體系結(jié)構(gòu)以滿足交互設(shè)備的集成調(diào)度，并且按照調(diào)度的總體圖序列，通過(guò)順序求解混合整數(shù)規(guī)劃問(wèn)題以獲得滿足AGV沖突規(guī)避的軌跡規(guī)劃；Yang等［20］建立一個(gè)雙層編程模型并提出基于道路堵塞預(yù)防規(guī)則的雙層遺傳算法，以解決碼頭起重機(jī)、自動(dòng)導(dǎo)引車(chē)和堆場(chǎng)起重機(jī)的集成調(diào)度問(wèn)題；Xin 等［21］提出一種兩級(jí)能量感知方法，通過(guò)高級(jí)控制器解決控制問(wèn)題以確定各個(gè)AGV 的碰撞規(guī)避軌跡；Li等［22］提出AGV 系統(tǒng)流量控制算法，通過(guò)減少每個(gè)區(qū)域的最小允許面積來(lái)提高工作區(qū)的利用率并設(shè)計(jì)一種緊急交通控制方案，以避免因車(chē)輛故障而導(dǎo)致的車(chē)輛碰撞和死鎖。然而目前，自動(dòng)化碼頭AGV路徑規(guī)劃相關(guān)研究較少。

上述文獻(xiàn)提出的算法大多數(shù)在規(guī)劃路徑時(shí)設(shè)計(jì)沖突預(yù)測(cè)機(jī)制以檢測(cè)沖突，發(fā)現(xiàn)沖突后則返回路徑規(guī)劃或者調(diào)度問(wèn)題求解中，然而算法并沒(méi)有實(shí)時(shí)檢測(cè)沖突路段進(jìn)行一次路徑規(guī)劃，因此增加了計(jì)算的復(fù)雜性。本文研究自動(dòng)化碼頭AGV 路徑規(guī)劃問(wèn)題，在AGV 作業(yè)任務(wù)順序確定條件下，通過(guò)構(gòu)造AGV 的時(shí)空網(wǎng)絡(luò)以實(shí)時(shí)反映AGV 狀態(tài)信息和檢測(cè)沖突路段，并以任務(wù)完工時(shí)間最小為目標(biāo)，對(duì)實(shí)際路段擁堵情況建立模型和設(shè)計(jì)時(shí)空網(wǎng)絡(luò)算法，優(yōu)先調(diào)整路線以規(guī)避路徑的碰撞和擁堵。

1 問(wèn)題描述

ACT 由岸邊、AGV 和堆場(chǎng)三個(gè)作業(yè)區(qū)組成，布局如圖1所示。其中，AGV 作業(yè)區(qū)包括海陸兩側(cè)裝卸區(qū)、緩沖區(qū)和行駛區(qū)，海側(cè)裝卸區(qū)和行駛區(qū)下設(shè)有能控制小車(chē)轉(zhuǎn)彎方向的車(chē)道。AGV 作業(yè)可分為進(jìn)口箱和出口箱作業(yè)。以進(jìn)口箱作業(yè)為例說(shuō)明其作業(yè)流程。1）在海側(cè)裝卸區(qū)的起始位置（O點(diǎn)），岸橋放置集裝箱到AGV 上，AGV 完成裝載；2）AGV 轉(zhuǎn)彎進(jìn)入緩沖區(qū)進(jìn)行排序，根據(jù)規(guī)劃的路徑進(jìn)入指定的行駛區(qū)車(chē)道，行駛到陸側(cè)裝卸區(qū)的目標(biāo)位置（D點(diǎn)）；3）場(chǎng)橋卸載AGV 上的集裝箱移至堆場(chǎng)箱區(qū)存儲(chǔ)，AGV 完成一次裝卸作業(yè)。對(duì)于出口箱作業(yè)任務(wù)，則反之。一輛AGV 同一時(shí)刻只能作業(yè)一個(gè)任務(wù)，只有完成當(dāng)前的作業(yè)任務(wù)才可以執(zhí)行下一個(gè)任務(wù)，同一個(gè)任務(wù)在作業(yè)過(guò)程中不能中斷。另外，AGV 行駛過(guò)程需遵守港區(qū)局部物流交通系統(tǒng)中的交通規(guī)則，例如轉(zhuǎn)彎、擁堵停車(chē)和讓道等，當(dāng)某一道路擁堵時(shí)AGV可在緩沖區(qū)等待。

圖1 自動(dòng)化集裝箱碼頭布局Fig.1 Layout of automated container terminal

通常，將一輛AGV 從任務(wù)的O點(diǎn)到D點(diǎn)的行駛路徑設(shè)為兩點(diǎn)之間的最短路徑，并且假定該最短路徑上的所有路段都是通暢可行的［23］，然而該做法沒(méi)有考慮AGV 在實(shí)際路段中的運(yùn)行軌跡以及運(yùn)行過(guò)程中的實(shí)時(shí)動(dòng)態(tài)干涉，導(dǎo)致AGV 根據(jù)規(guī)劃路徑進(jìn)行作業(yè)時(shí)產(chǎn)生沖突。路徑?jīng)_突情況包括碰撞和擁堵，在圖2中，舉例說(shuō)明AGV 沖突問(wèn)題。任務(wù)1 和任務(wù)2 同為進(jìn)口箱作業(yè)，任務(wù)1和任務(wù)2的OD點(diǎn)分別為O1D1、O2D2，實(shí)線表示小車(chē)實(shí)際經(jīng)過(guò)的路線，虛線表示計(jì)劃行駛但未行駛的路線。圖2（a）展示了碰撞的發(fā)生情況，執(zhí)行任務(wù)1 的AGV 與執(zhí)行任務(wù)2 的AGV 在不同時(shí)刻出發(fā)卻在同一時(shí)刻到達(dá)點(diǎn)A，發(fā)生碰撞導(dǎo)致任務(wù)執(zhí)行失敗。圖2（b）展示了擁堵的發(fā)生情況，執(zhí)行任務(wù)1和執(zhí)行任務(wù)2的2輛AGV 會(huì)在同一時(shí)刻到達(dá)A點(diǎn)，但為避免碰撞，執(zhí)行任務(wù)2 的AGV 行駛到緩沖區(qū)B點(diǎn)時(shí)停車(chē)等待，造成擁堵現(xiàn)象。AGV 發(fā)生碰撞將直接導(dǎo)致設(shè)備損壞，大幅度增加成本，設(shè)備停留在路段中占用路段資源，可能與即將行駛進(jìn)路網(wǎng)的AGV 發(fā)生二次碰撞，并且處理碰撞事故所需時(shí)間和人力成本較高；等待是避免碰撞的常用手段，但AGV減速及加速過(guò)程所消耗的電力成本較高，并且AGV 等待減少了可用的道路資源，道路會(huì)因?yàn)锳GV 的等待而出現(xiàn)擁堵，嚴(yán)重時(shí)會(huì)導(dǎo)致整個(gè)路網(wǎng)癱瘓導(dǎo)致ACT 被迫停止運(yùn)作。所以，當(dāng)路段本身成為臨界資源時(shí)，AGV 對(duì)路段具有獨(dú)占性，因此，考慮AGV 在不同時(shí)刻在路網(wǎng)上的狀態(tài)是判別碰撞和擁堵的前提條件。

圖2 AGV在路網(wǎng)上的沖突情況Fig.2 Conflicts of AGVs in road network

在AGV 的行駛過(guò)程中，從當(dāng)前時(shí)刻的位置出發(fā)，下一時(shí)刻可選的到達(dá)位置通常有多個(gè)；在各個(gè)不同位置上的下一個(gè)可能到達(dá)的位置又是不同的，因此，建立在道路網(wǎng)絡(luò)背景下隨時(shí)間演變的時(shí)空網(wǎng)絡(luò)。利用AGV 在不同時(shí)刻可能到達(dá)的不同位置，從而刻畫(huà)出AGV 從任務(wù)起點(diǎn)出發(fā)的一個(gè)可行的帶有時(shí)間和位置標(biāo)簽的網(wǎng)絡(luò)，路徑規(guī)劃則是在該網(wǎng)絡(luò)中選擇一條完工時(shí)間最短的路徑。本文在ACT 背景下建立AGV時(shí)空網(wǎng)絡(luò)，在時(shí)空網(wǎng)絡(luò)中規(guī)劃AGV 最短路徑，以任務(wù)完工時(shí)間最短為目標(biāo)，建立數(shù)學(xué)模型并設(shè)計(jì)時(shí)空網(wǎng)絡(luò)算法，使規(guī)劃路徑規(guī)避碰撞并緩解擁堵。

2 數(shù)學(xué)模型

路徑優(yōu)化基礎(chǔ)模型如M1所示，其相關(guān)符號(hào)定義如表1所示。

模型M1的目標(biāo)函數(shù)（1）為最小化時(shí)間成本；約束（2）和（3）表示任務(wù)作業(yè)的先后關(guān)系，AGV 從起始位置O開(kāi)始作業(yè)，作業(yè)完成后回到終點(diǎn)位置D；約束（4）是網(wǎng)絡(luò)流量平衡約束，任意節(jié)點(diǎn)的出度等于節(jié)點(diǎn)的入度。

M1不考慮AGV 在實(shí)際路段中的運(yùn)行軌跡，并假定路徑之間不會(huì)互相干涉。實(shí)際上，M1規(guī)劃出的當(dāng)前路徑可能產(chǎn)生一些時(shí)刻下的不可行路段，若執(zhí)行后續(xù)任務(wù)的AGV 占用不可行路段將產(chǎn)生沖突。為了規(guī)避沖突，保證AGV 在運(yùn)行過(guò)程中路徑的暢通，根據(jù)上述界定的2 種沖突情況（碰撞和擁堵）進(jìn)行建模。建模思想為：通過(guò)更新路網(wǎng)中新任務(wù)開(kāi)始時(shí)刻下的可用節(jié)點(diǎn)集合實(shí)時(shí)規(guī)避該路徑可能出現(xiàn)的碰撞以及緩解路網(wǎng)的擁堵；更新方法為：在時(shí)空網(wǎng)絡(luò)下剔除當(dāng)前任務(wù)規(guī)劃下的不可用路段。值得注意的是，每一次規(guī)劃新任務(wù)路徑前，由于當(dāng)前任務(wù)的路徑產(chǎn)生了一些時(shí)刻下的新不可行路段，因此每個(gè)節(jié)點(diǎn)的碰撞和擁堵?tīng)顟B(tài)是任務(wù)開(kāi)始時(shí)刻計(jì)算出來(lái)的并且在每個(gè)新任務(wù)開(kāi)始前會(huì)進(jìn)行更新。對(duì)于執(zhí)行某具體任務(wù)的AGV 而言，需要做出以下決策：1）經(jīng)過(guò)的路段；2）經(jīng)過(guò)該路段的時(shí)間；3）該路段是否可用（不存在沖突情況）。建立模型M2，其相關(guān)符號(hào)定義如表2所示。

表1 模型M1相關(guān)符號(hào)定義Tab.1 Related symbol definitions of model M1

表2 模型M2相關(guān)符號(hào)定義Tab.2 Related symbol definitions of model M2

建模的具體說(shuō)明如下：1）定義道路網(wǎng)絡(luò)Net=(N，E)，其中，將道路網(wǎng)絡(luò)離散化為間隔是單位時(shí)間1 的網(wǎng)絡(luò)，即Tl=1，l∈E。2）定義離散時(shí)間集合T。擴(kuò) 展Net定 義NetT=(NT，ET)，其中NT=，對(duì)于a∈NT，a[1]和a[2]分別取路網(wǎng)節(jié)點(diǎn)和時(shí)間；，對(duì) 于e∈ET，e[1]和e[2]分別表示第一個(gè)和第二個(gè)節(jié)點(diǎn)的狀態(tài)。3）考慮路網(wǎng)中部分節(jié)點(diǎn)在特定時(shí)間被占用的問(wèn)題，引入表示不可用節(jié)點(diǎn)，據(jù)此得到不可達(dá)集合，，并更新擴(kuò)展網(wǎng)絡(luò)為。

模型M2剔除了時(shí)空網(wǎng)絡(luò)中因路徑?jīng)_突而產(chǎn)生的不可行路段，在更新后的新時(shí)空網(wǎng)絡(luò)中規(guī)劃最優(yōu)路徑，目標(biāo)函數(shù)（5）為最小化時(shí)間成本；約束（6）和（7）表示在可行的路網(wǎng)中任務(wù)作業(yè)的先后關(guān)系，AGV從起始位置O開(kāi)始作業(yè)，作業(yè)完成后回到終點(diǎn)位置D；約束（8）是可行路網(wǎng)流量平衡約束，任意節(jié)點(diǎn)的出度等于節(jié)點(diǎn)的入度。

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

3.1 時(shí)空網(wǎng)絡(luò)求解算法

時(shí)空網(wǎng)絡(luò)記錄AGV 在不同時(shí)刻能到達(dá)的多個(gè)位置及其可行的路段，故AGV 的時(shí)間狀態(tài)信息體現(xiàn)在網(wǎng)絡(luò)節(jié)點(diǎn)上。構(gòu)造時(shí)空網(wǎng)絡(luò)的目的是讓AGV 在所有可行路段中選擇一條路徑，在規(guī)避沖突下完成從起點(diǎn)到終點(diǎn)的任務(wù)。對(duì)于時(shí)空網(wǎng)絡(luò)的結(jié)構(gòu)而言，不同的道路交通規(guī)則下時(shí)空網(wǎng)絡(luò)表現(xiàn)出不同的形態(tài)，而同一道路交通規(guī)則下的時(shí)空網(wǎng)絡(luò)在更新時(shí)不改變其形態(tài)，每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)仍記錄AGV 的時(shí)間狀態(tài)信息。因此，時(shí)空網(wǎng)絡(luò)是空間網(wǎng)格在時(shí)間維度的迭代，而空間網(wǎng)格是港區(qū)道路網(wǎng)絡(luò)依據(jù)單位時(shí)間距離的離散化。具體而言，對(duì)每一個(gè)路段，依據(jù)單位時(shí)間距離進(jìn)行近似等分得到路段上的節(jié)點(diǎn)，這些中間節(jié)點(diǎn)僅僅與相鄰節(jié)點(diǎn)以單位時(shí)間連通。依據(jù)模型M2的定義，離散后得到的道路網(wǎng)絡(luò)節(jié)點(diǎn)記為N，時(shí)空網(wǎng)絡(luò)的節(jié)點(diǎn)記為NT，在路段上單位時(shí)間連通的節(jié)點(diǎn)構(gòu)成ET中的元素，不可用節(jié)點(diǎn)集合標(biāo)記為-NT，并據(jù)此得到-ET。

基于以上的概念和模型，設(shè)計(jì)基于時(shí)空網(wǎng)絡(luò)的算法——TS-SP（Tempo-Spatial Shortest Path），TS-SP 算法由算法1 和算法2組成。其中，算法1通過(guò)生成時(shí)空網(wǎng)絡(luò)，更新時(shí)空網(wǎng)絡(luò)，以及調(diào)用M2計(jì)算最短路徑獲得給定一個(gè)OD的AGV 路徑；算法2調(diào)用算法1，通過(guò)迭代策略求解OD任務(wù)序列中的所有O和D配對(duì)的路徑。算法2 根據(jù)已獲得的路徑更新不可用節(jié)點(diǎn)集合-NT（步驟5）以實(shí)時(shí)檢測(cè)沖突，而算法1則利用不可用節(jié)點(diǎn)集合更新時(shí)空網(wǎng)絡(luò)（步驟2）以實(shí)時(shí)規(guī)避沖突并進(jìn)行一次路徑規(guī)劃（步驟3），因此針對(duì)多個(gè)OD任務(wù)，在時(shí)空網(wǎng)絡(luò)上運(yùn)用最短路徑算法，根據(jù)路徑結(jié)果更新時(shí)空網(wǎng)絡(luò)，并通過(guò)迭代最終獲得滿足避碰和緩解擁堵條件的路徑規(guī)劃，而M2的求解過(guò)程能夠通過(guò)拓展基本最短路徑算法（如Dijkstra 算法）實(shí)現(xiàn)。時(shí)空網(wǎng)絡(luò)算法流程如圖3 所示。算法開(kāi)始，依據(jù)時(shí)間順序從任務(wù)集中選取任務(wù)執(zhí)行。針對(duì)每一個(gè)當(dāng)前任務(wù)，首先生成時(shí)空網(wǎng)絡(luò)，并依據(jù)當(dāng)前的不可用節(jié)點(diǎn)集合更新時(shí)空網(wǎng)絡(luò)，接著在更新后的時(shí)空網(wǎng)絡(luò)中采用Dijkstra算法計(jì)算任務(wù)最短路徑，并依據(jù)當(dāng)前任務(wù)的最短路徑結(jié)果更新不可用節(jié)點(diǎn)集合。判斷任務(wù)集是否為空：任務(wù)集不為空則選擇下一個(gè)任務(wù)執(zhí)行；任務(wù)集為空則說(shuō)明已完成所有任務(wù)，算法結(jié)束。

圖3 時(shí)空網(wǎng)絡(luò)算法流程Fig.3 Flowchart of tempo-spatial network algorithm

算法1 單個(gè)OD任務(wù)最短路徑優(yōu)化算法（Single_OD_SP）。

輸入 任務(wù)的起點(diǎn)O和終點(diǎn)D、開(kāi)始時(shí)間t0、調(diào)度周期總時(shí)長(zhǎng)T；所有節(jié)點(diǎn)的集合N，不可用節(jié)點(diǎn)集合-NT；

步驟1 生成時(shí)空網(wǎng)絡(luò)NetT=(NT，ET)：NT={(i，t)|i∈N，t∈T}；

步驟2 更新時(shí)空網(wǎng)絡(luò)：

步驟3 采用M2計(jì)算最短路徑：

對(duì)Pe中的節(jié)點(diǎn)，取a[1]=O作為開(kāi)始節(jié)點(diǎn)，依次順序插入后續(xù)節(jié)點(diǎn)得到Path

算法2 OD任務(wù)序列最短路徑優(yōu)化算法。

輸入 任務(wù)集合OD={(O，D)}、開(kāi)始時(shí)間t0、調(diào)度周期總時(shí)長(zhǎng)T；所有節(jié)點(diǎn)的集合N，不可用節(jié)點(diǎn)集合；

輸出 路徑集合Paths={(O，D，Path)}。

步驟2 取(O，D) ←OD[i]。

步驟3 求最短路徑：

步驟4 更新路徑集合：Paths←Paths∪{(O，D，Path)}。

步驟6i←i+1，如果i＜|OD|，轉(zhuǎn)到步驟2；否則終止。

3.2 算法舉例

為了分析算法的機(jī)理，在圖4中，設(shè)計(jì)例證說(shuō)明算法求解最優(yōu)路徑及其更新過(guò)程。設(shè)節(jié)點(diǎn)集合N={1，2，…，9}，離散時(shí)間集合T={0，1，2，…}，任務(wù)集合I={i，j}，任務(wù)i，j的OD位置及出發(fā)時(shí)間分別為(1，9，0)，(2，9，1)。AGV行駛過(guò)程中從一個(gè)節(jié)點(diǎn)出發(fā)只能到達(dá)其右邊或其下邊相鄰的節(jié)點(diǎn)，如節(jié)點(diǎn)2 可到達(dá)節(jié)點(diǎn)3 或節(jié)點(diǎn)5，并且經(jīng)過(guò)每一條短邊的時(shí)間成本記為1個(gè)單位時(shí)間。AGV 在時(shí)空網(wǎng)絡(luò)中行駛對(duì)應(yīng)時(shí)間和空間位置要素，如執(zhí)行任務(wù)i的AGV 在0時(shí)刻從節(jié)點(diǎn)1 出發(fā)，此時(shí)AGV狀態(tài)記為(1，0)。

算法開(kāi)始，在圖4（a）中，任務(wù)i的時(shí)空網(wǎng)絡(luò)如式（9）、（10）。此時(shí)不可用節(jié)點(diǎn)及邊集合，產(chǎn)生一條最優(yōu)路徑Pathi，如式（11）。在圖4（b）中任務(wù)j的時(shí)空網(wǎng)絡(luò)如式（12），（13）。此時(shí)，若規(guī)劃任務(wù)j在時(shí)空網(wǎng)絡(luò)下的最優(yōu)路徑Pathj，如式（14），則兩個(gè)任務(wù)所規(guī)劃的路徑在節(jié)點(diǎn)5存在沖突，即執(zhí)行任務(wù)i的AGV 和執(zhí)行任務(wù)j的AGV 在T=2時(shí)刻同時(shí)到達(dá)節(jié)點(diǎn)5，如圖4（c）。因此，為了任務(wù)i和任務(wù)j的路徑均可行，首先依據(jù)Pathi確定不可行節(jié)點(diǎn)與路段集合，如式（15）、（16），更新任務(wù)j的時(shí)空網(wǎng)絡(luò)，，如式（17）、（18），再規(guī)劃路徑，如式（19），以此消除沖突，如圖4（d）。然而，任務(wù)j更新后的路徑和任務(wù)i的路徑，在到達(dá)終點(diǎn)的時(shí)刻相等，即AGV 在執(zhí)行卸載（或裝載）集裝箱操作時(shí)發(fā)生沖突。因此，使任務(wù)j在節(jié)點(diǎn)6 等待1 個(gè)單位時(shí)間，得到Path″j，如式（20）。至此，任務(wù)i和任務(wù)j的路徑規(guī)劃完成，在規(guī)避所有沖突的條件下得到最優(yōu)路徑，Pathi，j，如式（21）。算法結(jié)束，其機(jī)理得以驗(yàn)證。

圖4 算法優(yōu)化路徑的過(guò)程Fig.4 Process of optimizing path planning by the algorithm

4 計(jì)算實(shí)驗(yàn)與結(jié)果分析

4.1 算例設(shè)計(jì)

參照上海洋山四期自動(dòng)化集裝箱碼頭的工藝布局設(shè)計(jì)算例，首先說(shuō)明自動(dòng)化碼頭的設(shè)計(jì)參數(shù)，如表3 所示，然后，設(shè)置規(guī)則并生成算例。考慮兩種類(lèi)型的任務(wù)，即進(jìn)口箱作業(yè)和出口箱作業(yè)。同一岸橋或同一堆場(chǎng)釋放一個(gè)待AGV運(yùn)輸?shù)倪M(jìn)口箱或出口箱時(shí)間間隔分別服從均勻分布U(100，120)、U(40，60)。以進(jìn)口箱作業(yè)為例，說(shuō)明算例的生成規(guī)則。每個(gè)進(jìn)口箱任務(wù)包括5 個(gè)參數(shù)：開(kāi)始時(shí)間t0、作業(yè)岸橋Qi、裝卸車(chē)道Li、目標(biāo)箱區(qū)Bi以及目標(biāo)車(chē)位Pi，其中，依據(jù)表3的參數(shù)設(shè)置，Qi、Li、Bi、Pi分別服從均勻分布U(1，2)、U(1，4)、U(1，3)、U(1，5)。根據(jù)作業(yè)任務(wù)數(shù)量，分別產(chǎn)生5組不同規(guī)模的算例R10、R50、R100、R200、R400。其中，算例R10見(jiàn)表4。

表3 參數(shù)設(shè)置Tab.3 Parameter settings

表4 算例集R10Tab.4 Dataset R10

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

AGV時(shí)空網(wǎng)絡(luò)由Python3.7 平臺(tái)的NetworkX 工具包編譯實(shí)現(xiàn)，網(wǎng)格精度設(shè)置為6 m ×6 m。算例設(shè)計(jì)3 組實(shí)驗(yàn)以驗(yàn)證模型和算法的有效性。實(shí)驗(yàn)假設(shè)：1）AGV 數(shù)量滿足裝卸任務(wù)需要；2）岸橋和場(chǎng)橋的裝卸效率足夠高，沒(méi)有出現(xiàn)延遲或等待現(xiàn)象。實(shí)驗(yàn)中采用的基本最短路徑算法選取Dijkstra 算法。值得注意的是，AGV 路徑規(guī)劃問(wèn)題有2個(gè)特征，分別為車(chē)輛碰撞和路網(wǎng)擁堵，時(shí)空網(wǎng)絡(luò)算法則是能夠避免路徑之間的碰撞并緩解路網(wǎng)擁堵，因此依據(jù)該問(wèn)題特征，實(shí)驗(yàn)對(duì)比了2 種不同路徑規(guī)劃求解策略，即基本最短路徑求解策略和停車(chē)等待求解策略，據(jù)此設(shè)計(jì)了2 個(gè)對(duì)比求解算法，分別為算法P、SP，算法特征如表5所示。P算法求解過(guò)程中不更新時(shí)空網(wǎng)絡(luò)，因此不能規(guī)避路徑中可能發(fā)生的沖突；SP 算法則更新時(shí)空網(wǎng)絡(luò)，檢測(cè)沖突路段，小車(chē)按原最短路徑行駛，在緩沖區(qū)停車(chē)等待以規(guī)避碰撞；TS-SP算法通過(guò)更新時(shí)空網(wǎng)絡(luò)，檢測(cè)沖突路段，并且在更新后的時(shí)空網(wǎng)絡(luò)中規(guī)劃路徑以緩解路網(wǎng)的擁堵。

表5 算法特征Tab.5 Algorithm features

實(shí)驗(yàn)一 模型與算法的避碰效果驗(yàn)證。分別考慮進(jìn)口箱作業(yè)和出口箱作業(yè)下，采用P算法和TS-SP算法求解不同規(guī)模的算例，計(jì)算兩種算法規(guī)劃出的路徑下小車(chē)發(fā)生的碰撞次數(shù)。依據(jù)AGV 實(shí)際尺寸，實(shí)驗(yàn)設(shè)置AGV 之間的安全距離為12 m，計(jì)算不同規(guī)模算例下執(zhí)行每一個(gè)任務(wù)的AGV 與路網(wǎng)中其他執(zhí)行任務(wù)的AGV 之間的最小相對(duì)距離，其中任務(wù)數(shù)量用N表示。

實(shí)驗(yàn)二 模型與算法的緩解擁堵效果驗(yàn)證。分別考慮進(jìn)口箱作業(yè)和出口箱作業(yè)下，采用SP 算法和TS-SP 算法求解不同規(guī)模的算例，計(jì)算小車(chē)總行駛路程、小車(chē)總行駛時(shí)間、最小完工時(shí)間、小車(chē)總延誤時(shí)間、延誤任務(wù)數(shù)量以及延誤任務(wù)數(shù)量占比，分別表示為S、T、M、W、K和G。以算例R400為例，與P 算法求解得的最小任務(wù)完成時(shí)間相比，計(jì)算SP 算法和TS-SP 算法求解下執(zhí)行每個(gè)任務(wù)的AGV 到達(dá)時(shí)間差。又因路網(wǎng)中的擁堵現(xiàn)象表現(xiàn)為小車(chē)在行駛過(guò)程中因避免碰撞而發(fā)生等待行為，故以任務(wù)延誤時(shí)間比上最小任務(wù)完成時(shí)間表示路網(wǎng)平均擁堵度［24］，其中，N為任務(wù)數(shù)量。

實(shí)驗(yàn)三 算法性能驗(yàn)證。分別考慮進(jìn)口箱作業(yè)和出口箱作業(yè)下，采用P 算法、SP 算法和TS-SP 算法求解不同規(guī)模的算例，在Win10-PC、i7CPU、內(nèi)存8 GB 的計(jì)算環(huán)境下各算法的計(jì)算時(shí)間，保留4位有效數(shù)字。

4.3 結(jié)果分析

1）實(shí)驗(yàn)一結(jié)果與分析。用P 算法和TS-SP 算法求解的碰撞次數(shù)以及AGV最小相對(duì)距離分別如表6、圖5所示。

表6 P和TS-SP算法求解下碰撞次數(shù)Tab.6 Number of collisions in P and TS-SP algorithms

圖5 AGV最小相對(duì)距離圖Fig.5 The minimum relative distances of AGVs

由表6可知，P算法求解下小車(chē)在任務(wù)規(guī)模較大時(shí)碰撞次數(shù)較多，如進(jìn)口箱作業(yè)N=400時(shí)，并且碰撞次數(shù)隨著任務(wù)規(guī)模的增加而增加，如出口箱作業(yè)。而在時(shí)空網(wǎng)絡(luò)算法下，無(wú)論任務(wù)的規(guī)模多大，AGV 之間碰撞次數(shù)均為0。該結(jié)果說(shuō)明時(shí)空網(wǎng)絡(luò)算法規(guī)劃的路徑互不干涉，AGV 之間無(wú)碰撞從而保證AGV安全作業(yè)。

由圖5 可知，P 算法求解下部分執(zhí)行任務(wù)的AGV 發(fā)生碰撞，AGV 最小相對(duì)距離則為0，在未發(fā)生碰撞的情形下，仍有部分執(zhí)行任務(wù)的AGV 最小相對(duì)距離小于安全距離，如出口箱作業(yè)算例R100時(shí)。TS-SP 算法求解下，無(wú)論任務(wù)的規(guī)模多大，執(zhí)行每個(gè)任務(wù)的AGV 最小相對(duì)距離都大于或等于安全距離。AGV 在實(shí)際行駛時(shí)由于車(chē)身長(zhǎng)度因素會(huì)對(duì)不止一個(gè)路段具有獨(dú)占性，從而對(duì)路網(wǎng)中其他AGV 行駛產(chǎn)生影響，時(shí)空網(wǎng)絡(luò)算法充分考慮到AGV 車(chē)身長(zhǎng)度因素使得AGV 最小相對(duì)距離始終大于安全距離，結(jié)果說(shuō)明該算法下AGV 行駛過(guò)程中是安全的，提高了AGV運(yùn)行效率。

2）實(shí)驗(yàn)二結(jié)果與分析。用SP算法與TS-SP算法求解任務(wù)集結(jié)果、AGV 到達(dá)時(shí)間差以及路網(wǎng)平均擁堵度分別如表7、圖6、7所示。

由表7 可知，1）進(jìn)口箱作業(yè)下，SP 算法和TS-SP 算法求解同一規(guī)模算例下AGV 總行駛時(shí)間與最小完工時(shí)間均相同，任務(wù)總延誤時(shí)間隨著任務(wù)規(guī)模的增加而增加。同等規(guī)模下，因TS-SP 算法為避免小車(chē)發(fā)生碰撞而選擇規(guī)劃新路徑，故TS-SP算法求解得總行駛路程大于SP 算法求解得總路程，但TS-SP算法求解得總延誤時(shí)間小于SP 算法求解得總延誤時(shí)間，在較大規(guī)模下，TS-SP 算法求解得延誤任務(wù)占比數(shù)值較小，如N=400時(shí)。2）出口箱作業(yè)下，兩種算法求解同一規(guī)模算例下AGV最小完工時(shí)間相同。TS-SP算法求解得總路程大于SP算法下的總路程，但SP 算法下AGV 總行駛時(shí)間則較大，如N=200時(shí)。任務(wù)總延誤時(shí)間隨著任務(wù)規(guī)模的增加而增加，同等規(guī)模下，TS-SP 算法求得任務(wù)總延誤時(shí)間小于SP 算法求得總延誤時(shí)間；并且當(dāng)任務(wù)規(guī)模較大時(shí)，TS-SP 算法能有效地縮短總延誤時(shí)間，如N=400時(shí)。TS-SP 算法能有效減少延誤任務(wù)數(shù)量，降低延誤任務(wù)占比數(shù)值，如N=200時(shí)。

表7 SP和TS-SP算法求解結(jié)果比較分析Tab.7 Comparison of SP and TS-SP solving results

由圖6（a）可知，進(jìn)口箱作業(yè)下，TS-SP算法與SP算法求解400 個(gè)任務(wù)時(shí)，大部分執(zhí)行任務(wù)的AGV 到達(dá)時(shí)間差為0，少部分AGV到達(dá)時(shí)間差大于0且集中出現(xiàn)在任務(wù)規(guī)模較大時(shí)。在求解第227 個(gè)任務(wù)時(shí)，TS-SP 算法下AGV 到達(dá)時(shí)間差較大，其他情況下AGV 到達(dá)時(shí)間差數(shù)值相等。SP 算法下平均時(shí)間差為3.56 s，TS-SP 算法下平均時(shí)間差為3.67 s。由圖6（b）可知，出口箱作業(yè)下，TS-SP算法與SP算法求解結(jié)果中有較多執(zhí)行任務(wù)的AGV 到達(dá)時(shí)間差大于0 且分布較為均勻。其中，大部分AGV 到達(dá)時(shí)間差數(shù)值相等，少部分到達(dá)時(shí)間差數(shù)值不等，SP 算法求解得AGV 到達(dá)時(shí)間差較大的任務(wù)個(gè)數(shù)為9，TSSP 算法求解得AGV 到達(dá)時(shí)間差較大的任務(wù)數(shù)量為3。SP 算法下平均時(shí)間差為3.3 s，TS-SP 算法下平均時(shí)間差為3.18 s。值得注意的是，TS-SP算法下AGV到達(dá)時(shí)間差大于0是由于新規(guī)劃的路徑長(zhǎng)度較長(zhǎng)，AGV 行駛時(shí)間長(zhǎng)且行駛過(guò)程中也可能出現(xiàn)等待行為；而SP 算法下的時(shí)間差大于0是由于AGV 在原路徑行駛過(guò)程中發(fā)生等待行為。該結(jié)果表明，大部分任務(wù)下，時(shí)空網(wǎng)絡(luò)算法下AGV 依據(jù)新規(guī)劃的路徑行駛的時(shí)間與停車(chē)等待策略下依據(jù)原路徑行駛的時(shí)間相等；少部分任務(wù)下，時(shí)空網(wǎng)絡(luò)算法減少了任務(wù)完成時(shí)間。

由圖7 可知，同一作業(yè)模式下TS-SP 算法比SP 算法求解得路網(wǎng)平均擁堵度低，當(dāng)任務(wù)規(guī)模較大時(shí)，路網(wǎng)平均擁堵度較低，如出口箱作業(yè)N=400時(shí)。由于出口箱作業(yè)數(shù)量多且間隔時(shí)間短，出口箱作業(yè)下路網(wǎng)平均擁堵度比進(jìn)口箱作業(yè)下路網(wǎng)平均擁堵度高，如N=200時(shí)，進(jìn)口箱作業(yè)下?lián)矶露葹?.089%，而出口箱作業(yè)下?lián)矶露葎t為0.630%。該結(jié)果說(shuō)明時(shí)空網(wǎng)絡(luò)算法能有效緩解路網(wǎng)的擁堵，減少AGV 停車(chē)等待成本，AGV的暢通行駛提高了碼頭運(yùn)作效率。

圖6 AGV到達(dá)時(shí)間差Fig.6 AGV arrival time difference

3）實(shí)驗(yàn)三結(jié)果與分析。用P 算法、SP 算法和TS-SP 算法求解不同規(guī)模的算例的計(jì)算時(shí)間如圖8所示。

由圖8 可知，進(jìn)口箱作業(yè)和出口箱作業(yè)下P 算法、SP 算法和TS-SP 算法求解不同規(guī)模算例的計(jì)算時(shí)間趨勢(shì)相同，以進(jìn)口箱作業(yè)模式為例，說(shuō)明計(jì)算時(shí)間增長(zhǎng)趨勢(shì)。如圖8（a）所示，進(jìn)口箱作業(yè)下，計(jì)算時(shí)間隨任務(wù)規(guī)模的增大而增大，在任務(wù)數(shù)量小于等于200時(shí)，隨任務(wù)數(shù)量增大，計(jì)算時(shí)間平穩(wěn)增長(zhǎng)；當(dāng)任務(wù)數(shù)量為400時(shí)，計(jì)算時(shí)間大幅增長(zhǎng)，尤其表現(xiàn)為SP 和TSSP 算法，增長(zhǎng)幅度分別為319.86%和347.31%；當(dāng)任務(wù)數(shù)量大于等于100時(shí)，TS-SP 算法計(jì)算時(shí)間比SP 算法計(jì)算時(shí)間長(zhǎng)，這是因?yàn)門(mén)S-SP算法考慮了問(wèn)題的2個(gè)特征（碰撞及擁堵），而SP 算法僅考慮了車(chē)輛避碰條件。同等任務(wù)規(guī)模下，完成出口箱作業(yè)的計(jì)算時(shí)間比完成進(jìn)口箱作業(yè)的計(jì)算時(shí)間要長(zhǎng)，如當(dāng)N=400時(shí)，出口箱作業(yè)下TS-SP 算法計(jì)算時(shí)間為71.870 1 s，而進(jìn)口箱作業(yè)下的計(jì)算時(shí)間為52.842 s。計(jì)算結(jié)果說(shuō)明，TSSP 算法可以在有效的計(jì)算時(shí)間內(nèi)完成較大規(guī)模任務(wù)集計(jì)算。

圖7 路網(wǎng)平均擁堵度Fig.7 Average congestion rate of road network

圖8 3種算法求解不同規(guī)模的算例的計(jì)算時(shí)間對(duì)比Fig 8 Calculating time comparison of three algorithms for sloving different scale examples

以上實(shí)驗(yàn)結(jié)果表明，時(shí)空網(wǎng)絡(luò)算法能有效求解沖突規(guī)避的大規(guī)模路徑規(guī)劃問(wèn)題，減少任務(wù)延誤時(shí)間，使進(jìn)出口集裝箱滿足岸邊或堆場(chǎng)堆存計(jì)劃安排，大幅度降低自動(dòng)化碼頭運(yùn)營(yíng)的時(shí)間成本以及其他人力、物力成本，并且算法可以考慮AGV 車(chē)身長(zhǎng)度對(duì)路網(wǎng)的影響，更加符合自動(dòng)化碼頭實(shí)際規(guī)劃情況。

5 結(jié)語(yǔ)

本文針對(duì)自動(dòng)化集裝箱碼頭AGV 行駛過(guò)程中路網(wǎng)實(shí)際可用路段資源有限的特征，以任務(wù)完工時(shí)間最短為目標(biāo)，建立了路徑優(yōu)化的整數(shù)規(guī)劃模型，為求解模型，設(shè)計(jì)了基于時(shí)空網(wǎng)絡(luò)的啟發(fā)式算法。算例分析結(jié)果表明，該算法能完全避免路徑之間的碰撞，與停車(chē)等待策略下的路徑優(yōu)化算法相比，該算法能降低路網(wǎng)平均擁堵度，最大降低程度為0.68%。與已有研究相比，本文主要工作包括：1）所建模型考慮了路網(wǎng)中路段的時(shí)變沖突并以沖突規(guī)避為約束優(yōu)化AGV 作業(yè)路徑；2）提出基于時(shí)空網(wǎng)絡(luò)的迭代求解策略，提高ACT 作業(yè)系統(tǒng)優(yōu)化的精細(xì)化程度。本文考慮了沖突規(guī)避的AGV 作業(yè)路徑優(yōu)化問(wèn)題，而對(duì)AGV 能耗約束、任務(wù)送達(dá)時(shí)間窗約束沒(méi)有考慮，進(jìn)一步研究還可以考慮基于時(shí)空網(wǎng)絡(luò)的AGV 調(diào)度問(wèn)題，拓展時(shí)空網(wǎng)絡(luò)算法的研究方向。