邱亭秀　倪欣園　于露　竇萬峰

摘 ?要：本文結(jié)合最優(yōu)路徑算法、時(shí)間窗、沖突處理策略，提出一種基于結(jié)點(diǎn)時(shí)間窗修改初始路徑的多AGV（Automated Guided Vehicle）調(diào)度的方法。該方法適用于路徑選擇少，對備用路徑選擇依賴性小的情況。本文首先運(yùn)用A*算法進(jìn)行靜態(tài)初始路徑規(guī)劃，結(jié)合時(shí)間窗進(jìn)行沖突預(yù)判，在結(jié)點(diǎn)采用“時(shí)間點(diǎn)+固定時(shí)間片”進(jìn)行路徑結(jié)點(diǎn)時(shí)間窗更改，提高了路徑使用效率;然后，在初始路徑上依據(jù)沖突類型修改或添加結(jié)點(diǎn)及時(shí)間窗。最后，通過仿真實(shí)驗(yàn)，驗(yàn)證了本文提出的方法可以減少實(shí)時(shí)運(yùn)算的負(fù)擔(dān)且提高了長路段的利用效率。

關(guān)鍵詞：時(shí)間窗;調(diào)度策略;路徑規(guī)劃;結(jié)點(diǎn)時(shí)間點(diǎn);初始路徑修改

中圖分類號(hào)：TP391.7 ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

A Novel Scheduling Method of Modifying the Initial Path based on Node Time Window

QIU Tingxiu， NI Xinyuan， YU Lu， DOU Wanfeng

（School of Computer Science and Technology， Nanjing Normal University， Nanjing 210023， China）

1430273936@qq.com; 821787886@qq.com; 897741680@qq.com; douwanfeng@njnu.edu.cn

Abstract： Based on optimal path algorithm， time window and conflict elimination strategy， this paper proposes a multi-AGV （Automated Guided Vehicle） scheduling method which modifies the initial path based on node time window. This method is suitable for the case of less path selection and less dependence on alternative path selection. Firstly an algorithm， namely A*， is used to gain a static initial path for a task combined with time window for conflict prediction， and "time point +

fixed time slice" is used to change time window of the node with time conflicts. Then， on the initial path， nodes and time windows are added or altered according to conflicting types. Finally， the simulation results show that this scheduling method can reduce the burden of real-time operation and improve the utilization efficiency of long road sections.

Keywords： time window; scheduling strategy; path planning; node time; initial path modification

1 ? 引言（Introduction）

AGV（Automated Guided Vehicles）是一種典型的用于無人工廠進(jìn)行重復(fù)性的運(yùn)輸任務(wù)作業(yè)的無人駕駛的移動(dòng)機(jī)器人[1，2]。

AGV小車是智能車間重要的物流運(yùn)輸資源，能否將物料按時(shí)送達(dá)加工單元將影響系統(tǒng)生產(chǎn)資源的利用率。因此，如何快捷高效地調(diào)度有限的AGV小車，使得車間的生產(chǎn)效率最高是智能車間生產(chǎn)的重要環(huán)節(jié)盤[3]。國內(nèi)外對AGV的調(diào)度研究主要集中在AGV的路徑規(guī)劃、AGV的數(shù)量配置以及AGV的任務(wù)分配三個(gè)方面[4]。在物料配送模式中，最重要的是確定AGV的行駛路線，即AGV的路徑規(guī)劃問題，其本質(zhì)上是VRP（Vehicle Routing Problem）問題[5]。AGV的路徑規(guī)劃不當(dāng)會(huì)使得AGV相互沖突，此時(shí)不但無法提高車間的運(yùn)作效率，反而阻礙車間順暢運(yùn)作。因此，AGV路徑規(guī)劃是亟待解決的問題[6]。

