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

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

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

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

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

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

為進(jìn)一步權(quán)衡路徑的最優(yōu)性與計算效率，本文提出了一種終端策略，并通過經(jīng)驗規(guī)則和模糊推理系統(tǒng)（fuzzyinferencesystem，F(xiàn)IS）對終端策略進(jìn)行合理設(shè)置，以提升RSA在求解 k SPP時的效率和準(zhǔn)確性，能夠更好地應(yīng)對復(fù)雜網(wǎng)絡(luò)環(huán)境中的路徑規(guī)劃問題。

1核心理論與關(guān)鍵技術(shù)

1.1 k. SPP問題描述

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

假設(shè)路網(wǎng)表示為圖 G（V，E） ，其中 V={v₁ ， v₂ ，…， v_n} 表示為含有 n 個節(jié)點(diǎn)的節(jié)點(diǎ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 的權(quán)值。

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

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

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

假設(shè)第 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模糊推理系統(tǒng)

模糊推理系統(tǒng)是一種通過經(jīng)驗生成的模糊邏輯來進(jìn)行推理和決策的系統(tǒng)，其實現(xiàn)流程如圖1所示。

基本架構(gòu)包含以下五個步驟[21]：

a）確定模糊推理系統(tǒng)的結(jié)構(gòu)。

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

為了提高系統(tǒng)的穩(wěn)定性，輸入和輸出變量通常需要?dú)w一化處理，將其映射到[0，1]或[-1，1]。這有助于減少數(shù)值波動對系統(tǒng)決策的影響。

b）確定模糊推理系統(tǒng)的結(jié)構(gòu)。

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

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

其中： a?b?c 。

假設(shè)漣漪擴(kuò)散過程中節(jié)點(diǎn)的漣漪輸入變量的模糊子集分別為“大”“中”和“小”，則其形式如圖2所示。

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

c）建立模糊規(guī)則。

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

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

規(guī)則庫的設(shè)計通?；趯＜医?jīng)驗或歷史數(shù)據(jù)，以確保規(guī)則能夠反映實際情況。模糊規(guī)則庫中的每條規(guī)則由輸入隸屬度和輸出隸屬度之間的關(guān)系構(gòu)成，常見的模糊規(guī)則包括不完整規(guī)則、或規(guī)則、單一模糊陳述等。

d）近似推理。

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

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

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

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

2算法改進(jìn)

2.1 ARSA

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

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

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

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

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

2.2 ARSA改進(jìn)

2.2.1終端策略 H_T

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

該策略通過對路網(wǎng)中除起點(diǎn)和終點(diǎn)外的節(jié)點(diǎn)進(jìn)行分級，并為每個級別 i 的節(jié)點(diǎn)設(shè)置一個漣漪產(chǎn)生上限 h_i （1?h?k） ，從而在保證最優(yōu)性的前提下提高計算效率。

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

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

規(guī)則1設(shè)第1級節(jié)點(diǎn)的數(shù)量為 N_L2D ，所有第1級節(jié)點(diǎn)所能產(chǎn)生漣漪上限的總和大于 k ，即

N_L2D×h_T，1?k

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

規(guī)則2對任意的 i（1?i?N_T） ，第 i 級節(jié)點(diǎn)的漣漪上限h_T，i 大于或等于 h ，即

h_T，igt;h

原理通常情況下，僅對靠近終點(diǎn)的節(jié)點(diǎn)進(jìn)行分級即可得到較好的結(jié)果，而對遠(yuǎn)離終點(diǎn)的節(jié)點(diǎn)則仍使用ARSA中默認(rèn)的漣漪數(shù)量上限 h 值。通過這種方式，既能確保計算效率，又能保證最優(yōu)路徑的精度?？拷K點(diǎn)的節(jié)點(diǎn)漣漪上限較大，可以保證有足夠的漣漪數(shù)量到達(dá)終點(diǎn)，而遠(yuǎn)離終點(diǎn)的節(jié)點(diǎn)則設(shè)置較小的漣漪數(shù)量上限以提高計算效率。

規(guī)則3對任意的 i ， ，第 i 級節(jié)點(diǎn)所能產(chǎn)生漣漪的上限 h_T，i 大于第 j 級節(jié)點(diǎn)所能產(chǎn)生漣漪的上限h_T，j ，即

h_T，i?h_T，j

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

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

2.2.2模糊推理過程設(shè)置 H_T

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

為了實現(xiàn)單位化處理，本文提出了一種新的變量構(gòu)建方法，利用已知的 k 值 ?^h 值、節(jié)點(diǎn)數(shù) N_N 、連接數(shù) N_L 和層級 i 值及節(jié)點(diǎn)級別 i 內(nèi)節(jié)點(diǎn)的數(shù)量（記作 N_tier-i ）來構(gòu)建新的單位化變量。

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

通常情況下 h?klt;N×N_L，v_NI，1 ， v_N，2 和 v_NI，3 的值在（0，1]內(nèi)，但為了確保 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 級節(jié)點(diǎn)只能產(chǎn)生不超過1個漣漪，所有 i 級節(jié)點(diǎn)仍然可以產(chǎn)生遠(yuǎn)遠(yuǎn)超過 k 個漣漪，這意味著 k 條最短路徑不可能不經(jīng)過該 i 級節(jié)點(diǎn)。在本研究中，假設(shè) 足夠大，以使 i 級節(jié)點(diǎn)產(chǎn)生與 k 條最短路徑相關(guān)的所有漣漪。因此，式（12）可以被修改為

