城市公交线路选择算法优化

汤亭亭，严 凌，孙梦瑶

（上海理工大学 管理学院，上海 200093）

0 引言

生活水平的提高，给人们的出行活动在一定范围内带来了便利，但是随之而来交通问题的负反馈使得人们意识到了合理发展交通方式的重要性。公共交通已经成为城市化发展和全面提升城市化水平的首要问题[1]。近年来，在公交优先的思想下，国内各个城市开始大力发展公共交通，期望用大容量公共交通系统来改善交通环境。国外学者也将乘客出行效率作为整体的优化目标，在优化过程中尽可能地减少换乘次数、降低出行时耗[2]。研究表明，居民在公交线路选择过程中首要关心的是换乘次数，其次是花费的时间[3]。当乘坐公交出行换乘过于繁琐而且时间花费大于人们的预期时，人们往往会在下次出行时重新选择交通方式。公交站点是乘客起点上车、换乘、终点下车的必须环节，根据调查数据显示，在公交车的延误耗时里，由于站点停车而造成的损失时间占据了公交车总运行时间的19%～21%[4]。因此，本文将换乘次数和站点数量作为主要的限定条件，尽可能的减少在一次出行过程中的换乘次数与所经过的站点数量，这将有效地减少乘客乘坐公交的出行时间，提高出行效率。

1 问题提出及分析

1.1 问题提出

公交路径的最优选择方案目前依旧是NP 问题[5]，解决此类问题的方法主要可分为三种：第一种是最短路径的搜索算法，主要代表有Dijkstra 算法，该算法可以快速高效地找出整个路网所有公交站点间的最短路径。但是没有考虑到公交线路之间的换乘次数，往往得到的公交路径确实是最短的，但却可能需要经过数次换乘才能到达目的地；第二种是采用数据库或者集合的查询算法；第三种是基于智能技术的查询算法，如遗传算法。后两种算法在计算过程中容易将一些不合理的路径加入到搜索结果中，容易产生维数爆炸问题，不适用于规模较大的公交网络[6]。

1.2 问题分析

最短路经典的Dijkstra 算法是计算网络中一个节点到其它任意节点的最短路径，以已知的起点向外一层一层扩散直到寻找到终点为止，该方法的优点是可以找到全局最优解[7]。但是该算法只考虑路径最短，并未将换乘次数考虑在内，忽略了乘车人所能接受换乘次数的心理因素。广度优先迭代从起点开始一层一层往下遍历所有站点，直至找到目标站点，但是存在搜索量大并且耗费空间等明显的缺点。

本文借鉴先前学者的研究方法，将集合与广度优先迭代相互结合使用[8]，两端的集合逐步向外扩展并且不断靠近直至出现两个集合共有的交集，在这个庞大的无向公交路网中，找到所需换乘的最少公交线路的所有路径。但找的不一定是唯一线路，所以再使用Dijkstra 算法在选择的换乘最少的线路中找出最优线路。

2 广度优先迭代与Dijkstra 算法相结合的居民出行公交线路优化

2.1 基本假设

（1）一条线路的公交不构成环形回路；

（2）公交车上行和下行站点线路相同；

（3）完整的公交车线路可以覆盖所有的公交车站点；

（4）公交车的起点和终点的站点固定；

（5）使用Dijkstra算法时公交站点站距均设为1，便于寻找站点最少的线路。

2.2 广度优先迭代搜索最少换乘线路

将整个城市的公交站点线路看成一个联通无向交通网络，任意两点经过有限次数的换乘后都可以到达。考虑到实际情况和居民出行心理，需要对换乘次数规定一个上限。经过数据研究，乘客所能接受的最多换乘次数为三次[9]。

第一步：首先假定A,B 为两个已经确定的起讫点，并且存在于公交路网的公交站点中。设经过A点的所有公交线路为sA(i)，经过B点的所有公交线路为sB(j)。

上式中i 和j 分别代表通过A 点和B 点的公交线路，n和m均为正整数。

