基于局域降維Dijkstra算法的校園送餐機器人多目標路徑規劃

宮金良，牛作碩，張彥斐

(1. 山東理工大學 機械工程學院, 山東 淄博 255049；2.山東理工大學 農業工程與食品科學學院，山東 淄博 255049)

智能時代的到來為人們生活帶來了極大方便，近年來同城即時配送行業開始興起[1]。校園作為一種特殊的室外送餐環境，其運行路段相對社會交通比較簡單，但人口流動性大，尤其在課間休息時間，道路上行人更為密集。同時，校園居住人口較多，用餐時間相對集中，所以對送餐效率有較高的要求，因此送餐路徑的規劃和選擇起到決定性作用。

目前路徑規劃常用的算法有Dijkstra算法、Johnson算法、Floyd-Warshall算法和A*算法等。Dijkstra算法作為一種貪心算法，通過搜索局部最優解求出全局最優解，在很多領域得到廣泛應用。李澤文等[2]提出一種基于Dijkstra算法的電網故障行波定位方法，解決了電網故障定位解網復雜的問題。王乙斐等[3]使用Dijkstra算法建立了一種最優解列斷面搜索方法。Wongso等[4]使用Dijkstra算法對城市公交運行最短路徑求解方法進行了分析。

本文通過環境建模，對校園送餐過程中存在的道路狀況進行分析，實現多目標優化，通過創建鄰接矩陣對傳統Dijkstra算法迭代過程中存在的數據冗余現象進行優化，并使用改進后的Dijkstra算法對校園送餐路徑進行規劃。

1 校園送餐環境模型搭建

1.1 校園送餐環境模型搭建與路徑分析

相對城市錯綜復雜的道路交通而言，校園送餐路徑僅包括校園主干路和穿插公寓之間的輔助路段，布局相對規則。根據實際需求和道路環境，將送餐道路交叉點和取餐點定義為路徑節點，節點之間的路徑定義為路段。以山東理工大學西校北公寓區為例，建立校園送餐拓撲地圖，如圖1所示。

圖1 校園送餐路徑圖Fig.1 Campus food delivery route map

本文在搭建送餐環境的過程中，使用一款基于北斗系統進行定位的智能小車執行配送餐任務。通過GPS/北斗結合IMU對任務車輛進行定位是當前的主流做法[5]，與使用激光雷達或者視覺建模進行定位相比，該定位方式可以減小數據處理量，同時降低了控制算法復雜性，在保證滿足定位需求的同時可大大降低開發成本。在定位和導航過程中，需對運行路段進行坐標采集，獲得送餐地理路線，從而結合環境特點從中選取合適的送餐路徑。忽略路徑的垂直落差，將采集到的送餐路段地理坐標信息轉化為直觀路徑長度信息，得到節點之間的距離權值。

1.2 多目標問題轉化

多目標優化問題[6-7]往往涉及到一個或多個沖突，對某一目標的優化，往往會影響其它目標的優化。本文將對送餐的路徑長短、實時路況、路徑簡繁、突發情況以及能耗等影響因子進行綜合考慮，對校園路徑規劃進行多目標優化。

將時間消耗作為單一目標函數，替代傳統的距離加權函數進行路徑規劃。建立路徑耗時函數G=min{∑path_costi(state_Tx)}，其中G為餐車運行總耗時。路段i的耗時用path_costi表示，state_Tx為該路段影響因子x的時間消耗值。特別地，在傳統路徑規劃中，兩個節點之間的實際弧段距離L為非負值，經過等價轉換后的state_Tx仍為正值。下面對state_Tx的5種優化目標進行轉化分析。

1)路程長短state_Tlength與實時路況state_Tcrowd

作為影響整個配送消耗的主導因素，路徑長度最短是首要考慮的目標。使用兩節點之間的歐氏距離作為路段長度，即

state_Tlength=length/average_speed，

(1)

式中average_speed為預設速度，其值由當前道路通暢程度決定。道路的實時情況可以通過步行人群稠密度和車輛通行狀況進行分析。高校學生主要交通方式為步行且易集群，根據不同路段的人口通行量，將路段進行經驗性等級劃分，設置為擁擠、正常、通暢3個等級。根據車流量大小對路段添加交通警示標記，以此對車輛通行狀況進行分析。針對不同路況的路段設置合適的運行速度，可以提高配送效率。上述兩種影響因素可統一表述為

(2)

