過必經點集且具有額外硬約束的最短路徑算法

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

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

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

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

1 問題描述

1.1 背景

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

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

圖1 應用場景示意圖Fig.1 Schematic diagram of match field

1.2 建模

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

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

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

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

1.3 變量定義

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

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

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

2 算法實現

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

2.1 預處理

2.1.1 輸入參數

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

2.1.2 相鄰點查找函數

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

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

（1）得到圖的大小，創建合適的數據結構變量存儲各點的相鄰點信息，首先求得圖中節點的個數length，然后以維度為length的一個列表對象用以存儲變量。

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

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

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

對于本次賽題，預處理后得到賽道無向帶權圖中①～?各個節點的相鄰點列表，具體為[[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 預處理階段的輸出

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

2.2 核心算法描述

2.2.1 參數定義

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

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

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

變量定義總結成表格如表2所示。

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

2.2.2 偽代碼描述

（1）最短路徑求解函數

算法1 最短路徑求解

（2）必經點路由判斷函數

算法2 必經點路由判斷

（3）硬約束條件狀態判斷函數

算法3 硬約束條件判斷

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

2.2.3 算法流程圖描述

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

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

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

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

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

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

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

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

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

（8）輸出最短路徑。

3 實驗測試與結果分析

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

3.1 時間效率和最優率的影響因素——必經點集中節點個數

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

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

表3 必經節點集的影響Table 3 Impact of choosing necessary node set

3.2 時間效率和最優率的影響因素——t_limit參數

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

表4 參數t_limit 的影響Table 4 Impact of t_limit parameter

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

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

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

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

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

4 結束語

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