判断集合A和集合B的公交线路交集zl,若集合|zl|=1,则表明AB 两点有且仅有一条直达的公交线路，直接输出集合 |zl|中的线路，结束运算；若集合|zl|＞1，则表明有数条公交线路可以直达，使用Dijkstra算法寻找站点最少的线路；若集合|zl|=0，则说明两站点之间没有直达线路，继续下一步操作。

第二步：搜索公交线路sA(i)的所有站点数据，存入公交站点矩阵M(i,m)(m 为正整数)，搜索公交线路sB(j)的所有公交站点数据，存入公交站点矩阵N(j,n)(n为正整数)。判断矩阵M和矩阵N是否存在名称相同的站点，若存在，则将该站点存入集合 |XS|中。若集合|XS|=1，则表明AB两点之间有且仅有一条换乘一次的线路，输出两条公交线路名称i 和j。若集合|XS|＞1，表明有多种换乘线路可以到达，用Dijkstra算法进行下一步处理。若|XS|=0，表明两站点换乘一次无法到达，继续执行。

第三步：将所有经过m 站点的公交线路存入公交线路集合M(k)(k 为正整数)。与第二步相同，搜索公交线路sM(k)的所有站点数据，存入公交站点矩阵K(m,k)，判断矩阵K 和矩阵N 中是否存在相同站点，将满足该条件的站点名称存入集合YS中。若集合|YS|=1，则表明AB 两点之间有且仅有一条换乘两次的线路，输出三条公交线路名称i，k 和j。若集合|YS|＞1，表明有多种经过两次换乘线路可以到达，用Dijkstra 算法进行下一步处理。若|YS|=0，表明两站点换乘两次还是无法到达。继续执行。

第四步：与第三步操作基本相同，将所有经过n站点的公交线路存入公交线路集合N(f)(f 为正整数)。搜索公交线路sN(f)的所有站点数据，存入公交站点矩阵F(n,f),判断矩阵F和矩阵K是否存在相同的站点，将相同站点名称放入公交站点集合WS中。集合|WS|=1，表明AB两站点有一条换乘三次到达的线路，输出四条线路i,k,f 和j。若集合|WS|＞1，表明线路存在多种换乘三次的方式，需做最短路判断。若|WS|=0，表明两站点间即使换乘三次也无法到达。

公交换乘示意图如图1所示。

图1 公交换乘示意图

最后设定换乘次数上限为三次，在换乘次数不大于三次的迭代前提下找到可行线路并输出。在实际编程运行过程中，基本任意两站点都可以做到三次换乘到达。

由于得到的换乘最少线路不一定唯一，所以需要进一步筛选。采用Dijkstra 算法对换乘最少的线路进行进一步处理，得到最终的最优公交乘车线路。

2.3 Dijkstra算法寻找站点最少线路

用筛选得到的最少换乘次数的公交线路构建有边权重的有向无环图，将所有公交站点间的距离设置为1，不相连的站点间距离设置为无穷大，所有换乘站点看作是所到达的节点。接着采用Dijkstra 算法的思想在确定换乘最少的线路中寻找站点最少的线路。首先设置两个集合S 和V，集合S 是一个逐步扩大的顶点集合，用来存放已经确定最短路径的顶点。集合V是初始的尚未确定最短距离的所有顶点的集合。在运行中集合S 按照相临站点路径长度递增的顺序逐个添加，直至包含所有顶点，使得V-S为空集。

（1）将已经确定的公交起点站点设为源点O1，则开始时集合S 只包含顶点O1，再次设置一个集合U，令U=V-S，此时集合U 包含除源点O1的所有顶点。源点O1对应的距离值为0,即D[O1]=0。对于集合U中所有顶点对应的距离做如下规定：如果图中相临站点间有弧(O1,Vk)，则Vk顶点的距离为这个边的权值，不相连边的值记为无穷大；

（2）从U 中选择一个距离最小的顶点Vk加入到集合S中；

（3）集合S 每加入一个顶点Vk，就要对在集合U中的各个顶点的距离进行一次修改，将新加入的顶点Vk作为中间顶点进行距离值判断，若(O1,Vk)+(Vk,Vj)＜(O1,Vj) ，则用 (O1,Vk)+(Vk,Vj) 来代替(O1,Vj)的距离值。

