馮樹(shù)民，吳海月，王弟鑫

(哈爾濱工業(yè)大學(xué)　交通科學(xué)與工程學(xué)院，黑龍江　哈爾濱　150090)

?

基于理想點(diǎn)法的多目標(biāo)最短路求解算法研究

馮樹(shù)民，吳海月，王弟鑫

(哈爾濱工業(yè)大學(xué)交通科學(xué)與工程學(xué)院，黑龍江哈爾濱150090)

摘要：為了簡(jiǎn)化多目標(biāo)最短路算法并解決不同度量單位之間存在的換算問(wèn)題，利用理想點(diǎn)法的優(yōu)點(diǎn)，探索出一種多目標(biāo)最短路問(wèn)題的簡(jiǎn)便算法。該算法首先確定理想點(diǎn)，計(jì)算各目標(biāo)的k-最短路路徑，這些路徑組成一個(gè)存在可能解的集合, 然后對(duì)所有的最短路目標(biāo)值進(jìn)行歸一化處理，并確定所有路徑歸一化之后的目標(biāo)值與理想點(diǎn)之間的加權(quán)歐幾里得距離，從路徑集合中尋找與理想點(diǎn)距離最近的路徑，該路徑即為多目標(biāo)最短路問(wèn)題的滿(mǎn)意解。最后，給出了算法分析和算法流程，并通過(guò)一個(gè)虛擬運(yùn)輸網(wǎng)絡(luò)對(duì)算法進(jìn)行了驗(yàn)證。結(jié)果表明：這種算法能夠解決多目標(biāo)最短路問(wèn)題中不同目標(biāo)度量單位之間換算或相互矛盾的問(wèn)題，并能夠把復(fù)雜的非線性函數(shù)轉(zhuǎn)換為簡(jiǎn)單的線性函數(shù)，是一種簡(jiǎn)單、有效的算法。

關(guān)鍵詞：交通工程；多目標(biāo)最短路; 理想點(diǎn)法; k-最短路; 加權(quán)歐幾里得距離

0引言

現(xiàn)實(shí)生活中許多問(wèn)題都屬于多目標(biāo)最優(yōu)化問(wèn)題，如工程設(shè)計(jì)、貨物運(yùn)輸、經(jīng)濟(jì)規(guī)劃、金融決策、資源分配等。由于各個(gè)目標(biāo)之間通常存在一些沖突，不可能同時(shí)達(dá)到最優(yōu)，因此多目標(biāo)優(yōu)化問(wèn)題一般不存在最優(yōu)解集，而是一個(gè)滿(mǎn)意解集，也稱(chēng)為Pareto解集[1-2]。多目標(biāo)最短路問(wèn)題屬于特殊的多目標(biāo)最優(yōu)化問(wèn)題，如交通網(wǎng)絡(luò)上的貨物運(yùn)輸問(wèn)題，它需要同時(shí)考慮成本、風(fēng)險(xiǎn)、時(shí)間等因素并且盡可能使它們最小。目前多目標(biāo)最短路求解方法主要包括3類(lèi)：(1)效用函數(shù)法，利用決策者的先驗(yàn)信息確定效用函數(shù)，比較常用的方法是線性加權(quán)法[3]；(2)交互法，利用決策者的先驗(yàn)信息與分析者進(jìn)行對(duì)話，逐步求出最終解[4]；(3)產(chǎn)生法，直接求解Pareto解集，然后決策者根據(jù)需要找出滿(mǎn)意解，主要包括動(dòng)態(tài)規(guī)劃法、Pareto標(biāo)記法和Pareto等級(jí)法等[5-7]。對(duì)多目標(biāo)的最短路算法，通常的處理方法是對(duì)不同的目標(biāo)進(jìn)行線性加權(quán)或?qū)⒛承┠繕?biāo)轉(zhuǎn)化為約束條件,但對(duì)于線性加權(quán)法而言, 其權(quán)重的確定卻很困難。而對(duì)于有約束的最短路問(wèn)題，已經(jīng)被證明是NP-hard問(wèn)題[8]。

理想點(diǎn)法[9]的思路是利用決策者的先驗(yàn)信息構(gòu)造滿(mǎn)足所有目標(biāo)的理想點(diǎn)，然后在約束條件內(nèi)尋找與該理想點(diǎn)最接近的可行解，該方法在多目標(biāo)決策及多目標(biāo)優(yōu)化中已有廣泛應(yīng)用。郭惠昕等[10]將理想點(diǎn)法用于多目標(biāo)模糊優(yōu)化設(shè)計(jì)，以可行解與正理想點(diǎn)和負(fù)理想點(diǎn)的距離構(gòu)造模糊判決，提出了基于理想點(diǎn)的求解算法。武新宇等[11]應(yīng)用理想點(diǎn)法對(duì)梯級(jí)水電站多目標(biāo)優(yōu)化模型的非劣解集進(jìn)行了最優(yōu)解選擇。魏航等[12]在求解雙目標(biāo)最短路問(wèn)題中定義了雙目標(biāo)最短路的理想點(diǎn)，為多目標(biāo)最短路問(wèn)題理想點(diǎn)的構(gòu)造提供了參考。

