一種基于終端策略的近似漣漪擴散算法

Approximate ripple spreading algorithm based on terminal strategy

Wang Ruixianga，Zhang Yingfeib，Li Hang?，Hu Xiaobing?t （a.Sino-EuostoatonColfSfeceamp;in，iltonUesitf 300300，China）

Abstract： This paper proposed an improved algorithm to enhance the efficiency and adaptability of solving the k -shortest path problem （ k -SPP） incomplex network environments.The algorithm optimized the original ripple spreading algorithm（RSA） bylimiting thenumberofripplesgeneratedbyeachnode，which increasedcomputational eficiencyandformed theapproximate ripple spreading algorithm（ARSA）. It introduced a terminal strategy H_T ，by layering nodes and setting different ripple limits tobalanceoptimalityandcomputationaleficiency.Itfurtherenhanced thestrategy’sadaptabilitybyutilizingafuzzy inference system（FIS），which dynamically adjusted the H_T strategy based on network characteristics. Simulation experiments conducted on grid，random，small-world，and scale-free networks show that the H_T strategy significantly improves ARSA’s performance，while the FIS enables rapid configuration of the H_T strategy. Experimental results indicate that the proposed algorithm achieves high eficiency and reliability in solving k -SPP， providing a novel approach to path planning in complex network environments.

Key words： k -shortest paths problem； approximate ripple spreading algorithm；terminal strategy； fuzzy inference system;path planning

0 引言

k 最短路徑問題（kshortestpathsproblem， k -SPP）是圖論中的經典問題，其目標是在給定的有向圖中尋找從起點到終點的k 條最短路徑。在實際應用中， k -SPP被廣泛應用于網絡路由優化[1]、車輛巡檢[2]、物流配送[3]及應急路線規劃[4]等領域。例如，在網絡路由中，k-SPP可用于計算多條備用路徑，從而提升網絡的可靠性和抗故障能力；在物流配送中，k-SPP則為規劃提供了多條可選路徑，增加了運輸方案的靈活性。因此，如何高效地求解 k -SPP成為了學術研究的一個重要方向，眾多學者提出了不同的解決方案[5-7]

大多數求解 k -SPP的算法基于1971年提出的Yen算法，采用了“偏離路徑”的策略。在此方法中，每次計算第 k 條最短路徑時，都會在第 k-1 條最優路徑的基礎上，將除了起點和終點之外的節點視為“偏離點”，從每個偏離點出發計算到終點的新的候選路徑，并對這些候選路徑進行排序，以確定第k條最短路徑。這種方法雖然直觀，但計算過程復雜，且效率較低，尤其是在處理大規模復雜圖時更為明顯。

為了降低Yen算法的求解 k -SPP的復雜度，研究人員提出了多種改進策略。文獻[8]將“偏離路徑”的計算過程視為動態更新網絡中一對多的最短路徑問題，每次搜索僅恢復一個節點和一個鏈路，從而重復利用先前搜索的最短路徑結果。文獻[9]采用反向一對多的Dijkstra算法預計算所有節點到目的地的最短路徑，使用預先計算的子路徑作為“偏離路徑”。Chen等人[1°]在搜索\"偏離路徑\"時，采用每次僅恢復一個節點的策略，并結合終身規劃 A^* （lifeplanning A^* ， LPA^* ）算法來快速生成“偏離路徑”。

此外，額外的預處理階段也有助于加速 k -SPP算法的計算效率。文獻[11]在預處理過程中通過添加捷徑邊來收縮道路的層次結構。文獻[12]提出了一種基于大規模道路網絡的行駛方向路由引擎，可以實時查詢所需的“偏離路徑”。然而，這些方法在計算前 k 條最短路徑時仍依賴于前（k-1）條最短路徑的信息。

漣漪擴散算法（ripple spreading algorithm，RSA）[13，14]是一種處理最短路徑問題的確定性算法，該算法通過模擬水面上的漣漪擴散現象，在圖中傳播“漣漪”以尋找最短路徑。相比于傳統路徑規劃算法，RSA在處理復雜路網環境時表現出了更高的計算效率和強大的全局尋優能力，因此被成功應用于求解 k-SPP^{[14， 15]} 、多目標路徑優化[16，17]和動態路徑規劃[18]等問題。

