基于城市公交系统的最优换乘线路策略研究 |
| 2013-04-15 17:30 作者：杜利明 来源：硅谷网-《硅谷》杂志 HV： 编辑： 【搜索试试】
|
|
硅谷网文 据《硅谷》杂志2012年第23期刊文称，针对乘客选择出行公交线路的问题，对较完善的城市公交系统进行分析研究，建立城市公交系统时间、费用及综合最优模型，给出时间、费用及综合浪费度的定义，基于Dijkstra最短路径算法思想，提出综合最优模型下的换乘策略算法，该算法为出行者提供最优公交线路的选择策略。
关键词：公交线路；浪费度；Dijkstra算法；最优换乘
0引言
随着我国城市经济的发展、规模的扩大以及人口的增长，城市交通问题日益突出。城市公共交通运输以其覆盖面广、经济、快捷的特点，成为绝大多数出行者的首选方式，也是各地城市政府大力发展的一种交通方式。然而随着城市公共交通系统的发展，城市交通路网逐步形成并越来越复杂化，线路之间的耦合度也随之变高，乘客在出行过程中如何选择换乘线路成为一个重要的研究内容，国内外许多学者在这方面做了大量的研究，取得很多成果。1989年SpiessH.FlorianM通过对公交网络出行策略理论进行研究，提出由发车频率的高低决定出行策略的解决方法。
2004年Gentile等人在前人理论的基础之上提出了公交乘客路径选择算法，这种方法有着很大的优势，能在站点实时信息条件下得出优选路径，大大提升了站点选择的精度和效率，也为进一步优化公交路径选择的智能化夯实了基础。国内不少学者也对线路最优策略方面的问题进行了研究[1-8]，其中文献[1]提出了一种便于乘客进行路线选择的最少换乘算法，并探讨了以换乘次数最少为目标的公交查询方案。运用Dijkstra标号法的推广算法和线性规划理论，文献[5]建立了已知公交起点站到欲到达的公交目的站的最优线路数学模型。上述研究的最优出行线路主要考虑最少的换乘次数或者最短路径下的最优方案，然而现实中随着城市公交系统的发展，换乘次数已不是主要问题，因为多数城市交通系统能够保证在很少的换乘次数后，能够由出发站点到达目的地，另一方面，只追求路径最短也不一定是最优的线路选择方案，有些乘客比较关心时间问题，有些乘客比较关心费用问题，有些可能同时考虑各种因素的最优。通过以上分析，可以看出基于时间最优、费用最优以及综合最优条件下的城市公共交通换乘策略的研究有重要的研究价值，就目前所查阅的资料来看，这方面成果较少。本文首先对城市公交系统进行建模，首先考虑城市公交系统只包含公共汽车线路的情况，给出时间最优模型、费用最优模型以及综合最优模型，并给出换乘策略及算法，然后考虑了城市公交系统中包含地铁的情况，综合考虑了乘车时间、乘车费用、换乘等待时间以及乘客乘车指数等因素，给出相应模型描述及算法。
1城市公交系统模型分析
在进行模型分析之前先做适当的模型假设：
1）相邻公交站平均行驶时间不变；
2）交通情况良好，无堵车及车辆损坏等意外情况发生；
3）设各种交通工具的换乘时间保持不变；
4）将换乘次数这一因素作为第一约束目标，其次考虑路程和费用等因素；
5）公交环行线是单向行驶，地铁环行线是双向行驶；
6）根据实际情况，如果出行过程中转乘次数太多，会增加出行复杂度，而且通过2次换乘能到达目的地，两次以内换乘比较合理，超过两次不予考虑；
7）对于车次不同票价不同的理解，以沈阳为例，公共汽车大多为无人售票，个别公共汽车采用6站1元的计费方式，地铁采用阶梯计费，综合统计公交线路费用有1元、2元、3元、4元的几种情况。
下面给出公交系统网络拓扑结构图，如图1所示。
在该网络拓扑图中，假设为源节点，为目标节点，其他站点看作拓扑图中的子网节点。位于第一维子网的站点表示与初始站点有公交线路直接相通，即可直达，位于第二维子网的站点表示与初始站点没有直达公交线，而与之间有直达，故初始站点需要在第一维子网中转站一次，才能到达，同理对于，初始站点需要转站二次才能到达。由假设1可知，乘客最多转乘两次，所以在依据实际公交系统建立的拓扑图中，最多只有两层子网。
说明1：为保证处理后的数据具有科学性与合理性，需要删除一些不符合实际的所有线路。有些线路虽然转多次车能到达，但现实中由于线路转车需要额外的时间与费用成本，而且转乘太多，市民多会选择其它方式出行，故这样的情况是不可取。
对乘客来说，每条选出的线路包含初始站乘车线路、中转站站号、转乘线路、所乘车经过站点、转乘次数等信息。考虑到不同查询者的需求不同，我们分别建立了时间最少模型和费用最少模型。
1）时间最少模型
总耗时为转乘所花的时间、乘车所花时间的、起始等待时间三者之和：
（1）
（2）
其中表示转公交次数，表示相邻公交站平均行驶时间，表示公交平均换乘时间，表示途经的站点数，为起始等待时间，其中与表示公交线路中站点顺序编号。
2）费用最少模型
总费用为所有乘车花费的总和：
（3）
其中表示在第条线路上经过站所需的费用，售票方式为。
3）综合最优模型
考虑到人们对公交的综合要求，需要对费用和耗时进行综合考虑，给出一个更为满意的折衷方案，既要使花费相对较少，又要使耗时相对较少。
首先给出时间浪费度、费用浪费度和综合浪费度的概念。
定义1：时间浪费度
（4）
其中表示第条线路所花费的时间，表示所有方案中的最少耗时，表示最大耗时，越大表示时间的浪费越多。
定义2：费用浪费度
（5）
其中表示当前线路所需的费用，表示方案中的最少费用，表示方案中的最大费用，越大表示费用的浪费越多。
定义3：综合浪费度定义为两个浪费度的加权求和：
（6）
其中加权系数可以由用户根据自己的不同偏好进行调整。
由此可将综合最优模型描述为
（7）
该模型以综合浪费度作为评判线路优劣的标准，当综合浪费度越小，在时间和费用上都同时取得了相对最优。
2模型的进一步推广
城市公交系统的进一步发展，城市公共交通除了公共汽车外，其它的公共交通手段也越来越多，本文中以公交系统中包含地铁情况为例进行分析。由于换乘地铁所需的等待时间、乘车时间、计费方式等因素与公共汽车不同，乘客对不同的交通工具有不同的喜好选择，综合考虑各种影响因素，给出下面的模型描述。
2.1时间最小模型
总耗时为转乘所花的时间（其中包括公交-公交、公交-地铁、地铁-公交、地铁-地铁）、乘车所花的时间、起始等待时间三者之和：
（8）
（9）
（10）
其中表示地铁转乘公交的次数，表示地铁所经过的站数，其中与表示公交线路中站点顺序编号，表示地铁转乘地铁的次数，表示公交转地铁的次数，为只乘坐公交相邻两站的平均时间，为只乘坐地铁相邻两站的平均时间，、、与分别为乘客的各种转乘需要的单位时间，假设起始站点为公交车站而非地铁站。
2.2费用最少模型
查询者所乘车的路线所需的费用可用下式表示：
（11）
式中的意义与公式（3）相同，但是售票方式不仅包含公共汽车的多种计费方式，也包含地铁的计费方式。
2.3综合模型
计算乘坐地铁所需的时间和费用，将地铁视为公交，把地铁的时间和费用等数据加入到公交系统，再加入公交和地铁选择的乘车指数，和公交同时做最优化，做出不同需求下的最优线路，得出综合浪费度计算公式
（12）
其中表示第条线路的时间浪费度，表示第条线路的费用浪费度，表示第条线路的乘车指数，代入综合最优模型公式（7）中，当综合浪费度最小时，乘车方案取得了相对最优。
3最优换乘策略算法描述
根据公交网络系统本身所具有的连通性、节点性以及有向性等特点，本模型将把公交或地铁车站各站点抽象为点，公交线路抽象为线，从数据结构的角度，将研究的问题抽象为图论中赋权有向连通图的问题。
1）将实际公交线路图含有的所有信息提取出来，抽象成一个加权图。公交线路上的站点对应于图中的一个点，点需要包含以下信息：
①所对应公交站点的实际名称；
②到达此站点花费的费用；
③站点位于当前线路站点数；
④入点和出点，即所有到达站点的线路与所有从站点出发的线路；
⑤到达此点所选择的交通工具。
公交线路中相邻两站的线路在图中表现为赋权的边，边应包含的信息有：
①边的权值；
②边连接的两个点。
2）基于最优路径的算法理论基础[11]对上述网络图的每条边，给定权。对中的任意一条有向路，定义的长度为：
（13）
式中，权的处理与基本模型类似，是关于相对时间浪费度，相对费用浪费度，乘车指数加权后的一个函数：
（14）
其中
设网络图顶点为查询者给的初始站点，到其它顶点的最短路长度按大小排列为：
（15）
其中，表示到本身的最短路长度。记，则
（16）
公式（16）中不搜索重复点，取达到上述最小值的点为，与此同时在算法中对每一点增加一个前点标记，并且记录边中所包含的信息。
以上分析只适用于一般赋权有向连通图，在乘车问题中还要考虑车辆转乘这一因素。倘若这个点位于多条线路的交叉处，即有多条线经过点，表明站可以换车。那么要保存可换乘车的车次以及换乘车次的相关信息，这样给存储数据带来了极大的不便。也就是对于经过的不同线路，都分配一个虚拟的点，这些虚拟的点只是为了存储数据的方便，实际上共同对应的是公交线路上的一个站点。由上面分析可知，所有边均是有向的，对于有两条线通过的点应扩展成四个点。四种不同的转乘信息分别是：、、、。
经过处理后，每条线路中不用考虑转乘影响。因此可得与间的最短长度。对于以后求出的，一律记为。而采用“标号”方法对它们加以区别，属于的点给予“永久”的标号，对应的的值是到点的最短路长度；不属于的点给予“临时”标号，对应的的值是计算的中间结果，供进一步计算时使用。当每个顶点都得到永久标号时，算法结束。
4结束语
本文对城市公共交通系统最优换乘策略进行了分析研究，首先考虑了公交系统中仅包含公共汽车的情况，给出了时间最短模型、费用最少模型、综合最优模型，在此基础上基于算法思想，同时考虑公共交通系统中存在公交与地铁线路的情况，通过分析研究给出时间最短模型、费用最少模型、综合最优模型描述，给出任意两站点间最优线路选择算法描述。 |
|
|
|
【对“基于城市公交系统的最优换乘线路策略研究”发布评论】 |
版权及免责声明：
① 本网站部分投稿来源于“网友”，涉及投资、理财、消费等内容，请亲们反复甄别，切勿轻信。本网站部分由赞助商提供的内容属于【广告】性质，仅供阅读，不构成具体实施建议，请谨慎对待。据此操作，风险自担。
② 内容来源注明“硅谷网”及其相关称谓的文字、图片和音视频，版权均属本网站所有，任何媒体、网站或个人需经本网站许可方可复制或转载，并在使用时必须注明来源【硅谷网】或对应来源，违者本网站将依法追究责任。
③ 注明来源为各大报纸、杂志、网站及其他媒体的文章，文章原作者享有著作权，本网站转载其他媒体稿件是为传播更多的信息，并不代表赞同其观点和对其真实性负责，本网站不承担此类稿件侵权行为的连带责任。
④ 本网站不对非自身发布内容的真实性、合法性、准确性作担保。若硅谷网因为自身和转载内容，涉及到侵权、违法等问题，请有关单位或个人速与本网站取得联系（联系电话：01057255600），我们将第一时间核实处理。
|
|
|
|
