基于路段賦值的多目標最短路算法研究

馮樹民，王憲凱，孫祥龍

(1. 哈爾濱工業大學 交通科學與工程學院，黑龍江 哈爾濱 150090； 2. 東北林業大學 土木工程學院，黑龍江 哈爾濱 150040)

0 引 言

多目標最短路問題(multi-objective shortest path problem, MOSPP)在最優化、運輸路線設計、通信網絡設計等領域被廣泛研究[1-3]。解決多目標最短路問題的關鍵在于尋找滿足多個目標的有效路徑集合，而這些目標之間一般相互沖突。例如，通信網絡中最優線路要兼顧延遲最小、交換量最大兩個矛盾目標；運輸路線規劃中要同時滿足成本、路徑長度、旅行時間3個目標最小化。不同于單目標優化問題中求解一個目標函數的最優解，多目標優化的任務不是找到每個目標函數的最優解，而是找到一個同時滿足所有目標的最優解。往往在大多數情況下，這個全局的最優解并不存在，一般只有一個有效解或非劣解的集合。

多目標最短路問題的處理方法一般可分為交互法、產生法和權重法[4]。交互法可以通過一個用戶界面得到完整的有效路徑集合，幫助決策者根據自身偏好找出最終解[5-6]。產生法是大量列舉有效解，然后根據實際情況和決策者偏好選擇滿意解[7-10]。權重法是根據不同目標函數的重要程度，賦予其一定的權值來求解多目標最短路問題，常用方法是線性加權法和幾何加權法[11-12]。相比而言，對不同的目標進行加權將多目標問題轉化為單目標問題求解，是一種較好的思路。但是，如何確定權重來體現目標的重要性是權重法的一個難點。

因此，筆者在常規線性加權法和幾何加權法的基礎上，提出路段賦值法來求解多目標最短路問題。路段賦值法綜合考慮每條路線的路段數和距離對路線選擇的影響，計算各目標下相應路段的賦值，并依據不同權重進行加權疊加，最終形成賦值網絡，在該路段賦值網絡中求得的最短路徑即為該多目標最短路問題的優選路徑。同時，以江西省萍鄉市運輸網絡為例，對常規線性加權法、幾何加權法與路段賦值法進行了對比分析。

1 問題描述

多目標最短路問題可以描述為：對于網絡G=(N，E)，E為節點間的有向邊的集合，N為節點集，fq(i,j)≥0(q=1,2,…,Q)為節點i到節點j的第q個目標值，求解起點O到終點D之間的最短路。

定義變量δij如下：

則多目標最短路模型可表述為式(1)：

(1)

?

該模型滿足式(2)所述約束條件：

(2)

δij∈{0,1},?(i,j)∈E

2 算法分析

2.1 多目標優化相關定義

多目標優化問題的最終目的是使多個矛盾的子目標盡可能同時極小化，而多目標最短路問題作為多目標優化的具體案例，可描述為式(3)[13]：

X?En,m>2

(3)

與單目標優化問題的解不同，多目標優化一般不存在唯一的全局最優解，而是存在多個最優解的集合。因此，關于多目標最短路的解有如下定義。

2.2 路段賦值法

多目標最短路的線性加權是將多目標函數的各目標按相應的準則加權后以某種方式進行求和，做出評價函數g(f(x))，再對評價函數進行單目標極小化，表達式Pg如式(4)：

(4)

權系數λ的確定，不僅要考慮目標的重要程度，也要考慮目標單位量綱的不同。為了消除單位不同產生的不可公度性，應對不同目標進行標準化。記單一目標下最短路線上的所有路段賦值為1。對于非最短路線上的路段，可賦值為路線距離與最短路距離之比并加以路段個數的修正值，路線距離的比值體現路線距離的重要程度，比值越小越重要；同時為消除路線上路段個數的影響，用最短路線路段個數與比較路線路段個數的比值加以修正，以此保證路段賦值與原路線路段有良好的對應關系。

設最短路線Lmin的路段數為Smin，距離為Dmin，則最短路線上的所有路段賦值都為1，對起訖點之間路線Li，路段數為Si，距離為Di，則該路線上所有路段賦值為ai，表達式見式(5)：

(5)

利用路段賦值后，Pg表達式轉換為式(6)中Pg1所述形式：

(6)

如果某路段多次賦值，則選取最小的賦值。在實際應用中，如果網絡很大，對每個路段都進行賦值需要的工作量很大，考慮到最優路徑一般都是在單目標下的K-最短路中取得[14]，因此先求不同目標下的K-最短路，然后對求得的所有路段進行賦值。

2.3 主要結果

作為農業綠色發展基礎的土壤，目前面臨著嚴重的“變質”問題，土壤侵蝕、土壤養分不平衡、土壤中碳和生物多樣性喪失、土壤酸化、土壤鹽漬化、土壤板結、土壤污染等多種威脅制約著土壤質量的發揮和土壤安全的保障。除自然因素外，土壤污染是導致多重土壤問題的主要原因。汪洪表示，與大氣污染和水體污染不同，土壤污染不易被人體直接感受到，需要通過儀器設備的檢測才可以感知，具有隱蔽性、滯后性、累積性、成因復雜等特點，也因此易于被公眾所忽視。

