一種基于結(jié)點時間窗修改初始路徑的調(diào)度方法

邱亭秀　倪欣園　于露　竇萬峰

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

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

中圖分類號：TP391.7 ? ? 文獻標(biāo)識碼：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）是一種典型的用于無人工廠進行重復(fù)性的運輸任務(wù)作業(yè)的無人駕駛的移動機器人[1，2]。

AGV小車是智能車間重要的物流運輸資源，能否將物料按時送達加工單元將影響系統(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ù)分配三個方面[4]。在物料配送模式中，最重要的是確定AGV的行駛路線，即AGV的路徑規(guī)劃問題，其本質(zhì)上是VRP（Vehicle Routing Problem）問題[5]。AGV的路徑規(guī)劃不當(dāng)會使得AGV相互沖突，此時不但無法提高車間的運作效率，反而阻礙車間順暢運作。因此，AGV路徑規(guī)劃是亟待解決的問題[6]。

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

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

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

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

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

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

3.1 ? 時間窗設(shè)計

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

AGV的路徑時間窗和結(jié)點時間窗定義如下：

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

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

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

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

3.2.1 ? 沖突預(yù)判

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

3.2.2 ? 沖突處理

Methode1：暫停處理，在時間上達到?jīng)_突點的錯位，即可完成空間上的避讓。

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

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

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

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

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

5 ? 結(jié)論（Conclusion）

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

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

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

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

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

[7] 徐鎮(zhè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] 霍凱歌，張亞琦，胡志華.自動化集裝箱碼頭多載AGV調(diào)度問題研究[J].大連理工大學(xué)學(xué)報，2016，56（3）：244-251.

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

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

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

作者簡介：

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

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

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

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