國內(nèi)外學(xué)者對AGV路徑規(guī)劃問題作了不少研究[7-10]。彭成吉[11]提出運(yùn)用Dijkstra算法計(jì)算出最短路徑及初始時(shí)間窗向量表，運(yùn)用結(jié)點(diǎn)標(biāo)記后重新路徑規(guī)劃的方法進(jìn)行沖突處理;梁承姬等[12]提出在原路徑上插入時(shí)間窗的方法進(jìn)行沖突處理;許倫輝等[13]提出推遲時(shí)間窗后，按照延遲時(shí)間重新排列優(yōu)先級(jí)的方法。盡管這些文章都運(yùn)用了最短路徑結(jié)合時(shí)間窗的方法進(jìn)行調(diào)度，但均采用結(jié)點(diǎn)之間的路徑段的時(shí)間片進(jìn)行沖突判斷，沖突處理大都運(yùn)用的是重新規(guī)劃路徑或者僅對時(shí)間窗進(jìn)行處理。本文提出的方法是運(yùn)用結(jié)點(diǎn)“時(shí)間點(diǎn)+固定時(shí)間片”進(jìn)行沖突預(yù)判，在原路徑加入避讓點(diǎn)和時(shí)間停頓相結(jié)合的方式進(jìn)行沖突處理，迭代判斷至無沖突。最后仿真實(shí)驗(yàn)結(jié)束表示本文的方法是可行的。

2 ?地圖建模與系統(tǒng)結(jié)構(gòu)（Map modeling and system structure）

本文中研究的無人工廠為長、寬25米，擁有25臺(tái)機(jī)床，8臺(tái)AGV。倉庫長16米，寬1.5米。此系統(tǒng)，假設(shè)的基本信息如下：

（1）所有路徑為單行道，為雙向行駛;AGV速度假定為2m/s，行駛勻速，系統(tǒng)以小車1單元格（0.5m）的時(shí)間進(jìn)行循環(huán)。（2）根據(jù)路線規(guī)劃，結(jié)點(diǎn)1是出發(fā)點(diǎn)，4是回歸點(diǎn)。（3）編號(hào)8—32的結(jié)點(diǎn)為上下貨點(diǎn)又為避讓點(diǎn);編號(hào)33—47的結(jié)點(diǎn)為沖突高發(fā)點(diǎn)，相鄰結(jié)點(diǎn)之間等距。實(shí)驗(yàn)地圖模型如圖1所示。

本調(diào)度系統(tǒng)流程圖如圖2所示。結(jié)點(diǎn)時(shí)間窗算法基本思想：是在離線情況下，用A*算法規(guī)劃得到最短路徑庫的初始路徑，與各節(jié)點(diǎn)的時(shí)間窗進(jìn)行時(shí)間比對，進(jìn)行沖突預(yù)判。如果產(chǎn)生沖突，則結(jié)點(diǎn)時(shí)間窗與小車靜態(tài)路徑時(shí)間窗結(jié)合沖突處理機(jī)制，對路徑在原有基礎(chǔ)上進(jìn)行修改，再進(jìn)行沖突預(yù)判，直至無沖突，發(fā)出小車。

3 ?時(shí)間窗規(guī)劃算法（Time window planning algorithm）

3.1 ? 時(shí)間窗設(shè)計(jì)

基于時(shí)間窗的多AGV動(dòng)態(tài)路徑規(guī)劃策略是給結(jié)點(diǎn)和小車加上了時(shí)間間隔屬性。本文主要運(yùn)用小車時(shí)間窗和結(jié)點(diǎn)時(shí)間窗的對比判斷，以及數(shù)據(jù)更新對靜態(tài)初始路徑進(jìn)行動(dòng)態(tài)調(diào)整。本文中為每個(gè)AGV小車和結(jié)點(diǎn)設(shè)置時(shí)間窗，對比多種存儲(chǔ)結(jié)構(gòu)后，Map數(shù)據(jù)結(jié)構(gòu)因其鍵值特性，而被采納使用。

AGV的路徑時(shí)間窗和結(jié)點(diǎn)時(shí)間窗定義如下：

存放小車靜態(tài)路徑各結(jié)點(diǎn)時(shí)間窗，表示第個(gè)小車，將在時(shí)間后到達(dá)結(jié)點(diǎn);存放各結(jié)點(diǎn)的時(shí)間窗，表示第個(gè)結(jié)點(diǎn)，將在時(shí)間后被小車占用。

時(shí)間窗結(jié)構(gòu)如圖3所示。時(shí)間窗存儲(chǔ)了小車分配到的靜態(tài)任務(wù)路徑，通過其中定位對應(yīng)結(jié)點(diǎn)，存儲(chǔ)此的占用情況。兩者進(jìn)行時(shí)間重疊預(yù)判沖突，保證調(diào)度無沖突性，即確保中的結(jié)點(diǎn)時(shí)間占用情況是與已寫入的無沖突的。

3.2 ? 基于時(shí)間窗的調(diào)度過程

