轨道交通乘客个性化出行路径规划算法

轨道交通乘客个性化出行路径规划算法刘莎莎;姚恩建;张永生【摘要】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.%随着城市轨道交通网络的不断完善，可供乘客选择的轨道交通出行路径日益增加，乘客出行路径决策愈加复杂。本文在分析轨道交通服务水平变量对不同属性乘客出行路径选择行为影响的基础上，提出轨道交通乘客个性化出行路径规划算法。首先，基于非集计理论构建针对不同类别乘客的路径选择模型，该模型综合考虑乘车时间、换乘时间、换乘次数、车内拥挤度及个人属性等因素对乘客路径选择行为的影响。其次，基于不同类别乘客的路径选择行为差异，构建考虑车内拥挤度变化的乘客个性化出行路径动态规划算法，为不同属性乘客规划广义出行时间最小的路径。最后，基于广州地铁数据对算法进行验证。结果表明，该算法针对乘客个人属性规划的最优出行路径，更加贴合乘客的出行心理。【期刊名称】《交通运输系统工程与信息》【年(卷)，期】2014(000)005【总页数】6页(P100-104,132)【关键词】城市交通;路径规划;路径选择行为分析;个性化;车内拥挤度【作者】刘莎莎;姚恩建;张永生【作者单位】北京交通大学交通运输学院，北京100044;北京交通大学城市交通复杂系统理论与技术教育部重点实验室，北京100044;北京交通大学交通运输学院，北京100044;北京交通大学北京城市交通协同创新中心，北京100044;北京交通大学交通运输学院，北京100044【正文语种】中文【中图分类】U121传统的路径规划算法大多基于时间最短、换乘次数最少等单一最优目标，不能全面反映轨道交通服务水平变量(乘车时间、换乘时间、换乘次数、车内拥挤度等)对乘客出行路径选择行为的影响，更不能根据乘客的社会经济属性提供符合其选择嗜好的出行路径.因此，从理论上深入研究乘客在轨道交通网络中的路径选择规律，构造符合不同类别乘客选择偏好的个性化出行路径规划算法，对于改善轨道交通的出行信息服务水平、提高轨道交通系统的吸弓I力具有重要意义.目前，国内夕卜学者在路径规划算法方面的研究主要针对道路网络上车辆的最短行驶路径及公交线路的最短乘车路径［1］,而对城市轨道交通网络中乘客最优出行路径研究较少.Zhang［2］基于MNL(MultinomialLogit)模型设计了轨道交通路径规划算法，但是该算法没有考虑不同属性乘客路径选择偏好的差异及车内拥挤度对乘客路径选择的影响.设计综合考虑各种影响因素的轨道交通路径规划算法，首先要对乘客的路径选择行为进行分析.影响乘客路径选择的因素有很多，不仅包括轨道交通服务水平变量［3.4］，还包括乘客的个人属性(年龄、收入水平、出行目的等).同时，路网拓扑结构、换乘设施的便捷性［5］、乘客对路网的熟悉程度及出行习惯［6］等也对乘客的路径选择行为产生影响.上述研究对于轨道交通乘客路径选择行为的分析及路径规划具有重要的意义，但是他们大都没有考虑乘客的社会经济属性对乘客路径选择行为的影响，更没有基于车内拥挤度的变化构造动态路径规划算法.基于此，本文拟在综合考虑乘车时间、换乘时间、换乘次数、车内拥挤程度及个人属性等因素的基础上，构建针对不同类别乘客的路径选择模型，分析不同类别乘客的轨道交通路径选择规律.进而，基于乘客广义出行时间最小的原则，考虑车内拥挤度等动态因素，构造轨道交通乘客个性化出行路径动态规划算法，以弥补传统路径规划算法的不足.2.1影响因素分析在城市轨道交通网络中，乘客的路径选择行为受很多因素影响.广州地铁乘客出行特征调查显示，49.6%的乘客将旅行时间最短作为路径选择的首要因素，旅行时间包括乘车时间和换乘时间.20.4%的乘客则认为换乘次数是最重要的因素，在各条路径的旅行时间接近的情况下，换乘次数越小的路径被选择的概率越大.同时，11.5%的乘客最看重车内人少的因素，为了表示车内拥挤度对乘客路径选择偏好影响的连续变化，本文引入〃平均拥挤费用”.式中是OD对rs间路径k的平均拥挤费用；&j是区间（i,j）的满载率；Tij是区间（i,j）的运行时间；是路径k的总区段数；Fij是区间（i,j）的断面客流量；f表示发车频率；Y表示列车额定载员.2.2建立模型轨道交通网络结构一般比较简单，而且由于轨道交通按图行车，与复杂的道路网相比，重复路段对路径独立性的影响较小，出行路径之间较好地符合IIA特性；同时，根据以往的研究成果［6,7］，MNL模型能够较好地解释轨道交通乘客的路径选择行为.因此，本文基于MNL离散选择模型构建乘客出行路径选择模型，并利用极大似然估计法、t值检验法和拟合优度判定法标定参数.MNL模型及效用函数表示如下：式中对于第n类乘客，在OD对rs间的路径k，表示该路径被选择的概率；Ursk,n表示路径k的效用，由效用固定项和随机误差项组成；参数入与的方差成反比，取值大于0，一般取分别表示路径k的乘车时间、换乘时间、换乘次数、平均拥挤费用；M表示乘客的出行目的，作为哑元变量处理.根据广州地铁乘客出行特征调查结果，以通勤通学为出行目的的乘客倾向于选择时间最短路径，为了表示乘客的出行目的对路径选择偏好的影响，将通勤通学出行下的时间最短路径的效用函数中的出行目的哑元变量取为1,其他备选路径取为0；自由出行下，各路径的的效用函数中的出行目的哑元变量均取分别为对应的系数.3.1计算广义出行时间基于路径选择模型的标定结果，利用各影响因素与乘车时间之间的边际替代率，将各变量均换算成乘车时间，再结合路径的服务水平变量计算等效乘车时间之和，即可得到各路径的广义出行时间.计算公式如下：式中Crsk,n表示对于第n类乘客，OD对rs间路径k的广义出行时间分别表示换乘时间、换乘次数、平均拥挤费用、出行目的与乘车时间之间的边际替代率；表示第i个影响因素在模型中的系数.3.2个性化路径规划考虑到乘客大都将旅行时间最短作为路径选择的首要因素，本文首先利用K短路搜索算法中时间复杂度和空间复杂度相对较低、执行效率相对较高的doublesweep算法（含无回路处理），基于旅行时间最短的原则，筛选每个OD对之间每一类乘客的K条备选路径集合然后基于调查获得的乘客可以忍受的路径时间与最短路径时间的比值和差值设定可接受的临界阈值，基于非补偿原则确定最终的备选路径集合.备选路径集合中每条备选路径的属性包括起讫点、换乘车站、途径车站、乘车时间、换乘时间、换乘次数和路径的运营时间.路径的运营时间可通过该路径的起点站有效运营时间来表示［8］，起点站有效运营时间为起点站的首末班车时间和该路径中各换乘站首末班车时间反推起点站进站时间的交集.在建立备选路径集合的基础上，基于广义出行时间最小的原则，进行个性化路径规划的流程如下.Step1输入乘客出行的起讫点rs、出发时间及个人属性（第n类乘客）.Step2根据乘客出行的起讫点rs，搜索该OD对间第n类乘客的备选路径集合Step3结合乘客的出发时间和线路的运营时间，判定各备选路径的有效性，获得最终有效路径集合Step4根据乘客的个人属性，结合动态的车内拥挤度数据，计算有效路径集合中各路径的广义出行时间Step5选择有效路径集合中广义出行时间最小的路径，作为该类乘客的最优出行路径.该算法基于非补偿原则确定备选路径集合，以广义出行时间最小为最优目标，根据不同类别乘客的路径广义费用及车内拥挤程度等动态指标，实现高效合理的个性化路径规划.基于广州地铁工作日15399份乘客路径选择偏好的RP（RevealedPreference）调查问卷数据，对不同属性乘客的路径选择行为进行分析，进而结合车内拥挤度的动态数据，对本文所提出的乘客个性化出行路径规划算法进行了验证.4.1乘客出行路径选择行为分析根据调查问卷中设定的乘客属性进行交叉分类：不同性别乘客对路径选择影响因素的敏感性差别不大，在此不进行分类；按照年龄分为24-40岁和其他年龄段两类，24-40岁人群为工作适龄人群，且比较年轻，他们较重视旅行时间，对换乘、车内拥挤度等关注较少；按照出行目的分为通勤或通学（有严格时间限制）和自由出行（无严格时间限制）两类；按照出行时间段分为早高峰、平峰和晚高峰三类.根据上述乘客属性交叉分类后，乘客可以大致分为12类出行者，其中出行目的看作0-1变量处理.针对不同类别的乘客，分别建立路径选择模型，模型标定结果如表1所示.其他年龄（24岁以下或40岁以上）乘客在晚高峰出行时，若考虑车内拥挤度的影响，t值不满足检验要求，因此将拥挤度从该模型中剔除从表1可以看出，不同模型中各变量的t值的绝对值均大于1.96，即有95%的把握认为各系数估计值可信；优度比均大于0.2，表明模型的精度较高；各变量的系数均小于零，说明乘客出行时，总是寻求乘车时间和换乘时间最短、换乘次数最少、车内拥挤度最小的路径，符合实际情况.4.2最优出行路径规划根据表1中模型的标定结果，可得各变量与乘车时间之间的边际替代率，如表2所示，再结合各备选路径的服务水平变量，进而可得各路径的广义出行时间.基于广义出行时间最小的原则，结合车内拥挤度的动态数据，应用个性化路径规划算法可以为不同属性的乘客规划最优出行路径.其中，车内拥挤度通过以往平均断面客流量确定，每15min更新一次.以西朗一白云大道北为例说明，不同属性乘客的最优出行路径规划结果如表3所示，路径规划结果中的两条路径如图1所示.传统的时间最短路算法为不同属性乘客规划的最优路径均为路径1，而由表3可以看出，不同属性乘客的最优出行路径是不同的.同时，车内拥挤度的动态变化对最优路径规划结果的影响显著.本文在分析轨道交通乘客路径选择行为的基础上，提出了轨道交通乘客个性化出行路径规划算法.该算法在建立备选路径集合的基础上，结合乘客的个人属性（年龄、出行目的、出发时间），同时考虑车内拥挤度的动态变化，为乘客规划广义出行时间最小的路径.通过对广州地铁网络的路径规划结果可知，不同属性乘客的最优出行路径不同，而且车内拥挤度的动态变化对最优路径规划结果的影响显著.此外，16.0%和9.4%的广义出行时间最小路径并非为时间最短路和换乘最少路径.因此，传统的路径规划算法并不能规划出符合乘客路径选择规律的路径，本文所提出的路径规划算法更加符合乘客的路径选择偏好，可为乘客提供综合考虑了乘车时间、换乘时间、换乘次数、车内拥挤度及个人属性等因素影响的广义出行时间最小的个性化出行路径.【相关文献】鄢勇飞.大城市公共交通网络最优路径算法研究[D].武汉：武汉理工大学，2009.[YANYF.Researchonoptimalpathalgorithmofpublictransitnetworkinmetropolis[D].Wuhan:WuhanUniversityofTechnology,2009.]ZhangYS,YaoEJ,YangY.Aroute-planningalgorithmbasedonsubwaypassengerrouteschoicebehavioranalysis[C].ProceedingsoftheSecondInternationalConferenceonTransportationInformationandSafety.Wuhan,China:AmericanSocietyofCivilEngineers,2013:1972-1978.四兵锋，毛保华，刘智丽.无缝换乘条件下城市轨道交通网络客流分配模型及算法[J].铁道学报，2007,29(6):12-18.[SIBF,MAOBH,LIUZL.Passengerflowassignmentmodelandalgorithmforurbanrailtrafficnetworkundertheconditionofseamlesstransfer[J].JournaloftheChinaRailwaySociety,2007,29(6):12-18.][4]刘剑锋，孙福亮.城市轨道交通乘客路径选择模型及算法[J].交通运输系统工程与信息，2009,9(2):81-86.[LIUJF,SUNFL.Passengerflowrouteassignmentmodelandalgorithmforurbanrailtransitnetwork[J].JournalofTransportationSystemsEngineeringandInformationTechnology,2009,9(2):81-86.]SebastianRave