公交转车问题(数学建模)ppt课件.ppt
《公交转车问题(数学建模)ppt课件.ppt》由会员分享,可在线阅读,更多相关《公交转车问题(数学建模)ppt课件.ppt(67页珍藏版)》请在三一办公上搜索。
1、公交转车问题,南京邮电大学理学院杨振华制作,南京邮电大学数理学院杨振华制作 ,公交转车问题,针对市场需求,某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足查询者的各种不同需求。公交:指公共交通工具 ,包括公共汽车与地铁。,南京邮电大学数理学院杨振华制作 ,公交转车问题,1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用你们的模型与算法,求出以下6对起始站终到站之间的最佳路线 (1)S3359S1828 (2)S1557S0481 (3)S0971S
2、0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676 2、同时考虑公汽与地铁线路,解决以上问题。,南京邮电大学数理学院杨振华制作 ,基本参数设定,相邻公汽站平均行驶时间(包括停站时间): 3分钟相邻地铁站平均行驶时间(包括停站时间): 2.5分钟公汽换乘公汽平均耗时: 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时: 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时: 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时: 6分钟(其中步行时间4分钟)公汽票价:分为单一票价与分段计价两种,标记于线路后;其中分段计价的票价为:020站:1元;2140站:2元
3、;40站以上:3元地铁票价:3元(无论地铁线路间是否换乘)注:以上参数均为简化问题而作的假设,未必与实际数据完全吻合。,南京邮电大学数理学院杨振华制作 ,公汽线路信息,公汽运行方式(1)环形(2)上下行(有可能上下行路线一致)公汽收费方式(1)分段计价(2)单一票制1元,南京邮电大学数理学院杨振华制作 ,公汽线路信息,文件列出了520条公汽线路,下面是其中的一条:L001分段计价。S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710该线路是分段计价,且上下行路线一致的。
4、,南京邮电大学数理学院杨振华制作 ,地铁线路信息,T1票价3元,本线路使用,并可换乘T2。D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21-D22-D23T2票价3元,本线路使用,并可换乘T1。环行:D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24,南京邮电大学数理学院杨振华制作 ,地铁T1线换乘公汽信息,D01:S0567,S0042,S0025D02:S1487D03:S0
5、303,S0302D04:S0566D05:S0436,S0438,S0437,S0435D06:S0392,S0394,S0393,S0391D07:S0386,S0388,S0387,S0385D08:S3068,S0617,S0619,S0618,S0616D09:S1279D10:S2057,S0721,S0722,S0720D11:S0070,S2361,S3721D12:S0609,S0608D13:S2633,S0399,S0401,S0400D14:S3321,S2535,S2464D15:S3329,S2534D16:S3506,S0167,S0168D17:S0237,S0
6、239,S0238,S0236,S0540D18:S0668D19:S0180,S0181D20:S2079,S2933,S1919,S1921,S1920D21:S0465,S0467,S0466,S0464D22:S3457D23:S2512,南京邮电大学数理学院杨振华制作 ,地铁T2线换乘公汽信息,D24:S0537,S3580D25:S0526,S0528,S0527,S0525D26:S3045,S0605,S0607D12:S0609,S0608D27:S0087,S0088,S0086D28:S0855,S0856,S0854,S0857D29:S0631,S0632,S0630
7、D30:S3874,S1426,S1427D31:S0211,S0539,S0541,S0540D32:S0978,S0497,S0498D18:S0668D33:S1894,S1896,S1895D34:S1104,S0576,S0578,S0577D35:S3010,S0583,S0582D36:S3676,S0427,S0061,S0060D37:S1961,S2817,S0455,S0456D38:S3262,S0622D39:S1956,S0289,S0291,南京邮电大学数理学院杨振华制作 ,问题分析,从实际情况考虑,不同的查询者有不同的要求。在数学上体现出目标的不同。一般可以考虑
8、转车次数、乘车费用、乘车时间这3个目标。问题可以归结为多目标优化问题。,南京邮电大学数理学院杨振华制作 ,问题分析,如何处理上面的多个目标?多目标的处理最常用的方法是单目标化,即采用加权平均等方法将多个目标结合形成一个单一的目标。本问题中,单目标化并不合适,比较适当的方法是对每个目标寻求最佳线路,然后让乘客按照自己的需求进行选择。,南京邮电大学数理学院杨振华制作 ,模型建立,我们先仅考虑公汽线路的情况。设N表示问题中的公汽站点数,即N=3957,A0(a(i,j,0)NN是直达最小站数矩阵,当存在公共汽车从站点直达站点时,表示从直达的最小站数。否则该元素取为+。,南京邮电大学数理学院杨振华制作
9、 ,模型建立,令Am(a(i,j,m)NN是m次转乘最小站数矩阵,其元素a(i,j,m)表示m次转车情形下,从Si到Sj的最小站数。显然,南京邮电大学数理学院杨振华制作 ,最小转车次数模型,对于给定的公汽站点Si与Sj ,最小转车次数模型可以写为,南京邮电大学数理学院杨振华制作 ,最小乘车时间模型,转车次数为m时,从Si到Sj的总时间为5m+3a(i,j,m),(转一次车5分钟,每乘一站,用时3分钟)下面是最小乘车时间模型:,南京邮电大学数理学院杨振华制作 ,最小乘车费用模型,最小乘车费用模型可以写为如下的形式:,该模型是形式上的,对于求解没有实质性的作用。,南京邮电大学数理学院杨振华制作 ,
10、最小转车次数模型求解,对于给定的公汽站点Si与Sj ,只要逐次求出(a(i,j,m),直到其为有限值即可。,在实际求解时,先根据公汽线路的数据将a(i,j,0)的数据存储在矩阵A0中。,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,算法一(逐次查找)对于给定的i,j,(1)若a(i,j,0)+,表明转车次数为0,否则转(2);(2)k从1到N进行搜索,若a(i,k,0)+,a(k,j,0) +,则转车次数为1,否则转(3);(3) k1, k2从1到N进行搜索,若a(i,k1,0)+, a(k1,k2,0)+, a(k2,j,0) +,则转车次数为2.,南京邮电大学数理学院杨振华制作
11、 ,最小转车次数模型求解,逐次查找算法的复杂度若只要转一次车,则循环的步数为N;若要转2次车,循环的步数为N2;若要转3次车,循环的步数为N3由于N=3957, N3 6.21010,普通计算机运行时间较长,若要转4次车,很难承受计算量!,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,算法二(存储逐次查找)(1)若a(i,j,0)+,表明转车次数为0,否则转(2);(2) 求出矩阵A1(a(i,j,1)NN ,其每个元素通过上面的表达式,用k从1到N循环求得.若对给定的i,j,有a(i,j,1)+,表明转车次数为1;类似可以计算多次转车的情况注:矩阵A0,A1等计算后存储在计算机中,
12、南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,存储逐次查找算法的复杂度矩阵A1的计算:一共计算N2个元素,每个元素的计算要循环N步,计算量为N3.运行时间依然较长。优点:矩阵Am (m1)的计算工作量与A1一致!有可能计算转多次车.,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,在前面的两个算法中,每次循环都要进行N次.事实上,对给定的i,满足a(i,k,0)+的k是很少的,我们只要对这些k进行循环.在实际问题中,任何一个城市中,任何一个公汽站点所能到达的公汽站点只是城市中的一些“线”,相对于整个城市而言,数目是比较少的.,南京邮电大学数理学院杨振华制作 ,最小转车次数模型
13、求解,算法三(有限搜索逐次查找)给出矩阵B,其第i行记录的是满足a(i,k,0)+的所有的“k”.将存储逐次查找算法中的k从1到N循环改为正对矩阵B第i行中的“k”进行循环.,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,有限搜索逐次查找算法的复杂度矩阵Am的计算:一共计算N2个元素,每个元素的计算要循环的步数大大小于N,大约为N/10,计算量约为N3/10.一般的计算机可以实现.,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,对于题目中给出的六组公汽站点,其最小转车次数分别为(1)S3359S18281(2)S1557S04812(3)S0971S04851(4)S000
14、8S00731(5)S0148S04852(6)S0087S36761,南京邮电大学数理学院杨振华制作 ,转车次数,由于算法复杂性的问题,许多参赛队都假设“最多转2次车”,少数参赛队考虑转3次车,个别的参赛队考虑转4次车或更多.由于所给的6组站点最小转车次数为1或2,似乎假设最多转2次车是合理的.根据题目中的数据,北京市的任意两个公汽站点之间一般需转几次车?,南京邮电大学数理学院杨振华制作 ,转车次数,N=3957,一共有N(N-1)=15653892对公汽站点,我们给出它们的最小转车次数,根据题目中的数据,北京市的公汽站点转5次车可以全部到达.,根据表中的数据,假设转最多2次车是不合理的,假
15、设转最多3次车有一定的合理性.,南京邮电大学数理学院杨振华制作 ,最小乘车费用,左边的表给出的时最小转车次数,即对应的一种乘车方案的乘车费用.,关于最小乘车费用,其模型一般只有形式上的,对求解没有直接的作用.我们对具体的六对站点给出讨论的结果.,南京邮电大学数理学院杨振华制作 ,最小乘车费用,易见,第二,四,五,六对站点对应的费用是最小费用(为什么?),南京邮电大学数理学院杨振华制作 ,最小乘车费用,对于第一个点对S3359S1828,如果换乘次数大于等于2,显然费用至少为3.若换乘次数为1,采用枚举方法将乘车方案全部列出.一共由9种方案,其中8种费用为3元,一种费用为4元.因此, 最小乘车费
16、用为3.类似,第三个点对的换乘次数为1的11种方案的最小费用也是3.,南京邮电大学数理学院杨振华制作 ,最小乘车时间模型求解,根据上面的模型,若已知a(i,j,m)的值,则可以求出tS(i,j,m)关于m的最小值.由于m的取值从0到无穷大,必须采用一定的技巧来求出最小值.注:参赛队一般选取m从0到2(或0到3),是不合理的,不过也“成功”避免了求解的困难.,南京邮电大学数理学院杨振华制作 ,最小乘车时间模型求解,考虑第一对公汽站点1)S3359S1828最小转车次数为1,a(i,j,0) = , tS(i,j,0)=;a(i,j,1) = 32, tS(i,j,1)=101;由于a(i,j,m
17、) m+1,有tS(i,j,m) 8m+3.若m13,则tS(i,j,m) 105tS(i,j,1).因此,我们可以将m的范围放在0到12内求最优.,南京邮电大学数理学院杨振华制作 ,最小乘车时间模型求解,若m的范围过大,求解会有一定困难.能否缩小m的范围?在上页的讨论中,不等式a(i,j,m) m+1的含义是总站数比转车次数至少大一.我们可以给出a(i,j,m) 更好的下界,从而缩小m的范围.,南京邮电大学数理学院杨振华制作 ,两站点之间的最小站数,a(i,j,m)表示m次转车下,从Si到Sj的最小站数.设nS(i,j)表示站点Si到Sj的最小站数(可以转车任意次).显然a(i,j,m) n
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 公交 转车 问题 数学 建模 ppt 课件

链接地址:https://www.31ppt.com/p-1386748.html