公交出行优化线路系统设计
来源:用户上传
作者: 王家玉
摘要:本文给出了一种公交查询系统算法设计,在综合考虑出行人的心理因素前提下,选择以最少换乘次数为第一目标,以出行总花费为第二目标,建立公交优化模型,从而解决公众出行的最佳乘车路线问题。
关键词:交通网络;广度优先搜索;搜索树
中图分类号: G421文献标识码:A文章编号:1003-2851(2010)08-0105-01
一、引言
在城市数字地图中,公共交通信息模块是必不可少,公交换乘信息的查询倍受用户的关注。在现有的公共交通条件下,设计合理的公交出行路径有助于人们确定出发时间、出行线路和换乘方案等。
在本文中选择以最少换乘次数为第一目标,以出行总花费为第二目标。首先将所有公汽线路作为一个节点,搜索出整个公汽线路的连通网络,然后再由出行起始站点A和终止站点B出发,考虑换乘次数有限的条件,用广度优先搜索出从站点A到站点B的局部连通网络,再利用深度优先搜索从站点A到站点B在局部连通网络中的所有可能的路径,并给出相应的效用值(换成次数,出行费用)从中找出各自目标下的最优出行路线。
二、出行系统模型设计步骤
第一步:初始化公汽连通网络。
(1)将每一条公交线看成一个点,上、下行分别考虑,单线、环行均为双向行驶,作为两个点,记为No1,No2,……No;
(2)判断任意两条公交线是否相连,任意取一条线路,按站点次序搜索,判断是否与其他线路连通,若连通将该线路标记在所取线路的neighbours中。当所有线路搜索完毕则可以得到公汽连通网络,设l1,l2,...ln表示所有线路。
第二步:按广度优先搜索连接起始点A到终止点B在有限换乘下的连通网络。
(1)将所有包含起始站点A的线路作为一个start集,所有包含终止站点B的线路作为一个end集。
(2)标记start集中的各节点(线路),找出和start各个线路相连的节点(线路),start集中与之相连的节点为该节点的父节点。
(3)当到达一定层次(如n=10时,即当换乘次数超过n次时,我们认为是不可取的)结束,否则,将这些节点作为新的start集,返回(2)。
第三步:按深度优先搜索,从起始点A到终止点B。在换乘次数有限条件下的局部连通网络中的所有路径Paths。对end中的每一个节点做如下步骤:
(1)赋初始值P.count=0,P.change=0,P.price=0;
(2)任取end集中一个节点li∈end;
(3)找出li的父节点lj,li与lj的换乘站点记为Sij;
(4)若li的type<5且站点Sij的序号>站点B序号,去掉父节点lj返回(3)
站点Sij的序号< 站点B序号P.count=站点B的序号 - 站点Sij的序号;
若lj的type5且站点Sij的序号>站点B的序号
P.count=线路li的总站数+站点Sij的序号-站点B的序号
若lj的type5且站点Sij的序号<站点B的序号
P.count=线路li的总站数+站点B的序号-站点Sij的序号
(5)change=change+1;
(6)若li的price=1,则P.price=P.price+1;
若li的price=0则
当站点B的序号 - 站点Sij的序号20时,P.price=P.price+1;
当20?荞站点B的序号 - 站点Sij的序号?荞40时,P.price=P.price+2
当站点B的序号 - 站点Sij的序号>40时, P.price=P.price+3
(7)若lj∈start,则得出一条可达路径,记入Paths中,记n=n+1;
(8)lj遍历所有可能父节点,结束。
(9)找出lj的父节点lk,记lk=lj,Sij记为B,返回(2),利用函数f(T)=minK1×P.change+K2×P.count+K3×P.price,找出(三个目标)下的最优路径。
三、 实例
利用2007年全国大学生数学建模竞赛B题中给出的北京市公交线路及其基本假设,在上述函数f(T)中令K1=1,K2=K3=0,即可得到换乘次数最少的最优路径:
令K1=5,K2=1,K3=0得乘车时间最小时的最优路径,令K1=K2=0,K3=1;得出行费用最小时路径,对其要求的几个出行方式即可求解。
四、结论
本模型通过一次编程,仅通过简单的参数修改,即可很快得出换乘次数最少、乘车费用最低两个因素,分别给出满足不同乘客要求的最佳路线,若将上面四个因素进行加权(加权系数可以由乘客给出),由于该模型的第三步中已给出局部网络中所有线路的效用值,只要重新定义的赋值,即能给出乘客较为满意的参考路线。
参考文献
[1] 刘云翔.基于城市道路网的最短路径分析解决方案[J].小型微型计算机系统, 2003,24(7):1-4.
[2] 夏春林.道路网络中最短路径的算法与实现[J].辽宁工程技术大学学报,2003,22(2):1-2.
转载注明来源:https://www.xzbu.com/1/view-173558.htm
