郭展羽，張志明，賀蘭山，鄭家齊，趙師兵，康 琦

同濟大學(xué) 電子與信息工程學(xué)院，上海200092

最短路徑問題一直是運籌學(xué)、計算機科學(xué)、地理信息科學(xué)、交通運輸?shù)阮I(lǐng)域的研究熱點，并廣泛應(yīng)用到公共交通運輸網(wǎng)絡(luò)規(guī)劃、無人自動駕駛、機器人自主導(dǎo)航等的實際問題中[1-6]。現(xiàn)實生活里有許多問題都可以抽象轉(zhuǎn)化為最短路徑問題，路徑規(guī)劃要求根據(jù)某種優(yōu)化準則，在給定的真實環(huán)境中尋找到一條從起始位置到目標位置可行并且代價最小的路徑。研究如何有效地計算和求解最短路徑問題，其面臨的難點是如何在較短的時間內(nèi)找到較為完備的解。根據(jù)對環(huán)境信息的掌握程度不同，路徑規(guī)劃可分為全局路徑規(guī)劃和局部路徑規(guī)劃，兩者沒有本質(zhì)上的區(qū)別。經(jīng)典的全局路徑規(guī)劃算法有Dijkstra算法[7]和A*算法[8]等，可以靜態(tài)地規(guī)劃出最優(yōu)或次優(yōu)路線。近年來，國內(nèi)外學(xué)者在此基礎(chǔ)上，引入啟發(fā)式算法和仿生算法等，提出多種最短路徑改進算法[9-16]，如模擬退火法、蟻群算法、遺傳算法、粒子群算法、深度優(yōu)先算法和廣度優(yōu)先算法等，并在解決過必經(jīng)點集的最短路徑問題上已經(jīng)取得很好的成效，康文雄等人[9]通過分層回溯的Dijkstra 算法，有效地減少問題求解的計算時間；Daniele 等人[10]對約束最短路徑漫游問題（constrained shortest path tour problem，CSPTP）提出新的數(shù)學(xué)模型和高效的分支定界方法；王磊等人[14]使用改進的A*算法，對最短路徑段進行拼接，使運算效率得到顯著提高。

在探究路徑規(guī)劃算法的過程中，應(yīng)用場景由于物理條件的限制會存在額外硬約束條件，而上述算法在處理此類問題時，往往需要簡化前置條件，忽略硬約束，導(dǎo)致實際解算過程中會存在求解難度高、求解速度慢、求解結(jié)果不可靠甚至不可行等的不足，需要做出相應(yīng)改進。本文以第十五屆全國大學(xué)生智能車競賽室外光電組總決賽實車比賽[17]為例，將比賽賽道抽象建模為無向帶權(quán)圖表示，提出一種基于深度優(yōu)先搜索的隨機搜索算法，以解決具有額外硬約束條件下過必經(jīng)點集的最短路徑問題。該算法的創(chuàng)新點在于，搜索過程中對路徑的可行性加入額外硬約束條件進行實時判定，在給定的真實環(huán)境中最終尋找到過必經(jīng)點集的最優(yōu)或次優(yōu)的最短路徑。

1 問題描述

1.1 背景

第十五屆全國大學(xué)生智能車競賽室外光電組總決賽采用G型等比縮小的無人車模，場景化地復(fù)現(xiàn)人工智能在實際領(lǐng)域中的應(yīng)用。無人車在長寬17 m×10.5 m大小的場地內(nèi)進行比賽，賽道由若干區(qū)域連通而成，分布如圖1（a）和圖1（b）中所示。比賽要求無人車從起點區(qū)域處出發(fā)并開始計時，規(guī)劃合理的路徑，經(jīng)過賽道上若干所有指定的區(qū)域后到達指定終點區(qū)域，停止計時并判定完賽，最終的比賽成績按完成時間進行排名；無人車在未經(jīng)過所有指定區(qū)域之前到達終點，不會停止計時。起點區(qū)域、終點區(qū)域，以及中途要經(jīng)過的若干區(qū)域和無人車的發(fā)車方向，在比賽開始前隨機指定給出。無人車在運行途中可以多次通過賽場中的某個賽道區(qū)域，且經(jīng)過隨機指定區(qū)域的先后順序不限，但需要至少穿過一次指定區(qū)域。