在應用RSA求解 k -SPP時，該算法不依賴于前（k-1）條最短路徑的信息。具體來說，RSA通過模擬自然漣漪擴散的過程來尋找前 k 條最短路徑，每個節點最多產生 k 條漣漪，并通過這些漣漪到達終點的路徑確定前 k 條最短路徑。然而，由于每個節點可能產生冗余的漣漪，導致了算法效率的降低。為了解決這一問題，文獻［14]提出了近似漣漪擴散算法（approxi-matedripplespreadingalgorithm，ARSA），該確定性算法在假設每個節點最多產生 h 條漣漪（ 1?h?k ）的情況下，證明了可以以更高的效率找到前 k 條路徑，盡管會在一定程度上犧牲最優性。

為進一步權衡路徑的最優性與計算效率，本文提出了一種終端策略，并通過經驗規則和模糊推理系統（fuzzyinferencesystem，FIS）對終端策略進行合理設置，以提升RSA在求解 k SPP時的效率和準確性，能夠更好地應對復雜網絡環境中的路徑規劃問題。

1核心理論與關鍵技術

1.1 k. SPP問題描述

根據路徑中是否存在回路（即路徑中是否存在重復的節點），可以將前 k 條最短路徑問題分為前 k 條最短簡單路徑問題（即路徑中不存在回路）和前 k 條最短通用路徑問題（即路徑中存在回路）。本文主要討論前 k 條最短簡單路徑問題。

