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

宮金良，牛作碩，張彥斐

(1. 山東理工大學(xué) 機械工程學(xué)院, 山東 淄博 255049；2.山東理工大學(xué) 農(nóng)業(yè)工程與食品科學(xué)學(xué)院，山東 淄博 255049)

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

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

本文通過環(huán)境建模，對校園送餐過程中存在的道路狀況進行分析，實現(xiàn)多目標優(yōu)化，通過創(chuàng)建鄰接矩陣對傳統(tǒng)Dijkstra算法迭代過程中存在的數(shù)據(jù)冗余現(xiàn)象進行優(yōu)化，并使用改進后的Dijkstra算法對校園送餐路徑進行規(guī)劃。

1 校園送餐環(huán)境模型搭建

1.1 校園送餐環(huán)境模型搭建與路徑分析

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

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

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

1.2 多目標問題轉(zhuǎn)化

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

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

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

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

state_Tlength=length/average_speed，

(1)

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

(2)

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

(3)

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

表1 人口密度及相應(yīng)的參數(shù)設(shè)定Tab.1 Population density and corresponding parameter setting

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

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

2)路徑簡繁state_Tcomplexity

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

(4)

式中turning_factor是轉(zhuǎn)彎耗時Tturn_cost的布爾型參數(shù)，根據(jù)當前路段的前節(jié)點是否執(zhí)行過轉(zhuǎn)彎取值1或0。節(jié)點耗時Tnode為常量值，根據(jù)路過節(jié)點個數(shù)進行累加，對規(guī)劃路徑的復(fù)雜度進行控制。

3)突發(fā)情況state_Tsudden_situation

校園內(nèi)突發(fā)情況包括道路的施工、活動占用等情況，該路段會呈臨時阻斷狀態(tài)，此時添加標記量block進行調(diào)整規(guī)劃，即

state_Tsudden_situation=situation·block，

(5)

式中路況通行狀態(tài)situation為布爾型變量，設(shè)置block為無窮大值，當該道路不能通行時，situation置1，此時路段權(quán)值為無窮大，不加入路徑規(guī)劃。

4)能源消耗state_Tenergy

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

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

(6)

2 校園送餐機器人多節(jié)點路徑規(guī)劃

2.1 基于傳統(tǒng)Dijkstra算法的路徑規(guī)劃迭代過程

基于傳統(tǒng)Dijkstra算法[10]的路徑規(guī)劃迭代過程如下：

1)確定路徑規(guī)劃節(jié)點，根據(jù)路段長度進行路段節(jié)點距離權(quán)值的賦值，同一節(jié)點之間距離為0、非相鄰節(jié)點之間距離為∞，以此為依據(jù)創(chuàng)建距離權(quán)值鄰接矩陣。

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

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

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

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

2.2 Dijkstra算法降維改進

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

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

圖3 距離權(quán)值鄰接矩陣 Fig.3 Adjacent weight matrix of distance

圖4 時間權(quán)值鄰接矩陣Fig.4 Adjacent weight matrix of time

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

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

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

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

表2 算法局部域?qū)Ρ萒ab.2 Local domain comparison of two algorithms

步驟5 重復(fù)步驟3—步驟4，直至將目的節(jié)點e2放入集合M。

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

3 實驗仿真結(jié)果與分析

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

圖5 QT規(guī)劃界面Fig.5 QT programming interface

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

表3 路徑規(guī)劃結(jié)果Tab.3 Path planning results

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

4 結(jié)論

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

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