（13）

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

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

模糊規(guī)則1 如果 v_NI，1 越大，則 h_T，i 應(yīng)該越大。

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

模糊規(guī)則2如果 v_N，2 越大，則 h_T，i 應(yīng)該越小。

原理漣漪上限 h 越大，表示節(jié)點(diǎn)產(chǎn)生的漣漪數(shù)量更大，h_T，i 的下界應(yīng)更接近 h ，而不是 k ，從而提升計算效率。

模糊規(guī)則3如果 v_NI，3 越大，則 h_T，i 應(yīng)該越小。

原理如果 h 值較大，則漣漪產(chǎn)生上限 h_T，i 應(yīng)降低，以避免降低算法的效率。

模糊規(guī)則4如果 v_NI，4（i） 越大，則 h_T，i 應(yīng)該越小。

原理對于離終點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)，其漣上限應(yīng)適當(dāng)減小，以提高計算效率，避免冗余的計算。

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

2.2.3復(fù)雜度分析

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

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

當(dāng)使用模糊推理過程預(yù)測終端策略 H_T 時，模糊推理的時間復(fù)雜度為 O（R×M+N+Q） ，其中， R 是規(guī)則數(shù)量， M 是輸人變量數(shù)量， N 是輸人數(shù)據(jù)的維度， Q 是輸出模糊集合的大小。但是相對于節(jié)點(diǎn)數(shù)量來說，往往 N_Lgt;gt;N 因此，使用模糊推理過程的算法復(fù)雜度依然可以認(rèn)為是 O（h×N_L×N_ATU） 。

3仿真實驗

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

3.1關(guān)于有無終端策略 H_τ 的ARSA的實驗結(jié)果

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

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

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

b）網(wǎng)格網(wǎng)絡(luò)表現(xiàn)。對于網(wǎng)格網(wǎng)絡(luò)，無 H_T 的ARSA能顯著提高計算效率，并且在小規(guī)模網(wǎng)絡(luò)中 h=50 時保持最優(yōu)性，在大規(guī)模網(wǎng)絡(luò) h=30 時可以輸出前 k 條最短路徑但是不保證最優(yōu)性。

c）隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無標(biāo)度網(wǎng)絡(luò)。當(dāng)小規(guī)模網(wǎng)絡(luò)h=50 、大規(guī)模網(wǎng)絡(luò) h=60 時，最優(yōu)性開始喪失，導(dǎo)致無法找到最優(yōu)解。對于無標(biāo)度網(wǎng)絡(luò)，許多最短路徑需要經(jīng)過樞紐節(jié)點(diǎn)，如果樞紐節(jié)點(diǎn)的漣漪生成次數(shù)小于 k ，則很多路徑會被遺漏，導(dǎo)致最優(yōu)性喪失。

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

3.2關(guān)于不同終端策略 H_τ 的ARSA的實驗結(jié)果

在本節(jié)實驗中，進(jìn)一步研究了如何通過調(diào)整終端策略 H_T 來優(yōu)化ARSA的性能。實驗網(wǎng)絡(luò)與上一節(jié)相同，分為 h=5 和h=10 兩組。對于每組實驗，本文調(diào)整終端策略 ，h_T，2，h_T，3] ，并將其應(yīng)用于生成的每個網(wǎng)絡(luò)。實驗中分別為兩個規(guī)模的網(wǎng)絡(luò)提供了五種手動設(shè)置的 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節(jié)中提出的模糊方法，根據(jù) k -SPP的特征自動設(shè)置 H_r

以下是實驗結(jié)果分析：

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

b）閾值效應(yīng)。當(dāng) h 和 H_T 值超過某一閾值時，進(jìn)一步增加這些值不會顯著縮短APL，反而會導(dǎo)致CT值急劇增加。因此，終端策略 H_T 的設(shè)置需要精確調(diào)整，以避免過高的計算

成本。

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

3.3終端策略 H_τ 的ARSA實際應(yīng)用

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

根據(jù)表7的數(shù)據(jù)可以看到，手動設(shè)置的終端策略 H_T 在APL和NOPF上強(qiáng)于模糊推理設(shè)置的終端策略 H_T ，但在CT上模糊推理設(shè)置的終端策略 H_T 較為優(yōu)秀。同時，可以發(fā)現(xiàn)由于模糊推理設(shè)置的終端策略 H_T 對節(jié)點(diǎn)進(jìn)行了限制，極大地改變了尋找的前 k 條路徑的結(jié)構(gòu)，使得模糊推理設(shè)置的終端策略H_T 得到的候補(bǔ)路徑中存在一條可以繞開所有積水阻塞的路徑，從而快速到達(dá)目標(biāo)地點(diǎn)。

4結(jié)束語

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

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

未來的工作將更加關(guān)注終端策略 H_T 的設(shè)置，例如結(jié)合智能優(yōu)化算法、深度學(xué)習(xí)，得到更準(zhǔn)確的終端策略 H_T 以平衡算法計算效率和最優(yōu)性。

參考文獻(xiàn)：

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

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

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

[4]展慧.考慮復(fù)合鏈生災(zāi)害事故情形的化學(xué)品集中區(qū)人員應(yīng)急疏 散路徑規(guī)劃[D]．北京：北京化工大學(xué)，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].北京：清華 大學(xué)出版社，2Oo8．（Shi Xinmin，Hao Zhengqing.Fuzzycontrol anditsMATLAB simulation[M].Beijing：Tsinghua University Press， 2008）.