行人稠密度density與車流量信息vehicle_flow作為平均速度的臨時變化系數，反映不同路段的道路狀況對預設速度的影響，即

(3)

通過引入人口密度ρ(單位為：人/m2)的概念對density分析賦值[8-9]。根據校園路段人口稠密度調查，將路況劃分為3個等級，并設定對應的人口密度為：通暢、正常、擁擠，參數設置見表1。vehicle_flow根據有無警示標記取系數0.8或1。

表1 人口密度及相應的參數設定Tab.1 Population density and corresponding parameter setting

加入路況信息后的路徑圖如圖2所示。

圖2 校園送餐路況圖Fig.2 Campus food delivery road traffic map

2)路徑簡繁state_Tcomplexity

路徑簡繁是指行駛路徑中相關影響因素的繁雜程度。如在實際的駕駛過程中，人們更傾向于選擇轉彎次數少、紅綠燈路口少的路徑，以提高駕駛體驗。這種決策方式可以避免因過多考慮道路路況等原因而造成路徑過于復雜，從而保證運送效率。路徑簡繁主要體現在路過的節點個數和節點處轉彎的次數，考慮到通過節點和轉彎都會造成額外的時間消耗，因此有

(4)

式中turning_factor是轉彎耗時Tturn_cost的布爾型參數，根據當前路段的前節點是否執行過轉彎取值1或0。節點耗時Tnode為常量值，根據路過節點個數進行累加，對規劃路徑的復雜度進行控制。

3)突發情況state_Tsudden_situation

校園內突發情況包括道路的施工、活動占用等情況，該路段會呈臨時阻斷狀態，此時添加標記量block進行調整規劃，即

state_Tsudden_situation=situation·block，

(5)

式中路況通行狀態situation為布爾型變量，設置block為無窮大值，當該道路不能通行時，situation置1，此時路段權值為無窮大，不加入路徑規劃。

4)能源消耗state_Tenergy

能耗控制可以延長配送車輛的運行時間，保證送餐過程的可持續性。當規劃出耗時相近的多條路徑時，選擇路程短的路徑執行任務，以減小能源消耗。此過程為附加判斷，不加入單條路段權值計算。

通過對5種因素進行目標歸一化處理，得到目標函數表達式為

(6)

2 校園送餐機器人多節點路徑規劃

2.1 基于傳統Dijkstra算法的路徑規劃迭代過程

基于傳統Dijkstra算法[10]的路徑規劃迭代過程如下：

1)確定路徑規劃節點，根據路段長度進行路段節點距離權值的賦值，同一節點之間距離為0、非相鄰節點之間距離為∞，以此為依據創建距離權值鄰接矩陣。

2)創建標記節點集合M={start_node}與未標記節點集合U(包含start_node以外的所有節點)，以start_node作為第一次迭代初始點開始從U中搜索距離start_node最近節點nearest_node，并記錄對應最近節點的節點值。

3)將nearest_node節點作為下一次迭代初始點，設置start_node為last_node，并從U中取出，放入標記集合M中，對U中各個節點與起始點的距離值進行更新。

4)進行再一輪迭代，直至搜索到目標點，結束計算。

傳統的Dijkstra算法過程簡潔，但具有一定的冗余計算，當數據量較大時，多余的搜索和更新時間會使路徑規劃效率急劇下降。本文提出一種創建節點鄰點集合N的方式，將實時搜索域和更新范圍進行縮小，從而提高路徑規劃效率。

2.2 Dijkstra算法降維改進

根據校園送餐場景，以a1點為初始點、e2點為送餐點為例，提出改進的Dijkstra算法路徑規劃方案。

步驟1 將節點按照圖1從上到下和從右到左的順序賦予ID值并排序，分別以距離和時間作為路徑權值創建鄰接矩陣，結果如圖3(單位:m)和圖4(單位:s)所示。

圖3 距離權值鄰接矩陣 Fig.3 Adjacent weight matrix of distance

圖4 時間權值鄰接矩陣Fig.4 Adjacent weight matrix of time

通過不同權值的鄰接矩陣可以看出，與單一考慮路徑長短的規劃相比，在多目標優化后，路徑權值的排序因為實時路況的不同而發生變化，從而解決了受路況影響無法選擇最優送餐路線的問題。該方法的路段權值大小優先順序更符合實際，有利于提升路徑規劃的時效性，證明了多目標優化的必要性。