本文AGV的優(yōu)先級(jí)為消息接收順序，減少AGV優(yōu)先級(jí)的頻繁變更從而減少時(shí)間窗變更的復(fù)雜性。系統(tǒng)運(yùn)行從消息隊(duì)列中依次讀取任務(wù)消息開始，識(shí)別小車消息進(jìn)行對應(yīng)的調(diào)度指令，分配小車對應(yīng)的靜態(tài)任務(wù)路徑。分得路徑后首先計(jì)算AGV到達(dá)此路徑中各個(gè)結(jié)點(diǎn)的時(shí)間，存入此小車靜態(tài)路徑時(shí)間窗，尋找此路徑中所有結(jié)點(diǎn)對應(yīng)的結(jié)點(diǎn)時(shí)間窗進(jìn)行沖突預(yù)判。如果判斷結(jié)果無沖突，則可發(fā)車;如果判斷結(jié)果出現(xiàn)沖突，則進(jìn)行沖突處理。迭代直到無沖突。

3.2.1 ? 沖突預(yù)判

存入的是時(shí)間點(diǎn)，無法精準(zhǔn)控制小車的進(jìn)出。所以在沖突預(yù)判階段用的時(shí)間處理。首先進(jìn)行沖突預(yù)判，如果存在重疊，則進(jìn)行方向判斷。同向采取Methode1;相向則采取Methode2。如果不存在重疊，需要再加入時(shí)間片進(jìn)行掃描。判斷每個(gè)無沖突的結(jié)點(diǎn)的內(nèi)有無AGV占領(lǐng)，如果有且相向，則采取Methode2;否則視為無沖突。沖突預(yù)判流程如圖4所示。

3.2.2 ? 沖突處理

Methode1：暫停處理，在時(shí)間上達(dá)到?jīng)_突點(diǎn)的錯(cuò)位，即可完成空間上的避讓。

Methode2：沖突高發(fā)點(diǎn)的相向沖突無法通過暫停避讓時(shí)，采用加入避讓點(diǎn)的策略。在高頻沖突點(diǎn)的路徑會(huì)大大減少了路徑利用率，損失系統(tǒng)效率，故在避讓點(diǎn)中等待。沖突處理流程如圖5所示。

4 ?系統(tǒng)實(shí)現(xiàn)與結(jié)果分析（System implementation and result analysis）

本文通過實(shí)現(xiàn)系統(tǒng)進(jìn)行可行性驗(yàn)證，系統(tǒng)由三個(gè)子系統(tǒng)組成：調(diào)度子系統(tǒng)，通信子系統(tǒng)，仿真子系統(tǒng)。調(diào)度子系統(tǒng)通過通信子系統(tǒng)與仿真子系統(tǒng)進(jìn)行消息傳遞，給出小車指令并進(jìn)行反饋，也達(dá)到實(shí)時(shí)監(jiān)控的目的。通信子系統(tǒng)采用socket通信原理完成。仿真子系統(tǒng)采用JavaFX實(shí)現(xiàn)。其中實(shí)現(xiàn)的技術(shù)主要有：（1）可視化技術(shù)：通過創(chuàng)建GUI應(yīng)用程序所需要的各種功能的Java庫實(shí)現(xiàn)。（2）動(dòng)畫模擬技術(shù)：通過其中Animation類實(shí)現(xiàn)。（3）多線程技術(shù)：運(yùn)用于調(diào)度和仿真部分，通過Thread類和Runnable接口實(shí)現(xiàn)。

本文通過多次測試多輛agv小車，評價(jià)其沖突處理和沖突處理時(shí)間，來驗(yàn)證策略可行性。選取其中一起沖突案例進(jìn)行說明（表1以agv2發(fā)車時(shí)刻為0時(shí)刻記錄數(shù)據(jù)展示）。到達(dá)時(shí)間，其中轉(zhuǎn)彎時(shí)間一次=0.5s。進(jìn)入時(shí)間窗的順序是agv2-agv1-agv3，首先agv1判斷是將會(huì)在41結(jié)點(diǎn)與agv2相沖突;則進(jìn)行避讓點(diǎn)避讓（此處等待4s），情況如表2所示。當(dāng)agv3進(jìn)入，發(fā)現(xiàn)與agv1同向沖突，進(jìn)行暫停策略（），則情況如表3所示。

表1—表3中數(shù)據(jù)可見，小車成功進(jìn)行避障。實(shí)驗(yàn)證明策略可以解決小車沖突，并且高效的利用了長路段，驗(yàn)證該算法進(jìn)行無沖突調(diào)度多臺(tái)AGV的可行性。

