基于k最短路徑的現(xiàn)代有軌電車線網(wǎng)優(yōu)化

胡軍紅 過秀成 陶 濤 胡婷婷

(1東南大學交通學院, 南京 210096)(2南京工業(yè)大學交通運輸工程學院, 南京 210009)

基于k最短路徑的現(xiàn)代有軌電車線網(wǎng)優(yōu)化

胡軍紅1,2過秀成1陶 濤1胡婷婷1

(1東南大學交通學院, 南京 210096)(2南京工業(yè)大學交通運輸工程學院, 南京 210009)

為科學合理地進行現(xiàn)代有軌電車線網(wǎng)的優(yōu)化與改進,基于現(xiàn)代有軌電車線網(wǎng)優(yōu)化的約束條件,引入k最短路徑算法進行線網(wǎng)優(yōu)化．首先運用道路空間資源要素和線路重復系數(shù)這2個約束條件實現(xiàn)對初始網(wǎng)絡圖中有效邊的篩選,形成備選線路集合,其次將非直線系數(shù)和節(jié)點綜合重要度這2個約束條件組成聯(lián)合熵權,將該聯(lián)合熵權作為現(xiàn)代有軌電車最優(yōu)路徑的判定參數(shù),從而構建滿足多約束條件下的現(xiàn)代有軌電車線網(wǎng)優(yōu)化方法．最后,以南京河西新城現(xiàn)代有軌電車線網(wǎng)優(yōu)化為例,驗證了該方法的有效性，表明k最短路徑算法是適用于現(xiàn)代有軌電車線網(wǎng)規(guī)劃的有效方法，該方法可為現(xiàn)代有軌電車線網(wǎng)規(guī)劃提供參考．

現(xiàn)代有軌電車;k最短路徑算法;聯(lián)合熵權;線網(wǎng)優(yōu)化

現(xiàn)代有軌電車線網(wǎng)規(guī)劃是在城市綜合交通體系規(guī)劃、有軌電車交通功能定位和需求分析的基礎上,構建初始線網(wǎng),經(jīng)優(yōu)化與改進,形成最終方案的過程．目前線網(wǎng)生成常用方法包括“面、線、點”要素分析法、最優(yōu)路徑搜索法和逐線規(guī)劃擴充法等．而k最短路徑算法通過提供k條非遞減的可供選擇的最短路徑備選方案集[1],在滿足多種約束條件的情況下,可以使用戶最大限度進行個性化選擇,符合現(xiàn)代有軌電車線網(wǎng)優(yōu)化的決策過程．

k最短路徑是單一最短路徑算法的改進與推廣,在公共交通系統(tǒng)方面大多用于線網(wǎng)交通分配或公共交通路徑選擇與換乘研究．段宗濤等[2]提出了k最短路徑集合算法,求交通網(wǎng)絡中k個長度等級的最短路徑集合,并將大規(guī)模交通網(wǎng)絡下的交通流量分配至不同等級的最短路徑,解決了交通流合理分配問題．徐濤等[3]提出約束Yen算法,運用于國際航線聯(lián)程路徑搜索問題．王莉等[4]認為針對公共交通系統(tǒng)用最短路徑算法得到的往往不是最佳路徑,通過引入最小換乘矩陣對待檢驗的標號進行篩選,可得到一條綜合考慮換乘和路徑長度的最佳路徑．

本文擬在分析現(xiàn)代有軌電車線網(wǎng)優(yōu)化約束條件的基礎上,利用偏離路徑算法構建k條最短路徑備選方案集,采用聯(lián)合熵權進行最優(yōu)路徑選擇,實現(xiàn)初始線網(wǎng)優(yōu)化的目標．然后以南京河西新城現(xiàn)代有軌電車線網(wǎng)優(yōu)化為算例,進一步說明k最短路徑算法在線網(wǎng)優(yōu)化方面的應用．

1 現(xiàn)代有軌電車線網(wǎng)優(yōu)化約束

現(xiàn)代有軌電車線網(wǎng)規(guī)劃需要綜合考慮不同交通方式之間的影響、區(qū)域重要集散點的分布、道路空間資源及實施條件等各方面制約關系．因此,線網(wǎng)規(guī)劃是滿足一定約束條件下的優(yōu)化決策過程．在對初始線網(wǎng)進行優(yōu)化改進時應考慮的主要約束條件包括:道路空間資源要素、線路重復系數(shù)、節(jié)點綜合重要度、非直線系數(shù)等．

