资源预览内容
第1页 / 共55页
第2页 / 共55页
第3页 / 共55页
第4页 / 共55页
第5页 / 共55页
第6页 / 共55页
第7页 / 共55页
第8页 / 共55页
第9页 / 共55页
第10页 / 共55页
亲,该文档总共55页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
. .公交查询系统的最正确乘车方案设计摘要本文研究的问题是针对的公交线路信息如何设计出最正确的乘车方案。首先,进展数据处理,用excel建立起公交线路矩阵。然后,上网查阅了公交乘客乘车心理分析的资料,得出影响乘客出行的三个主要因素依次为为:换乘次数、出行时间、出行费用随后,建立了站点线路序列模型。利用公交乘客的出行过程抽象为站点线路的交替转换的思想,从而确定了出行者出行路线的一般数学表达式。针对问题一,仅考虑公汽的情况下,以换乘次数最少为第一目标、出行时间为第二目标、乘车费用为第三目标,建立起多目标最优化分层求解模型。并依靠站点线路序列模型确定的出行线路表达式,采用图论中计算方法并结合广度搜索法经matlab编程(见附录一) 得到了公交乘客的最少换乘次数,所经过的站点,出行时间、出行费用(见表1)。针对问题二,在问题一的根底上考虑了地铁线路,处理的方法是将地铁线当成特殊的公交线,将地铁站点当成公交站点并与给定的公交站连接。按照问题一的模型和算法得到乘客的最少换乘次数,出行时间、出行费用(见表2)。针对问题三,在问题二的根底上考虑了所有站点之间的步行时间,由成人步行速度估算出该时间大小。步行线路与公汽线路一样但每条均有上行和下行。将步行线路矩阵与公交线路矩阵整合后按照问题二的算法得到乘客的最少换乘次数,出行时间、出行费用(见9.2)。最后,建立公交负载模型对前三问的模型进展了改良。考虑到了实际中公交线路堵车的情况,将堵车线路拆分为两段新的线路并相应改变公交线路矩阵。算法与前三问算法一样,但使得最正确路径的选择更加灵活且更符合实际情况。关键词:分层求解 交替序列 多目标最优化 改良广度搜索法1问题重述1.1问题背景我国人民翘首企盼的第29届奥运会明年8月将在举行,届时有大量观众到现场观看奥运比赛,其中大局部人将会乘坐公共交通工具简称公交,包括公汽、地铁等出行。这些年来,城市的公交系统有了很大开展,市的公交线路已达800条以上,使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。1.2需要解决的问题为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足查询者的各种不同需求。请你们解决如下问题:问题一:仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用你们的模型与算法,求出以下6对起始站终到站之间的最正确路线要有清晰的评价说明。(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676问题二:同时考虑公汽与地铁线路,解决以上问题。问题三:假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。2模型的假设及符号说明2.1模型假设假设1:假设乘客都是理性乘车且能顺利到达目的地假设2:假设不考虑红绿灯造成的等待时间,不考虑堵车,车祸等因素假设3:假设乘客能承受的最大换乘次数为2次假设4:假设乘客乘车过程中不能2次经过同一站点。假设5:假设公交与地铁换乘距离固定,换乘步行时间为常数2.2符号说明符号说明S公汽站点集,L表示公汽线路集,D地铁站点集,T表示地铁线路集,vik出行者选择第条公交线路所经过的第个站点(或)出行者选择第条公交线路所乘坐的第辆公交工具(或)Ni换乘次数Si途经的车站数ti行程时间Qi所需费用3问题分析本文研究的问题是设计一个公交线路选择的自助查询的计算机系统,并从实际情况出发考虑,以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。针对问题一:问题一要求只考虑公汽线路,给出最正确路径。通过查阅相关资料,知道对乘客影响最大的三个因素:换乘次数,行程时间,所需费用(重要性从大到小)。据此,我们建立以换乘次数为第一目标,行程时间最为第二目标,所需费用为第三目标的多目标最优化模型。对于换乘次数,联系被选择线路上的站点线路交替序列TRi个数可以表示出来;站点总数那么采用给同一线路上的站点排序的方法也可以求到,由于只考虑了公汽之间的换乘,那么出行时间只与换乘次数和所历站数有关;对于出行费用那么在换乘次数的根底上,引入分段计价的加价函数也可求得。针对问题二:问题二在一得根底上考虑可以搭乘地铁,乘客的选择更加灵活。主要变化为:地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用,相邻站点之间的距离较公汽站点大,而运行时间却相对减少;地铁与公汽之间进展换乘时,由于地铁站点不可能与公汽站点都建在同一个地方,因此从地铁站到公汽站的步行时间相对较多,而且位于与地铁换乘的公汽站点还可以通过本地铁站进展免费耗时换乘到下一个公汽站。我们可以把跨公交站的步行视为一种免费耗时的交通方式,据此分层求解。针对问题三:考虑到出行者在步行时,所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过,由问题三的条件可知,步行时所经过的两站点之间的步行时间是一个值。当换乘的两站之间站数不多时,我们考虑步行,这要可以减少换乘次数,节约金钱。4数据处理及分析4.1数据处理4.1.1数据统计我们运用Excel软件对给的“公汽线路信息和“地铁线路信息进展统计得到如下数据:表1公汽线路站点数地铁线路分段计价单一票价上下行路径不同上下行路径一样环形路线公汽站点地铁站点直行线路环形线路283条237条409条89条22条3957个39个1条1条公交系统共有公汽线路520条总站点3996个地铁线路共2条根据表一并结合本文参数设定中的票价信息,综合考虑,分析如下:在分段计价路线中,共有27条的公汽站点数不超过20,有148条的公汽站点数在2140之间,公汽站点数超过40的线路有108条。因此,从单独的计算角度来考虑,可以将分段计价中站数不超过20的线路归为单一票制1元的线路,因此上述信息可修正为:票价信息为单一票制1元的线路264条;在分段计价的路线中,共有256条,其中有148条的公汽站点数在2140之间,公汽站点数超过40的线路有108条。4.1.2数据的储存与处理由于所给的数据格式不利于程序软件直接读取和操作,我们运用Excel将数据处理为规X格式,建立起公交线路矩阵A。(1) 把公汽线路信息以及地铁线路信息分别导入到Excel表格中(2) 将公汽数据中的上下行一样、上下行不同、环行的线路分别找出并归类。(3) 将上下行一样的上行序列倒序后作为下行序列。那么每条线路对应两个行向量。(4) 环行线路假设有n个站点,那么依次以每个站点为起点和终点建立起n条首位一样的线路序列。(5) 在第k条线路对应的所有序列前加上数字k作为标记列,其意义为第k条路线。(6) 运用Excel的查找替换功能将公汽站点编号“S和地铁站点编号“D分别用0和111代替。目的是为了在汽车站和地铁站区别的条件下让matlab可以识别和进展矩阵操作。(7) 将所有的序列整合到同一个excel表中,建立交线路矩阵A,每一行储存一条线路站点信息,没有信息的点用“0”填充。 公交线路矩阵A建立交线路矩阵A后,我们可以把矩阵A导入MATLAB中,运用改良广度搜索算法求解最正确路径。5模型的准备5.1乘客心理调查公交车线路达800条以上,每一个公交站点可能有多条线路贯穿,通往不同的起点或终点,同样,一个目的地也可由多条线路到达,错综复杂的公交车路线犹如网状般将各站点联系起来,将城市的行人们带到其各自的目的地。我们通过互联网查阅相关资料发现,影响乘客公交线路的选择,主要有以下几个因素:换乘次数 ,行程时间,所需费用,途经的总站数等。其中有18.6%的乘客出行时,首先考虑的是乘车费用,30.4%的乘客首先考虑的是行程时间,42%的乘客首先考虑的是换乘次数。图1:乘客出行调查图就乘客本身而言,公交乘客出行更多考虑的是出行的方便性和舒适性,下面就影响公交乘客出行的各因素进展具体分析,不妨将以上影响因素作如下归纳解释:(1)换乘次数:出行者完成一次从出发点到终点出行过程中所换车的次数。(2)行程时间:出行者在一次乘公交出行过程中所用的总时间。(3)所需费用:出行者在完成一次由起点到达目的地过程中所花的车费。(4)途径的总站数:出行者完成一次出发点到终点过程中所经过的车站总数5.2影响选择因素分析“换乘次数和“行程时间是影响出行者的两个独立的因素,经研究说明多数的公交乘客希望换乘次数最少,况且公交公司对公交线路的设计也是尽量减少乘客的平均换乘次数;而且公交乘客出行时还受到行李、地理位置等客观因素的影响,这样更不希望有较多的换乘。其次对于看奥运非常心切的出行者来讲,出行耗时对他们也是比拟关键的。在此当给出供乘客选择的公交路线也应当尽可能的满足公交乘客的需求。当然,在此根底上我们还要考虑乘车费用。综上所述,可以以换乘次数最少为第一目标,再选择易于量化的“出行时间和“所需费用作为第二位的优化目标。由此,我们认为,乘客在选择路线时,可以根据自己的不同需求,对线路进展选择。5.3最优乘车方案算法分析在站点上放置一个便于乘客查询到达目的地的理想乘车方案的计算机系统,必须让计算机收集到本站到其他任意一站的路径与换乘信息,因此单独设计这样的算法是相当困难的,而且算法的精度要求也比拟高。对本文附件中的公交系统中所列的3957个公汽站点和39个地铁站点来说,直接要得到所有任意两站点之间的最优公交路径的计算量是相当大的。当面对这样一个密集的交通网络来说,对路线的选择主要是将面临一个类问题,根据类问题的处理特点,可以用某种主次改良的方法来求解。由于每次改良中的计算量都是多项式界的,改良的次数也是多项式界的。目前已找到具有这种特性的算法,如椭球算法,卡马卡算法,但都相当复杂。因此要满足出行者的路线需求,那么有必要对目标进展归类筛选,以降低不必要的选择、计算与搜索。不妨采用改良的广度优先搜索算法,基于改良次数为多项式界的算法理论,本文选择从某次乘公交的起点和终点的两端进展同时搜索,在满足换乘次数最少的条件下寻找不同线路中的共同站点或不同站点之间的一样线路,并计算其总路线的中的乘车时间和站点数。6站点线路交替序列模型的建立6.1模型的建立本文所要解决的根本问题是设计一个公交线路选择的自助查询的计算机系统,并从实际情况出发考虑,以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。我们建立交替序列模型寻找最优线路。6.1.1模型的预处理出行者所选择出行的起始站为v0,终到站为vd,从v0到vd的所有路径的集合也为TR,其中第i条路径为TRi,所乘坐的第节公交工具为pik。进一步分析和考虑出行者乘公交的具体情况,一个出行者的出行可简单描述为如下路径图2:出行者选乘公交路径规律分析示意图起始站中转站1乘第1节公交离开公交完毕选乘初次车出发
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号