(7)

(8)

3 算法步驟

在上述分析的基礎上，提出基于路段賦值的多目標最短路求解算法，算法的具體步驟如下。

步驟1：運用Dijkstra算法分別求解各目標的最短路徑Lmin和最短路距離Dmin；

步驟3：運用K-最短路算法分別求解各目標對應的K-最短路徑Li和距離Di；

步驟5：按各目標權重對多目標進行加權疊加，求出最短路徑；

步驟6：令K=K+1，轉入步驟(3)，若兩次所求得的路徑相同，則該路徑即為多目標最短路問題的滿意解，算法結束；否則，繼續令K=K+1值，直到前后兩次所求得的路徑相同為止。

算法流程如圖1。

圖1 算法流程Fig. 1 Flowchart of algorithm

4 案例分析

江西省萍鄉市運輸網絡如圖2，運輸網絡中每個路段包含3個度量值，分別為運輸風險、運輸成本和路段擁堵評分。其中，運輸風險值越大，表明此路段的運輸風險越高；運輸成本值越大，表明此路段的運輸成本越高；路段擁堵評分用于描述不同路段的擁堵程度，其值介于0～100之間，路段擁堵評分越大表示路段擁堵越嚴重，具體路段屬性詳見表1。運輸線路的選取屬于多目標最短路問題，其中目標1為運輸風險最小，目標2為運輸成本最小，目標3為路段擁堵評分最小。求解起點20到終點13之間3個目標下的最短路徑。

圖2 運輸網絡Fig. 2 Transport network

路段號風險成本擁堵評分路段號風險成本擁堵評分1→278179407→111454371→13162133408→97125701→163454448→193124412→326488→20485792282→12259329→143103572→1519468269→20204862443→4430101210→2055128783→19916282111→1748238533→21112591111→19267134274→5782252311→211 32121464→148082503512→13262159354→15370951012→171 256226205→1462417212→2113227115→1821286913→1754752296→7188108714→19642209276→10787905115→1665162246→177252615→1855313747→822595916→18157316657→101 3164046

只考慮單個目標，求解不同目標下的最短路線和最短路距離，計算結果見表2及圖3，從表2及圖3中可以看出，在3個不同的目標下，所得結果各不相同，且相差較大。

表2 單目標結果Table 2 Single target result

圖3 單目標下各目標的最短路Fig. 3 The shortest path of each target under single objective

將3個目標按照不同的權重λq進行線性加權，求得不同權重下的最優路徑見表3和圖4，可以看出對于不同的權重系數，最終的最優路徑并不相同，但總體上傾向于目標1的最短路。

表3 線性加權法計算結果表Table 3 Calculation results of linear weighting method

圖4 線性加權法最短路Fig. 4 The shortest path of linear weighting method

將3個目標按照不同的權重λq進行幾何加權，求得不同權重下的最優路徑見表4和圖5。可以看出對于不同的權重系數，最終的最優路徑總體上傾向于目標3的最短路。

表4 幾何加權法計算結果Table 4 Calculation results of geometric weighting method

圖5 幾何加權法最短路Fig. 5 The shortest path of geometric weighting method

在相同的權重下以路段賦值法進行計算，求得不同權重下的最優路徑見圖6和表5，可以看出由于目標3函數的度量值較小，因此在線性加權中作用被低估，而采用路段賦值法則將目標函數標準化，更能體現目標之間的關系，有多條最優線路傾向于目標3的最優路線。

圖6 賦值法最短路Fig. 6 Shortest path of assignment method

λq路徑目標1目標2目標31∶1∶120→10→6→17→131 8921 966246∶3∶120→9→14→5→18→16→1→135681 8373916∶1∶320→10→6→17→131 8921 966243∶6∶120→10→7→11→21→12→2→1→133 5761 3571803∶1∶620→10→6→17→131 8921 966241∶3∶620→10→7→6→17→132 6091 573361∶6∶320→10→7→6→17→132 6091 573364∶4∶220→10→6→17→131 8921 966244∶2∶420→10→6→17→131 8921 966242∶4∶420→10→7→6→17→132 6091 57336

5 結 論

1)提出了求解多目標最短路問題的路段賦值法，并證明了該方法的可行性。路段賦值法綜合考慮了路線的距離及路段數對路線選擇的影響，對最短路和非最短路的不同賦值符合出行選擇規律。路段賦值法能有效地消除各目標所對應度量值的差異造成的影響。

2)為減少計算工作量，結合K-最短路算法和路段賦值的過程，給出了路段賦值法求解多目標最短路的計算步驟。

3)通過實例研究比較了各單目標、不同權重下常規線性加權與幾何加權算法、路段賦值法計算所得的不同結果。結果表明，常規線性加權法中對于度量值較小的目標在線性加權中作用被低估；而在幾何加權法中，度量值較小的目標所造成影響被過度放大；筆者所提出的路段賦值法則將目標函數標準化，更能體現多目標之間的關系，對現有研究方法進行了改進與優化。