1) 道路空間資源要素是現(xiàn)代有軌電車線路敷設的基礎條件,通常以道路用地邊界線之間的道路紅線寬度w作為關鍵要素,包括機動車、非機動車和行人交通所需的道路寬度．現(xiàn)代有軌電車系統(tǒng)一般選擇城市主干路、次干路作為敷設線路的基礎,要求道路紅線寬度不少于30 m．

2) 線路重復系數(shù)β是指公共交通線路總長度與區(qū)域內(nèi)線路網(wǎng)長度之比．公交線網(wǎng)重復系數(shù)以1.25～2.50為宜[5]．為協(xié)調(diào)不同公共交通方式在線網(wǎng)層面的關系,提高城市公共交通系統(tǒng)整體運行效益,一般要求現(xiàn)代有軌電車線路不宜與城市快速軌道交通或快速公交(BRT)等城市骨干公交線路重復．在k最短路徑算法中,線路重復系數(shù)β一般作為控制k條最短路徑之間線路重復程度的約束條件．

3) 節(jié)點綜合重要度主要依據(jù)線路中節(jié)點所在區(qū)域的區(qū)位條件、客流發(fā)生吸引的能力和集散點之間的相對交通可達性進行判斷,一般采用熵值法或德菲爾法確定.現(xiàn)代有軌電車線網(wǎng)應盡可能覆蓋城市主要客流集散點,為區(qū)域內(nèi)主要節(jié)點提供快速高效的客流集散．規(guī)劃區(qū)域內(nèi)的集散點主要包括重要的集中居住區(qū)、商業(yè)中心、商務中心(CBD)、行政中心及各類學校、醫(yī)院和文體活動場所．

4) 非直線系數(shù)ξ是表征線網(wǎng)中線路順直性的指標．非直線系數(shù)定義為線路起訖間的實際線路距離與兩點間空間直線距離的比值,公共交通線路非直線系數(shù)不應大于1.4,整個線網(wǎng)的平均非直線系數(shù)應以1.15～1.20為宜[6]．現(xiàn)代有軌電車線路設置盡可能保持線型順直,減少線網(wǎng)的換乘次數(shù)．

現(xiàn)代有軌電車線網(wǎng)優(yōu)化是多約束條件下的決策過程,一般不存在全局最優(yōu)解．而k最短路徑算法能夠在滿足多約束條件的情況下,構建多重備選方案集來滿足不同需求[7]．

2 基于k最短路徑的線網(wǎng)優(yōu)化算法

2.1 問題描述

k最短路徑問題是在網(wǎng)絡圖中以一種非遞減的順序?qū)ふ移瘘c和終點間的多條備選優(yōu)化路徑,形成最短路徑組,以最大程度滿足用戶對不同路徑的選擇需求．它除了要確定最短路徑之外,還要確定第2短路徑、第3短路徑,直至找到第k條最短路徑為止[8]．

k最短路徑問題是確定備選路徑集合Pk={p1,p2,…,pk}∈Pst,并滿足以下2個條件[9]:

① 備選路徑集k條最短路徑按非遞減排序,即c(pr)

②k條最短路徑任一條路徑的權值均不大于s與t之間非備選路徑的權值,即c(pk)

2.2 k最短路徑算法

k最短路徑問題大致可分為限定無環(huán)問題和一般問題2種,現(xiàn)代有軌電車初始線網(wǎng)優(yōu)化問題為限定無環(huán)k最短路徑問題．計算過程是首先采用Dijkstra算法尋找第1條最短路徑,然后采用偏離路徑的概念計算第r+1(1≤r≤k-1)條最短路徑,在求第r+1條最短路徑時,將第r條路徑上除了終止節(jié)點之外的所有節(jié)點都視為潛在的偏離節(jié)點進行計算,以偏離邊的縮小長度最小作為尋找第k+1條最短路徑的選擇標準[10]．

該算法通過引入道路空間資源要素(如道路紅線寬度w)對初始圖G0=(V0,E0)中的邊進行篩選,形成新的圖G=(V,E);采用k最短路徑算法計算第1條最短路徑;引入線路重復系數(shù)β的概念,對偏離路徑算法進行改進,計算第2至k條最短路徑,形成備選路徑集．重復計算網(wǎng)絡圖中的k最短路徑,生成現(xiàn)代有軌電車線網(wǎng)備選方案集合．算法步驟如下:

1) 構建網(wǎng)絡圖．以城市規(guī)劃道路網(wǎng)中的主干線和次干線作為邊的集合V0,主要的線路節(jié)點及客流集散點作為節(jié)點的集合E0(重要的集中居住區(qū)、商業(yè)中心、商務中心(CBD)、行政中心及各類學校、醫(yī)院和文體活動場所、交通樞紐場站等)構建初始網(wǎng)絡圖[11]．

2) 網(wǎng)絡圖篩選．根據(jù)現(xiàn)代有軌電車線網(wǎng)優(yōu)化相關的約束條件,進行初始網(wǎng)絡圖篩選．

① 剔除不符合規(guī)劃條件的邊,如位于城市快速路上不宜敷設現(xiàn)代有軌電車線路的邊,或者是與既有或規(guī)劃的城市快速軌道交通線路重復達到一定限值的邊．

② 引入道路紅線寬度w不低于30 m這個約束條件,剔除不具備敷設現(xiàn)代有軌電車線路的邊．對初始圖G0=(V0,E0)中的邊進行篩選優(yōu)化后形成新的圖G=(V,E)．

3) 確定網(wǎng)絡起終點組合集．選定起終點組合集OD=(S,T),(S=s1,s2,…,sN;T=t1,t2,…,tN)．根據(jù)城市客流廊道和客流集散點空間分布確定的現(xiàn)代有軌電車初始線網(wǎng),選定各線路通道需要連接的起始節(jié)點和終止節(jié)點OD組合數(shù)量．從而將現(xiàn)代有軌電車線網(wǎng)規(guī)劃問題轉(zhuǎn)變?yōu)榇_定起終點集OD=(S,T)中的每一組起始節(jié)點和終止節(jié)點(s1,t1),(s2,t2),…,(sN,tN)的k最短路徑問題．

4) 求第1條最短路徑p1.

① 以起始節(jié)點S作為當前節(jié)點i,權值賦值為ci=s=0,將當前節(jié)點保存到節(jié)點集合E′．

② 以路段長度作為邊的權值,計算與當前節(jié)點i相鄰的所有節(jié)點之間的權值cij,(i=S;j=1,2,…,h),h為與當前節(jié)點相鄰的所有節(jié)點數(shù)量．

⑤ 重復執(zhí)行步驟②～④,直到i=t時,算法結(jié)束,輸出結(jié)果和權值cs．搜索到的最短路徑信息為從s到t之間的最短路徑節(jié)點集合E′,最短路徑權值為cs;將其作為p1放入備選路徑集合中．

5) 求最短路徑pr+1.

① 選取偏離節(jié)點．取pr(1≤r≤k-1)中除了終止節(jié)點之外的每個節(jié)點vi作為可能的偏離節(jié)點．

③ 路徑拼接．將從偏離節(jié)點vi至節(jié)點t之間最短路徑與當前路徑pr上從s至vi的路徑拼接在一起,構成pr+1的一條路徑候選路徑,存入備選路徑集合中．

④ 從候選路徑列表中選擇最短的一條路徑作為pr+1,放入備選路徑集合中．

⑤ 重復①～④,找到k條路徑后,終止計算,并輸出備選路徑集合p=(p1,p1,…,pk),作為起始節(jié)點和終止節(jié)點之間的現(xiàn)代有軌電車線路的備選路徑．

按照以上計算步驟,計算網(wǎng)絡圖中起終點集OD=(S,T)中的每一組起始節(jié)點和終止節(jié)點si,ti(i=2,…,N)的k條最短路徑,生成現(xiàn)代有軌電車線網(wǎng)初始備選方案．

3 現(xiàn)代有軌電車初始線網(wǎng)優(yōu)化

引入非直線系數(shù)ξ和節(jié)點綜合重要度E(p)的聯(lián)合熵權W(p)的概念作為選擇現(xiàn)代有軌電車線路最優(yōu)路徑的參數(shù).這樣選出的線路路徑不一定是最短路徑,但一定是聯(lián)合熵權最大的線路．逐一選擇網(wǎng)絡圖中每一對起終點組合OD=(S,T)的現(xiàn)代有軌電車線路最優(yōu)路徑,從而實現(xiàn)對現(xiàn)代有軌電車初始線網(wǎng)的優(yōu)化[12]．計算步驟如下:

① 計算p=(p1,p2,…,pr,…,pk)中最短路徑pr的非直線系數(shù)ξ(pr),且

(1)

式中,ξ(pr)為最短路徑pr的非直線系數(shù);d(s,t)為起終點(s,t)空間直線距離．

