公交换乘算法研究

《公交换乘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、公交换乘算法研究任轶（北京灵图软件技术有限公司，北京100094,renyi@lingtu.com）摘要：随着城市交通状况的日益恶化，以及政府“节能减材”口号的提出，社会的目光慢慢集中到公共交通上面，如何提供优秀的公共交通换乘方案，成为GIS行业日益关心的问题。本文根据公交的实际情况进行分析，从而引出符合实际情况的公交换乘算法，并对算法中计算可达路由部分以及线路评估部分进行详尽的论述。关键字：公交换乘算法地理信息系统1.公交换乘的现实特点1.1使用公交线路的特点对于实际乘车的用户来说，享受公交服务是一种

2、被动式的，即使已经确认了换乘方案也不可能像使用导航产品的用户那样可以立即主动沿着导航线路开车到达目的地，而是要在车站等待公共汽车的到达。所以一条线路的快捷与否不仅与它途经道路的拥堵状况和车速有关而且还和他的发车间隔有相当大得联系。更一步的由于几乎所有的线路都有运营时间，如在上午9点在北京乘公交车可以到达任意的地方。但是夜里23点左右的时候，基本上就没有公交可以乘坐了。而使用导航服务的用户就不需要考虑这点。线路和线路之间虽然起始点和终点不同，但是会有很多线路会有一部分的途径线路相同或者都经过提供相同起点和

3、终点，那么对于有这种需求的用户来说乘哪辆车都是一样的。1.2换乘的特点不同于道路网图，如果b线路与a线路在空间上相交，那么就可以由a线路驶入b线路中。即使公交线路b与公交线路a在相当长的距离上行驶同一条道路上、空间上重合，也不可以判定公交线路b与公交线路a有换乘关系。公交线路之间的换乘关系只能在车站与车站之间发生。一般来说如果车站和车站空间位置上重合，那么可以认为有换乘关系。其次如果两个站点之间步行在用户忍受范围内，我门也认为是有换乘关系的，值得注意的是大部分时候，考虑实际道路环境的复杂性步行距离和空间

4、距离是不对等的。比较经典的例子是两个站点之间被一个主干道隔离，那么用户不得不绕行通过地下通道或者过街天桥来达到相关站点。1.3用户的体验的特点对于用户来说他们总是期望换乘站点是个“大站”，如北京的西直门。因为在大站的话可以选择的车辆很多而减少候车时间。换乘时候对步行距离的忍耐程度也会因为所换乘车辆的不同而不同，比如在中关村软件园工作的员工，一般都喜欢走1到2公里取西二旗地铁站乘坐城铁，如果是其他换乘其他车辆的话，1到2公里明显超出了用户的忍受范围。而且对于用户来说从出发点走到第一条线路的上车站点的容忍程

5、度要大于中间换乘时候的步行距离。1对于用户来说换乘一次是一个很大的乘车开销，距离最近、时间最短的但是需要多次换乘的线路，往往不能被用户接受。1999年在南京市的8个主要公交站点进行了一次公交乘客出行心理问询调查，共得到有效[1]表格440份。图是调查结果。50%41.16%40%30.93%30%18.60%20%9.30%10%0%路程最短时间最短换乘最少其他图1南京市公交乘客出行路径选择因素由图可见，41.16%的乘客在选择出行路径时首选考虑的是换乘最少，其次才是时间最短、路程最短。从调查得到仅有3

6、0.70%的乘客不用换乘，31.40%的乘客需换乘1次，26.98%的乘客需换乘2次，13.26%的乘客需换乘2次以上才能到达终点。2.路线可达算法的分析以及实现2.1公交换乘网络的抽象公交换乘网络可以抽象为以各条线路为有向边，以可换乘站点对为节点的有向图。那么公交换乘问题就可以抽象为解决如何取得从公交网络有向图的一个节点到另外一个节点的换乘方案集。2.2公交换乘算法的目的为用户提供有效的,并贴切用户体验的换乘方案。2.3算法对象的转变以北京为例全市公交如果往返公交线路算两条线路的话，也只有1300多条

7、记录，而站点则有30000多条记录，即使同名算站点合并后也有6000多条记录。也就是说站点个数要远远大于公交线路的个数。而由于公交线路的特殊性，如果找到途径目标站点的公交线路就可以解决了可达问题。所以对于公交换成算法来说与其考虑节点到节点之间的可达问题，不如考虑有向边与有向边的可达问题，这样就减少了算法的负担。2.4算法对换乘次数考虑以北京为例，使用8199对随机站点进行线路可达试验得到如下数据20%0%13%22%直达可达一次可达二次可达三次可达四次可达65%图2直达一次二次三次四次五次总数18165

8、2701064272208199表1图二和表一表明2此换乘就可以满足99%以上的可达需求。之前在用户的体验的特点这个章节里讨论了，对用户来说换乘是一个很大的负担，并且换乘次数少是关心最多的问题。在这里我们可以得出一个结论，公交换乘应该考虑优先得到换乘次数少的换乘方案。一般的说，当得到足够多的少换乘次数的公交换乘方案那么再去求取多换乘次数的换乘方案就显得没有意义了。2.5公交换乘算法综上所述，如果改成以求公交线路与公交线路之间的那么即使是公交