本文即在此背景下展開工作，解算無人車在給定起點和終點之間的最短路徑。舉例如下：如圖1（b）中所示，設(shè)比賽要求從起點（start）vs=1出發(fā)，經(jīng)過指定區(qū)域（pass）vp={2，7，10}后到達終點（destination）vd=6。通過直接觀察可以得出最優(yōu)解，即路徑1→2→10→7→6為最短路徑，如圖1（c）中所示；該賽道可以建模抽象為無向帶權(quán)圖如圖1（d）中所示。然而，在面臨比賽現(xiàn)場更加復(fù)雜的環(huán)境要素時，需要將該最短路徑問題建立合適的數(shù)學(xué)模型，引入硬約束條件后，設(shè)計合適的算法，才能進行快速且完備的求解。

圖1 應(yīng)用場景示意圖Fig.1 Schematic diagram of match field

1.2 建模

圖1 所示的賽道區(qū)域位置圖可以抽象成一個無向帶權(quán)圖，權(quán)值即為賽道圖中點與點之間的路程距離。假設(shè)無人車在各段賽道上的行駛速度一致，則可以將時間最優(yōu)化目標轉(zhuǎn)換為總路程最優(yōu)化目標，將該問題抽象為過必經(jīng)點集的最短路徑問題。與此同時，本次最優(yōu)化問題還存在有額外的硬約束：無人車ART-RC底盤機械尺寸為560 mm（長）×350 mm（寬）×230 mm（高），由于賽道寬度的限制，使得無人車無法調(diào)頭行駛，即路徑中不能存在包含相鄰節(jié)點的子路徑A→B→A（設(shè)A、B 為相鄰節(jié)點）；由于無人車車模轉(zhuǎn)彎半徑的物理條件限制，無人車在實際賽道上無法轉(zhuǎn)過轉(zhuǎn)角小于90°的彎道（銳角彎，即急彎，下文稱為“銳角彎”），如對于圖1（b）中的路徑8→7→10，無人車無法通過，但路徑8→7和7→10，在無向帶權(quán)圖（d）中存在，且不能通過預(yù)處理的方法將該路徑從圖中剔除。

依據(jù)上文所述優(yōu)化目標和約束條件，可以轉(zhuǎn)化為如下給定的一個無向帶權(quán)圖G(P,E) 數(shù)學(xué)模型，其中P={p1,p2,…,pn}為節(jié)點集，E={e1,e2,…,en}為無向邊集，設(shè)ωij為連接pi節(jié)點和pj節(jié)點的無向邊的權(quán)值。必經(jīng)點集P′?P-{s,d}，其中s和d分別為路徑規(guī)劃的起點和終點。硬約束條件邊集H，其內(nèi)部的邊元素由前中后三個節(jié)點構(gòu)成，如上文所舉例的{8,7,10}。最短路徑可以有兩種等價的表示形式：以節(jié)點集描述的最短路徑Wp={pa,pb,…,px,py}和以無向邊集描述的最短路徑We={eab,ebc,…,exy}。求解滿足以下約束條件的優(yōu)化目標函數(shù)獲得最短路徑。

其中，式（1）表明以路徑最短為優(yōu)化目標；式（2）為約束條件之一，要求路徑Wp經(jīng)過必經(jīng)點集P′中的每一個節(jié)點；式（3）為約束條件之二，要求路徑滿足額外硬約束條件。

因此，在求解過必經(jīng)點集的最短路徑問題的過程中，受到如上文所述額外硬約束的限制。為了便于程序處理并計算數(shù)據(jù)，將抽象出來的無向帶權(quán)圖轉(zhuǎn)化為二維鄰接矩陣，矩陣中存有圖中任意相鄰兩點之間的距離。當兩點不是相鄰時，距離值設(shè)為-1；點與其自身的距離值設(shè)為0。

1.3 變量定義

定義算法中的相關(guān)變量，如表1中所示。設(shè)定算法中路徑規(guī)劃的起點節(jié)點start、面朝點節(jié)點next（小車運行方向前方選擇的后一個節(jié)點，從起點出發(fā)時即為所選擇經(jīng)過的第一個節(jié)點）、必經(jīng)點集point_list[]和終點所在節(jié)點區(qū)域destination等，根據(jù)這些參數(shù)計算出一條可行的最優(yōu)路徑；在計算的過程中，分別定義當前搜索到的路徑way[]、已知路徑當中的最短路徑temp_way[]和最終的最優(yōu)最短路徑shortest_way[]；無向帶正權(quán)圖的所有信息保存到一個二維鄰接矩陣dis[][]。