② 計算pk最短路徑的節(jié)點綜合重要度E(pr),且

(2)

式中,Ei為pr最短路徑節(jié)點i的重要度．可以通過調(diào)查節(jié)點Ei的區(qū)位條件(節(jié)點所在區(qū)域、所在地段、周邊主要用地性質(zhì))、客流發(fā)生與吸引能力(吸引范圍內(nèi)居住人口數(shù)、就業(yè)崗位數(shù)、商業(yè)零售數(shù)、客流分布方向的影響)、相對可達性(客流到達難易程度、周圍路網(wǎng)等級級配)等進行綜合確定．

③ 計算pr最短路徑聯(lián)合熵權W(pr),且

(3)

式中,W(pr)為pr最短路徑的聯(lián)合熵;α為權重系數(shù)．

④ 選擇最優(yōu)路徑．從s到t之間的現(xiàn)代有軌電車線路中,選取聯(lián)合熵權W(p)最大的最短路徑作為最優(yōu)路徑,即

W(p)=max{W(p1),W(p2),…,W(pk)}

(4)

按照以上計算步驟,對網(wǎng)絡圖中起終點集OD=(S,T)中的每一組起始節(jié)點和終止節(jié)點(si,ti)(i=2,3,…,N)的最優(yōu)路徑進行選擇,實現(xiàn)對現(xiàn)代有軌電車初始線網(wǎng)方案的優(yōu)化．

4 算例

以南京河西新城為例,基于k最短路徑算法構建現(xiàn)代有軌電車網(wǎng)絡圖,引入聯(lián)合熵權進行線網(wǎng)優(yōu)化,確定現(xiàn)代有軌電車線網(wǎng)布局方案．

4.1 南京河西新城現(xiàn)代有軌電車網(wǎng)絡圖

4.1.1 構建網(wǎng)絡圖并選定起始點組合

基于河西地區(qū)的集散點分布,以河西地區(qū)主干路和次干路為主,構建初始網(wǎng)絡圖G0=(V0,E0),如圖1所示．該初始網(wǎng)絡圖包含42個節(jié)點組成的V0集合和63條邊組成的E0集合．

圖1 南京河西新城現(xiàn)代有軌電車初始網(wǎng)絡(單位：km)

根據(jù)南京河西新城道路空間資源條件對初始網(wǎng)絡圖中的邊進行篩選,形成新的網(wǎng)絡圖G=(V,E),其中V為篩選后所有41個節(jié)點的集合,E為篩選后所有53條邊的集合,采用連接道路長度給各邊賦值,如圖1所示．選定各線路通道需要連接的起始節(jié)點和終止節(jié)點OD組合,即OD={(s1,t1),(s2,t2),…,(s6,t6)}．

4.1.2 現(xiàn)代有軌電車線網(wǎng)備選方案集

按照前述初始線網(wǎng)生成模型與方法,計算網(wǎng)絡圖中每一組起始節(jié)點和終止節(jié)點si,ti(i=1,2,…,N)的k最短路徑,生成現(xiàn)代有軌電車線網(wǎng)初始備選方案集．

以起終點s1,t1為例,設定k=3,β≤1.2．按前述尋求最短路徑的計算步驟搜索現(xiàn)代有軌電車k最短線路:

① 第1條最短路徑p1=(s1,3,6,10,15,t1),q1=(1.53,1.32,1.16,1.57,0.95),c(p1)=6.53 km．

② 第2條最短路徑p2=(s1,1,s2,7,12,17,t1),q2=(0.49,1.52,0.94,1.21,1.98.1.75),c(p2)=7.89 km．

③ 第3條最短路徑p3=(s1,2,s4,4,5,8,9,11,14,16,t1),q3=(0.41,1.41,1.41,0.91,0.63,0.71,0.82,0.99,0.94,0.96),c(p3)=9.19 km．找到給定的k=3條路徑后,終止計算,并輸出備選路徑集合p=(p1,p2,p3),作為起始節(jié)點和終止節(jié)點s1,t1的備選路徑．

④ 重復以上步驟,計算起始節(jié)點和終止節(jié)點si,ti(i=2,3,…,N)之間的備選路徑組,生成現(xiàn)代有軌電車初始線網(wǎng)備選方案集．

4.2 南京河西新城現(xiàn)代有軌電車線網(wǎng)優(yōu)化

