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

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