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