最佳公交线路的实时查询模型及算法

1最佳公交线路的实时查询模型及算法摘要本文针对查询者的不同需求，为公交查询系统提供了最佳线路查询的模型与算法。查询者的需求从换乘次数少、时间少和费用少三方面进行考虑。故查询算法从换乘次数（从实际出发，换乘不超过两次）入手：对直通的任意两站点，可设计出较简单的最佳直通线路查询算法（直通算法）。故对需要查询的两站点，算法先由线路、站点的原始数据判断此两站点是否直通，若是，便可通过直通算法进行查询。不论是否存在直通线路，算法都考虑对换乘的情形进行查询。考虑到城市公交系统中的站点基数较大，可行的换乘方案数也将较大，故查询算法根据所有可行的一、二换乘点必与起、止站点直通的原则，对可能成为给定两站点的换乘点的站点进行了筛选，得到相关站点集，较大的缩小了查询的范围。得到相关站点集后，建立了反映站点集中任意两站点直通关系的连通矩阵，并通过矩阵乘法，较快地得出了所有可行的一次、二次换乘点。考虑到所有可行的换乘点可能较多，特别是二次换乘的情形，故查询算法采用分支定界法以较高效率对最佳方案进行了最后的筛选。在考虑地铁的公交系统时，本文从实际出发，对模型进行了一定的修改。同时，本文考虑了引入站点之间的步行时间的情况，提出了线路选择的模型。由于筛选算法、矩阵乘法和分支定界法的高效性，整个查询算法具有很高的效率，并能在换乘次数不超过两次的条件下，求得全局最优解，得出满足查询者不同需求的所有最佳方案。并且，从系统设计的角度出发，整个系统需要预存的数据量很小，系统的实用性很强。对给定的六对站点，采用本算法进行查询，在1.7GHZ的CPU环境下，平均运行时间为：1.27秒，最长运行时间为7.43秒，验证了算法的实时性。同时，对每一对站点，得到了满足不同查询需求的所有最佳线路方案，验证了模型与算法的精确性。关键词：最佳线路、实时、筛选算法、分支定界2一、问题重述第29届奥运会将于今年8月在北京举行，届时有大量观众到现场观看比赛，其中大部分人将乘坐公共交通工具（包括公汽、地铁等）出行。北京市的800多条公交线路使得公众面临多条线路选择问题。因此，有必要开发一个解决公交线路选择问题的自主查询计算机系统。现有如下数据：1.基本参数设定：包括相邻站点平均行驶时间、换乘时间、票价等信息。2.公交线路信息：包括公汽和地铁的所有线路、途经站点、票制等信息。3.公交换乘信息：包括在每个地铁站点可以换乘的所有公汽站点。从实际情况出发考虑，在满足查询者不同需求的条件下，我们需要完成如下工作：1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的最佳线路（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762.同时考虑公汽与地铁线路，解决以上问题。3.假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二、问题分析对于公交线路查询系统，需设计查询最佳公交线路的模型和算法，满足查询者的各种需求，并使查询系统具有实时性。对于一般的查询者来说，对线路的选择主要有以下几种需求：换乘次数少、乘车总时间少和乘车总费用少，但不同的查询者对这三个因素有不同的偏好，故查询系统应能提供多种方案供查询者自行选择。可以先固定换乘次数，求得连通某两个站点的所有方案；再对在该换乘次数下的每一种乘车总费用所对应的方案，筛选出花费时间最少的方案；最后再对换乘次数不同的方案进行比较，淘汰掉劣势方案，得出满足不同查询者需求的最佳线路集。从实际的城市交通状况出发，交通部门在设置公交站点时会保证整个城市交通网的连通性，以方便人们出行，故可以假设任何两个公汽或地铁站点最多经过2次换乘便可到达。在查询系统寻找最佳线路集时，若给定的两站点直通，可方便的找出其最佳线路，得到其乘车总费用及总时间。但对于存在换乘点的方案，需要确定途径的线路和换乘点，使得通过这些线路和换乘点可以到达终到站，并需要判断各个方案的优劣。对于目前的城市交通系统，线路和站点的数目都较大，故可能的换乘方案的数目也会较多，特别是对2次换乘的情形。这对各个方案的筛选即最佳线路集的确定将带来一定难度，并对查询算法的效率提出了较高的要求。故问题的关键在于怎样高效的找出最佳方案中的换乘点。现需要考虑的是有着3957个公汽站点的交通网的最优线路查询问题。为了便于量化交通网中任意两站点的连通关系，先由线路原始数据可建立所有站点的连通矩阵。在查询给定两站点的最佳线路时，由于查询时间和遍历的站点数目成正相关，故不宜采用直接遍历全部站点的方法，应考虑对可能成为换乘点的站点进行筛选。由于假设的换乘次数不超过两次，故所有可能的换乘点都与起始站或终到站直通，则可考虑将经过起始站和终到站的所有线路上的站点作为可能的换乘点集合。再对该集合中的站点构3成的连通矩阵进行分析，可以得出所有可行的换乘方案。可行的换乘方案数目也可能很多，特别是对城市中心地带。故在确定最佳方案时，应考虑采用较高效的对比算法。鉴于第一个换乘站点和第二个换乘站点的确定具有先后顺序，两者的层次分明，故可考虑用分支定界算法。对于公汽地铁混合公交系统，地铁票价与站点数无关、地铁间的换乘和同一地铁站对应的任意两个公汽站之间的换乘均属免费、地铁线的引入增强了整个公交网络的连通性、地铁相对公汽更便捷且无阻塞，这些因素在会对两站点间的连通关系及换乘点的选择产生影响，需要综合考虑。对于考虑了步行时间的最佳线路选择问题，由于存在在某站下车步行到另一站上车的情况，会对整个公交网络的连通性产生较大影响，具有一定的复杂性。而步行时间无具体数据，故只给出一般模型和求解思路。三、变量说明)520,2,1(iLi：已知的520条公汽线路编号(1,2,3957)isi：交通网络中各个公汽站点)3957,2,1(iSi：经过站点is的线路集)3957,2,1(iNi：经过站点is的线路数量(包括上下行，算两次))520,2,1(iLSi：线路属性向量，记录该向量为来回、上下行、环行。(,)(0,1,2)kCijk：分别为从站点si到站点sj的直通、一次换乘、二次换乘票价(,)(0,1,2)ktijk：分别为从站点si到站点sj的直通、一次换乘、二次换乘时间0s：起始站点，ds：终止站点四、基本假设1.换乘次数不超过两次。2.不考虑交通事故等意外情况。3.不考虑车辆内部的拥挤情况及交通阻塞。4.换乘时间及相邻两站的行驶时间都取为平均值。5.若两站点连通且直通线路上的中间站点数不超过3个，则不考虑换乘。五、模型建立先对数据进行处理，缩小搜索范围；然后设计快速算法找出任意两个站点经过直通、换乘一次及换乘两次连通的所有可行线路；最后根据查询者在换乘次数、时间和费用上的不同需求从可行线路中筛选出相应的最佳线路。5.1公汽最佳线路选择模型5.1.1建模前的准备名词解释：1.直通：站点i到站点j不需要换乘，则称站点i直通到站点j。2.连通矩阵A：由n个站点构成的nn的0、1方阵。当ij时，ija=1表示站点i联通到站点j；反之，ija=0。当ij时，规定ija=0。3.单一站点：站点i只在一条线路上，只考虑来回线及环形线上的站点。数据处理：1.对已有的公汽站点数据进行统计，得到3957个公汽站点。42.得到原始连通矩阵0A。该矩阵为3957阶0、1方阵，反映任何两个站点的直通关系。3.得到单一站点集G。4.得到站点-线路集S。123957{,...}SSSS，iS表示由经过站点i的所有线路构成的集合。5.线路－站点集L。12520{,...}LLLL，iL表示由线路i上的所有站点构成的集合。5.1.2模型的建立（1）建立连通矩阵A定义1：前续站点：若站点i能直通到终点站，则称站点i为终点站j的前续站点。由终点站j的所有前续站点构成的集合称为终点站j的前续站点集Q。定义2：后续站点：若起点站i能直通到站点j，则称站点j为起点站i的后续站点。由起点站i的所有后续站点构成的集合称为起点站i的后续站点集H。结合北京公交的实际情况，换乘次数最多为2次，即认为两个站点之间需要经过至少经过三次转车才可达的情况是不存在的。换乘情况如图1所示：图1两站点间的各种换乘情况起点终点起点终点换乘点起点终点第一换乘点第二换乘点由单一站点和前、后续站点的定义知：一次换乘点和二次换乘点只可能在QH中，不可能在G中，由此得到相关站点集合F=()/QHG，该集合包含了所有的换乘点。若在F外存在一换乘点，则必然至少存在另外两个换乘点，分别与起始站点和终止站点连通，即至少由三次换乘。故若只存在一次换乘或二次换乘，其换乘站点必在F中。将集F中所有元素（假定个数为n）在原始连通矩阵0A中对应n行n列的2n个交点提取出来并保持相对位置不变，即得到连通矩阵A。一对起止站点0dss，就有一个连通矩阵0dA与之对应。该矩阵反映了与起、止站点直通的所有站点间的连通信息。下面将得到0dA的算法总结如下:a)得到终止站点ds的前续站点集Q及起始站点0s的后续站点集Hb)得到相关站点集()/FQHGc)由原始连通矩阵0A及相关站点集F，得到连通矩阵0dA（2）两站点的直通判断及最佳线路选择对给定的起点站i和终点站j，若0ija，表示站点i到站点j不存在直通线路。若1ija，表示站点i到站点j存在直通线路。当站点i到站点j存在多条直通线路时，就要从中筛选出最佳线路。由于相邻公汽站的平均行驶时间相同且不经过换乘，站点数最少的线路就是最短时间线路，也是最少费用线路。从所有直通线路中筛选出站点数最少的线路，就是同时满足时间最短和费用最少的最佳直通线路方案。（3）两站点的一次换乘及较优线路选择a)确定可能换乘点数目命题：令一次换乘矩阵2BA，若kbij(0,1,2...)k，则表示从站点is到站点js存5在k个一次换乘点。简要证明如下：若站点is直通到站点js，则记为ijss由矩阵乘法，一次换乘矩阵B的第i行第j列的元素ijb为连通矩阵A的第i行元素和第j列对应元素乘积的和。即可表示为：njjjinijiiijaaaaaaab2121,,，01ijijaij站点不能连通到站点站点连通到站点当ij时，规定0ijb；当ij时，若ijbk，表示n个乘积项中有k个为1，其余为0。下面以111ijaa为例，将其表示的实际意义说明如下：若111ijaa，则111ijaa，表示11,ijssss，所以，1ijsss表示从站点is出发，在站点1s处经过一次换乘，可以到达站点js。一般地，当kikj且时，1ikkjaa时，表示ikjsss。当ki时，由于0iia，无论ija为何值，0iiijaa，表示即使站点i与站点j直通，对ijbk也没有贡献。即ijb中不包含站点i与站点j的直通信息。因此，当ijbk时，表示从站点is到站点js存在k个一次换乘点。b)确定k个一次换乘点令ibinijiiaaaa,,21，njjjjaaac21，定义运算符’’的运算规则如下：njinjjijjijijiijaaaaaaaacbf,,,2211若ijf中第k个元素非零，则表示ikjsss，即可从起点站is出发，在站点ks换乘到达终点站js。c)确定一次最佳换乘线路图2两站点间的一次换乘方案示意图起点终点换乘点换乘点换乘点通过a)、b)两步，得到了起点站is到终点站js经过一次换乘的所有可行换乘点集12{,...}kkkknSsss。然后，采用直通算法分别得到ikiss及(1,2...)kijssin的最佳直通线路，由此得到n条一次换乘线路。下面从最少费用和最短时间方面得到最佳一次换乘线路。费用表达式：6100(,)(,)(,)CijCikCkj