從每一對起始節(jié)點和終止節(jié)點si,ti(i=2,3,…,N)之間的備選路徑組中選擇最優(yōu)路徑,實現(xiàn)對初始線網(wǎng)方案的優(yōu)化．具體步驟如下:

① 根據(jù)c(p1)=6.53 km,c(p2)=7.89 km,c(p3)=9.19 km,d(S1,T1)=6.05 km,按式(1)計算p=(p1,p1,p3)中最短路徑pr的非直線系數(shù)．

② 采用德菲爾法和式(2),計算最短路徑pr的節(jié)點綜合重要度E(pr),E(p1)=1.43,E(p2)=0.85,E(p3)=1.05．

③ 按照式(3),權重系數(shù)α取0.35,計算最短路徑pr的聯(lián)合熵權W(pr),W(p1)=1.25,W(p2)=0.82,W(p3)=0.91．

④ 選取聯(lián)合熵最大的最短路徑pr作為從s1到t1之間的現(xiàn)代有軌電車線路最優(yōu)路徑,即

W(p)=max{W(p1),W(p2),…,W(pk)}=

max{1.25,0.82,0.91}=W(p1)

最優(yōu)線路為p1=(s1,3,6,10,15,t1),線路長度c(p1)=6.53 km．

同理,選定其他現(xiàn)代有軌電車線路需要連接的起訖節(jié)點OD組合(s2,t2),(s3,t3),(s4,t4),(s5,t5),(s6,t6),進行k最短線路和最優(yōu)線路選擇．

原河西現(xiàn)代有軌電車規(guī)劃線網(wǎng)是在點、線、面要素分析法的基礎上生成,所推薦的線網(wǎng)由12條線路組成,線網(wǎng)規(guī)模約70.7 km．利用k最短路徑算法優(yōu)化后的河西現(xiàn)代有軌電車線網(wǎng)布局方案如圖2所示,線網(wǎng)總規(guī)模約56.5 km,形成“四縱、四橫、一聯(lián)”的布局結(jié)構,從線網(wǎng)布局規(guī)劃來看,線路走向與現(xiàn)狀的實際客流方向一致,線網(wǎng)結(jié)構與河西新城布局形態(tài)相協(xié)調(diào)．

圖2 河西新城現(xiàn)代有軌電車線網(wǎng)布局圖(單位:km)

5 結(jié)語

本文研究了現(xiàn)代有軌電車線網(wǎng)優(yōu)化方法,在構建網(wǎng)絡圖的基礎上,引入道路空間資源要素、線路重復系數(shù)的約束條件實現(xiàn)對初始網(wǎng)絡圖有效邊的篩選．運用改進的偏離路徑算法,生成k條最短路徑,從而構成備選線路集合,引入節(jié)點綜合重要度和非直線系數(shù)作為約束條件計算出聯(lián)合熵權,選取聯(lián)合熵權最大的線路作為最短線路,使線網(wǎng)優(yōu)化決策過程最大限度契合線網(wǎng)功能需求、發(fā)展定位和實施條件,確定最終線網(wǎng)布局方案．并以南京河西新城為例進行應用研究,優(yōu)化結(jié)果表明k最短路徑算法是適用于線網(wǎng)規(guī)劃的一種有效的優(yōu)化方法．

)

[1] 白軼多,胡鵬, 夏蘭芳, 等.關于k次短路徑問題的分析與求解[J].武漢大學學報(信息科學版), 2009, 34(4):492-494.

Bai Yiduo, Hu Peng, Xia Lanfang, et. Akth-shortest path algorithm based onk-1 shortest paths[J].GeomaticsandInformationScienceofWuhanUniversity, 2009,34(4):492-494. (in Chinese)

[2] 段宗濤, Wang Weixing, 康軍, 等. 面向城市交通網(wǎng)絡的k最短路徑集合算法[J]. 交通運輸系統(tǒng)工程與信息, 2014, 14(3): 194-200. DOI:10.3969/j.issn.1009-6744.2014.03.030.