5 ? 結(jié)論（Conclusion）

本文提出的基于結(jié)點(diǎn)時(shí)間窗修改初始路徑的調(diào)度方法，通過時(shí)刻點(diǎn)+時(shí)間片進(jìn)行預(yù)判，避讓點(diǎn)和暫停相結(jié)合來處理沖突。相對于動(dòng)態(tài)規(guī)劃調(diào)度，可以減少實(shí)時(shí)運(yùn)算的負(fù)擔(dān);相較于其他時(shí)間窗處理調(diào)度，運(yùn)用時(shí)間點(diǎn)的方式減少計(jì)算復(fù)雜度，時(shí)間片的利用大大提高了長路段的利用效率;避讓點(diǎn)從空間上更好的結(jié)合了時(shí)間窗進(jìn)行沖突處理。最后案例證明了策略的可行性，且在一定的規(guī)模下路段利用率提高，但在較高的規(guī)模下要保持高效，還需要做進(jìn)一步研究。

參考文獻(xiàn)（References）

[1] Kelly A.， Nagy B.， Stager D.， et al. An infrastriucture-free

automated guided vehicle based on computer vision[J]. IEEE Robot Mag， 2007， 14（3）：24-34.

[2] Wu X.， Zhang Y.， Zou T.， et al. Coordinated path tracking of two vision-guided tractors for heavy-duty robotic vehicles[J]. Robot Comput Integr Manuf， 2018， 53（100）：93-107.

[3] 陳敏，黎展滔，陳慶新，等.考慮有限物流運(yùn)輸能力的智能車間AGV調(diào)度算法研究[J].工業(yè)工程，2019，22（4）：49-57.

[4] 常建娥，王璐，莫易敏，等.基于Manhattan距離的汽車總裝車間帶時(shí)間窗多AGV小車調(diào)度優(yōu)化[J].武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版），2017，41（4）：489-594.

[5] 于濱，靳鵬歡，楊忠振.兩階段啟發(fā)式算法求解帶時(shí)間窗的多中心車輛路徑問題[J].系統(tǒng)工程理論與實(shí)踐，2012，32（8）：1793-1800.

[6] 梁承姬，沈珊珊，胡文輝.基于路段時(shí)間窗考慮備選路徑的AGV路徑規(guī)劃[J].工程設(shè)計(jì)學(xué)報(bào)，2018，25（2）：200-208.

[7] 徐鎮(zhèn)華，馬殷元.基于時(shí)間窗的改進(jìn)兩階段AGV路徑規(guī)劃研究[J].測控技術(shù)，2018，37（06）：145-149.

[8] Duinkerken MB， Lodwijks C. Routing of AGVs on automated container terminals[C]. IEEE 19th International Conference on Computer-Supported Cooperative Work in Design， Calabria， 2015.

[9] Song L.， Huang S. A hybrid metaheuristic method for dispatching antomated guided vehicles in container terminals[C]. IEEE Symposium on Computational Intelligence in Scheduling， Singapore， 2013.

[10] 霍凱歌，張亞琦，胡志華.自動(dòng)化集裝箱碼頭多載AGV調(diào)度問題研究[J].大連理工大學(xué)學(xué)報(bào)，2016，56（3）：244-251.

[11] 彭成吉.基于時(shí)間窗算法的多AGV路徑?jīng)_突的研究[A].中國煙草學(xué)會(huì)學(xué)術(shù)年會(huì)優(yōu)秀論文集[C].2017：5.

[12] 梁承姬，沈珊珊，胡文輝.基于路段時(shí)間窗考慮備選路徑的AGV路徑規(guī)劃[J].工程設(shè)計(jì)學(xué)報(bào)，2018（25）：200-208.

[13] 許倫輝，黃寶山，鐘海興.AGV系統(tǒng)路徑規(guī)劃時(shí)間窗模型及算法[J].廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2019（37）：1-8.

作者簡介：

邱亭秀（1999-），女，本科生.研究領(lǐng)域：信息管理與信息系統(tǒng)，軟件工程，仿真處理.

倪欣園（1999-），女，本科生.研究領(lǐng)域：信息管理與信息系統(tǒng).

于 ?露（1999-），女，本科生.研究領(lǐng)域：軟件工程，通信工程.

竇萬峰（1968-），男，博士，教授.研究領(lǐng)域：軟件工程，分布式與并行計(jì)算，大數(shù)據(jù)分析與挖掘.