城市公交网络出行路径选择的计算机算法研究

摘　要：随着经济的发展以及城市居民的生活质量的提高，外出购物、访友、娱乐等活动成了人们不可缺少的与日常活动，因此，与人们出行息息相关的公共交通工具也受到前所未有的挑战，为了提高公共交通的使用效率为人们带来便利以及缓解交通拥堵的现状，公共交通工具的充分、合理、规范化的出行路线的制定是解决问题的关键。本文比较了BP神经计算机模型、时间链公交计算机模型、二分图模型以及Branch-Cut 计算法、蚂蚁计算法的优缺点，为制定正确的公交路线提供依据。

关键词：公交网络；路径选择；计算方法

1. 前  言
　　伴随人们消费水平的迅猛增长出现的各能源价格飞速上涨以及城市的空气质量日趋下降的问题，大力倡导节能、环保的理念已成为时代的主题，以在各大城市中广大市民出行首选的公共交通工具为例，公共交通不仅可以节省时间、减少开支，还可以节约能源、缓解交通拥堵的难题。因此，在一些大、中型城市中公共交通的覆盖范围和运行数量在不断的扩大，交通工具也由相对比较单一的公共汽车发展到高速、节省空间的轻轨、地铁等多种出行选择。人们出行次数的增加以及出行理念的改善在给公共交通工具带来发展机遇的同时，也对公共交通的正常、快捷、高效的运行带来巨大挑战，这就要求公交网络的设计更人性、更合理、更完善。
　　
　　建立最简便有效的最有公交路线的设计规划成了热点话题，不同学者对于"最优"的理解含义不同，可以从不同角度出发选择不同的最有公交网络出行路线的计算方法，最优路线的理论研究主要包括公交网络的数学模型描述和设计最优路线的算法。在数学描述方面，Qiu-jin Wu等利用图论中的K最短路径算法求解出公交网络中多路径优化问题的答案；Choi等讨论了如何利用GIS技术，从街道的地理位置设定公交线路和站点的问题；而Anez等对于用偶图描述公交路线的可能覆盖范围，为人们找出更多的可能性。在设计最优路线方面，Konez等提出了以换乘次数少为主要目标，以出行距离短为次要目标的一种公交网络路径选择算法；除此外还有Floyd算法、Dijkstra算法、Moore-pape算法、二分图发、BP模型法、蚂蚁计算法等。
　　本文首先对公交网络进行了系统描述，继而分析了公交乘客出行时所面临的各种重要因素，从换乘次数、途径站点、出行耗时和出行费用等进行考虑，比较了不同最优公交路线选择的计算方法的不同特点。
2. 公交网络的特点
　　公交网络跟计算机网络一样，具有拓扑性质。公交网络尽管依附于路网，但又与网络有区别拥有自身的特点。
2.1 时间特性--公共交通一般具有固定的时间表，但也受实时交通状况等因素的影响。
2.2 换乘特性--公共交通共具的换乘包括同站间的换乘和异站间的换乘，同站换乘需要考虑到诸多站点内部的细节；而异站换乘则需要建立各个站点之间的相互连接，而且换乘需要付出时间、金钱等代价。
2.3 有向性--完整的公交路线大体上分为上行和下行两个空间叠加的行驶方向，一般不同方向具各自的运行时间表和行驶站点分布，甚至不同的行驶线路线。
2.4连通性--单独的公交线路并不具备连通特性，只有当与换乘连接弧段一起的时候才能组成完整的连通公交网络。
3.公交网络出行路线选择的方法研究
3.1时间链公交网络数据模型计算
　　伴随人们日常节奏加快的现象，本方法将时间作为人们选择出行最主要的考虑因素。从人们出行时间链的视角出发，可以把影响出行意愿和偏好等不同类型的因素（如目的距离、换乘次数、等车时间、距离车站的远近等）折换成时间，并且用时间作为唯一的主要影响因素进行计算。由于公交网络中时间链的复杂程度较高，从时间链的视角出发建立公交网络模型较少。
相对时间是指人们出行的持续时间，它是一个相对完整的出行时间链，有4种因素决定：T=Twalk + Twait + Tv + Ti  
其中Twalk 代表步行时间，是人们距离公交站点所花费的时间。Twait  代表等车时间，Tv 是实际乘车时间，Ti 是换乘所消耗的时间，包括上下车、各站点步行所需时间。
　　上述公式即为公交出行时间链，乘客每次出行即完成一个出行时间链。由此可以用以上4种时间的总和考虑不同出行方式的花费，进而求出最优路径。因为换乘需要较高的时间代价换取（上下车、步行和等车等花费的时间），除非换乘直接到达的车次，缩短路线，节省更多的时间，否则人们轻易不会换乘车次。乘客的步行时间主要由出发地、目的地到车站的距离决定，人们的步行速度相差不大是一个定值，因此距离的长短成了主要的因素；而乘客等车时间则与发车频率、停车耗时、交通的通畅度等因素有关，一般用发车间隔的一半来表示；车辆的行驶时间与路段上公交路线和车速大小有关，常用公交线路运行距离与平均车速的比值表示；换乘时间主要由上下车时间、换乘距离、换乘数等决定，一般用换乘距离与步行平均速度的比值表示。
　　本方法是一个相对简洁的网络公交路线选择的方法，适用于人口密度较小的中小型城市的公交规划。
3.2 二分图法计算模型
　　二分图是一种不论在理论研究或是实际应用中都具有丰富意义的特殊模型。在二分图中，所有站点都被分割为两个集合M和N，其中M或N中任意两个在同一集合中的点都不直接相连。本方法运用标有站牌号的二分图对公交网络进行建模，并结合此模型和站点网络图给出最佳出行路径的计算方法。
　　公交网络二分图模型是包含线路和站点集合的网络，若某条线路经过某些站点，则将站点间用一条无向线段相连。公交系统二分图模型是将标有站牌号的站点与线路之间用一条赋予数字(数字表示该线路经过该站点时的站牌号)的无向线段相连。并与站点网络图选择两站点间最优出行路径的算法和选择方案。从乘车的方案看，二分图算法还可以展示出整条换乘线路。
3.3 分支一切割法计算模型
　　分支一切割法即Branch-Cut algorithms 法它是一个求解混合整数规划的成功模型。它首先由Grotchel、Junger和Reinelt等人应用线性排序解决大规模混合整数规划难题，以提高分支运行效率的方法。
3.4  BP计算模型
　　BP计算模型即误差反向传播神经网络模型，它是人工神经网络ANN模型中使用性能最优越的一款计算方法，它是以MATLAB环境下开发的ANN工具为运行背景，具有预测分析各交通分区现状及不同因素变化下的公交出行比例的功能，该方法不需要详细分析各变量之间的相互影响，尤其是数学关系，减少很多不必 要的琐碎复杂的因素，该方法还具有简易的学习过程，并不需要很多的训练样本数据，而取得较好的预测结果。
3.5 蚂蚁算法
　　蚂蚁算法最早是由意大利学者M．Dorigo等人提出的模拟生物世界中蚂蚁觅食行为的仿生类算法。它是一种新的本质上并行和随机搜索的优化算法，具有很好的灵活性、分散性和自发组织性。考虑到城市道路结构复杂，公交线网规划考虑的因素众多，特别是直达客流量的影响，这一系列特征正好与蚂蚁觅食的现象相似，公共密集场所如市中心、商业区等正如蚂蚁的巢穴，蚂蚁每向前行走一步，对应公交网络中从一个节点到另一个节点。蚂蚁在路径上留下的信息素，对应于网络从一个状态变化到另一个状态，路段的权值发生的变化。
4. 结 语
城市网络交通的便利畅通与否，与人们的日常生活息息相关，为使人们的生活工作出行的便捷、准确、安稳，网络交通的人性化、合理化的计算规划十分重要，伴随时代进步的脚步，公交网络出行路线的计算机选择也正日新月异，提出不同的计算方法，没有最好或者最优的计算方法，只有根据当地的影响因素设定最适合的路线才是人们所需求的。

参考文献：
[1] 公交出行完整路线计算方法研.刘岳峰,张 鑫,孙华波,刘 婷
[2] 公交最优路径选择的数学模型及算法.雷一鸣.广东工业大学
[3] 公交网络最优路径选择算法研究.陈小辉.榆林学院计算机与网络工程系
[4] 大城市公共交通网络最优路径算法研究.鄢勇飞.武汉理工大学