数学建模论文-公交系统最佳路线的查询模型.doc
《数学建模论文-公交系统最佳路线的查询模型.doc》由会员分享,可在线阅读,更多相关《数学建模论文-公交系统最佳路线的查询模型.doc(32页珍藏版)》请在三一文库上搜索。
1、公交系统最佳路线的查询模型摘要本文针对“乘公交,看奥运”的问题,建立了多目标优化模型,解决了仅坐公车,可坐公车和地铁,可坐公车、地铁或步行等三种情况下最佳出行路线的确定问题。对于问题一,我们用多目标决策中的分层序列法对该多目标问题优化,建立了分别以“换乘次数最少为第一目标,出行时间最短和车费最少为第二、第三目标”和以“出行时间最短为第一目标,换乘次数最少和车费最少为第二、第三目标”的优化模型和模型。同时,给出了乘客满意度函数,根据不同乘客的需求,对这两种模型进行了比较,满足了不同乘客的需求。在模型情况下,6对起始站终点站的最佳线路有:最佳路线有2条,转车1次,耗时104分,车费共3元;:最佳路
2、线有2条,转车2次,耗时109分,车费共3元;:最佳路线有1条,转车1次,耗时131分,车费共2元;:最佳路线有5条,转车1次,耗时86分,车费共2元;:最佳路线有1条,转车2次,耗时109分,车费共3元;:最佳路线有1条,转车1次,耗时68分,车费共2元。对于问题二,我们通过改进后的Floyd算法,将地铁交通系统嵌入原有的公交系统中,并分层序列法建立的优化模型,得出了较第一问时间上更优化的路线。6对起始站终点站的最佳线路有:最佳路线有1条,共转车3次,其中公交与地铁间转乘2次,地铁与地铁间转乘1次,耗时87.5分钟,车费共计5元。 :最佳路线有10条,转车2次,都为公交与地铁间转车,耗时99
3、分钟,车费共计5元。:最佳路线有1条,转车2次,其中公交与地铁间转乘2次,地铁与地铁间转乘1次,耗时56.5分钟,车费共计5元。:最佳路线有1条,转车0次,通过地铁到达,耗时30分钟,车费共计3元。对于问题三,我们提出了交通阻抗的概念,得到了乘客在公交线上出行的换乘次数、出行时间、乘车费用、乘车距离等综合费用指标,将多目标优化问题转化为了单目标优化问题。并以为例,进行了计算,得出对于最佳路线为 乘坐 在S1784下车,步行一站至。关键词:多目标优化模型;分层序列法;乘客满意度;交通阻抗;综合费用指标 一、 问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行,届时有大量观众到现场观看奥
4、运比赛,其中大部分人将会乘坐公共交通工具(简称公交,包括公汽、地铁等)出行。这些年来,城市的公交系统有了很大发展,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足查询者的各种不同需求。请你们解决如下问题:1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用你们的模型与算法,求出以下6对起始站终到站之间的最佳路线(要有清晰的评价说明)。(1)、S33
5、59S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S36762、同时考虑公汽与地铁线路,解决以上问题。3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。二、问题分析该问题是一个解决城市公交系统最佳路线的优化问题。首先,由于原题中给的数据不规范,为了实现Matlab的编程,须对数据进行预处理。对数据初步分析,可以发现,一般来说,每条线路都有上行和下行之分,但如果下行线是上行线原路返回或是环线,即缺失了下行线数据。为了简化编程,我们将缺失的下行数据进行如下处理:若
6、下行线是上行线的原路返回,则将上行线的站点逆置后加到对应的下行线中;而对于环行线,则直接照搬到对应的下行线中。其次,解决城市公交系统的最优路线选择问题,需要结合乘客的多方需要,从市场调查分析中,我们可以把乘客的基本需求归纳为:换乘次数应尽量减少;乘车时间应尽量节省;乘车费用应尽量降低;乘车经过的站数尽量少。因此,我们应该建立一个多目标的优化模型来对最优线路进行选择。再次,对城市公交路线进行最优分析,需要把公交系统的实体抽象成图论中的网络拓扑图,Dijkstra算法是当今在最短路问题中比较常用的方法,但是在此处,该算法不完全适用,因为,1该算法要求要求给出两点间的直接距离,而在此处,上千个公交站
7、点之间的距离并未直接给出,我们需要在考虑时间、票价的同时给出相应的权值,工作量较大。2该算法算出的是一点到其余各点的权值最少路径,城市的公交站点有上千个,用该算法计量很大,使公交系统的查询时间过长。3该算法给出的是最短路径图,在选择路线的时候可能适用,但在选择公交路线时可能未考虑乘客不愿意转乘的心理,其计算结果可能造成乘客需要换乘好几次或十几次才能够到达目的地, 这显然是没有任何意义的。因此我们采用了改进的Dijkstra算法对问题进行求解。最后,在第二问同时考虑公交和地铁线路时,出现了一个地铁站对应一个或多个公车站的情况,由于一个地铁站对应的多个公车站之间可以通过地铁站换乘,必须对题中给出的
8、换乘时间及步行时间做进一步细化,如表1表1 细化后换乘时间表公汽车站间步行平均耗时分钟地铁车站间步行平均耗时分钟公汽车站与地铁站间步行平均耗时分钟等待公车的平均耗时分钟等待地铁的平均耗时分钟公汽换乘公汽平均耗时分钟地铁换乘地铁平均耗时分钟地铁换乘公汽平均耗时分钟公汽换乘地铁平均耗时分钟第三问增加步行的方式,加大了路线选择的灵活性,但由于各站点之间的明确距离或步行时间未给出,我们只能给出初步的模型。三、模型假设1. 假设题目所给的数据真实可靠;2各种公交方式都正常运行,如:公交车道不堵车,每列地铁正点按班到站等。3各种公交方式的平均邻站行驶时间及换乘时间基本符合实际情况。4. 乘客所能接受的最大
9、换乘次数为2次,若包括地铁与地铁之间的换乘,乘客的最大换乘次数不超过3次。四、定义与符号说明表示换乘总次数表示乘车总费用表示乘车总耗时表示通过车站的公车数表示两站、之间可直达的公车数表示和之间的一次中转站个数表示与可通过一次公车直达的车站个数表示能在地铁站换乘的公车数表示从地铁站到地铁站所有路径数表示公车站表示通过车站的公车表示两站、之间可直达的公车表示乘车从到的时间表示乘车从到的车费表示与可通过一次公车直达的车站表示和之间的一次中转站表示能在地铁站换乘的公车表示从地铁站到地铁站的时间表示从地铁站到地铁站的车费五、问题一的模型建立与求解(一)模型的分析 首先,选择公交方式出行时,可行的乘车方案
10、一般有多个,出行者必须做出选择。而出行者考虑的因素很多,不能简单的抽象为最短路问题。因此需要对公交乘客的出行心理、行为进行调查研究,确定模型的优化目标和约束条件。公交乘客选择出行路径的决策过程主要受到以下4 个因素的影响:“换乘次数”、“出行距离”、“出行耗时”和“车费”。所以,这个问题是一个多目标优化问题。其目标是, 由于同时处理多个目标问题的最优化较困难,经常是有所失才能有所得,故我们采用分层序列法分析。分层法的思想是把目标按其重要性给出一个序列,分为最重要目标,次要目标等等。为了得出各项指标的重要性,我们查找了相关资料。图1是1999 年在南京市的8 个主要公交站点进行了一次公交乘客出行
11、心理问询调查结果。由图1 可见, 41.16 %的乘客在选择出行路径时首选考虑的是换乘最少,其次是时间最短。并考虑到题目数据中只给出的耗时数据及乘车费用, 而且一般来说,当相邻公汽站平均行驶时间和换乘车时间基本确定时,路程的长短与出行时间的长短成正比。故除了换乘次数,我们还选择了易于量化的“公交出行时间最少”和“车费最少”。在上述分析的基础上,我们分别选用“换乘次数最少”和“时间最少”作为第一优化目标, 建立了分层优化的多目标模型和模型。(二)模型的建立1按上所述,模型以换乘次数最少为第一目标,出行时间最短和车费最少分别为第二和第三目标。设其序列分别为,然后逐个将其最优化:对第一目标即换乘次数
12、最少求最优并找出所有最优解的集合记为。然后在内求第二个目标即出行时间最短的最优解,记这时的集合为。最后在内求第三目标即乘车费用最少的最优解,记这时的集合为,其模型如下: 若,则集合为模型的最佳线路。2算法的描述(1) 算法的流程图描述 流程图如图2。图2 模型算法流程图 (2)算法的数学描述1) 符号定义1. 起始站为,则通过起始站的公车为;2. 终点站为,则通过终点站的公车为。2)若存在使得,则与可直达做该次公车从到的时间为;车费为。这种情况下优化第二目标的算法为 ;优化第三目标的算法为 。3) 若通过换乘车一次可到达考虑起始站和终点站,那么有、。若存在,使得,说明和可以通过即站中转。那么乘
13、客所乘的公车车次为分别为、。这种情况下优化第二目标的算法为 优化第三目标的算法为 。4) 如若考虑两次换乘车能到达有使得存在,说明从起始站到终点站可以通过两次换乘车实现。两个中转站分别为、。乘客所乘车次为。这种情况下优化第二目标的算法为最小化函数: 优化第三目标的算法为最小化函数: (三)模型的建立1按上所述,该模型以时间最少为第一目标,换乘次数最少和车费最少分别为第二和第三目标。设其序列分别为,然后逐个将其最优化:对第一目标即出行时间最短求最优并找出所有最优解的集合记为。然后在内求第二个目标即换乘次数最小的最优解,记这时的集合为。最后在内求第三目标即乘车费用最少的最优解,记这时的集合为,其模
14、型如下: 若,则集合为模型最佳路线。2.算法的流程图描述图3 模型算法流程图 (四)模型和的求解我们根据以上的模型和算法,利用MATLAB编程(源程序见附录1)。输入问题中六对起始站点和终点后,分别得出了的它们之间的最佳路线。模型情况下确定的最佳路线如下,(1) :最佳路线有2条,转车1次,耗时104分钟,车费共计3元。(注:该处的耗时加上了起始站点的平均等车时间,下同) (2):最佳路线有2条,转车2次,耗时109分钟,车费共计3元。 (3) :最佳路线有1条,转车1次,耗时131分钟,车费共计2元。 (4):最佳路线有5条,转车1次,耗时86分钟,车费共计2元。 (5):最佳路线有1条,转
15、车2次,耗时109分钟,车费共计3元。 (6):最佳路线有1条,转车1次,耗时68分钟,车费共计2元。 模型情况下确定的最佳路线如下(1) :最佳路线有30条,转车2次,耗时76分钟,车费共计3元。(此处只列举2条,完整的路线见附录3)(2):最佳路线有2条,转车2次,耗时109分钟,车费共计3元。 (3) :最佳路线有2条,转车2次,耗时79分钟,车费共计3元。 (4):最佳路线有1条,转车2次,耗时70分钟,车费共计3元。 (5):最佳路线有1条,转车2次,耗时109分钟,车费共计3元。 (6):最佳路线有6条,转车2次,耗时49分钟,车费共计3元。 (四)结果的评价由于题目中要求所建模型
16、需满足查询者的各种不同需求,我们对第一问的结果给出一个评价模型。评价一条路线优劣的方法有很多,这里,我们采用乘客的满意度进行分析。假设,乘客对换乘次数的满意度函数为 (为正整数);乘客对乘车时间的满意度函数为 乘客对乘车费用的满意度函数为 (为正整数)对于该多目标函数,最优解是但对第一问的结果分析发现,三个函数很难同时达到最大值,在这里用线性加权法构造一个总体满意度函数目标函数为 ;而的权重,根据人群的不同,取值也是不尽相同的。它由个人的性格等决定。由于奥运会期间,北京将吸引大批的中外游客,故在此定义两类人群:A外地游客型:外地游客借在北京观看奥运的机会欣赏古城的美景,因此行程时间、票价对于他
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 论文 公交 系统 最佳 路线 查询 模型
链接地址:https://www.31doc.com/p-3931618.html