（4）重复（2）和（3）的操作步骤，将所有集合U 中修改过的最短距离值的顶点加入到集合S中，直到S集合中包含图中所有顶点，使得S=V。得到的最终结果为换乘次数相等的线路间的站点比较，最终得出站点最少的换乘线路。

以换乘一次为例，如图2 所示，假设通过广度优先迭代可以确定公交起讫点之间最少换乘次数为一次，并且有三种换乘线路。此时构建有边权重的有向无环图，起讫点和换乘站点设为顶点，公交站距设为1，可以确定每条边的距离，不相连的顶点距离设置为无穷大。

图2 换乘一次线路图

图3 换乘一次有边权重的无向图

如图3 所示，首先确定集合S={O(0)} ，集合U={A(4),B(2),C(2),D(∞)} ，选择距离最少的顶点加入到扩充集合S 中，S={O(0),B(2),C(2)} ，接着判断(O,B)+(B,C)是否小于(O,C) ，规定不相连的顶点距离 为 无 穷 大 所 以 (O,B)+(B,C)＞(O,C) ，同 理(O,B)+(B,A)＞(O,A) ，最 终 结 果 集 合S={O(0),A(4),B(2),C(2),D(4)}，可以得出讫点O到达终点D 的最短距离为4，最优换乘线路为O→B→D。

3 实例分析

3.1 公交线路站点数据爬取

为了对模型和算法进行验证，本文选取长沙市公交线路作为验证对象，用python 编程爬虫技术，从8684 公交网站爬取长沙市目前的所有公交站点线路，包括每条线路的公交站点名称与公交站点的经纬度数据，共有32286条有效站点数据。爬取后保存成csv 文件便于后面调用。爬取后的数据如图4 所示。

3.2 编程实现

图4 长沙市公交站点爬取数据

使用python 语言按照上面的基本思路进行编程实现，随机选取两个起讫站点运行结果，其截图如图5所示。

图5 长沙火车站（南坪）到窑岭东站点运行结果图

随机选取的公交站点起始站点为长沙火车站（南坪），到达站点为窑岭东，如图5所示，从运行结果可以看出最优公交线路为9 路，共有五个公交站点。百度地图给出两战点间的最优线路如图6所示，其最优线路也是9 号线路，并且公交站点数目也是五个，初步验证了该算法的有效性。

再次随机选取两个相距较远的公交站点，再次验证算法在多次换乘中运行的有效性，其运行结果如图7所示。

选取的公交站起始站点为枫树山小学大桥校区，到达站为长沙简牍博物馆。从运行结果可以看出，两站点之间需要经过一次换乘，换乘的线路为917路和122路公交车。将运行结果与百度地图进行对比分析，如图8 所示。从图8 可以看出，百度地图给出的推荐路线包含了我们所给出的换乘路线，在时间最短的的运行线路中，百度地图给出了地铁换乘线路，但是地铁换乘线路需要步行的距离较长，需要步行2.2km，距离过长。而公交换乘线路出行时间仅次于地铁换乘并且步行距离短。

4 结语

本文采用改进的双向广度优先搜索算法，首先寻找出换乘次数最少的所有可能的公交路线，再结合传统的Dijkstra 算法，将公交站点数目作为边权重的判别方式，能够准确地找出在公交线路网络中任意两站点间的最优线路。双向搜索极大地降低了算法在时间和空间上的复杂度，提升了算法的运行效率，而且用Dijkstra 算法处理简化后的换乘路网，极大地提高了运行效率，避免了需要遍历所有站点的繁琐过程，简化了运行过程。

图6 长沙火车站（南坪）到窑岭东站点百度地图推荐线路

图7 枫树山小学大桥小区到长沙简牍博物馆站点运行结果图

从上面两个实例运算与现有百度地图做对比可以说明该公交路径选择算法可以准确地寻找出任意两公交站点间换乘次数最少和行程时间最短的线路，得到了较好的运行效果，验证了算法的有效性。

图8 枫树山小学大桥校区到长沙简牍博物馆站点百度地图推荐线路