假設路網表示為圖 G（V，E） ，其中 V={v₁ ， v₂ ，…， v_n} 表示為含有 n 個節點的節點集， E={e₁ ， e₂ ，…， e_m 為有 ∣m∣ 條邊的邊集。對于任意的 e_l（1?l?m） ，存在 i j∈V （ {≠j） 將 e_l 表示為 （i，j） ，其中 C（i，j） 表示邊 e_l 的權值。

假設向量 P 記錄一條路徑且 P（i）=j 表示該路徑中的第 χ_i 個節點為節點j（ 1?i?p ， j∈V） ，那么該路網的起點和終點分別可以表示為 P（1） 和 P（p） ，其中 p 表示路徑向量 P 所含的節點總數。

已知路徑向量 P ，則通過路徑向量 P 所耗費的代價可以表示為

其中 ：f（P） 為路徑 P 的總代價。

假設第 k 條最短路徑可以表示為 P_SP，k ，則第1條最短路徑P_SP，1 的路徑代價可以表示為

f（P_SP，1）=min_P∈Ωf（P）

其中：itOmega 為所有可行路徑的集合。

對于任意的 kgt;1，P_SP，k 滿足這種序列性確保了路徑按代價從小到大排序，符合 k -SPP的定義和要求。

1.2模糊推理系統

模糊推理系統是一種通過經驗生成的模糊邏輯來進行推理和決策的系統，其實現流程如圖1所示。

基本架構包含以下五個步驟[21]：

a）確定模糊推理系統的結構。

首先需要明確輸人變量和輸出變量。常見的輸入變量可能包括溫度、濕度、速度、壓力等，輸出變量可以是控制信號，如電流、閥門開度等。

為了提高系統的穩定性，輸入和輸出變量通常需要歸一化處理，將其映射到[0，1]或[-1，1]。這有助于減少數值波動對系統決策的影響。

b）確定模糊推理系統的結構。

根據實際控制需求，定義輸入和輸出變量的模糊集。常見的模糊集包括“低”“中”“高”等級。例如，在漣漪擴散過程中，定義模糊集為節點處可以產生漣漪數量的級別為“大”“中”和“小”。

隸屬度函數用于衡量模糊集和變量之間的關系，其選用通常取決于經驗，本文所使用的隸屬度函數為三角隸屬度函數，其形式如式（4）所示。

其中： a?b?c 。

假設漣漪擴散過程中節點的漣漪輸入變量的模糊子集分別為“大”“中”和“小”，則其形式如圖2所示。

若該輸入變量的值為0.8，則此時可以看到在圖2中“大”的值為0.6，“中”的值為0.4，“小”的值為0。

c）建立模糊規則。

模糊規則通常采用IF-THEN的形式，如式（5）所示。

其中： ??A_i^l 和 B^l 分別是 U_i∈R 和 V∈R 上的模糊集合; x=（x₁ x，…， x_n）^T∈U 和 y∈V 分別是模糊系統的輸入和輸出變量；U 和 V 分別是輸入和輸出變量的集合；“ x_i 為 A_n^l ”是一個模糊命題。

規則庫的設計通常基于專家經驗或歷史數據，以確保規則能夠反映實際情況。模糊規則庫中的每條規則由輸入隸屬度和輸出隸屬度之間的關系構成，常見的模糊規則包括不完整規則、或規則、單一模糊陳述等。

d）近似推理。

近似推理以模糊命題為前提，運用模糊規則得出新的模糊命題為結論的推理過程。通過步驟b）c）得到的模糊集和模糊規則，可以得到輸出值的模糊集。但由圖2可以發現，通過清晰值得到的模糊集可能不止一個，需要用到的模糊規則也不止一個，因此通過近似推理將模糊規則進行合成。

近似推理法則的合成算法有很多種，其選用往往也需要通過經驗選擇合適的合成算法，本文近似推理法則的合成算法為“取小-取小\"算法，其具體算法見文獻[19]。

e）輸出變量的去模糊化。

去模糊化是模糊推理系統的最后一步，即將模糊輸出轉換為具體的控制信號或數值。常見的去模糊化方法有最大隸屬度法、重心法和平均法和中位數法，本文使用的方法為最大隸屬度法，其具體方法見文獻[19]。

2算法改進

2.1 ARSA

ARSA是基于RSA的改進確定性算法，用于解決 k 最短路徑問題，主要用于求解k最短路徑問題。RSA通過模擬漣漪接力賽的方式，尋找圖中從起點到終點的第一條最短路徑。具體來說，RSA的過程如下：從起點開始，產生第一個漣漪，并以恒定的速度向周圍的節點擴散；當漣漪到達一個尚未被訪問過的節點時，該節點將被激活，并開始產生自己的漣漪；當一個漣漪第一次到達終點時，漣漪的傳播過程停止，此時可以通過回溯該漣漪的路徑得到第一條最短路徑。

RSA在求解 k 最短路徑問題時，每個節點產生多個漣漪，且路徑上每條漣漪的傳播速度相同。理論上，若路網中存在 k 條最短路徑，則有 k 條漣漪最終會按照時間的先后順序到達終點。通過回溯這些漣漪的傳播路徑，可以得到從起點到終點的k 條最短路徑。例如，在圖3（a）中，RSA展示了其在求解某個路網的前2條最短路徑時的尋路過程，其中 o 節點為起點， D 節點為終點。

盡管RSA在解決 k 最短路徑問題時具備較好的性能，但隨著路徑數量 k 的增加，算法的計算效率會受到影響。這是因為每個節點在尋找路徑時需要產生多個漣漪，導致計算量和內存消耗的增加。

為了提高效率，ARSA在RSA的基礎上進行了一定的優化。ARSA的關鍵改進在于限制每個節點產生的漣漪數量，設定為最多生成 h 條漣漪（其中 1?h?k ）。這種限制意味著，在尋找路徑的過程中，每個節點不再像RSA算法那樣生成無限數量的漣漪，而是只生成一定數量的漣漪，從而減少了路徑計算的冗余，提高了計算效率。

然而，降低每個節點漣漪生成數量的上限，也意味著犧牲了某些情況下的最優性。具體來說，若每個節點最多只能產生1條漣漪（即 h=1 0，則只能找到從起點到終點的1條最短路徑，而無法探測到其他備選路徑。這種情況下，路徑的多樣性會大大降低，最終導致求解 k 最短路徑問題時的結果并不完全符合最優解。例如，在圖3（b）所示的路網中，當 h=1 時，ARSA只能找到1條最短路徑，而無法找到其他可能的最短路徑。因此，雖然ARSA在提高計算效率的同時，犧牲了一定的最優性，但它為解決大規模復雜圖中的 k 最短路徑問題提供了一種更加高效的方案。

2.2 ARSA改進

2.2.1終端策略 H_T

為了有效解決ARSA在最優性和計算效率之間的平衡問題，本節提出了一種終端策略 H_r （hierarchyterminal strategy）。

該策略通過對路網中除起點和終點外的節點進行分級，并為每個級別 i 的節點設置一個漣漪產生上限 h_i （1?h?k） ，從而在保證最優性的前提下提高計算效率。

設想路網中有 N_L2D 個節點與終點有直接連接，則將這些節點稱為第1級節點;如果有若干個節點與第1級節點有直接連接但與終點沒有直接連接，則這些節點為第2級節點；依此類推，路網中除起點和終點外的節點被分為 N_τ 個級別（ 1? N_r ）。每個級別的節點都有一個對應的漣漪上限 h 值，設定為向量 H_T=[h_T，1 ， h_T，2 ，…， h_T，NT] ，其中 H_?T[i] 表示每個第 i 級節點所能產生漣漪數量的上限。

通常情況下，終端策略 H_T 的設置取決于所解決的實際問題。根據已有問題的經驗，提出如下規則：

規則1設第1級節點的數量為 N_L2D ，所有第1級節點所能產生漣漪上限的總和大于 k ，即

N_L2D×h_T，1?k

原理為了確保至少有 k 個漣漪到達終點，首先要保證與終點有直接鏈接的所有節點（即第1級節點）能產生總共不少于 k 個漣漪。此規則確保了從最接近終點的節點開始，能夠有足夠的漣漪到達終點。

規則2對任意的 i（1?i?N_T） ，第 i 級節點的漣漪上限h_T，i 大于或等于 h ，即

h_T，igt;h

原理通常情況下，僅對靠近終點的節點進行分級即可得到較好的結果，而對遠離終點的節點則仍使用ARSA中默認的漣漪數量上限 h 值。通過這種方式，既能確保計算效率，又能保證最優路徑的精度。靠近終點的節點漣漪上限較大，可以保證有足夠的漣漪數量到達終點，而遠離終點的節點則設置較小的漣漪數量上限以提高計算效率。

規則3對任意的 i ， ，第 i 級節點所能產生漣漪的上限 h_T，i 大于第 j 級節點所能產生漣漪的上限h_T，j ，即

h_T，i?h_T，j

原理為了確保算法的計算效率，每個級別的節點所能產生的漣漪數量應盡可能少。具體地，為了保證最優路徑能夠盡快找到，靠近終點的節點應盡量產生更多的漣漪，而遠離終點的節點則應限制產生漣漪的數量，從而提高算法的計算效率。此規則通過設定層級的漣漪上限，使得每一層節點的計算量逐步減少，從而平衡了最優性和計算效率之間的矛盾。

通過上述終端策略 H_T 的設置規則，可以針對不同的節點為節點設置不同的漣漪上限，從而實現了最優性和計算效率的平衡。如圖3（c）所示，設置了終端策略 H_T 的ARSA可以生成比圖3（a）更少的漣漪，從而提高計算效率；而相對于圖3（b）設置了終端策略 H_r 的ARSA找到了最優的前 k 條路徑。

2.2.2模糊推理過程設置 H_T

從理論上講，良好的終端策略 H_T 可以有效地幫助ARSA在最優性和計算效率之間找到平衡。盡管在2.2.1節中已經提出了一些關于終端策略 H_T 的設定規則，但在實際應用中，設定合適的終端策略 H_T 仍需要進行調試。此時，模糊理論和方法因其強大的經驗處理能力，成為解決這一問題的有效工具。本節提出了一種基于模糊推理的終端策略 H_T 設置過程，其中輸人為給定的 k -SPP以及路網的特征（如 k 值、節點數N_N 、連接數 N_L 和層級 i ），輸出為終端策略 H_T 中每個層級節點的漣漪產生上限 h_T，i 的數值。

為了實現單位化處理，本文提出了一種新的變量構建方法，利用已知的 k 值 ?^h 值、節點數 N_N 、連接數 N_L 和層級 i 值及節點級別 i 內節點的數量（記作 N_tier-i ）來構建新的單位化變量。

具體的變量定義如式（9）＼～（12）所示。

通常情況下 h?klt;N×N_L，v_NI，1 ， v_N，2 和 v_NI，3 的值在（0，1]內，但為了確保 v_NI，1?v_NI，2 和 v_NI，3 的取值在（0，1]，上述式（9） ～ （11）被改寫為

