一种基于自适应骨干网的快速公交选线算法

摘要

本发明是一种基于自适应骨干网的快速公交选线算法，主要应用于城市的公交、地铁线路查询领域，能够解决现有的公交线路查询、选择算法不能支持多次换乘、查询时间过长的问题。本发明提出自适应骨干网构建技术，首先构建公交网络中的自适应骨干网，然后依次根据如下原则选择任意两个站点之间的可行线路组合：一、如果两个站点之间存在公交线路直达，那么可以不经过骨干网；二、如果这两个站点之间不存在直达的公交线路，就只能换乘，但必须在骨干站点进行换乘，同时使换乘次数尽可能少；三、在所有可行的线路组合中根据乘客不同的出行需求再选择最优的线路组合。

主权项

1.算法的基本思想本算法假设：1、任何两个站点通过有限次换乘可达；2、换乘只能在骨干站点上实现。换乘站只能为骨干站点的限制可能导致得到的线路不是最优线路，但是考虑到实际情况，这却很可能是最优的，因为骨干站点都是十余条、数十条公交线路交汇的地区，也必然是人流密集的地区，对于陌生的查询者来说是便于记忆和识别的。两种骨干网的建立方法如下：(1)自适应骨干网的建立算法基本思想：当查询者任意给出起始站点vstart和目的站点vend后，首先根据vstart确定最大的u，使得vstart∈V(Lu)，u也就是通过vstart的公交线路的条数。其次根据vend确定最大的v，使得vend∈V(Lv)，v也就是通过vend的公交线路的条数。则骨干网的度n＝min(u，v)，然后可以通过骨干网的度n确定其规模。(2)固定折中骨干网建立算法基本思想：骨干网的度n越大，则骨干网的规模越小，覆盖的公交线路越少；反之骨干网的度n越小，则骨干网的规模越大，覆盖的公交线路越多。为了提高求解的准确性，我们希望骨干网覆盖的公交线路越多越好，为了降低运算的复杂度，我们希望干网的规模越小越好。为了解决此矛盾，可采用折中的思想，定义y＝n*x％，其中n为“n度骨干网”的度，x％是“n度骨干网”覆盖的公交线路条数占总公交线路条数的百分比(也可选择任意两站点在骨干网上可达的概率进行计算)。先求使得y值最大时的骨干网的度n，然后可以通过骨干网的度n确定其规模。基于骨干网的线路选择算法的基本思想是：查询者任意给出起始站点vstart和目的站点vend，首先计算L(vstart)和L(vend)，判断L(vstart)∩L(Vend)是否为φ，若不为φ则说明vstart和vend 有公交线路直达，记录直达的公交线路；否则说明vstart和vend没有公交线路直达，需要进行换乘。若vstart和vend没有公交线路直达，进而考虑一次换乘的情况，计算经过站点vstart的所有公交线路上的骨干站点的集合VB(L(vstart))和经过站点vend的所有公交线路上的骨干站点的集合VB(L(vend))，判断VB(L(vstart))∩VB(L(vend))是否为φ，若不为φ则说明vstart和vend可以通过在某些骨干站点一次换乘到达，记录一次换乘的公交线路；否则说明vstart和vend不能通过一次换乘到达，需要进行多次换乘。若vstart和vend不能通过一次换乘到达，进而考虑二次换乘的情况，首先计算起点站直达的骨干站点的集合Vstart＝VB(L(vstart))，再计算能直达终点站的骨干站点的集合Vend＝VB(L(vend))，下来任取vi∈Vstart，vj∈Vend，判断vi和vj是否能够直达，也即找lk，使得vi∈V(lk)∩ vj∈V(lk)成立，若能找到一个或多个这样的lk，说明vstart和vend可以通过二次换乘达到，vi和vj为两个换乘站点，并记录路径信息；否则vstart和vend不能通过二次换乘到达。若vstart和vend不能通过两次换乘到达，即Vstart中任意一个站点和Vend中的任意一个站点均不可直达，可以考虑三次换乘的情况，对于这种情况考虑使用递归：任取vi∈Vstart，vj∈Vend，判断vi和vj是否能够一次换乘可达，而判断两个站点是否一次换乘可达的算法已经给出。若vi和vj能够一次换乘可达，说明vstart和vend三次换乘可达，若vi中任意一个站点和vj中的任意一个站点均不可通过一次换乘可达，则vstart和vend三次换乘不可达。依次递归，任意两个站点之间都可以通过若干次换乘达到。通过上述方法将得到若干条“最小换乘”的可行线路组合，再对这些线路再进行费用和耗时两个方面的评估，选择满足查询者需求的最优线路。2、算法的实施步骤算法步骤如下：算法输入：起始站点vstart、终点站点vend，算法输出：可达的线路集合。Step1：循环变量i＝1，变量L(vstart)＝L(vend)＝φ。从L中取li，若vstart∈V(li)，则L(vstart)＝L(vstart)∪{li}；若vend∈V(li)，则L(vend)＝L(vend)U{li}；若i≠520，则i＝i+1并转到Step1。Step2：若L(vstart)∩L(vend)≠φ，则记录这些直达线路并EXIT。Step3：循环变量i＝1，变量VB(L(vstart))＝φ。从L(Vstart)中取元素li，令VB(L((vstart))＝VB(L(vstart))∪{vj|vj∈V(li)∩vj∈Vn}(即将线路li上的骨干站点全部并入VB(L(vstart))，其中Vn已由骨干网建立的算法所确定)，如果i＜|L(vstart)|，i＝i+1转到Step3。Step4：循环变量i＝1，变量VB(L(vend))＝φ。从L(vend)中任取元素li，令VB(L(vend))＝VB(L(vend))∪{vj|vj∈V(li)∩vj∈Vn}(即将线路li上的骨干站点全部并入VB(L(vend))，其中Vn已由骨干网建立的算法所确定)，如果i＜|L(vend)|，i＝i+1转到Step4。Step5：若VB(L(vstart))∩VB(L(vend))≠φ，则记录经由这些站点一次换乘的可达的线路组合并EXIT；Step6：在VB(L(vstart))中任取站点vi，在VB(L(vend))中任取站点vj，令vstart＝vi，vend＝vj，即将vi和vj看作新的起始站点和目的站点，递归调用Step1、Step2中算法，若vi和vj可直达，则vstart和vend二次换乘可达，输出选路信息并EXIT；Step7：在VB(L(vstart))中任取站点vi，在VB(L(vend))中任取站点vj，令vstart＝vi，vend＝vj，即将vi和vj看作新的起始站点和目的站点，递归调用Step3、Step4、Step5中算法，若vi和vj一次换乘可达，则vstart和vend三次换乘可达，输出选路信息并EXIT；Step8：如此递归下去，直至得到换乘次数最小的可行解。再对可行的线路组合进行评估。设第i条可行路线组合的费用函数为$c\left(i\right)=\underset{j=0}{\overset{D_i}{\Sigma }}{f}_{i,j}(x,y,s)$ 其中，$f_{i,j}(x,s)=\left\{\begin{array}{cc}1& x=0,x=1^s\le 20\\ 2& x=1^20\le s\le 40\\ 3& x=1^40<s\end{array}\right.$表示第i条可行路线的第j段线路的费用(x＝0表示单一票价，x＝1表示分段票价，s表示公交站点数，此处假设公汽票价包括单一票价：1元/票和与分段票价：0～20站1元；21～40站2元；40站以上3元)，第j段线路是在两个站点之间可直达的公交线路，第i条可行路线组合共有Di段，那么min(c(1)，c(2)，…，c(m))(m为可行路线组合的总数)即为花费最小的可行线路组合。设第i条可行路线组合的耗时函数为$t\left(i\right)=\underset{j=0}{\overset{D_i}{\Sigma }}{g}_{i,j}(x,m)+\underset{k=0}{\overset{D_i-1}{\Sigma }}{h}_{i,k}$ gi，j(s)＝pshi，k＝q其中，gi，j(s)表示第i条可行路线的第j段线路的耗时(s表示公交站点数，此处假设每站之间的耗时p相同，p可以根据城市的实际情况进行调整)，hi，k表示第i条可行路线的第k次换乘的耗时(此处假设每站之间的耗时q相同，q也可以根据城市的实际情况进行调整)，那么min(t(1)，t(2)，…，t(m))(m为可行路线组合的总数)即为耗时最短的可行线路组合。此外，还可以综合考虑费用和耗时的问题构建目标函数min(F(c(1)，t(1))，F(c(2)，t(2))，…，F(c(m)，t(m)))