步驟2 將節點1至21放入整體節點集合W中，并添加節點屬性值(P(ni),li)。其中，P(ni)表示節點ni距離出發點start_node所需要的時間，li為前一次的迭代節點last_node，通過記錄last_node即可獲得最終的規劃路徑。根據時間權值鄰接矩陣為所有節點創建鄰點集合Nx，例如節點a1的鄰接集合為Na1={a2,b1}。

步驟3 創建標記節點集合M={a1}與未標記節點集合U={a2,a3,...,e3}，以a1作為start_node開始規劃。傳統Dijkstra算法將從U中搜索距離a1最近的節點，過程中會對U中所有節點進行遍歷，遍歷對象包含大量與a1距離為∞的節點。優化后算法通過節點的鄰接集合Nx創建局部域Z=∑Nx-U，x∈U，即當前所有標記點鄰點集合的并集去除標記點后的點集。以局部域Z作為搜索域，此時由圖2可以看出，與a1相鄰的節點只有a2與b1，即只需要從兩相鄰節點中搜索即可。

步驟4 此時a2為當前nearest_node，設置a2為start_node，a1為last_node，則M={a1，a2}。傳統Dijkstra算法將對U中所有元素的P(ni)值進行更新，同樣需要對U中所有節點的P(ni)值進行遍歷更新。此時對M中節點的非相鄰節點進行P(ni)值更新并無意義，因此使用當前局部域Z作為更新域進行更新，可以縮小更新域范圍，提高更新速度。傳統Dijkstra算法與改進Dijkstra算法第一次迭代過程使用的局部域對比見表2。

表2 算法局部域對比Tab.2 Local domain comparison of two algorithms

步驟5 重復步驟3—步驟4，直至將目的節點e2放入集合M。

在后續搜索過程中，節點的相鄰節點不超過4個，設此時Z中元素個數為n，則每次迭代的搜索和更新的次數皆小于4n，從而通過創建鄰點集合，使用局部域Z將計算由n2的二維運算量轉化為一維運算量，實現了降維計算。

3 實驗仿真結果與分析

在Linux操作系統環境下，使用C++圖形用戶界面開發軟件QT編寫程序，分別使用傳統Dijkstra算法和局域降維Dijkstra算法進行路徑規劃仿真，并使用高精度運行計數器頻率采樣函數QueryPerformanceFrequenc(&a)，對路徑規劃過程進行耗時統計。QT規劃界面如圖5所示。

圖5 QT規劃界面Fig.5 QT programming interface

通過設置不同送餐點進行多次模擬規劃,對規劃耗時取均值后的規劃結果見表3，路徑規劃耗時變化曲線如圖6所示。分析表3和圖6可知：在路徑選擇方面，兩種算法最終規劃的路徑相同；耗時方面，當參與規劃的路徑點較少時，傳統算法的耗時與改進后算法的耗時相近，但隨著路徑點的增多，改進后算法耗時與傳統算法耗時相比大大減小。因此，改進后的Dijkstra算法能夠通過縮小迭代的搜索域和更新域，針對規劃路徑逐漸復雜的情況，使該模擬路徑規劃耗時由1～2 ms指數增長為7～10 ms變為1～2 ms倍數增長為2～4 ms，耗時優化效果更佳。

表3 路徑規劃結果Tab.3 Path planning results

圖6 路徑規劃耗時變化曲線Fig.6 The change curve of path planning time

4 結論

1)針對校園特殊環境進行路徑分析建模，將路徑規劃中的傳統距離權值轉化為時間權值。通過多目標優化分析，使用路徑耗時函數對路徑規劃中的多影響因素進行統一轉化，使轉化后路段的權值在添加實際路況后更貼切反應真實的路況，使其更適合實際應用，整體提高了路徑規劃的可行性和針對性。

2)使用局域降維Dijkstra算法對校園送餐實例進行路徑規劃，在傳統算法的基礎上，提出創建節點鄰接集合的方法，縮小了迭代過程中的最小路徑搜索域和最優路徑更新域。使用軟件進行算法仿真，得出規劃路徑的同時，其算法時間復雜度由傳統的O(n2)降為O(n)，隨著規劃路徑復雜程度的增加，改進后算法能夠將規劃耗時變化控制在小浮動范圍內。模擬實驗結果表明，改進的Dijkstra算法大大減小了路徑規劃的耗時，提高了路徑規劃效率，具有很強的實用性。