胡軍紅 過秀成 陶 濤 胡婷婷

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.1 問題描述

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

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

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

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

2.2 k最短路徑算法

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

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

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

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

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

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

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

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

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

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

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

5) 求最短路徑pr+1.

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

(4)

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

4 算例

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

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

4.1.1 構(gòu)建網(wǎng)絡(luò)圖并選定起始點(diǎn)組合

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

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

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

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

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

以起終點(diǎn)s1,t1為例,設(shè)定k=3,β≤1.2．按前述尋求最短路徑的計(jì)算步驟搜索現(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條路徑后,終止計(jì)算,并輸出備選路徑集合p=(p1,p2,p3),作為起始節(jié)點(diǎn)和終止節(jié)點(diǎn)s1,t1的備選路徑．

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

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

從每一對(duì)起始節(jié)點(diǎn)和終止節(jié)點(diǎn)si,ti(i=2,3,…,N)之間的備選路徑組中選擇最優(yōu)路徑,實(shí)現(xiàn)對(duì)初始線網(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)計(jì)算p=(p1,p1,p3)中最短路徑pr的非直線系數(shù)．

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

③ 按照式(3),權(quán)重系數(shù)α取0.35,計(jì)算最短路徑pr的聯(lián)合熵權(quá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),線路長(zhǎng)度c(p1)=6.53 km．

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

原河西現(xiàn)代有軌電車規(guī)劃線網(wǎng)是在點(diǎn)、線、面要素分析法的基礎(chǔ)上生成,所推薦的線網(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é)構(gòu),從線網(wǎng)布局規(guī)劃來看,線路走向與現(xiàn)狀的實(shí)際客流方向一致,線網(wǎng)結(jié)構(gòu)與河西新城布局形態(tài)相協(xié)調(diào)．

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

5 結(jié)語

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

)

[1] 白軼多,胡鵬, 夏蘭芳, 等.關(guān)于k次短路徑問題的分析與求解[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 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)絡(luò)的k最短路徑集合算法[J]. 交通運(yùn)輸系統(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] 徐濤, 丁曉璐, 李建伏. 國(guó)際航線網(wǎng)絡(luò)聯(lián)程路徑搜索的KMCSP問題研究[J]. 西南交通大學(xué)學(xué)報(bào), 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] 王莉, 李文權(quán). 公共交通系統(tǒng)最佳路徑算法[J]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 中國(guó)公路學(xué)會(huì)《交通工程手冊(cè)》編委會(huì).交通工程手冊(cè)[M]. 北京:人民交通出版社,1998:234.

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

[7] 郝光, 張殿業(yè), 馮勛省. 多目標(biāo)最短路徑模型及算法[J]. 西南交通大學(xué)學(xué)報(bào), 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].長(zhǎng)安大學(xué)學(xué)報(bào)(自然科學(xué)版),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)系人)，男，博士，教授，博士生導(dǎo)師，seuguo@163.com.

江蘇省交通運(yùn)輸科技資助項(xiàng)目(2015Y17).

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

10.3969/j.issn.1001-0505.2017.06.030.