變量 v_NI，4（i） 是確定終端策略 H_T 中 h_T，i 值的重要組成部分。基本原理是，如果 v_N，4（i）gt;gt;1 （即 h×N_tier-igt;gt;k ，那么即使一個 i 級節點只能產生不超過1個漣漪，所有 i 級節點仍然可以產生遠遠超過 k 個漣漪，這意味著 k 條最短路徑不可能不經過該 i 級節點。在本研究中，假設 足夠大，以使 i 級節點產生與 k 條最短路徑相關的所有漣漪。因此，式（12）可以被修改為

（13）

對于任意層級 i 的節點，其模糊推理系統的輸入為 v_NI，1 、v_{NI，2?vNI，3} 和 v_NI，4（i） ，輸出為 h_T，i 。粗略地說， v_NI，1 越大， h_T，i 應該越大，而 v_{NI，2?vNI，3} 或 v_NI，4（i） 越小， h_T，i 應該越大。

為了模糊化 v_N，j（j=1，…，4） 和去模糊化 h_T，i ，本文將 v_N，j 和 h_T，i 的模糊子集分類為“大\"“中等\"或者“小”三類。除了滿足2.2.1節所屬的規則之外， v_N，j 和 h_T，i 的關系應該還滿足模糊規則，其模糊規則如下所示。