本文通過(guò)構(gòu)造多目標(biāo)最短路問(wèn)題的理想點(diǎn)，結(jié)合k-最短路，提出了基于理想點(diǎn)法的多目標(biāo)最短路求解算法，這種算法的優(yōu)勢(shì)包括：解決具有不同度量單位和相互沖突的多目標(biāo)決策問(wèn)題；采用軟約束，消除一般多目標(biāo)函數(shù)中存在的“硬約束”(即必須滿(mǎn)足的約束條件，這樣的硬約束實(shí)際上有時(shí)候滿(mǎn)足不了，因此就產(chǎn)生矛盾方程組，使得問(wèn)題無(wú)解)；理想點(diǎn)法的目標(biāo)函數(shù)是求偏差量的最小，而這種偏差是線性距離，計(jì)算更加容易。

2算法分析

2.1基本模型

(1)

(2)

(3)

式中wq為第q個(gè)目標(biāo)的權(quán)重。

因此，利用上述方法，多目標(biāo)最短路問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換為單目標(biāo)函數(shù)mindi。

2.2算法說(shuō)明

同時(shí)，多目標(biāo)問(wèn)題的最優(yōu)路徑肯定是在某個(gè)目標(biāo)的k-最短路中取得。

因此可以首先求解各目標(biāo)對(duì)應(yīng)的k-最短路路徑來(lái)確定起點(diǎn)到終點(diǎn)間各目標(biāo)的最短路徑集合，即有效路徑集合Ω，然后在集合Ω中尋找與理想點(diǎn)距離最小的路徑，該路徑即為多目標(biāo)最短路問(wèn)題的滿(mǎn)意解。

3算法流程

在算法分析的基礎(chǔ)上，提出基于理想點(diǎn)法的多目標(biāo)最短路求解算法，具體步驟如下：

(3)運(yùn)用k-最短路算法分別求解各目標(biāo)對(duì)應(yīng)的k-最短路路徑。

(6)計(jì)算歸一化處理后的目標(biāo)值與理想點(diǎn)間的加權(quán)歐幾里得距離di，確定最小距離所對(duì)應(yīng)的路徑。

(7) 令k=k+1，轉(zhuǎn)入步驟(3)，若兩次所求得的路徑相同，則該路徑即為多目標(biāo)最短路問(wèn)題的滿(mǎn)意解，算法結(jié)束；否則，繼續(xù)令k=k+1值，直到前后兩次所求得的路徑相同為止。

算法流程圖如圖1所示。

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

4案例分析

圖2　運(yùn)輸網(wǎng)絡(luò)Fig.2　Transport network

如圖2所示的虛擬運(yùn)輸網(wǎng)絡(luò)，運(yùn)輸起點(diǎn)為O，終點(diǎn)為D，運(yùn)輸路徑選取時(shí)考慮成本、風(fēng)險(xiǎn)及路段擁堵程度，其中路段擁堵程度采用路段擁堵評(píng)分來(lái)度量(路段擁堵評(píng)分介于0和10之間，路段擁堵評(píng)分越大則路段擁堵越嚴(yán)重)。因此，起點(diǎn)O與終點(diǎn)D間運(yùn)輸路徑的選取是一個(gè)三目標(biāo)最短路問(wèn)題，其中目標(biāo)1成本最小，對(duì)應(yīng)權(quán)重為0.5；目標(biāo)2風(fēng)險(xiǎn)最小，對(duì)應(yīng)權(quán)重為0.3；目標(biāo)3路段擁堵程度最小，對(duì)應(yīng)權(quán)重為0.2。

(1) 求解單目標(biāo)下各目標(biāo)的最短路路徑

在單目標(biāo)下，運(yùn)用Dijkstra算法分別求得各目標(biāo)的最短路路徑及對(duì)應(yīng)的目標(biāo)值，如圖3所示。

圖3　各目標(biāo)最短路路徑Fig.3　Objective shortest paths

根據(jù)圖3可知，這3個(gè)目標(biāo)的最短路路徑均不相同，該多目標(biāo)最短路問(wèn)題不存在最優(yōu)解，只存在滿(mǎn)意解。根據(jù)各目標(biāo)最短路路徑的目標(biāo)值可知理想點(diǎn)為(70,1 300,12)。