表1 變量定義1Table 1 Variable definition in algorithm，part 1

額外硬約束（“point_constraint”）：將指定的額外硬約束條件存放在一個列表當中，作為參數(shù)進行設(shè)定，在進行路徑搜索時，對搜索得出的解進行是否滿足額外硬約束的判定，即判斷解路徑中是否含有額外硬約束當中的子路徑。硬約束使用連續(xù)三個點作為約束，中點作為索引，如在圖1中，路徑2→3→11為不可通行的銳角彎，故point_constraint[3]中含有[2，3，11]；路徑3→11→5 也是不可通行的銳角彎，故point_constraint[11]中含有[3，11，5]，以此類推。將完整的硬約束提前設(shè)定好，供搜索時使用。

2 算法實現(xiàn)

算法主要分為預(yù)處理和核心算法兩個部分實現(xiàn)。預(yù)處理階段通過一定的步驟，將使用者輸入的信息轉(zhuǎn)化為后續(xù)階段核心算法所需要的信息，完成對問題的無向帶權(quán)圖的處理和建模。核心算法部分則使用基于深度優(yōu)先的隨機搜索算法，在滿足額外硬約束的要求下，求解過必經(jīng)點集的最短路徑問題。

2.1 預(yù)處理

2.1.1 輸入?yún)?shù)

通過程序輸入起點start、起點時的面朝點next、終點destination和存放在point_list[]當中的必經(jīng)點序號列表，額外硬約束條件由point_constraint[]變量載入，圖的信息以鄰接矩陣的形式存放在文件當中讀入。

2.1.2 相鄰點查找函數(shù)

輸入的鄰接矩陣僅僅描述了各點之間的距離，預(yù)處理時使用查找函數(shù)尋找遍歷各節(jié)點位置上的所有相鄰點，算法流程如圖2所示，具體步驟列舉如下：

圖2 相鄰點查找算法流程圖Fig.2 Flow chart of adjacent point set search algorithm

（1）得到圖的大小，創(chuàng)建合適的數(shù)據(jù)結(jié)構(gòu)變量存儲各點的相鄰點信息，首先求得圖中節(jié)點的個數(shù)length，然后以維度為length的一個列表對象用以存儲變量。

（2）對圖中任意未遍歷的點進行探索，判斷其與其余點的距離，如果距離大于0，則代表兩點相鄰，將后點加入前點的相鄰點列表。

（3）重復(fù)步驟（2），直到圖中所有的點均被遍歷。

（4）最后得到完整的相鄰點列表choices 并存儲。

對于本次賽題，預(yù)處理后得到賽道無向帶權(quán)圖中①～?各個節(jié)點的相鄰點列表，具體為[[2，9]，[1，3，4，10]，[2，4，11]，[2，3，5]，[4，6，11]，[5，7]，[6，8，10]，[7，9，10]，[1，8]，[2，7，8，11]，[3，5，10]]。

2.1.3 預(yù)處理階段的輸出

預(yù)處理工作結(jié)束后，得到如前所述的各項初始參數(shù)：start，next，destination，point_list[]，dis[][]，choices[]。

2.2 核心算法描述

2.2.1 參數(shù)定義

有效路徑次數(shù)限制（t_limit）：使用隨機搜索時，需要設(shè)置一個上限值來結(jié)束路徑的查找，每當找到一條符合條件的路徑時，有效路徑次數(shù)（t）加1。次數(shù)上限值越高，計算的結(jié)果最優(yōu)性也就越高，但相對的，時間與空間的消耗也就越大。

路徑長度限制（L_limit）：使用深度優(yōu)先的隨機算法尋找一條路徑時，限制路徑的長度（L）有助于結(jié)束對過長路徑做無意義的搜索，可以節(jié)省每次路徑搜索所耗費的時間和空間，但是相對的，如果受到限制后無法求得解，則需把該限制放寬。這個值不應(yīng)該大于任意一條能遍歷圖上所有節(jié)點的路徑長度的兩倍，否則就失去效用。如圖1 中的路徑1→2→10→7→6→5→4→3→11→10→8→9→1 可以循環(huán)遍歷所有節(jié)點，當起點要求為vs=10，終點要求為vd=1，要經(jīng)過vp={2，7，6}時，按上文所述的這條路徑則需要經(jīng)過10→7→6→5→4→3→11→10→8→9→1→2→10→7→6→5→4→3→11→10→8→9→1。由此可以得到結(jié)論，最多循環(huán)走過該條路徑兩次可以保證該問題有解。

