軌道交通乘客個(gè)性化出行路徑規(guī)劃算法

軌道交通乘客個(gè)性化出行路徑規(guī)劃算法劉莎莎;姚恩建;張永生【摘要】Withtherapiddevelopmentofurbanrailtransitnetwork,increasedavailableroutesmakepassengers’tripdecision-makingbecomemoreandmoredifficult.Thisstudyproposesadynamicmetrorouteplanningalgorithmwiththeleastgeneralizedcost,inwhichnetworkLOSvariablesandpersonalcharacteristicsaretakenintoconsideration.Firstly,basedonthedisaggregatechoicetheory,themetroroutechoicemodelsfordifferenttypesofpassengersareestablishedwiththeconsiderationofLOSvariables(e.g.in-vehicletraveltime,transfertime,numberoftransfers,in-vehiclepassengerdensity,etc.)andpersonalcharacteristics(e.g.age,trippurpose,etc.).Then,basedontheproposedmodelsandthetime-variedsectionalflowvolume,adynamicpersonalizedrouteplanningalgorithmisproposed,whichisexpectedtogeneratetheoptimalroutewiththeleastgeneralizedtimeforeachtypeofpassengers.Finally,theproposedalgorithmisevaluatedinGuangzhouMetroconditions.Theresultsindicatethatthealgorithmcanprovidepassengerswiththemorereasonableroutecorrespondingwiththeircharacteristics,andexpressespassenger'sroutechoicepreferencemoreprecisely.%隨著城市軌道交通網(wǎng)絡(luò)的不斷完善，可供乘客選擇的軌道交通出行路徑日益增加，乘客出行路徑?jīng)Q策愈加復(fù)雜。本文在分析軌道交通服務(wù)水平變量對(duì)不同屬性乘客出行路徑選擇行為影響的基礎(chǔ)上，提出軌道交通乘客個(gè)性化出行路徑規(guī)劃算法。首先，基于非集計(jì)理論構(gòu)建針對(duì)不同類別乘客的路徑選擇模型，該模型綜合考慮乘車(chē)時(shí)間、換乘時(shí)間、換乘次數(shù)、車(chē)內(nèi)擁擠度及個(gè)人屬性等因素對(duì)乘客路徑選擇行為的影響。其次，基于不同類別乘客的路徑選擇行為差異，構(gòu)建考慮車(chē)內(nèi)擁擠度變化的乘客個(gè)性化出行路徑動(dòng)態(tài)規(guī)劃算法，為不同屬性乘客規(guī)劃廣義出行時(shí)間最小的路徑。最后，基于廣州地鐵數(shù)據(jù)對(duì)算法進(jìn)行驗(yàn)證。結(jié)果表明，該算法針對(duì)乘客個(gè)人屬性規(guī)劃的最優(yōu)出行路徑，更加貼合乘客的出行心理。【期刊名稱】《交通運(yùn)輸系統(tǒng)工程與信息》【年(卷)，期】2014(000)005【總頁(yè)數(shù)】6頁(yè)(P100-104,132)【關(guān)鍵詞】城市交通;路徑規(guī)劃;路徑選擇行為分析;個(gè)性化;車(chē)內(nèi)擁擠度【作者】劉莎莎;姚恩建;張永生【作者單位】北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044;北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044;北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044;北京交通大學(xué)北京城市交通協(xié)同創(chuàng)新中心，北京100044;北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044【正文語(yǔ)種】中文【中圖分類】U121傳統(tǒng)的路徑規(guī)劃算法大多基于時(shí)間最短、換乘次數(shù)最少等單一最優(yōu)目標(biāo)，不能全面反映軌道交通服務(wù)水平變量(乘車(chē)時(shí)間、換乘時(shí)間、換乘次數(shù)、車(chē)內(nèi)擁擠度等)對(duì)乘客出行路徑選擇行為的影響，更不能根據(jù)乘客的社會(huì)經(jīng)濟(jì)屬性提供符合其選擇嗜好的出行路徑.因此，從理論上深入研究乘客在軌道交通網(wǎng)絡(luò)中的路徑選擇規(guī)律，構(gòu)造符合不同類別乘客選擇偏好的個(gè)性化出行路徑規(guī)劃算法，對(duì)于改善軌道交通的出行信息服務(wù)水平、提高軌道交通系統(tǒng)的吸弓I力具有重要意義.目前，國(guó)內(nèi)夕卜學(xué)者在路徑規(guī)劃算法方面的研究主要針對(duì)道路網(wǎng)絡(luò)上車(chē)輛的最短行駛路徑及公交線路的最短乘車(chē)路徑［1］,而對(duì)城市軌道交通網(wǎng)絡(luò)中乘客最優(yōu)出行路徑研究較少.Zhang［2］基于MNL(MultinomialLogit)模型設(shè)計(jì)了軌道交通路徑規(guī)劃算法，但是該算法沒(méi)有考慮不同屬性乘客路徑選擇偏好的差異及車(chē)內(nèi)擁擠度對(duì)乘客路徑選擇的影響.設(shè)計(jì)綜合考慮各種影響因素的軌道交通路徑規(guī)劃算法，首先要對(duì)乘客的路徑選擇行為進(jìn)行分析.影響乘客路徑選擇的因素有很多，不僅包括軌道交通服務(wù)水平變量［3.4］，還包括乘客的個(gè)人屬性(年齡、收入水平、出行目的等).同時(shí)，路網(wǎng)拓?fù)浣Y(jié)構(gòu)、換乘設(shè)施的便捷性［5］、乘客對(duì)路網(wǎng)的熟悉程度及出行習(xí)慣［6］等也對(duì)乘客的路徑選擇行為產(chǎn)生影響.上述研究對(duì)于軌道交通乘客路徑選擇行為的分析及路徑規(guī)劃具有重要的意義，但是他們大都沒(méi)有考慮乘客的社會(huì)經(jīng)濟(jì)屬性對(duì)乘客路徑選擇行為的影響，更沒(méi)有基于車(chē)內(nèi)擁擠度的變化構(gòu)造動(dòng)態(tài)路徑規(guī)劃算法.基于此，本文擬在綜合考慮乘車(chē)時(shí)間、換乘時(shí)間、換乘次數(shù)、車(chē)內(nèi)擁擠程度及個(gè)人屬性等因素的基礎(chǔ)上，構(gòu)建針對(duì)不同類別乘客的路徑選擇模型，分析不同類別乘客的軌道交通路徑選擇規(guī)律.進(jìn)而，基于乘客廣義出行時(shí)間最小的原則，考慮車(chē)內(nèi)擁擠度等動(dòng)態(tài)因素，構(gòu)造軌道交通乘客個(gè)性化出行路徑動(dòng)態(tài)規(guī)劃算法，以彌補(bǔ)傳統(tǒng)路徑規(guī)劃算法的不足.2.1影響因素分析在城市軌道交通網(wǎng)絡(luò)中，乘客的路徑選擇行為受很多因素影響.廣州地鐵乘客出行特征調(diào)查顯示，49.6%的乘客將旅行時(shí)間最短作為路徑選擇的首要因素，旅行時(shí)間包括乘車(chē)時(shí)間和換乘時(shí)間.20.4%的乘客則認(rèn)為換乘次數(shù)是最重要的因素，在各條路徑的旅行時(shí)間接近的情況下，換乘次數(shù)越小的路徑被選擇的概率越大.同時(shí)，11.5%的乘客最看重車(chē)內(nèi)人少的因素，為了表示車(chē)內(nèi)擁擠度對(duì)乘客路徑選擇偏好影響的連續(xù)變化，本文引入〃平均擁擠費(fèi)用”.式中是OD對(duì)rs間路徑k的平均擁擠費(fèi)用；&j是區(qū)間（i,j）的滿載率；Tij是區(qū)間（i,j）的運(yùn)行時(shí)間；是路徑k的總區(qū)段數(shù)；Fij是區(qū)間（i,j）的斷面客流量；f表示發(fā)車(chē)頻率；Y表示列車(chē)額定載員.2.2建立模型軌道交通網(wǎng)絡(luò)結(jié)構(gòu)一般比較簡(jiǎn)單，而且由于軌道交通按圖行車(chē)，與復(fù)雜的道路網(wǎng)相比，重復(fù)路段對(duì)路徑獨(dú)立性的影響較小，出行路徑之間較好地符合IIA特性；同時(shí)，根據(jù)以往的研究成果［6,7］，MNL模型能夠較好地解釋軌道交通乘客的路徑選擇行為.因此，本文基于MNL離散選擇模型構(gòu)建乘客出行路徑選擇模型，并利用極大似然估計(jì)法、t值檢驗(yàn)法和擬合優(yōu)度判定法標(biāo)定參數(shù).MNL模型及效用函數(shù)表示如下：式中對(duì)于第n類乘客，在OD對(duì)rs間的路徑k，表示該路徑被選擇的概率；Ursk,n表示路徑k的效用，由效用固定項(xiàng)和隨機(jī)誤差項(xiàng)組成；參數(shù)入與的方差成反比，取值大于0，一般取分別表示路徑k的乘車(chē)時(shí)間、換乘時(shí)間、換乘次數(shù)、平均擁擠費(fèi)用；M表示乘客的出行目的，作為啞元變量處理.根據(jù)廣州地鐵乘客出行特征調(diào)查結(jié)果，以通勤通學(xué)為出行目的的乘客傾向于選擇時(shí)間最短路徑，為了表示乘客的出行目的對(duì)路徑選擇偏好的影響，將通勤通學(xué)出行下的時(shí)間最短路徑的效用函數(shù)中的出行目的啞元變量取為1,其他備選路徑取為0；自由出行下，各路徑的的效用函數(shù)中的出行目的啞元變量均取分別為對(duì)應(yīng)的系數(shù).3.1計(jì)算廣義出行時(shí)間基于路徑選擇模型的標(biāo)定結(jié)果，利用各影響因素與乘車(chē)時(shí)間之間的邊際替代率，將各變量均換算成乘車(chē)時(shí)間，再結(jié)合路徑的服務(wù)水平變量計(jì)算等效乘車(chē)時(shí)間之和，即可得到各路徑的廣義出行時(shí)間.計(jì)算公式如下：式中Crsk,n表示對(duì)于第n類乘客，OD對(duì)rs間路徑k的廣義出行時(shí)間分別表示換乘時(shí)間、換乘次數(shù)、平均擁擠費(fèi)用、出行目的與乘車(chē)時(shí)間之間的邊際替代率；表示第i個(gè)影響因素在模型中的系數(shù).3.2個(gè)性化路徑規(guī)劃考慮到乘客大都將旅行時(shí)間最短作為路徑選擇的首要因素，本文首先利用K短路搜索算法中時(shí)間復(fù)雜度和空間復(fù)雜度相對(duì)較低、執(zhí)行效率相對(duì)較高的doublesweep算法（含無(wú)回路處理），基于旅行時(shí)間最短的原則，篩選每個(gè)OD對(duì)之間每一類乘客的K條備選路徑集合然后基于調(diào)查獲得的乘客可以忍受的路徑時(shí)間與最短路徑時(shí)間的比值和差值設(shè)定可接受的臨界閾值，基于非補(bǔ)償原則確定最終的備選路徑集合.備選路徑集合中每條備選路徑的屬性包括起訖點(diǎn)、換乘車(chē)站、途徑車(chē)站、乘車(chē)時(shí)間、換乘時(shí)間、換乘次數(shù)和路徑的運(yùn)營(yíng)時(shí)間.路徑的運(yùn)營(yíng)時(shí)間可通過(guò)該路徑的起點(diǎn)站有效運(yùn)營(yíng)時(shí)間來(lái)表示［8］，起點(diǎn)站有效運(yùn)營(yíng)時(shí)間為起點(diǎn)站的首末班車(chē)時(shí)間和該路徑中各換乘站首末班車(chē)時(shí)間反推起點(diǎn)站進(jìn)站時(shí)間的交集.在建立備選路徑集合的基礎(chǔ)上，基于廣義出行時(shí)間最小的原則，進(jìn)行個(gè)性化路徑規(guī)劃的流程如下.Step1輸入乘客出行的起訖點(diǎn)rs、出發(fā)時(shí)間及個(gè)人屬性（第n類乘客）.Step2根據(jù)乘客出行的起訖點(diǎn)rs，搜索該OD對(duì)間第n類乘客的備選路徑集合Step3結(jié)合乘客的出發(fā)時(shí)間和線路的運(yùn)營(yíng)時(shí)間，判定各備選路徑的有效性，獲得最終有效路徑集合Step4根據(jù)乘客的個(gè)人屬性，結(jié)合動(dòng)態(tài)的車(chē)內(nèi)擁擠度數(shù)據(jù)，計(jì)算有效路徑集合中各路徑的廣義出行時(shí)間Step5選擇有效路徑集合中廣義出行時(shí)間最小的路徑，作為該類乘客的最優(yōu)出行路徑.該算法基于非補(bǔ)償原則確定備選路徑集合，以廣義出行時(shí)間最小為最優(yōu)目標(biāo)，根據(jù)不同類別乘客的路徑廣義費(fèi)用及車(chē)內(nèi)擁擠程度等動(dòng)態(tài)指標(biāo)，實(shí)現(xiàn)高效合理的個(gè)性化路徑規(guī)劃.基于廣州地鐵工作日15399份乘客路徑選擇偏好的RP（RevealedPreference）調(diào)查問(wèn)卷數(shù)據(jù)，對(duì)不同屬性乘客的路徑選擇行為進(jìn)行分析，進(jìn)而結(jié)合車(chē)內(nèi)擁擠度的動(dòng)態(tài)數(shù)據(jù)，對(duì)本文所提出的乘客個(gè)性化出行路徑規(guī)劃算法進(jìn)行了驗(yàn)證.4.1乘客出行路徑選擇行為分析根據(jù)調(diào)查問(wèn)卷中設(shè)定的乘客屬性進(jìn)行交叉分類：不同性別乘客對(duì)路徑選擇影響因素的敏感性差別不大，在此不進(jìn)行分類；按照年齡分為24-40歲和其他年齡段兩類，24-40歲人群為工作適齡人群，且比較年輕，他們較重視旅行時(shí)間，對(duì)換乘、車(chē)內(nèi)擁擠度等關(guān)注較少；按照出行目的分為通勤或通學(xué)（有嚴(yán)格時(shí)間限制）和自由出行（無(wú)嚴(yán)格時(shí)間限制）兩類；按照出行時(shí)間段分為早高峰、平峰和晚高峰三類.根據(jù)上述乘客屬性交叉分類后，乘客可以大致分為12類出行者，其中出行目的看作0-1變量處理.針對(duì)不同類別的乘客，分別建立路徑選擇模型，模型標(biāo)定結(jié)果如表1所示.其他年齡（24歲以下或40歲以上）乘客在晚高峰出行時(shí)，若考慮車(chē)內(nèi)擁擠度的影響，t值不滿足檢驗(yàn)要求，因此將擁擠度從該模型中剔除從表1可以看出，不同模型中各變量的t值的絕對(duì)值均大于1.96，即有95%的把握認(rèn)為各系數(shù)估計(jì)值可信；優(yōu)度比均大于0.2，表明模型的精度較高；各變量的系數(shù)均小于零，說(shuō)明乘客出行時(shí)，總是尋求乘車(chē)時(shí)間和換乘時(shí)間最短、換乘次數(shù)最少、車(chē)內(nèi)擁擠度最小的路徑，符合實(shí)際情況.4.2最優(yōu)出行路徑規(guī)劃根據(jù)表1中模型的標(biāo)定結(jié)果，可得各變量與乘車(chē)時(shí)間之間的邊際替代率，如表2所示，再結(jié)合各備選路徑的服務(wù)水平變量，進(jìn)而可得各路徑的廣義出行時(shí)間.基于廣義出行時(shí)間最小的原則，結(jié)合車(chē)內(nèi)擁擠度的動(dòng)態(tài)數(shù)據(jù)，應(yīng)用個(gè)性化路徑規(guī)劃算法可以為不同屬性的乘客規(guī)劃最優(yōu)出行路徑.其中，車(chē)內(nèi)擁擠度通過(guò)以往平均斷面客流量確定，每15min更新一次.以西朗一白云大道北為例說(shuō)明，不同屬性乘客的最優(yōu)出行路徑規(guī)劃結(jié)果如表3所示，路徑規(guī)劃結(jié)果中的兩條路徑如圖1所示.傳統(tǒng)的時(shí)間最短路算法為不同屬性乘客規(guī)劃的最優(yōu)路徑均為路徑1，而由表3可以看出，不同屬性乘客的最優(yōu)出行路徑是不同的.同時(shí)，車(chē)內(nèi)擁擠度的動(dòng)態(tài)變化對(duì)最優(yōu)路徑規(guī)劃結(jié)果的影響顯著.本文在分析軌道交通乘客路徑選擇行為的基礎(chǔ)上，提出了軌道交通乘客個(gè)性化出行路徑規(guī)劃算法.該算法在建立備選路徑集合的基礎(chǔ)上，結(jié)合乘客的個(gè)人屬性（年齡、出行目的、出發(fā)時(shí)間），同時(shí)考慮車(chē)內(nèi)擁擠度的動(dòng)態(tài)變化，為乘客規(guī)劃廣義出行時(shí)間最小的路徑.通過(guò)對(duì)廣州地鐵網(wǎng)絡(luò)的路徑規(guī)劃結(jié)果可知，不同屬性乘客的最優(yōu)出行路徑不同，而且車(chē)內(nèi)擁擠度的動(dòng)態(tài)變化對(duì)最優(yōu)路徑規(guī)劃結(jié)果的影響顯著.此外，16.0%和9.4%的廣義出行時(shí)間最小路徑并非為時(shí)間最短路和換乘最少路徑.因此，傳統(tǒng)的路徑規(guī)劃算法并不能規(guī)劃出符合乘客路徑選擇規(guī)律的路徑，本文所提出的路徑規(guī)劃算法更加符合乘客的路徑選擇偏好，可為乘客提供綜合考慮了乘車(chē)時(shí)間、換乘時(shí)間、換乘次數(shù)、車(chē)內(nèi)擁擠度及個(gè)人屬性等因素影響的廣義出行時(shí)間最小的個(gè)性化出行路徑.【相關(guān)文獻(xiàn)】鄢勇飛.大城市公共交通網(wǎng)絡(luò)最優(yōu)路徑算法研究[D].武漢：武漢理工大學(xué)，2009.[YANYF.Researchonoptimalpathalgorithmofpublictransitnetworkinmetropolis[D].Wuhan:WuhanUniversityofTechnology,2009.]ZhangYS,YaoEJ,YangY.Aroute-planningalgorithmbasedonsubwaypassengerrouteschoicebehavioranalysis[C].ProceedingsoftheSecondInternationalConferenceonTransportationInformationandSafety.Wuhan,China:AmericanSocietyofCivilEngineers,2013:1972-1978.四兵鋒，毛保華，劉智麗.無(wú)縫換乘條件下城市軌道交通網(wǎng)絡(luò)客流分配模型及算法[J].鐵道學(xué)報(bào)，2007,29(6):12-18.[SIBF,MAOBH,LIUZL.Passengerflowassignmentmodelandalgorithmforurbanrailtrafficnetworkundertheconditionofseamlesstransfer[J].JournaloftheChinaRailwaySociety,2007,29(6):12-18.][4]劉劍鋒，孫福亮.城市軌道交通乘客路徑選擇模型及算法[J].交通運(yùn)輸系統(tǒng)工程與信息，2009,9(2):81-86.[LIUJF,SUNFL.Passengerflowrouteassignmentmodelandalgorithmforurbanrailtransitnetwork[J].JournalofTransportationSystemsEngineeringandInformationTechnology,2009,9(2):81-86.]SebastianRave