(2)計(jì)算k-最短路路徑

令k=2，在單目標(biāo)下分別計(jì)算各目標(biāo)的k-最短路路徑，計(jì)算結(jié)果如圖4所示。

圖4　各目標(biāo)的k-最短路路徑Fig.4　Objective k-shortest paths

(3) 確定最短路徑集合Ω

根據(jù)圖4中的路徑確定最短路徑集合Ω，如圖5所示。

圖5　路徑集合Ω中的所有路徑Fig.5　All the paths in path set Ω

分別計(jì)算集合Ω中每條路徑上3個(gè)目標(biāo)的目標(biāo)值，如表1所示。

表1　各條路徑上目標(biāo)對(duì)應(yīng)的目標(biāo)值

根據(jù)表1可知，3個(gè)目標(biāo)值的取值區(qū)間分別為X1=[70,103]，X2=[1 300,1 600]，X3=[12,16.7]。

(4)歸一化處理

根據(jù)式(1)，對(duì)理想點(diǎn)與目標(biāo)值進(jìn)行歸一化處理。以路徑OAED為例，處理后的值為：

(4)

(5)

(6)

(5) 計(jì)算目標(biāo)值與理想點(diǎn)間的距離

根據(jù)式(3)，計(jì)算目標(biāo)值與理想點(diǎn)間的加權(quán)歐幾里得距離。以路徑OAED為例，計(jì)算結(jié)果為：

(7)

同理，計(jì)算其余路徑上的目標(biāo)值與理想點(diǎn)間的加權(quán)歐幾里得距離，計(jì)算結(jié)果如表2所示。根據(jù)表2,最小距離為0.282，對(duì)應(yīng)的路徑為OBFED。

表2　各路徑上目標(biāo)值與理想點(diǎn)間的距離計(jì)算結(jié)果

(6) 檢驗(yàn)

令k=3，按上述步驟再次計(jì)算所求得的路徑為OBFED，前后兩次所求得的路徑相同。因此，路徑OBFED為該多目標(biāo)最短路問(wèn)題的滿(mǎn)意解。

圖6　多目標(biāo)最短路滿(mǎn)意解Fig.6　Satisfactory solution of multi-objective shortest path

5結(jié)論

通過(guò)運(yùn)用理想點(diǎn)法對(duì)多目標(biāo)最短路求解進(jìn)行研究，得到以下結(jié)論：

(1)多目標(biāo)最短路問(wèn)題的理想點(diǎn)只需通過(guò)在單目標(biāo)下求解各目標(biāo)的最短路路徑便可構(gòu)造，構(gòu)造方法簡(jiǎn)便、直觀，有利于理想點(diǎn)法的應(yīng)用。

(2) 結(jié)合k-最短路算法，提出了基于理想點(diǎn)法的多目標(biāo)最短路求解算法，并給出了算法流程。該算法的核心是在確定理想點(diǎn)的基礎(chǔ)上，通過(guò)計(jì)算k-最短路路徑確定起點(diǎn)和終點(diǎn)間的路徑集合，然后計(jì)算路徑集合的每條路徑與理想點(diǎn)間的距離，最小距離所對(duì)應(yīng)的路徑即為多目標(biāo)最短路問(wèn)題的滿(mǎn)意解。

(3) 該算法通過(guò)判斷從各目標(biāo)的最短路路徑是否相同來(lái)確定多目標(biāo)最短路問(wèn)題是否存在最優(yōu)解，在此基礎(chǔ)上，逐次增加k值并計(jì)算k-最短路路徑，從這些路徑中尋找多目標(biāo)最短路問(wèn)題的滿(mǎn)意解。該算法計(jì)算過(guò)程循序漸進(jìn)，其檢驗(yàn)過(guò)程防止了潛在的滿(mǎn)意解被遺漏。

(4) 該算法簡(jiǎn)便、易于理解，通過(guò)案例分析，驗(yàn)證了算法流程。

參考文獻(xiàn)：

References:

[1]GRANATA J, GUERRIERO F. The Interactive Analysis of the Multicriteria Shortest Path Problem by the Reference Point Method[J]. European Journal of Operational Research, 2003, 151(1):103-118.

[2]GUERRIERO F, MUSMANNO R. Label Correcting Methods to Solve Multicriteria Shortest Path Problems[J]. Journal of Optimization Theory and Applications, 2001, 111(3):589-613.

[3]BRUMBAUGH-SMITH J, SHIER D. An Empirical Investigation of Some Bicriterion Shortest Path Algorithms[J]. European Journal of Operational Research, 1989, 43(2):216-224.