狀態(tài)定義：在搜索時，每一個狀態(tài)含有參數(shù)的定義：當前點（now），即當前點的序號；當前路徑（way[]），即由多次循環(huán)當中的多個當前點形成；前點（pre），即當前路徑中前一點的序號；當前距離（d），即當前路徑總的距離長度。

變量定義總結(jié)成表格如表2所示。

表2 變量定義2Table 2 Variable definition in algorithm，part 2

2.2.2 偽代碼描述

（1）最短路徑求解函數(shù)

算法1 最短路徑求解

（2）必經(jīng)點路由判斷函數(shù)

算法2 必經(jīng)點路由判斷

（3）硬約束條件狀態(tài)判斷函數(shù)

算法3 硬約束條件判斷

其中變量point_constraint即為本問題中的額外硬約束條件參數(shù)，以節(jié)點7 為例，point_constraint[7]=[[8，7，10]，[10，7，8]]，經(jīng)過判斷即可得出該路徑的可行性。

2.2.3 算法流程圖描述

算法流程圖如圖3中所示，各步驟簡述如下：

圖3 核心算法流程圖Fig.3 Flow chart of core algorithm

（1）初始化搜索狀態(tài)，將變量L_limit歸零，所有臨時路徑和節(jié)點清空。

（2）隨機探索下一個非前點（pre），并更換搜索的狀態(tài)。探索的方式是從當前點的相鄰點列表中，排除前點后隨機選擇一個。

（3）判斷是否到達終點。若否，重復(fù)步驟（2）。

（4）判斷是否過所有必經(jīng)點。若否，重復(fù)步驟（2）。對必經(jīng)點集的各點進行逐個判斷。

（5）判斷是否滿足額外硬約束。任意截取長度為3的子路徑，判斷是否為point_constraint列表中的元素：若是，則不滿足額外硬約束；若否，重復(fù)步驟（2）。

（6）比較路徑長度與已知最短長度，如果當前路徑較短則替換為最短路徑。

（7）判斷是否超過次數(shù)限定，若否，重復(fù)步驟1。

（8）輸出最短路徑。

3 實驗測試與結(jié)果分析

實驗測試環(huán)境為：Windows 10操作系統(tǒng)，Intel 2.3 GHz i5-8300H CPU，8 GB 內(nèi)存，編程語言為Python3.7，編程環(huán)境為PyCharm Community Edition 2020.2.3。使用第十五屆全國大學(xué)生智能車競賽室外光電組總決賽賽題[17]的賽道建模數(shù)據(jù)進行仿真測試，所獲得的最短路徑用于實車測試。

3.1 時間效率和最優(yōu)率的影響因素——必經(jīng)點集中節(jié)點個數(shù)

在程序當中設(shè)置計時器記錄程序運行時間來粗略計算算法的時間效率。在其他點不變的情況下，增加必經(jīng)點集中節(jié)點的個數(shù)，每次實驗取100次最優(yōu)輸出進行結(jié)果平均。此次實驗條件為：start=1，next=2，destination=6，t_limit=20，L_limit=20，同時實驗結(jié)果還必須滿足額外的硬約束，即不能轉(zhuǎn)過小于90°的銳角彎賽道且不能倒車。取實驗結(jié)果的平均值記錄在表3。

由實驗結(jié)果可見，在序號為1、2、3 和序號為4、5 的實驗中得到的解算時間結(jié)果相差較大，數(shù)值不在一個數(shù)量級，但最優(yōu)率都為100%，最優(yōu)率的問題將留在后續(xù)的實驗2進行討論。針對時間結(jié)果，經(jīng)過分析可知求解花費時間較大差異的原因：經(jīng)過點v={3}的最短路徑同時也經(jīng)過vm={5，7}，所以計算時通過隨機搜索容易搜索到最優(yōu)解，而因為vn={9，11}沒有出現(xiàn)在此路徑中，當需要經(jīng)過它們的時候，需要更多的時間去搜索。其余實驗條件不變的情況下，必經(jīng)點集選為{3，9}，重做實驗6驗證上述分析，表3中給出實驗相關(guān)結(jié)果。比較實驗1、2、3、6的結(jié)果，可發(fā)現(xiàn)該算法的效率更多地取決于中間節(jié)點集的選取，而不是由中間節(jié)點的數(shù)量決定。由于解算過程中使用隨機搜索的算法，同一種實驗條件下，不同次實驗之間的時間可能會存在比較大的差異，但多次重復(fù)實驗后得到的時間結(jié)果會穩(wěn)定在一定均值附近范圍內(nèi)。