Duan Zongtao, Wang Weixing, Kang Jun, et al. Ak-th shortest path set algorithm for urban traffic network[J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2014,14(3): 194-200. DOI:10.3969/j.issn.1009-6744.2014.03.030.(in Chinese)

[3] 徐濤, 丁曉璐, 李建伏. 國際航線網(wǎng)絡聯(lián)程路徑搜索的KMCSP問題研究[J]. 西南交通大學學報, 2014, 49(1): 153-159. DOI:10.3969/j.issn.0258-2724.2014.01.024.

Xu Tao, Ding Xiaolu, Li Jianfu.K-multiple constrained shortest paths problem for connecting path search in international flight path network[J].JournalofSouthwestJiaotongUniversity, 2014,49(1): 153-159. DOI:10.3969/j.issn.0258-2724.2014.01.024.(in Chinese)

[4] 王莉, 李文權. 公共交通系統(tǒng)最佳路徑算法[J]. 東南大學學報(自然科學版), 2004, 34(2): 264-267. DOI:10.3321/j.issn:1001-0505.2004.02.029.

Wang Li, Li Wenquan. Best-routing algorithm for public transportation systems[J].JournalofSoutheastUniversity(NaturalScienceEdition), 2004,34(2): 264-267. DOI:10.3321/j.issn:1001-0505.2004.02.029.(in Chinese)

[5] 中國公路學會《交通工程手冊》編委會.交通工程手冊[M]. 北京:人民交通出版社,1998:234.

[6] 中華人民共和國建設部.GB 50220—1995城市道路交通規(guī)劃設計規(guī)范[S].北京:中國計劃出版社,1995.

[7] 郝光, 張殿業(yè), 馮勛省. 多目標最短路徑模型及算法[J]. 西南交通大學學報, 2007, 42(5): 641-646. DOI:10.3969/j.issn.0258-2724.2007.05.024.

Hao Guang, Zhang Dianye, Feng Xunsheng. Model and algorithm for shortest path of multiple objectives[J].JournalofSouthwestJiaotongUniversity, 2007,42(5): 641-646. DOI:10.3969/j.issn.0258-2724.2007.05.024.(in Chinese)

[8] Yen J Y. Finding theKshortest loopless paths in a network[J].ManagementScience, 1971,17(11): 712-716. DOI:10.1287/mnsc.17.11.712.

[9] Androutsopoulos K N, Zografos K G. Solving the-shortest path problem with time windows in a time varying network[J].OperationsResearchLetters, 2008,36(6): 692-695. DOI:10.1016/j.orl.2008.07.003.

[10] Wang Z P,Li G,Ren J W.A new search algorithm for transmission section based onkshortest paths[J].TransactionsofChinaElectrotechnicalSociety, 2012,27(4):193-201.

[11] Gao Z Y, Zhao X M, Huang H J, et al. Research on problems related to complex networks and urban traffic systems[J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2006,6(3):41-47.

[12] 馬超群,王玉萍.基于客流效益最大化的軌道交通線網(wǎng)優(yōu)化方法[J].長安大學學報(自然科學版),2010,30(1):76-79.

Ma Chaoqun, Wang Yuping. Method to optimize urban rail transit network based on maximizing the passenger flow [J].JournalofChang’anUniversity(NaturalScienceEdition),2010,30(1):76-79.

Optimizationofmoderntramnetworkbasedonk-shortestpathalgorithm

Hu Junhong1,2Guo Xiucheng1Tao Tao1Hu Tingting1

(1School of Transportation, Southeast University, Nanjing 210096, China)
(2College of Transportation Science and Technology, Nanjing Technology University, Nanjing 210009, China)

In order to carry out the optimization and improvement of the modern tram network scientifically and rationally, thek-shortest path algorithm is introduced based on the constraint conditions of modern tram network optimization. Road space resource factors and path duplication factors are used to select the proper edges in the initial network and a set of alternative paths is formed. The non-linear coefficient and node comprehensive importance degree are combined into joint entropy weight, and the joint entropy weight is used as the judgment parameter of the optimal path of modern tram. Then, the modern optimization method for tram line is constructed. Finally, the effectiveness of the method is verified through the practical example of Nanjing Hexi new urban district modern tram network optimization. It is shown that thek-shortest path algorithm is an effective method for modern tram network planning. This method can provide a reference for urban tram network planning.

modern tram;k-shortest path algorithm; joint entropy weight; network optimization

10.3969/j.issn.1001-0505.2017.06.030

U491.13

A

1001-0505(2017)06-1274-05

2017-05-06.

胡軍紅(1974—)，女，博士生，副教授；過秀成(聯(lián)系人)，男，博士，教授，博士生導師，seuguo@163.com.

江蘇省交通運輸科技資助項目(2015Y17).

胡軍紅,過秀成,陶濤，等.基于k最短路徑的現(xiàn)代有軌電車線網(wǎng)優(yōu)化[J].東南大學學報(自然科學版),2017,47(6):1274-1278.

10.3969/j.issn.1001-0505.2017.06.030.