（交通运输规划与管理专业论文）城际多方式出行路径规划方法研究.pdf

学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据 提供阅览服务，并采用影印、缩印或扫描等复制手段保存、汇编以供 同意学校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 签字日期：2 - d 1 0 年f 月f j 日 导 签字日 中图分类号： u d c ： 学校代码：1 0 0 0 4 密级：公开 北京交通大学 硕士学位论文 城际多方式出行路径规划方法研究 r e s e a r c ho nr o u t ep l a n n i n gm e t h o do f i n t e r c i t yt r a v e li nm u l t i m o d a l n e t w o r k s 作者姓名：王璇 导师姓名：刘军 学位类别：工学 学号：0 8 1 2 1 3 4 2 职称：教授 学位级别：硕士 学科专业：交通运输规划与管理研究方向：交通运输信息技术 北京交通大学 2 0 1 0 年6 月 致谢 在刘老师门下学习两年，收获良多。老师独特的人格魅力、敏锐的思维方式、 渊博的学术知识，一直影响着我。在此由衷地感谢老师对我耐心的指导。 感谢马敏书老师在课题中的耐心指导，感谢李春燕老师在论文撰写过程中热 心细致的帮助。 感谢实验室李海鹰老师、蒋熙老师、苗建瑞老师、贺振欢老师对我和同学们 在学术上的指导和帮助。 感谢王莹师姐在我徘徊时的指点和开导，感谢王伟师兄、刘广志师兄、郑金 子在学习过程中的帮助。感谢宋晓芳、高嵩、赵雅芳、贺协腾等同学和朋友的关 心和理解。 感谢室友徐荣在我低沉时的陪伴和开导。感谢张韬博士在生活上的帮助及论 文修改中的中肯意见。 感谢所有关心、帮助过我的人。 中文摘要 摘要：经济的发展与城际客运系统的完善使得城际出行范围扩大与出行总量的迅 速增加，个性化的出行需求日益明显。实际问题为城际多方式出行路径规划的理 论研究带来了需求。 城际多方式出行路径规划是指基于既有交通方式和载运工具，在考虑出行者 不同偏好( 快速、经济、少换乘及舒适) 情况下的城市间出行路径优化问题。与 传统路径规划问题相比，城际多方式出行依托已有服务网络而非物理网络，路径 的权值根据出行者偏好确定，另外，路径规划的结果不仅应该满足数学意义上的 最短，还要考虑出行者在中转城市选择时的习惯。 基于上述城际多方式出行问题的特点，本文从以下几个方面展开研究，并在 一定程度上实现了理论与应用的创新： 1 、构建能够包含既有出行信息的城际多方式出行网络。论文在分析实际城际 出行过程的基础上，以城市为节点，城市间既有车次( 航班) 为弧，构建城际多 方式出行网络； 2 、建立城际多方式出行路径优化模型。通过选取合理的指标，对城际出行的 时效性、经济性、换乘次数及舒适性进行量化，并设计出包含以上四方面的广义 费用模型； 3 、提出划分区域分步分层的求解算法。考虑到起讫点城市间需转换交通方式 才可达，论文采用空间聚类分析法对城际多方式出行网络划分区域，运用重心法 找出区域核心城市，首先以区域为单位根据出行偏好优先在相应单层网络上寻找 区域间最优路径，再考虑区域内如何通达。划分区域分步分层求解，能够在路径 规划结果合理化、人性化的同时，缩小网络规模，提高求解效率； 4 、选取部分城市与城市间车次( 航班) 信息作为验证数据做实证分析，实现 网络构建和算法过程，采用a r c g i s 展示路径规划结果，并进行比对分析。通过实 例验证，本文提出的算法是可行有效的。 关键词：城际；多方式；出行偏好；路径规划：区域划分 分类号：u l l 6 2 ；u 1 2 5 a b s t r a c t a b s t r a c t ：1 1 1 ei n t e r c i t yt r a v e lr a n g ei se x p a n d i n ga n dt h et o t a lf o ri n t e r e i t yt r i pi s i n c r e a s i n gr a p i d l yu n d e rt h ei n f l u e n c eo fd e v e l o p m e n to fe c o n o m ya n di m p r o v e m e n to f i n t e r c i t y p a s s e n g e rt r a n s p o r ts y s t e m ，a n dp e r s o n a l i z e dt r a v e ld e m a n dh a sb e c o m e i n c r e a s i n g l ye v i d e n t t h ep h e n o m e n o nm a k e st h er e s e a r c ho nr o u t ep l a n n i n gm e t h o do f i n t e r c i t yt r a v e li nm u l t i m o d a ln e t w o r k sn e c e s s a r y r o u t e p l a n n i n go fi n t e r c i t yt r a v e li nm u l t i m o d a ln e t w o r k sw h i c hi sb a s e do nt h ee x i s t i n g m o d e so ft r a n s p o r t a t i o na n dc o n v e y a n c ei sar o u t eo p t i m i z a t i o np r o b l e m ，i ne a s eo f d i f f e r e n tp r e f e r e n c e ( f a s t ，e c o n o m i c ，a n dl e s st r a n s f e ra n dc o m f o r t ) c o m p a r e dw i t ht h e t r a d i t i o n a lr o u t ep l a n n i n g ，r o u t ep l a n n i n go f i n t e r c i t yt r a v e li nm u l t i m o d a ln e t w o r k sr e l y o ns e r v i c en e t w o r kb u tp h y s i c a ln e t w o r k n ew e i g h to fa r ew o u l db ed e t e r m i n e db y t r a v e lp r e f e r e n c e t h er e s u l to fr o u t ep l a n n i n gi sn o to n l yf o rt h es h o r t e s t ，b u ta l s ot o c o n s i d e rt h eh a b i to fo p t i o ni nu r b a nt r a n s i t b a s e do nt h e s ec h a r a c t e r i s t i e s ，t h e f o l l o w i n ga s p e c t sa r es t u d i e di nt h ep a p e r ： ( 1 ) i n t e r c i t ya n dm u l t i m o d a lt r a v e ln e t w o r k sa r ec o n s t r u c t e dw h i c hc a ns h o wa l lt h e t r a v e li n f o r m a t i o nb e t w e e nc i t i e s t h e e x i s t i n gn e t w o r kc o n s t r u c t i o nm e t h o d sa r e i m p r o v e d i nt h em u l t i m o d a lt r a v e ln e t w o r k s ，n o d er e p r e s e n t sc i t ya n da r er e p r e s e n t s t r a i ns e r v i c eo rf l i g h t ( 2 ) i n t e r c i t yt r a v e lr o u t eo p t i m i z a t i o nm o d e l sa r eb u i l ti nc o n s i d e r a t i o no fd i f f e r e n t p r e f e r e n c e s b a s e do ns e l e c t i n ga p p r o p r i a t ei n d i c a t o r s ，r a p i d i t y 、e c o n o m y 、n u m b e ro f t r a n s f e ra n dc o m f o r ta r eq u a n t i z e d f i n a l l y , g e n e r a l i z e dc o s tm o d e li sb u i l ti n c l u d i n g a b o v e - m e n t i o n e dc o s t s ( 3 ) r e g i o n - d i v i d e da l g o r i t h mi sp r o p o s e d t h ef u z z yc l u s t e ra n a l y s i sa n dg r a v i t y m e t h o da r eu s e dt od i v i d et h er e g i o na n df i n dt h ec o r ec i t y i n t e r r e g i o n a lr o u t ew o u l db e p l a n e di nt h ec o r r e s p o n d i n gs i n g l e l a y e rn e t w o r ka c c o r d i n gt ot h et r a v e lp r e f e r e n c e sa n d t h e ni n t r a r e g i o n a lr o u t ew o u l db ep l a n e ds e p a r a t e l y f i n a l l yt h er e s u l t sa r ec o m b i n e d r e g i o n - d i v i d e da l g o r i t h mm a k e st h es c a l eo fn e t w o r ks m a l l e rt oi n c r e a s eo fe f f i c i e n c y o fa l g o r i t h m ，w h i l ee n s u r i n gt h er e s u l tr a t i o n a la n dh u m a n - o r i e n t e d ( 4 ) a c c o r d i n gt ot h ed a t ai nr e a l i t y , ap r o g r a mi sm a d et ot e s tt h ea l g o r i t h ma n ds h o w t h er o u t eb ya r c g i s t h ep r o p o s e da l g o r i t h mi sf e a s i b l ea n de f f e c t i v eb yc o m p a r a t i v e a n a l y s i s k e y w o r d s ：i n t e r c i t y ；m u l t i m o d a l ；t r a v e lp r e f e r e n c e ；r e g i o nd i v i s i o n ；r o u t ep l a n n i n g i v c l a s s n o ：u 1 1 6 2 ；u 1 2 5 v 目录 中文摘要i i i a b ；t r a c t i v 1绪论1 1 1问题的提出1 1 2国内外研究现状2 1 2 1 路径规划问题研究现状2 1 2 2 多式联运问题研究现状4 1 2 3 既有研究总结4 1 3研究目的与研究意义5 1 4 论文研究内容与技术路线一5 2城际多方式出行网络分析与构建7 2 1 城际多方式出行网络特性分析一7 2 2城际多方式出行网络构建1 0 2 2 1 城际多方式出行网络构建依据1 0 2 2 2 城际多方式出行网络的构建过程1 1 2 2 3 城际多方式出行网络的数学描述1 5 3城际多方式出行路径优化模型1 7 3 1多方式出行选择偏好及影响因素分析1 7 3 2 基于不同偏好的出行路径优化模型19 3 2 1 时间费用模型2 0 3 2 2 经济费用模型一2 l 3 2 3 换乘费用模型2 2 3 2 4 舒适性费用模型2 3 3 3基于广义费用最小的城际多方式出行路径优化模型2 4 4 城际多方式出行路径规划求解算法2 5 4 1 算法设计基础与思路一2 5 4 2区域划分2 7 4 2 1 区域划分方法一2 7 4 2 2 区域核心城市的确定方法3 0 4 3算法流程。3 0 5实证分析3 2 5 1输入数据3 2 5 2 程序实现一3 3 5 3结果分析3 5 6 结论一4 3 6 1论文的主要研究工作4 3 6 2论文的主要创新点4 3 6 3有待进一步研究的问题4 4 参考文献4 5 附蜀之4 7 作者简历5 7 独创性声明一5 8 学位论文数据集5 9 1 绪论 1 1 问题的提出 城际多方式出行路径规划是指基于铁路、航空和公路等多种交通方式的城市 间出行的路径选择，主要解决如何根据既有交通方式和载运工具，在考虑出行者 偏好( 如出行时间最短、票价最低、换乘最少等) 的情况下，给出较优出行路径 的问题。 随着我国经济的发展，城市化进程的加快，城际客运系统的完善，以大中城 市为中心的跨市域的城际混合公共交通出行快速发展，主要表现为出行范围的扩 大与出行总量的日益增加。以北京为中心的天津、石家庄环渤海交通圈，以上海、 南京、杭州构成的东部地区繁忙的交通网，以及以广州、深圳、珠海等构成的区 域交通网络，此外，中小城市的快速发展以及旅游资源的开发带动了以通勤流与 经商流、探亲流、旅游流相结合为特征的大范围的城际出行；城际交通运输需求 始终保持相对较高的增长态势，以2 0 1 0 年武汉为例，其对外铁路、公路、航空的 客运量将分别增长3 4 、3 3 和5 0 。随着社会生活水平的不断提高，人们对出行 服务水平和运输环境的要求也越来越高，不仅要求能安全到达目的地，而且还要 求快速、舒适、便捷，综合体现在出行者对经济性，便捷性和舒适性等方面的多 项指标提出了更高的要求。 另外，科学技术的日新月异和广泛应用使得交通运输业得到了快速发展，不 仅交通运输组织与管理更加完善，而且各种运输设施技术水平在很大程度上得到 了提高，例如城际高速铁路的发展，这也使得出行者在各种交通方式的选择结构 上发生了变化。因此，如何根据既有的公共交通运输资源，选择合理的出行路径 成为一个急待解决的问题。 城际多方式路径规划问题原理是运筹学中的最短路问题，与传统路径选择问 题相比较，不同点在于： 1 、城际出行依托既有公共交通方式( 铁路，航空和公路等) ，路径规划的基 础网络是服务网络而非物理网络，即两城市之间如果有路但是没有相应车次或航 班，那么这条路径是不可行的； 2 、公共交通出行需要考虑出行者不同的偏好，最短路不再是广义的距离最短， 路径权值的意义可以是出行时间、出行成本、换乘次数和舒适度等； 3 、城际出行涉及换乘，在做路径规划时要考虑出行者的心理因素，例如如何 选择符合出行习惯的换乘城市等。 本文将针对城际多方式路径规划问题的具体特点对其展开研究。 1 2 国内外研究现状 在交通运输领域中，对路径选择及优化问题的研究广泛而深入，已有方法的 很多思想可以借鉴到对城际多方式出行路径规划问题的研究中，针对本题的具体 特点，以下从路径规划问题与多式联运问题两个角度，对现有研究进行综述。 1 2 1 路径规划问题研究现状 传统的路径规划问题是指在指定的交通网络中，根据出行者提供的起讫点信 息给出快速的行驶路径，这种路径规划在车辆导航技术中的应用最为普遍，其原 理是在不同权重的条件下，求解带权有向图的最短路径问题。 文献【l 】采用标号法在多式出行网络中寻找起讫点最短路径，给出考虑出行费 用和换乘次数的可行路径集，即满足约束条件包含多种交通方式的连续路段。 文献【2 】建立了可响应不同需求的多式出行网络( m t s ) 模型，出行者可选择多种 交通方式出行，城内可选公共汽车、地铁等，城际可选铁路、公路等，文章提出 划分子网，在城际网络中将城市内节点与路段抽象成节点；给出了时间约束条件 下分层划区域的多式出行最短路径规划方法；并借助g i s 展示结果。 文献【3 】在讨论公交网络的有向线性质，即实际的公交线路是有方向的，起点和 终点决定了公交线路的行驶路径和方向，引入了新的数据类型有向线，同一公交 线路的上行线和下行线用不同的有向线来描述，通过结点索引区分线路的起始站 点、中间站点和目的站点，从而为结点赋权，弧段与属性的一对多关系被转化成 有向线与属性的一对一关系，使得属性数据的存储就克服了冗余。基于结点一弧 段一有向线的公交网的数据组织针对人们的出行理、公交线网的实际布线原则， 提出了一种在基于最短路径上对集合向外扩展、两个集合之间逐渐逼近的搜索方 法，在算法中，判断的原则是优先考虑换乘次数少的路径，在换乘次数相同的情况 下，再考虑出行距离最短。 文献【4 】提出一种分层路径规划算法，该算法利用道路网络中的不同等级特性 对路网进行分层处理，构造分层搜索策略，达到提高路径规划算法效率的目的。 最后通过在实时车辆导航系统中的应用，该算法能将路网中任意两点间的最短路 径解算时间控制在1 s 之内。 文献【5 】根据计算机图形学的理论建立了路网的模型，采用分层存储的方法， 2 并建立了包含不同图层地图数据之间的结点和路段的关联；在算法方面提出了两 种改进策略双向搜索和分层搜索，分析了改进算法的复杂度和执行效率，在 实验中比较了邻接矩阵存储结构下，单、双i f i d i j k s t r a 算法的对相同起讫点进行路 径规划，以及在邻接表数据存储结构下，比较t a * 算法与d i j k s t r a 算法对相同起讫 点之间进行路径规划的路径长度和搜索所花费的时间，得出理论值与实际值的差 距与地图的大小和形状有关的结论，最后给出了在实际导航系统中，根据地图数 据格式的不同，采用何种算法的原则。 文献【6 】主要研究动态交通条件下路径导航问题。文章考虑车辆通过某一路段 的时间特性，将实际的路网抽象成由车流通过时间相连接的路口结点集合，建立 有路段直接相连的两路口节点问车流的动态通行时间函数的集合，构建了动态路 网模型。在此基础上，使用遗传算法搜索最优路径，并进行了算例计算和分析。 文献【7 】在交通网络构建方面，将道路交叉口与路段特性( 如车道数) 发生变 化的点以及可能发生转向行为的点抽象为网络节点，将所有车道合并抽象为弧， 路段距离、行程时间为阻抗，借鉴蚁群算法，搜索最优路径。 文献【8 】主要研究公交出行路径选择问题。文中将公交站点作为顶点，对每条 公交线路，按照公交车的运行方向( 双向、上行或下行) ，在相邻两个站点之间连边 或弧，边或弧的权均为1 ，构建公交线路邻接关系图。在该图上，根据出行者的不 同需求，通过在直达关系图上定义不同的权系数，运用d i j k s t r a 算法，分别求得换 乘次数最少、出行耗时最少及出行费用最低的线路，并综合考虑出行者的需求情 况，给出出行者满意度最大的出行路线。 文献 9 】在分析公交网络特点的基础上，把空间位置相邻近的公交站点归并， 抽象成图的节点，将公交线路相邻站点间的路段抽象成边，边的权值根据路段长 度和道路的畅通情况设置；基于此网络，给出了两种路径规划的算法：一种是基 于网络变换的最短路径算法，公交网络经过网络变换，有换乘的网络问题变换为 没有换乘的网络问题，避免了计算直达矩阵与最小换乘矩阵，一种是基于前n 条最 短路径的以换乘次数最小为第一目标、出行距离最短为第二目标的路径选择模型， 并考虑乘客在步行距离范围内步行以减少公交换乘次数的实际情况，给出了一个 考虑步行换乘的双目标公交路径选择算法，并完成了公交信息查询系统的设计与 开发。 无论从研究深度还是研究广度，现有路径规划问题的研究还有很多，在网络 的构建、模型的刻画与最短路算法的选择与优化方面，一些思想可以被借鉴到城 际多方式出行路径规划问题中来，但是由于传统路径规划问题是基于路网的单一 方式出行，城市公交出行多为单目标路径规划，并且在建模时的指标选取上均与 城际出行不同，因此需要对已有方法进行改进，以适应城际出行基于服务网络、 3 涉及多种交通方式的特点。 1 2 2 多式联运问题研究现状 多式联运是由两种及其以上的交通工具相互衔接、转运而共同完成的复合运 输过程，主要指货物运输。针对多式联运网络的性质及其相关算法的研究，尤其 是寻求最佳运输路线方法的研究，各类相关文献仍涉及较少。 文献【l o 】从总费用最小为目标，建立了线性模型，该模型认为总运输费用由城 市问的运输费用和城市内的中转费用两方面构成。 文献【1 l 】提出了中转运输方式选择模型，给出了基于时间因素的多式联运方 案，主要考虑货物中转时间与节点到发时刻约束，并证明了算法的有效性与计算 复杂度，其计算复杂度依赖于节点数量与运输径路既定的到发时间。 文献 1 2 1 通过应用群集技术提出了聚类算法，用来提高网络中求解最短路问题 传统算法的计算性能。 文献 1 3 1 采用双向的研究策略来考虑多式联运网络，提出了源点和终点间运输 时间最小化条件下的最短路算法。 文献【1 4 】在r e d d y ( 1 9 9 5 ) 构建的总运输成本最小化条件下的多式联运模型基 础上提出一种求解最佳运输路线的广义最短路法，即通过构建多式联运网络多重 图，将运输过程中的数据、信息和图中的节点、边关联起来、然后对运输费用和 中转费用进行分析估计，并通过在联运网络图中加入虚拟的到、发站，使得该问 题可用d i j k s t r a 算法进行求解，从而获得广义费用最少的联运方案。 虽然多式联运涉及多种交通方式，但是以货物为主要运输对象，不会考虑出 行者的心理因素，如舒适度等；多式联运也可以采用公路自行运输，与城际公共 交通出行基于既有交通工具和车次也不是完全相同的。 1 2 3 既有研究总结 综上所述，无论是传统路径规划问题或者多式联运问题的研究，对于解决城 际多方式出行路径规划问题都有一定局限性，主要表现在： l 、在网络构建方面：自驾车传统路径规划问题是基于路网寻找距离最短或时 间最短的最优路径，任何路段都有可能作为可行路径，而城际出行是基于公共交 通方式的出行，应该以既有的车次( 航班) 为基础，构建路径规划的基础网络； 2 、出行者偏好方面：自驾车路径规划与多式联运未涉及舒适度的界定，而舒 适度是以人为出行主体的公共交通路径选择考虑因素之一； 4 3 、在算法方面：多式联运货物中转城市的选择多数费用因素，很少涉及对中 转城市客观特点的考虑，如城市交通规模等。 1 3 研究目的与研究意义 本文在已有研究的基础上，针对本题城际、多方式以及基于出行者偏好的具 体特征，研究城际公共交通出行路径优化方法，试图达到以下几个目的： 1 、从理论上进一步深入对城际多方式出行路径规划问题的分析，为了避免基 于物理网络做路径规划出现有路无服务的情况，本文将基于既有城际出行服务构 建城际多方式出行网络，并对其进行数学描述； 2 、在模型方面，针对城市出行，选择合理的量化指标，试图描述出行者对快 速、经济、少换乘及舒适的不同需求，建立基于出行者不同偏好的城际出行路径 优化模型； 3 、在算法方面，针对d i j k s t r a 算法在大规模网络搜索时的不足，提出划分区域 的路径规划算法，在保证结论精确性的同时提高搜索效率； 4 、选取适当城市及之间车次( 航班) 信息作为实例验证输入数据，程序实现 算法给出路径规划结果，使用g i s 展示，对算法可行性和有效性进行验证。 通过本文的研究，可以从大范围、多方式方面给出路径规划方法，进一步丰 富和完善路径规划理论；在实际应用方面，能够从交通方式及中转城市的选择及 节约出行时间与出行成本的角度，给出行者提供决策支持，对于交通信息化建设 的实际问题起到了指导作用。 1 4 论文研究内容与技术路线 在了解现有研究对城际多方式出行路径规划的适用性与局限性后，本文研究 主要存在以下重点和难点： 1 、如1 1 分析，城际多方式出行基于既有交通方式和载运工具，而非物理路网。 因此，如何对既有研究中网络构建的方法进行改进，根据既有出行服务构建城际 多方式出行网络，体现多种交通方式，并对其进行数学描述，是本题研究的首要 问题； 2 、解决以人为出行主体的路径选择问题，需要考虑如何刻画影响出行方式与 路径选择的出行者主观因素，既有相关研究多为城市公交出行路径选择中对出行 偏好的刻画，其量化指标与城际出行不尽相同。因此，针对城际出行，对出行者 的不同偏好构建模型是本文研究的重点之一； 5 3 、比较其它最短路算法j 考虑至1 d i j k s t r a 算法求解的精确性，本文拟采用其作 为城际多方式出行路径规划问题的求解方法，但是对于大规模网络最短路问题， d i j k s t r a 算法在搜索效率方面存在不足之处，因此，需要对求解过程进行改进，给 出适用于城际多方式出行路径规划问题求解算法。 基于以上几点，论文的研究内容主要包括： 1 、城际多方式出行网络的构建。对实际出行过程进行分析，构建城际多方式 出行网络，建立数学模型； 2 、基于不同偏好的城际多方式出行优化模型研究。在分析出行者对时效性、 经济性、便捷性、舒适性等不同需求的基础上，分别对其进行数学刻画，综合考 虑以上四种因素，给出广义费用最小的出行路径优化模型； 3 、城际多方式出行路径规划算法研究。分析d i j k s t r a 算法特点及对本文研究的 适用性与局限性，提出划区域求解的方法，给出算法思路与流程： 4 、实证分析。依据既有城市与城市间部分车次( 航班) 信息，对算法进行实 现与验证。 论文研究的技术路线如图1 1 所示： 网络的 l基于服务构建城际多方式出行网络 构建 千千 以城市为节点 以车次( 航班) 为弧 之乡 不同 基于广义费用最小的城际多方式出行路径优化模型 出行 偏好 时问费用 经济费用 换乘赞用 i 舒适性费用 的刻画 之乡 聚类分析 - l 划分区域 上 路径选取核心城市卜 i 重心法 规划 + 算法 区域问路径规划区域内路径规划 上 i 合成结果i 图1 1 论文技术路线 f i 9 1 1t h e t r a i no f t h o u g h ti ns t u d y 6 2 城际多方式出行网络分析与构建 在城市道路自驾车路径规划问题中，车辆始终沿道路行驶，因此可以直接根 据道路网来建立路径规划的网络模型，但在城际多方式出行中，铁路、航空及公 路客运是主要交通方式，而铁路网、航空网并不像城市道路能随时承载运输，而 是按既定的时刻表运行，若仍以物理路网作为路径规划的基础网络，会出现有路 无服务的情况。因此，城际多方式出行路径规划必须以车次、航班及班次为对象 进行新的网络构建。本章在分析城际多方式出行过程和网络特性的基础上，基于 服务，给出网络的构建过程与数学描述，为城际多方式出行路径选择目标的刻画 奠定基础。 2 1 城际多方式出行网络特性分析 城际多方式出行依托铁路、航空、公路客运等既有交通方式，仅以城市间物 理网络作为路径规划的基础网络具有一定局限性，因为既有公共交通方式出行区 别于自驾车能够随时行驶于道路上，铁路旅客列车、长途客运巴士等载运工具的 运行是基于物理网络( 如铁路线路、城际高速公路) 之上的，具有既定到发时间。 因此为了给出行者提供可行接续的出行路径，需要基于已有服务信息( 如车次、 航班) 构建城际多方式出行网络，以下对城际出行过程进行分析，以确定城际多 方式出行网络定义与形式以及其需要包含的信息。 假设出行者从城市a 到达城市b ，铁路时刻表、民航航班计划与公路客运班次 中城市a 、b 间的车次( 航班) 信息如表2 1 所示，其中a l 、a 2 、a 3 为城市a 可选的 交通出入口，即车站( 机场) ，b l 、b e 、b 3 为城市b 可选的交通出入口，c 卜c 2 分 别代表可中转城市c 的车站( 机场) ，d 卜d e 分别代表可中转城市d 的车站( 机场) ， e l 、e 2 分别代表可中转城市e 的车站( 机场) 。 表2 1 城市a b 间车次( 航班) 信息 t a b 2 1t r a v e li n f o r m a t i o nb e t w e e naa n db 车次( 航班号)交通方式始发城市始发站讫点城市终到站 1 公路城市a a 3城市bb 3 2铁路城市a a i城市cc l 3 铁路城市a a l城市dd l 4航空城市a a 2城市cc 2 5航空城市a a 2城市dd 2 7 车次( 航班号)交通方式始发城市始发站讫点城市终到站 6铁路城市c c l城市bb l 7航空城市c c 2城市b b 2 8铁路城市d d t城市ee l 9航空城市d d 2城市ee 2 l o铁路城市e e l城市bb i 11航空城市e e 2城市bb 2 假设城市a b 间城际公路物理网络如图2 1 所示，节点代表城市，弧段代表城市 间有省际公路连接。 图2 1 城市a b 间物理网络不意图 f i 9 2 1t h es k e t c hm a po f p h y s i c a ln e t w o r k b e t w e e naa n db 如图2 1 所示，既有的物理网络并不包含公路客运班次的服务信息，如果基于 物理网络做路径规划，会出现有路无服务的情况，例如城市a e 间虽然存在物理路 径，但是在表2 1 城市a b 间车次( 航班) 信息中，并没有由城市a 出发到达城市e 的班次，因此，仅仅基于既有物理网络做城际多方式出行路径规划并不能满足需 要，由此我们认为，城际出行路径规划基础网络应该包含城市及所有连接城市既 定车次( 航班) 信息，这也正是城际多方式出行网络的定义，基于此，本文试图 构建城际多方式出行网络来解决城际出行的路径规划问题。 由表2 1 可得城市a b 间出行信息示意图如图2 2 所示，节点代表城市，弧代表有 车次( 航班) 经过，不同线形的弧段代表不同交通方式。 8 公路 铁路 航空 中转城市c 市b 图2 2 城市a b 间出行信息示意图 f i 9 2 2t h es k e t c hm a po f t r a v e li n f o r m a t i o nb e t w e e naa n db 由图2 2 可以看出城市a b 间有以下不同的出行路径，可行路径的表现形式为起 讫点城市间既有的可接续的车次( 航班) 的组合，如图2 3 所示： , 2 - 一 一一一一 叫一 一一一一一 图例 公路 铁路一一一一一+ 航空 图2 3 城市a b 间可行路径示意图 f i 9 2 3t h es k e t c hm a po ff e a s i b l ep a t h sb e t w e e na a n db 9 9 对于一对起讫点城市，其间可以有若干个可行路径，那么，如何根据出行者 自身的偏好( 快速、经济等) 选择较优的出行路径，就归为在不同权重条件下， 求解有向图的最短路问题。因此，要解决城际多方式出行路径规划问题，首先要 构建路径规划的基础网络。 城际多方式出行网络包含了铁路旅客列车运行图、民航航班计划和公路客运 班次的全部信息，可以描述实际的城际出行过程。另一方面，城际多方式出行网 络应该建立于物理网络之上，即有车必有路。城际多方式出行网络以城市为节点， 以城市间车次( 航班) 为弧，与实际的物理网络布局一致，但是节点之间可以有 多条弧，来体现连接两城市节点的不同车次( 航班) ，表示两城市可基于既有交通 方式通达，弧的方向由车次( 航班) 起点城市指向终点城市，弧上权值可以代表 任何含义( 运行时间，成本等) ，通过权值的选择表征出行者的不同偏好，这样基 于服务构建的城际多方式出行网络，不仅能够体现城市及连接城市的车次( 航班) 的所有信息，并且能够根据弧段权值的不同意义与取值，刻画出行者的不同偏好， 采用合理的算法，寻找符合不同出行偏好的较优路径。 2 2 城际多方式出行网络构建 如2 1 所述，在城际多方式出行网络中，节点代表城市，弧代表连接城市的既 有车次( 航班) 。目前，作为城际出行可选的常规交通方式有铁路、航空、公路三 种，即城际多方式出行网络包含铁路旅客列车运行图、民航航班计划与公路客运 班次的所有信息。然而，由列车运行图、航班计划与客运班次分别构成的铁路网、 航空网与公路网是相对独立的，而且其中节点均为车站( 机场) 等交通出入口，而非 城际多方式出行网络中的城市。因此，以如下思路构建城际多方式出行网络：以 铁路旅客列车时刻表、民航航班计划与公路客运班次分别构建铁路网、航空网与 公路网，再对其进行叠加，将隶属同一城市的交通出入口，即车站( 机场) 归并 为城市节点，构成城际多方式出行网络。以下就构建依据以及构建过程进行说明， 并给出其数学描述。 2 2 1 城际多方式出行网络构建依据 如上所述，城际多方式出行基于铁路、航空与公路客运三种交通方式，因此， 要为城际出行者提供较优的出行路径，需掌握以下交通方式的服务信息： 1 、铁路旅客列车时刻表。根据列车时刻表获得旅客列车的车次、始发站、终 到站、中间停靠站、到达每个站点的时刻和从每个站点出发的时刻、每个区间的 l o 运行时间以及各车次的席别及票价； 2 、民航航班计划。根据民航航班时刻表获得航班号、始发站、终点站、起飞 时刻、到达时刻、座舱等级及票价； 3 、公路客运班次。包括行车路线、发车时间、终到时间、途经站以及每个班 次席别及票价。 基于以上信息，分别构建铁路网、航空网和公路网，再对其进行叠加，形成 城际多方式出行网络。 2 2 2 城际多方式出行网络的构建过程 如2 2 1 分析，首先根据铁路旅客列车运行图构建铁路网，由列车运行图可以 获得的信息如表2 2 所示： 表2 2 铁路网构建基础数据 t a b 2 2b a s i cd a t ao fr a i l w a yn e t w o r k 车次始发站终到站发车时间运行时间( 小时) 2 a lc i 8 ：0 0 4 3 a td i 9 ：0 03 6 c lb l 1 0 ：0 06 8 d ie i 1 3 ：0 02 1 0 e lb i 1 4 ：0 03 如图2 4 所示为如何由一条记录转化为一条弧段的过程，以始发站与终到站建 立节点，车次、发车时间与运行时间为弧的属性，图的下部分为弧段示意图，弧 上括号为其属性集合，其中信息表征其车次、发车时间、运行时间等属性值。需 要说明的是，对于非直达有中途停靠站的车次，分别以各停靠站为始发站和终到 站建立弧段，表征停靠站间有车次通达，弧段属性设置同上。例如车次t l 由北京 西站始发终到长沙火车站，途径石家庄、郑州，那么以石家庄、郑州分别建立节 点，北京西至石家庄、北京西至郑州、石家庄至郑州、郑州至长沙分别建弧，表 示有车次通达。 妒一一一一一一一峋 ，2 ，一峥一、6 、 呼 、 、 j ，) 协7 8 、兮1 。 表2 3 铁路网节点与弧属性表 t 抽2 3t h ea t t r i b u t e so fn o d ea n da r ci nr a i l w a yn e t w o r k n o d e l dn o d e n a m e e d g e l is t 节点属性 1 1 0 0 0 0 1北京西k 2 7 9 ，t l n e t w o r k e d g e i d s t a r t p o i n t e n d p o in ts t a r t t i m e b e l o n g t o 弧属性 d 7 0 3 lr a il w a y n e t w o r k广州东深圳1 4 ：2 0 e n d t i m er u n t i m es e a t l i s t p r i c e l i s t w e i g h t 1 5 ：2 21 1 硬座，软座7 5 ，9 5待定 同以上过程，根据表2 1 中民航航班信息构建航空网，如图2 6 所示，其中a 。， b 。，c ：，d 。，e ：分别代表机场，弧段代表有航班通达。 1 2 一一吣沙一 萝 叭一 图2 6 航空网示意图 f i 9 2 6t h es k e t c hm a p o fa i rl i n en e t w o r k 为方便起见，弧上未标注其属性信息。实际航空网弧的属性如表2 4 所示。 表2 4 航空网节点与弧属性表 1 a b 2 4t h ea t t r i b u t e so f n o d ea n da r ci na i rl i n en e t w o r k n o d e i dn o d e n a m e e d g e l is t 节点属性首都国际 1 1 0 0 0 0 5 c z 3 1 9 2 机场 n e t w o r k e d g e l d s t a r t p o i n te n d p o i n ts t a r t t i m e b e l o n g t o c z 3 1 9 2a i 订i n e n e t w o r k 首都国际宝安国际 弧属性机场机场 1 1 ：0 0 e n d t i m er u n t i m es e a t l i s tp r i c e l i s t w e i g h t 头等舱 2 6 3 0 1 4 ：1 53 4 2 待定 经济舱 1 7 5 0 公路客运网络建立过程与铁路网航空网相同，不再赘述。实际公路客运网上 节点与弧段属性如表2 5 所示。对于有途经站的班车，处理方法同铁路网有中途停 靠站的车次。 表2 5 公路客运网节点与弧属性表 t a b 2 5t h ea t t r i b u t e so f n o d ea n da r ci nh i g h w a yn e t w o r k n o d e l dn o d e n a m e e d g e l i s t 节点属性木樨园 1 1 0 0 0 0 7l l o o 长途站 n e t w o r k e d g e i d s t a r t p o i n te n d p o i n ts t a r t t i m e b e l o n g t o 木樨园天津客运 弧属性1 1 0 0 h i g h w a y n e t w o r k 1 4 ：0 0 长途站西站 e n d t i m er u n t i m e s e a t l i s tp r