表3 必經(jīng)節(jié)點集的影響Table 3 Impact of choosing necessary node set

3.2 時間效率和最優(yōu)率的影響因素——t_limit參數(shù)

基于實驗1，在僅僅選取3、9 兩點時平均需要消耗6.710 s的時間，此時的實驗條件中t_limit設(shè)為20。將該數(shù)值從小到大變化，進行100次實驗取實驗結(jié)果的平均值，將其變化對時間效率和最優(yōu)率的影響記錄在表4，其中最優(yōu)率為所求路徑結(jié)果中，最優(yōu)路徑（可能有多種）數(shù)量占所有路徑結(jié)果數(shù)量的比率。由表4 中的實驗結(jié)果可以看出，當t_limit設(shè)為較小的數(shù)時，計算時間較短，最優(yōu)率低；當t_limit參數(shù)值增大時，運行時間變長，最優(yōu)率增加；當設(shè)為10及以上數(shù)值時，最優(yōu)率可增長到97%以上直至100%。

表4 參數(shù)t_limit 的影響Table 4 Impact of t_limit parameter

3.3 不同算法對TSP問題求解的效果

本文提出的過必經(jīng)點集且具有額外硬約束的最短路徑搜索算法也可以用以解決旅行商問題（traveling salesman problem，TSP），按如下參數(shù)進行初始設(shè)置：起點start=1，面朝點next=2，終點destination=1，必經(jīng)點集point_list=[3，4，5，6，7，8，9，10，11]。和爬山法（hill climbing，HC）、模擬退火法（simulated annealing，SA）、遺傳算法（genetic algorithm，GA）等算法[18]做對比實驗，實驗分別測試100次，取實驗結(jié)果的平均值，列舉如表5中所示。

表5 不同算法效果之間的比較Table 5 Comparison results of different algorithms

從實驗結(jié)果可以看到，在多種算法之間，爬山法的計算速度最快，遺傳算法的計算速度最慢。從理論上分析，這三種傳統(tǒng)算法，會犧牲解的質(zhì)量來提高計算的速度，具體表現(xiàn)為爬山法較其余算法更容易陷入局部最優(yōu)解。但在本次實驗中由于計算規(guī)模較小，解的質(zhì)量差異不明顯，在此僅討論求解時間和最優(yōu)結(jié)果。可以看到前三種傳統(tǒng)算法給出的最優(yōu)結(jié)果均是：[1，2，10，11，3，4，5，6，7，8，9]，如圖4 中虛線所示，很明顯，所包含的中間路徑[…，2，10，11，…]是不滿足額外硬約束的，無人車無法轉(zhuǎn)過此處的賽道轉(zhuǎn)角。而本文提出的算法給出的最優(yōu)結(jié)果是：[1，2，10，7，6，5，4，3，11，10，8，9]，如圖4中實線所示，其中沒有包含違反額外硬約束條件的中間路徑，無人車可以順利完成任務(wù)。盡管本文算法在計算時間上不具有絕對的優(yōu)勢，但是可以有針對性地解決具有額外硬約束的過必經(jīng)點集的最短路徑問題。

圖4 不同算法求解得到的最短路徑示意圖Fig.4 Schematic diagram of obtained shortest path

4 結(jié)束語

本文對“過必經(jīng)點集且具有額外硬約束的最短路徑問題”進行抽象處理，并提出基于深度優(yōu)先搜索的隨機搜索算法。實驗測試表明，該算法具有可以添加額外的硬約束、解的最優(yōu)性好的優(yōu)勢。由于該算法是采用隨機搜索的算法，時間效率上受必經(jīng)節(jié)點數(shù)目的影響較小，但受必經(jīng)節(jié)點元素集的選取影響較大，難以得出統(tǒng)一的評判標準。通過TSP問題的求解對比實驗，該算法相比于傳統(tǒng)算法，盡管在計算時間上不具有絕對的優(yōu)勢，但是針對性地解決具有額外硬約束的過必經(jīng)點集最短路徑問題。該算法的優(yōu)勢在于代碼量少、最優(yōu)性好，可以解決額外硬約束問題，同時容易調(diào)整參數(shù)。