模糊規則1 如果 v_NI，1 越大，則 h_T，i 應該越大。

原理 k 值越大，意味著需要更大的漣漪上限 h_T，i 來確保產生足夠的漣漪以更接近 k 。

模糊規則2如果 v_N，2 越大，則 h_T，i 應該越小。

原理漣漪上限 h 越大，表示節點產生的漣漪數量更大，h_T，i 的下界應更接近 h ，而不是 k ，從而提升計算效率。

模糊規則3如果 v_NI，3 越大，則 h_T，i 應該越小。

原理如果 h 值較大，則漣漪產生上限 h_T，i 應降低，以避免降低算法的效率。

模糊規則4如果 v_NI，4（i） 越大，則 h_T，i 應該越小。

原理對于離終點較遠的節點，其漣上限應適當減小，以提高計算效率，避免冗余的計算。

終端策略 H_r 的模糊推理系統的流程如圖4所示。這個系統中，輸入的變量 v_NI，1?v_NI，2?v_NI，3 和 v_NI，4（i） 根據模糊規則進行推理，輸出結果為每個層級的漣漪上限 h_T，i 。

2.2.3復雜度分析

針對最優版本的 k -SPP的RSA，文獻[15]已經證明了其時間復雜度為 O（k×N_L×N_ATU） ，其中 N_L 為圖中的邊的數量，N_ATU 為漣漪在圖中的運動仿真時間，通常情況下 N_ATU 最壞情況和圖中的節點數量 N_N 數量級一致。經典的 k -SPP的Yen算法時間復雜度為 O（ktimes（N_N+N_L）×logN_N） ，文獻[15]證明Yen算法在稀疏圖（即邊較少的圖）遜色于 k -SPP的RSA，在正常情況下最優版本的 k -SPP的RSA時間復雜度略遜于Yen算法。

當使用ARSA時，無論是否使用 H_τ 策略，為了提高算法的計算效率， h 往往遠小于 ，即算法時間復雜度為O（h×N_L×N_ATU） 。因此遠遠低于 Yen 算法。

當使用模糊推理過程預測終端策略 H_T 時，模糊推理的時間復雜度為 O（R×M+N+Q） ，其中， R 是規則數量， M 是輸人變量數量， N 是輸人數據的維度， Q 是輸出模糊集合的大小。但是相對于節點數量來說，往往 N_Lgt;gt;N 因此，使用模糊推理過程的算法復雜度依然可以認為是 O（h×N_L×N_ATU） 。

3仿真實驗

