康太平 張曉剛 王宗峰 何尚錄

(蘭州交通大學數(shù)理與軟件工程學院，甘肅 蘭州 730070)

基于k短路徑算法的多目標最短路徑算法

康太平 張曉剛 王宗峰 何尚錄

(蘭州交通大學數(shù)理與軟件工程學院，甘肅 蘭州 730070)

為滿意地解決多目標最短路徑問題，提出基于循環(huán)搜索第k短路徑，構(gòu)造新集合做交集的多項式算法。該算法是在每一輪的k短路搜索完以后，通過交集產(chǎn)生多目標最短路徑或備選路徑。當有多條備選路徑時再用Vague集投影和距離的決策方法，根據(jù)評價值的大小對候選方案進行排序，從而選取最佳方案。

多目標;第k短路徑;Vague集

0 引言

經(jīng)典的最短路問題只涉及單目標優(yōu)化[1]，即從起點到終點路程最短或費用最少，但實際問題中，如在鐵路旅客運輸中，人們總是希望乘坐快速、舒適、便宜的列車去旅行，列車的運行時間、速度、列車級別、票價等構(gòu)成了多目標路徑問題。求解過程中有多個目標需要優(yōu)化，這就拓展出多目標最短路徑問題。由于多目標問題目標間往往存在的不相容性或目標的不可加性，造成了多目標問題的難解性。要使多個目標在一個方案中均達到最優(yōu)，是很難得到這樣的解的，實際上，也很少存在這樣的最優(yōu)解。多目標最短路徑問題一般不存在單一的最優(yōu)解，而只有滿意解也稱Pareto解[2-3]。目前，應用廣泛的有效用函數(shù)法、遺傳算法、蟻群算法等。通過改進文獻[4]中提出的方法，提出了基于k短路算法[5]的多目標最短路徑算法，通過逐次找目標的第k短路徑，構(gòu)造新的路徑集作交集而得出多目標最短路徑。

1 多目標最短路徑算法

多目標路徑選擇問題一般可描述為:對于G=(N，E)，節(jié)點集為N，節(jié)點間的有向邊的集合為 E，|N|=n，|E|=m。令 Aq(q=1，2，…，Q)表示第 q 個目標值，Aq(i，j)(q=1，2，…，Q)為從節(jié)點i到節(jié)點j的第q個目標值，求從起點O到終點D之間的最短路徑。

定義2 第 k短路徑——若 p1，p2，…，pk為頂點v1至頂點v的k條路徑，W(p1)≤W(p2)≤…≤W(pk)，現(xiàn)p為頂點v1至頂點v的任一條路徑，p?{p1，…，pk}，且 W(p)≥W(pk)，則稱 pk為頂點v1至頂點v的第k短路徑。

2 多目標最短路徑算法的具體步驟

步驟1 利用Dijstra搜索最短路徑算法獲得網(wǎng)絡 G=(N，E)中目標 q(q=1，2，…，Q)的最短路徑集(q=1，2，…，Q)。

3 算例

圖1為從起點S到終點T之間的運輸網(wǎng)絡圖，各條有向邊上的目標值見表1。3個成本類目標:目標1為距離，目標2為費用，目標3為事故率，3個目標的權(quán)重相等。求從起點S到終點T之間考慮多個目標的最短路徑。

圖1 S到T的運輸網(wǎng)絡

表1 各條有向邊的目標值

③若備選路徑不止1條時，根據(jù)文獻[6]，選用基于Vague集投影和距離的決策方法。發(fā)現(xiàn)當所有目標的第5短路徑全部搜索完，構(gòu)造新路徑集:

表2 與目標對應的k最短路徑及相應的目標取值

①分別計算各個候選方案的評價值，其中D(Ai，A*)為 Ai方案到理想方案的投影，J(Ai，A*)為Ai方案到理想方案的距離，Z(Ai，A*)為Ai方案的綜合評價值，評價值越大則對應的方案越優(yōu)。

②由 Z(A1，A*) ＞Z(A3，A*) ＞ Z(A2，A*)得方案的排序為A1＞A3＞A2，最優(yōu)方案為A1，方案的排序也符合k短路交集產(chǎn)生的結(jié)果。A1為第4短路徑搜索完產(chǎn)生的結(jié)果，算法結(jié)束。為了比較方案的優(yōu)劣和產(chǎn)生多條備選路徑時運用Vague集投影和距離的決策方法，搜索到第5短路徑結(jié)束時產(chǎn)生了方案A2和A3，運用Vague集投影和距離的決策方法比較得，方案A3比方案A2更優(yōu)。

4 結(jié)論

基于第k短路徑問題，給出了多目標最短路徑的算法。它是在每一輪的k短路搜索完以后通過交集產(chǎn)生的，當交集為空集時繼續(xù)搜索下一輪第k短路徑再作交集，當交集為一條路徑時它就是最先同時滿足各目標的最優(yōu)路徑。當交集產(chǎn)生多條備選路徑時通過Vague集投影和距離的決策方法比較產(chǎn)生出滿足各目標的最優(yōu)路徑，這樣每次都是在一輪的k短路搜索完以后才進行交集，也減少了作交集的次數(shù)同時提高了計算的效率。

[1]謝金星，刑文訓.網(wǎng)絡優(yōu)化[M].北京:清華大學出版社，2000:119-143.

[2]Martins E Q V，Santos J L E.The Labeling Algorithm for the Multiobjective Shortest Path Problem[R].CISUCTechnical Report TR99/005，Coimbra，Portugal:Universityof Coimbra，1999.

[3]Guerriero F，Musmanno R.Label Correcting Methods to Solve Multicriteria Shortest Path Problems[J].Journal of Optimization Theory and Applications，2001(3):589 -613.

[4]郝光，張殿業(yè)，馮勛省.多目標最短路徑模型及算法[J]，西南交通大學學報，2007(5):641-645.

[5]傅家良.運籌學方法與模型[M].上海:復旦大學出版社，2005:238-241.

[6]要瑞璞，沈惠璋.基于Vague集投影及距離的模糊多指標決策[J].數(shù)學的實踐與認識，2009(2):19-22.

Algorithm for Shortest Path of Multi-objectives Based on k Short Parth Algorithm

KANG Tai-ping ZHANG Xiao-gang WANG Zong-feng HE Shang-lu

(School of Mathematics，Physics and Software Engineering，Lanzhou Jiaotong University，Lanzhou 730070)

To obtain a multi-objective shortest path，which may meet the decision-maker's requirements，this paper presents the basis of syclic research k shortest path and constructs a polynomial algorithm to intersect the new set.After every round of the k shortest path searching，the algorithm preduces a multiobjective shortest path or alternative path by the intersection.When a number of alternative paths are available，the method of projection of Vague set and distance is used.The optional schemes are sequenced according to the evaluation size，thus the best optimal solution may be obtained.

multi-objective;k shortest path;Vague set

O122.6

A

1671-0436(2011)03/04-0025-03

2011-05-26

康太平(1986— )男，碩士研究生。

責任編輯:唐海燕