一種基于結點時間窗修改初始路徑的調度方法

邱亭秀　倪欣園　于露　竇萬峰

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

關鍵詞：時間窗;調度策略;路徑規劃;結點時間點;初始路徑修改

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

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

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

2 ?地圖建模與系統結構（Map modeling and system structure）

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

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

本調度系統流程圖如圖2所示。結點時間窗算法基本思想：是在離線情況下，用A*算法規劃得到最短路徑庫的初始路徑，與各節點的時間窗進行時間比對，進行沖突預判。如果產生沖突，則結點時間窗與小車靜態路徑時間窗結合沖突處理機制，對路徑在原有基礎上進行修改，再進行沖突預判，直至無沖突，發出小車。

3 ?時間窗規劃算法（Time window planning algorithm）

3.1 ? 時間窗設計

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

AGV的路徑時間窗和結點時間窗定義如下：

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

時間窗結構如圖3所示。時間窗存儲了小車分配到的靜態任務路徑，通過其中定位對應結點，存儲此的占用情況。兩者進行時間重疊預判沖突，保證調度無沖突性，即確保中的結點時間占用情況是與已寫入的無沖突的。

3.2 ? 基于時間窗的調度過程

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

3.2.1 ? 沖突預判

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

3.2.2 ? 沖突處理

Methode1：暫停處理，在時間上達到沖突點的錯位，即可完成空間上的避讓。

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

4 ?系統實現與結果分析（System implementation and result analysis）

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

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

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

5 ? 結論（Conclusion）

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

參考文獻（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調度算法研究[J].工業工程，2019，22（4）：49-57.

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

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

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

[7] 徐鎮華，馬殷元.基于時間窗的改進兩階段AGV路徑規劃研究[J].測控技術，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調度問題研究[J].大連理工大學學報，2016，56（3）：244-251.

[11] 彭成吉.基于時間窗算法的多AGV路徑沖突的研究[A].中國煙草學會學術年會優秀論文集[C].2017：5.

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

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

作者簡介：

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

倪欣園（1999-），女，本科生.研究領域：信息管理與信息系統.

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

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