本章的實驗旨在揭示所報道的ARSA終端策略 H_T 之間的差異，實驗分為兩部分：第一部分解釋ARSA在有無終端策略H_T 的情況下，最優性和計算效率之間的關系；第二部分實驗則探討是否通過模糊推理系統來設置終端策略 H_T 對ARSA的影響。實驗所使用的路網包括網格網絡、隨機網絡、小世界拓撲結構網絡和無標度拓撲結構網絡。其中網格網絡為均勻分布的節點，即每個節點僅與鄰居節點相連；隨機網絡即在網格網絡基礎上引入隨機干擾，節點位置和鏈接都被隨機化；小世界網絡[22]通過Watts-Strogatz模型生成，局部聚集性和全局短路徑長度并存；無標度網絡[23]則通過Barab?si-Albert模型生成，節點度數遵循冪律分布，少數節點連接大量其他節點。第三部分實驗為基于現實的鄭州路網的仿真實驗，為了驗證算法的應用價值，本文的仿真環境為Windows1064bit操作系統，內存為8GB，CPU為AMDRyzen54600H @ （20 3.00GHz ，仿真軟件為MATLAB R2019a 。

3.1關于有無終端策略 H_τ 的ARSA的實驗結果

首先，本文進行了綜合實驗，研究所提出的ARSA方法在有無終端策略 H_T 條件下解決 k -SPP時，最優性和計算效率之間的關系。在本節所使用的網絡中，每個節點大約有6個連接。因此，k-SPP的規模可以由節點數 N_N 和路徑數 k 來決定。本節中的網絡規模采用小規模網絡和大規模網絡兩種，其中小規模網絡節點數為 且 k=100 ，大規模網絡節點數為 N_N=1 000JN_L=800 且 k=120 。對于網格網絡、隨機網絡、小世界網絡和無尺度網絡的每一種網絡結構，控制節點的坐標隨機生成了100個網絡進行實驗，共400個隨機網絡。然后，分別應用第2章中的原始ARSA（即沒有終端策略 H_T 的ARSA）并使用不同的 h 值（小規模網絡為 h=5，10，20，50，100 大規模網絡為 h=5，10，30，60，120） ，且節點共有三層。同時在小規模網絡和大規模網絡分別將三層終端策略 H_T 應用于 h= 5的ARSA和 h=10 的ARSA中。在小規模網絡的三層終端策略 H_T 的設置中， h_T，1=50Ω，h_T，2=20 和 h_T，3=10 ，而在大規模網絡的三層終端策略 H_T 的設置中 h_T，1=60，h_T，2=30 和 h_T，3=10

在實驗中，本文主要分析了ARSA在不同參數設置下的輸出路徑的平均路徑長度（averagepathlength，APL）、ARSA在100個特定類別網絡中所消耗的平均計算時間（computationaltime，CT）（s）ARSA在100個某類網絡中輸出的平均路徑數（number of paths outputted，NPO）。由于 k=100 ，當 h=100 時的結果代表 k -SPP的最優解。所以，對于 h

a）最優性與效率的平衡。如果 h 值設置過小，ARSA的最優性會下降，找到的路徑少于 k 條。無 H_T 的ARSA在某些情況下可能找不到足夠的路徑。當 h 值較大時，算法能找到更多路徑，但計算時間急劇增加。通常在小規模網絡上， h=50 時，CT僅為 h=100 時CT值的 39%～59% ;在大規模網絡上， h=60 的CT僅為 h=120 時的 30%～45% 。在小規模網絡上，APL值僅比 h=100 時約多 2% ;在大規模網絡上，APL值僅比 h=120 時多 0.3%～6% 。

b）網格網絡表現。對于網格網絡，無 H_T 的ARSA能顯著提高計算效率，并且在小規模網絡中 h=50 時保持最優性，在大規模網絡 h=30 時可以輸出前 k 條最短路徑但是不保證最優性。

c）隨機網絡、小世界網絡和無標度網絡。當小規模網絡h=50 、大規模網絡 h=60 時，最優性開始喪失，導致無法找到最優解。對于無標度網絡，許多最短路徑需要經過樞紐節點，如果樞紐節點的漣漪生成次數小于 k ，則很多路徑會被遺漏，導致最優性喪失。

d）計算效率趨勢。實驗結果表明，無 H_T 的ARSA的計算時間隨著 h 的增大而線性增長。

3.2關于不同終端策略 H_τ 的ARSA的實驗結果