[4]GRANATA J, GUERRIERO F. The Interactive Analysis of the Multi-criteria Shortest Path Problem by the Reference Point Method[J]. European Journal of Operational Research, 2003, 151(1): 103-118.

[5]SKRIVER A J V, ERSEN K A. A Label Correcting Approach for Solving Bicriterion Shortest Path Problems[J]. Computers and Operations Research, 2000, 27(6):507-524.

[6]IORI M, MARTELLO S, PRETOLANI D. An Aggregate Label Setting Policy for the Multi-objective Shortest Path Problem[J]. European Journal of Operational Research, 2010, 207(3): 1489-1496.

[7]MACHUCA E, MANDOW L, DE LA CRUZ J L P, et al. A Comparison of Heuristic Best-first Algorithms for Bicriterion Shortest Path Problems[J]. European Journal of Operational Research, 2012, 217(1)：44-53.

[8]郝光, 張殿業(yè), 王東梅. 雙目標(biāo)最短路有效解的快速算法[J]. 公路交通科技, 2007, 24(11):96-99,104.

HAO Guang, ZHANG Dian-ye, WANG Dong-mei. A Fast Algorithm for Biobjective Shortest Path[J]. Journal of Highway and Transportation Research and Development, 2007, 24(11):96-99,104.

[9]范祥莉. 梯級(jí)水電站群中長(zhǎng)期多目標(biāo)優(yōu)化調(diào)度方法[D]. 大連: 大連理工大學(xué), 2010.

FAN Xiang-li. Multi-objective Optimization Scheduling Method of Mid-and-long Term for Cascade Hydropower Station Group [D]. Dalian: Dalian University of Technology, 2010.

[10]郭惠昕, 張龍庭, 羅佑新,等. 多目標(biāo)模糊優(yōu)化設(shè)計(jì)的理想點(diǎn)法[J]. 機(jī)械設(shè)計(jì), 2001,18(8):16-18.

GUO Hui-xin, ZHANG Long-ting, LUO You-xin, et al. The Ideal Point Method of Multi-target Fuzzy Optimal Design[J]. Journal of Machine Design, 2001,18(8):16-18.

[11]武新宇, 范祥莉, 程春田,等. 基于灰色關(guān)聯(lián)度與理想點(diǎn)法的梯級(jí)水電站多目標(biāo)優(yōu)化調(diào)度方法[J]. 水力學(xué)報(bào), 2012, 43(4):422-428.

WU Xin-yu, FAN Xiang-li, CHENG Chun-tian, et al. Multi-objective Optimal Operation Based on Grey Correlation and Ideal Point Method for Cascaded Hydropower Systems[J]. Journal of Hydraulic Engineering, 2012, 43(4):422-428.

[12]魏航, 蒲云, 李軍. 一種求解雙目標(biāo)最短路的方法[J]. 系統(tǒng)工程, 2005, 23(7):113-117.

WEI Hang, PU Yun, LI Jun. An Approach to Biobjective Shortest Path [J]. Systems Engineering, 2005, 23(7):113-117.

Study of Multi-objective Shortest Path Algorithm Based on Ideal Point Solution

FENG Shu-min, WU Hai-yue, WANG Di-xin

(School of Transportation Science and Engineering, Harbin Institute of Technology, Harbin Heilongjiang 150090, China)

Abstract：In order to simplify the multi-objective shortest path algorithm and solve the conversion problem between different measurement units, we explored a simple algorithm of multi-objective shortest path problem taking advantage of ideal point method. The algorithm determines the ideal points and calculates the corresponding objective k-shortest paths, these paths constitute a set of possible solutions. Then all the target values of the shortest paths are normalized, and the weighted Euclidean distance between each normalized target value and ideal point can be calculated. We can find out the nearest path to the ideal point from the set of paths. That is the satisfactory solution of multi-objective shortest path problem. Finally, we gave the algorithm steps and verified the algorithm through a virtual transport network. The result shows that this algorithm can solve the conversion and mutual contradiction problems among measuring units of different targets on the multi-objective shortest path problem, the algorithm can be able to convert complex nonlinear function to a simple linear function, it is a simple and effective algorithm.

Key words：traffic engineering; multi-objective shortest path; ideal point method; k-shortest path; weighted Euclidean distance

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1002-0268(2016)03-0097-05

中圖分類(lèi)號(hào)：U495

doi:10.3969/j.issn.1002-0268.2016.03.016

作者簡(jiǎn)介：馮樹(shù)民(1973-)，男，黑龍江哈爾濱人，教授. (zlyfsm2000@sina.com)

基金項(xiàng)目：黑龍江省交通運(yùn)輸廳科技項(xiàng)目(MJ20110034)

收稿日期：2015-03-19