在本節實驗中，進一步研究了如何通過調整終端策略 H_T 來優化ARSA的性能。實驗網絡與上一節相同，分為 h=5 和h=10 兩組。對于每組實驗，本文調整終端策略 ，h_T，2，h_T，3] ，并將其應用于生成的每個網絡。實驗中分別為兩個規模的網絡提供了五種手動設置的 H_T ：[50，0，0]、[50，20，0]、[50，20，10]、[50，50，50]、[100，100，100]和[60，0，0]、[60，30，0]、[60，30，10]、[60，60，60]、[120，120，120]。同時，采用2.2.2節中提出的模糊方法，根據 k -SPP的特征自動設置 H_r

以下是實驗結果分析：

a）模糊方法的效果。從表2、3和5、6可以看出，采用模糊推理方法自動設置 H_T 后，ARSAT表現出與手動設置 H_T 相似的性能，并且提供了更高效的平衡。模糊方法通過考慮網絡參數如節點數、連接數和層級節點數，自動計算出合適的 H_T ，優化了終端策略的選擇。

b）閾值效應。當 h 和 H_T 值超過某一閾值時，進一步增加這些值不會顯著縮短APL，反而會導致CT值急劇增加。因此，終端策略 H_T 的設置需要精確調整，以避免過高的計算

成本。

c）最佳手動設置。表2、3和表5、6顯示，小規模網絡手動設置的 H_T=[50，20，10] 和大規模網絡手動設置的 H_T=[60 30，10]在最優性和計算效率之間達到了較好的平衡，表現出理想的性能。盡管如此，選擇合適的人工設置終端策略 H_T 通常需要嘗試和測試，而這往往需要一定的時間和經驗。

3.3終端策略 H_τ 的ARSA實際應用

2021年7月20日，河南省鄭州市遭遇極端暴雨天氣，城市路網中出現積水，影響出行。為模擬當日出行情況，本節將鄭州市路網轉換為556個節點和971條邊的網絡，暴雨持續^10h 左右時，路網結構和道路積水情況如圖5所示，其中邊的顏色反映了道路積水的深度（見電子版）。為保障全市物資供應，全市若干個供貨點向目標點運輸物資，紅色點為起點，綠色點為終點。以圖中97號節點為起點，195號節點為終點為例，為保障物資的運輸，需提供多條路徑以避免因路面積水而無法通行。設置路徑的 k 值為20，設置終端策略 H_T 和仿真結果如表7所示，其中使用模糊推理得出的終端策略 H_T 為[9，6，5]，h值為3。

根據表7的數據可以看到，手動設置的終端策略 H_T 在APL和NOPF上強于模糊推理設置的終端策略 H_T ，但在CT上模糊推理設置的終端策略 H_T 較為優秀。同時，可以發現由于模糊推理設置的終端策略 H_T 對節點進行了限制，極大地改變了尋找的前 k 條路徑的結構，使得模糊推理設置的終端策略H_T 得到的候補路徑中存在一條可以繞開所有積水阻塞的路徑，從而快速到達目標地點。

4結束語

本文針對圖論中的 k 最短路徑問題（ k -SPP），提出了一種新的解決方案，旨在提高在復雜網絡環境中尋找前 k 條最短路徑的效率和準確性。現有的漣漪擴散算法（RSA）在解決 k 1SPP時把節點允許通過的漣漪上限設置為 k ，雖然可以求得 k SPP的最優解，但是計算效率較低。為了進一步提高效率，本文提出了近似漣漪擴散算法（ARSA），該算法限制了每個節點產生的漣漪數量，減少了計算量，但可能會犧牲一定的最優性。為了平衡最優性和計算效率，本文引入了終端策略 H_T ，并利用模糊推理系統（FIS）對其進行設置，且通過仿真實驗驗證了所提方法的有效性。

實驗結果表明，設置一個合理的終端策略 H_T 可以使ARSA在最優性和計算效率之間取得良好的平衡；而使用FIS設置的終端策略 H_r 雖然可能沒有手動調試設置的終端策略H_T 效果有效，但是可以在較快時間內快速得到終端策略，從而實現ARSA在最優性和計算效率之間的較好平衡。

未來的工作將更加關注終端策略 H_T 的設置，例如結合智能優化算法、深度學習，得到更準確的終端策略 H_T 以平衡算法計算效率和最優性。

參考文獻：

[1]張震霄，管建民，邵方明.k最短可靠路徑及其優化問題[J]．現代電子技術，2020，43（23）：58-61.（ZhangZhenxiao，GuanJianmin，ShaoFangming. k -shortestreliablepathsanditsoptimization[J].ModernElectronics Technique，2020，43（23）：58-61.）

[2]侯林杰．光伏巡檢無人車路徑規劃算法研究[D]．長春：吉林大學，2024.（Hou Linjie. Research on path planning algorithm of un-

[3]李慧婕.物料配送AGV多目標路徑規劃算法研究[D].沈陽：沈陽工業大學，2O23.（LiHuijie.ResearchonAGVmulti-objectivepath planning algorithm for material distribution[D].Shenyang：Shen-yangUniversity of Technology，2023.）

[4]展慧.考慮復合鏈生災害事故情形的化學品集中區人員應急疏 散路徑規劃[D]．北京：北京化工大學，2022.（ZhanHui.Emergencyevacuationpath planningofpeoplein chemical concentration areaconsidering compound chain-linked disasters and accidents[D]. Beijing：Beijing University of Chemical Technology，2022.）

[5]Yen JY.Finding thek shortest loopless paths in a network[J]. ManagementScience，1971，17（11）：712-716.

[6]Eppstein D.Finding thek shortest paths[C]//Proc of the 35th Annual Symposium on Foundations of Computer Science.Piscataway， NJ：IEEEPress，1994：154-165.

[7]Hershberger J，Maxel M，Suri S.Finding the k shortest simple paths ： anewalgorithmanditsimplementation[J].ACMTranson Algorithms，2007，3（4）：45.

[8]MichailD，KinableJ，NavehB，etal.JGraphT—aJavalibraryfor graphdata structuresand algorithms[J].ACM Trans on MathematicalSoftware，2020，46（2）：1-29.

[9]Yao Yao，Lei Siqi，Guo Zijin，etal.Fastoptimization forlarge scale logisticsin complex urban systemsusing the hybrid sparrow search algorithm[J].InternationalJournalofGeographicalInformation Science，2023，37（6）：1420-1448.

[10]Chen Biyu，Chen Xiaowei，Chen Huiping，et al.Eficient algorithm forfindinghshortest pathsbased on re-optimization technique[J]. TransportationResearchPartE：LogisticsandTransportation

Review，2020，133：101819.

[11]AtakishiyevS，SalamehM，YaoHengshuai，etal.Explainableartificialintelligence for autonomousdriving：a comprehensive overview and field guide for future research directions[J]. IEEE Access， 2024，12：101603-101625.

[12]DellingD，GoldbergAV，PajorT，etal.Customizable routeplanningin road networks[J].Transportation Science，2017，51（2）：566-591.

[13]Hu Xiaobing，WangMing，Leeson MS，et al.Deterministic agentbasedpath optimizationbymimicking the spreading of ripples[J]. Evolutionary Computation，2016，24（2）：319-346.

[14]Hu Xiaobing，Zhang Mingkong，Liao Jianqin.An approximate ripplespreading algorithm with terminal h strategy[C]//Proc of IEEE Symposium Series on Computational Intelligence.Piscataway，NJ：IEEE Press，2017：1-8.

[15]Hu Xiaobing，ZhangChi，ZhangGongpeng，etal.Finding the k shortestpathsbyripple-spreadingalgorithms[J].EngineeringApplicationsofArtificial Intelligence，2020，87：103229.

[16]Hu Xiaobing，Gu Shenghao，ZhangChi，etal.FindingallPareto optimalpathsbysimulatingripplerelayrace in multi-objectivenetworks [J].Swarmand Evolutionary Computation，2021，64：100908.

[17]Hu Xiaobing，WangMing，YeQian，etal.Multi-objective newproduct developmentby completePareto front and ripple-spreading algorithm[J].Neurocomputing，2014，142：4-15.

[18]Hu Xiaobing，ZhangMingkong，Zhang Qi，et al. Co-evolutionary path optimizationbyripple-spreadingalgorithm[J].TransportationResearchPartB：Methodological，2017，106：411-432.

[19］石辛民，郝整清.模糊控制及其MATLAB仿真[M].北京：清華 大學出版社，2Oo8．（Shi Xinmin，Hao Zhengqing.Fuzzycontrol anditsMATLAB simulation[M].Beijing：Tsinghua University Press， 2008）.