公交转车问题(数学建模).ppt

公交转车问题,南京邮电大学理学院杨振华制作 yangzhenhua,南京邮电大学数理学院杨振华制作 yangzhenhua,公交转车问题,针对市场需求，某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。 公交：指公共交通工具 ，包括公共汽车与地铁。,南京邮电大学数理学院杨振华制作 yangzhenhua,公交转车问题,1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线 (1)S3359S1828 (2)S1557S0481 (3)S0971S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676 2、同时考虑公汽与地铁线路，解决以上问题。,南京邮电大学数理学院杨振华制作 yangzhenhua,基本参数设定,相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。,南京邮电大学数理学院杨振华制作 yangzhenhua,公汽线路信息,公汽运行方式 （1）环形 （2）上下行（有可能上下行路线一致） 公汽收费方式 （1）分段计价 （2）单一票制1元,南京邮电大学数理学院杨振华制作 yangzhenhua,公汽线路信息,文件列出了520条公汽线路，下面是其中的一条： L001 分段计价。 S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710 该线路是分段计价，且上下行路线一致的。,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁线路信息,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-D23 T2 票价3元，本线路使用，并可换乘T1。 环行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁T1线换乘公汽信息,D01：S0567，S0042，S0025 D02：S1487 D03：S0303，S0302 D04：S0566 D05：S0436，S0438，S0437，S0435 D06：S0392，S0394，S0393，S0391 D07：S0386，S0388，S0387，S0385 D08：S3068，S0617，S0619，S0618，S0616 D09：S1279 D10：S2057，S0721，S0722，S0720 D11：S0070，S2361，S3721 D12：S0609，S0608 D13：S2633，S0399，S0401，S0400 D14：S3321，S2535，S2464 D15：S3329，S2534 D16：S3506，S0167，S0168 D17：S0237，S0239，S0238，S0236，S0540 D18：S0668 D19：S0180，S0181 D20：S2079，S2933，S1919，S1921，S1920 D21：S0465，S0467，S0466，S0464 D22：S3457 D23：S2512,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁T2线换乘公汽信息,D24：S0537，S3580 D25：S0526，S0528，S0527，S0525 D26：S3045，S0605，S0607 D12：S0609，S0608 D27：S0087，S0088，S0086 D28：S0855，S0856，S0854，S0857 D29：S0631，S0632，S0630 D30：S3874，S1426，S1427 D31：S0211，S0539，S0541，S0540 D32：S0978，S0497，S0498 D18：S0668 D33：S1894，S1896，S1895 D34：S1104，S0576，S0578，S0577 D35：S3010，S0583，S0582 D36：S3676，S0427，S0061，S0060 D37：S1961，S2817，S0455，S0456 D38：S3262，S0622 D39：S1956，S0289，S0291,南京邮电大学数理学院杨振华制作 yangzhenhua,问题分析,从实际情况考虑，不同的查询者有不同的要求。在数学上体现出目标的不同。 一般可以考虑转车次数、乘车费用、乘车时间这3个目标。 问题可以归结为多目标优化问题。,南京邮电大学数理学院杨振华制作 yangzhenhua,问题分析,如何处理上面的多个目标？ 多目标的处理最常用的方法是单目标化，即采用加权平均等方法将多个目标结合形成一个单一的目标。 本问题中，单目标化并不合适，比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。,南京邮电大学数理学院杨振华制作 yangzhenhua,模型建立,我们先仅考虑公汽线路的情况。 设N表示问题中的公汽站点数,即N=3957, A0(a(i,j,0)NN 是直达最小站数矩阵，当存在公共汽车从站点直达站点时，表示从直达的最小站数。否则该元素取为+。,南京邮电大学数理学院杨振华制作 yangzhenhua,模型建立,令Am(a(i,j,m)NN是m次转乘最小站数矩阵，其元素a(i,j,m)表示m次转车情形下，从Si到Sj的最小站数。 显然,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型,对于给定的公汽站点Si与Sj ，最小转车次数模型可以写为,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型,转车次数为m时，从Si到Sj的总时间为 5m+3a(i,j,m), （转一次车5分钟，每乘一站，用时3分钟） 下面是最小乘车时间模型：,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车费用模型,最小乘车费用模型可以写为如下的形式：,该模型是形式上的，对于求解没有实质性的作用。,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,对于给定的公汽站点Si与Sj ，只要逐次求出(a(i,j,m)，直到其为有限值即可。,在实际求解时，先根据公汽线路的数据将a(i,j,0)的数据存储在矩阵A0中。,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,算法一（逐次查找） 对于给定的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.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,逐次查找算法的复杂度 若只要转一次车,则循环的步数为N; 若要转2次车,循环的步数为N2; 若要转3次车,循环的步数为N3 由于N=3957, N3 6.21010,普通计算机运行时间较长， 若要转4次车，很难承受计算量!,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,算法二（存储逐次查找） (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等计算后存储在计算机中,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,存储逐次查找算法的复杂度 矩阵A1的计算: 一共计算N2个元素,每个元素的计算要循环N步,计算量为N3.运行时间依然较长。 优点： 矩阵Am (m1)的计算工作量与A1一致! 有可能计算转多次车.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,在前面的两个算法中,每次循环都要进行N次.事实上,对给定的i,满足a(i,k,0)+的k是很少的,我们只要对这些k进行循环. 在实际问题中,任何一个城市中,任何一个公汽站点所能到达的公汽站点只是城市中的一些“线”,相对于整个城市而言,数目是比较少的.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,算法三（有限搜索逐次查找） 给出矩阵B,其第i行记录的是满足a(i,k,0)+的所有的“k”. 将存储逐次查找算法中的k从1到N循环改为正对矩阵B第i行中的“k”进行循环.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,有限搜索逐次查找算法的复杂度 矩阵Am的计算: 一共计算N2个元素,每个元素的计算要循环的步数大大小于N,大约为N/10,计算量约为N3/10. 一般的计算机可以实现.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小转车次数模型求解,对于题目中给出的六组公汽站点,其最小转车次数分别为 (1)S3359S1828 1 (2)S1557S0481 2 (3)S0971S0485 1 (4)S0008S0073 1 (5)S0148S0485 2 (6)S0087S3676 1,南京邮电大学数理学院杨振华制作 yangzhenhua,转车次数,由于算法复杂性的问题,许多参赛队都假设“最多转2次车”,少数参赛队考虑转3次车,个别的参赛队考虑转4次车或更多. 由于所给的6组站点最小转车次数为1或2,似乎假设最多转2次车是合理的. 根据题目中的数据,北京市的任意两个公汽站点之间一般需转几次车?,南京邮电大学数理学院杨振华制作 yangzhenhua,转车次数,N=3957,一共有N(N-1) =15653892对公汽站点,我们给出它们的最小转车次数,根据题目中的数据,北京市的公汽站点转5次车可以全部到达.,根据表中的数据,假设转最多2次车是不合理的,假设转最多3次车有一定的合理性.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车费用,左边的表给出的时最小转车次数,即对应的一种乘车方案的乘车费用.,关于最小乘车费用,其模型一般只有形式上的,对求解没有直接的作用. 我们对具体的六对站点给出讨论的结果.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车费用,易见,第二,四,五,六对站点对应的费用是最小费用(为什么?),南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车费用,对于第一个点对S3359S1828,如果换乘次数大于等于2,显然费用至少为3. 若换乘次数为1,采用枚举方法将乘车方案全部列出.一共由9种方案,其中8种费用为3元,一种费用为4元.因此, 最小乘车费用为3. 类似,第三个点对的换乘次数为1的11种方案的最小费用也是3.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,根据上面的模型,若已知a(i,j,m)的值,则可以求出tS(i,j,m)关于m的最小值. 由于m的取值从0到无穷大,必须采用一定的技巧来求出最小值. 注:参赛队一般选取m从0到2(或0到3),是不合理的,不过也“成功”避免了求解的困难.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,考虑第一对公汽站点 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) m+1,有tS(i,j,m) 8m+3. 若m13,则tS(i,j,m) 105tS(i,j,1). 因此,我们可以将m的范围放在0到12内求最优.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,若m的范围过大,求解会有一定困难. 能否缩小m的范围? 在上页的讨论中,不等式a(i,j,m) m+1的含义是总站数比转车次数至少大一. 我们可以给出a(i,j,m) 更好的下界,从而缩小m的范围.,南京邮电大学数理学院杨振华制作 yangzhenhua,两站点之间的最小站数,a(i,j,m)表示m次转车下,从Si到Sj的最小站数. 设nS(i,j)表示站点Si到Sj的最小站数(可以转车任意次). 显然 a(i,j,m) nS(i,j) 我们有tS(i,j,m) = 5m+3a(i,j,m) 5m+3nS(i,j),南京邮电大学数理学院杨振华制作 yangzhenhua,两站点之间的最小站数,将公汽站点设为有向图中的结点.若Si乘公汽1站可以到达Sj ,我们就设一条有向边从结点i指向结点j.对于每一条有向边,指定其权为1,显然求nS(i,j)就转化为有向图中结点到结点的最短路径问题 . 对任意给定的i,j,我们可以采用Dijkstra算法求得 nS(i,j).,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,对于第一对公汽站点i=3359,j=1828, nS(i,j)=13,我们给出求解过程. a(i,j,0) = , tS(i,j,0)=; a(i,j,1) = 32, tS(i,j,1)=101; m 2时,tS(i,j,m) 52+313=49. 因此,最小乘车时间在区间49,101上. 为求精确的最优解,必须接着求解.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,a(i,j,2) = 18, tS(i,j,2)=64; m 3时,tS(i,j,m) 53+313=54. 最优解位于区间54,64; a(i,j,3) = 18, tS(i,j,3)=69; m 4时,tS(i,j,m) 54+313=59. 最优解位于区间59,64;,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,a(i,j,4) = 17, tS(i,j,4)=71; m 5时,tS(i,j,m) 55+313=64. 重复上述过程:tS(i,j,0)=, tS(i,j,1)=101, tS(i,j,2)=64,tS(i,j,3)=69, tS(i,j,4)=71, m 5时,tS(i,j,m) 64. 可以看出,最小乘车时间为64,在转2次车时可以在此时间到达.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解算法,由上面的例子, 我们只要找到一个转车次数m, 转车次数不大于m时,最小乘车时间为 TS(i,j,m)=mintS(i,j,k) | km 转车次数大于m时, 乘车时间的下界为 5(m+1)+3 nS(i,j) 若TS(i,j,m) 5(m+1)+3 nS(i,j), 则TS(i,j,m) 为最优解.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解算法,Step1 用Dijkstra算法求出nS(i,j) ,令m=0; Step2 求出a(i,j,m),令tS(i,j,m) = 5m+3a(i,j,m); Step3 若 TS(i,j,m)=mintS(i,j,k) | km 5(m+1)+3 nS(i,j), 则TS(i,j,m)即为最短乘车时间; 否则令m:=m+1，转Step2.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,第四对公汽站点S0008S0073的求解过程可以用下面的表格表示(nS(i,j)=13) :,最小乘车时间为59,需转4次车. 其它答案参见评阅要点(该要点给出的答案中包含了起始的3分钟),南京邮电大学数理学院杨振华制作 yangzhenhua,综合考虑公汽与地铁,(1)最小转车次数 将地铁线路看成公汽线路. 最小转车次数这一目标的讨论难度没有增加,只是增加了几条公汽线路. 对于题中给的六组站点,其前5组站点都不在地铁边,因此增加地铁后,最小乘车次数没有变化,仍然是原来的1或2. 第6组2个站点都在地铁线上,最小转乘次数为0.,南京邮电大学数理学院杨振华制作 yangzhenhua,综合考虑公汽与地铁,(2)最小乘车费用 对于一般的两个站点之间的最小乘车费用,仅考虑公汽时讨论就很复杂,增加了地铁之后讨论还是差不多复杂,要用枚举法来求解. 也可以说,难度没有增加. 对于题中给的六组站点,仅考虑公汽时,最小费用为2元或3元,因此在综合考虑公汽与地铁时依然是最优解(乘一次地铁3元),南京邮电大学数理学院杨振华制作 yangzhenhua,综合考虑公汽与地铁,(3)最小乘车时间 增加了地铁后乘车时间的讨论变得相当复杂. 注:如果假设换成次数最多为2或3,会将问题大大简化. 在此,为了将问题合理的简化,我们首先研究这样一个问题：在考虑时间最少时，线路中是否存在先乘地铁，再转公汽，再乘地铁这样的乘车方案？,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁-公汽-地铁?,考察下面两种方案 （A）从地铁站Dk乘地铁到地铁站Dk1然后由公汽站Ss1乘到公汽站Ss2 ，再转地铁站Dl1，乘地铁到地铁站Dl； （B）直接乘地铁由地铁站Dk到Dl 。 直观认识:(A)的时间(B)的时间,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁-公汽-地铁?,设tDB(i,j)表示乘地铁由地铁站Di到地铁站Dj的最短时间，nSA(i,j)表示可以由地铁站Di转乘的公汽站乘公汽到可以由地铁站Dj转乘的公汽站的最小公汽站数。 于是, TB = tDB(k,l) 如果(A)方案中没有公汽转车 TA = tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13 13表示换车时间 如果有公汽转车,等号要换成大于等于号,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁-公汽-地铁?,TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l) = 3 nSA(k1,l1) +13- tDB(k1,l1) + tDB(k,k1) + tDB(k1,l1)+ tDB(l1,l)- tDB(k,l) 最后一个中括号中的式子是非负的. 因此TA - TB 3 nSA(k1,l1) +13- tDB(k1,l1) 如果右式非负,则有TA - TB 0.,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁-公汽-地铁?,3 nSA(k1,l1) +13- tDB(k1,l1) 0? 一共有39个地铁站,我们通过计算机程序（k1,l1对从1到39进行遍历搜索）来判断上式左边的值,发现有四组地铁站对应的值为负,分别是(13,30),(16,30),(30,15),(30,16),这四组站点对应的nSA(k1,l1) 值均为1. 对这四组点,再观察 TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l) 右端的值,南京邮电大学数理学院杨振华制作 yangzhenhua,地铁-公汽-地铁?,tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l) =tDB(k,k1)+ tDB(l1,l)+16- tDB(k,l) 对于前面四组k1,l1,对k,l进行循环搜索,可以得到tDB(k,k1)+ tDB(l1,l)+16- tDB(k,l)的最小值都是2. 最终得到TA - TB 0. 结论:对于题中给的数据,为了时间最省,不存在“地铁-公汽-地铁”这种换乘方案. 换言之:地铁一次乘完!,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型,对于任意两个公汽站点,不乘地铁的时间最小方案在问题一中已经求得.下面考虑必须乘地铁的方案: 乘p次（转p-1次）公汽，再乘地铁，最后乘次q（转q-1次)公汽到达终点的方案，下面将这样的方案记为pDq。 注:该方案包含了仅乘地铁的情况(p=q=0).,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型,下面主要针对题中前5组站点进行研究.这五组站点均不能由地铁站直接转乘,因此p,q1. 求任意公汽站点Si到公汽站点Sj在方案下的最短时间,即对任意的p,q,以及任意的地铁站Dk,Dl,求出起点乘p次公汽到可以直接转乘地铁站Dk的公汽站的最短时间,加上Dk到Dl的最短时间,再加上可以由地铁站Dl直接转乘的公汽站乘q公汽次到达终点公汽站的最短时间.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型,(1)站数:N1(i,k,p-1),乘车时间: 3N1(i,k,p-1),转车时间5(p-1),Si,Dk,Sj,Dl,(1)p次,(3)q次,(3)站数:N2(l,j,q-1),乘车时间: 3N2(l,j,q-1),转车时间5(q-1),(2),(2)乘车时间: tD(k,l),(4)公汽转地铁,地铁转公汽时间:13,总时间:tSDS(i,j,p,q,k,l)= 3N1(i,k,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型,数学模型 mintSDS(i,j,p,q,k,l)|1p,q,1 k,l 39,kl 在tSDS(i,j,p,q,k,l)表达式中,地铁乘坐时间tD(k,l)是很容易计算的. 若没有转车, tD(k,l)=2.5nD(k,l)(每站2.5分钟) 若转1次车, tD(k,l)=2.5nD(k,l)+4. 不存在转2次以上的情况.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,tSDS(i,j,p,q,k,l)= 3N1(i,k,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13 对于固定的i,j,我们要遍历p,q,k,l来求上式的最小值. 对于k,l进行遍历是比较简单的. 为了缩小p,q的取值范围,可以类似于问题一来给出站数(公汽与地铁)的下界.,南京邮电大学数理学院杨振华制作 yangzhenhua,下界,设nSDS(i,j)表示从Si乘车(公汽或地铁,可以转车任意次)到Sj的最小乘车站数.我们可以用Dijkstra求最短路径来求出这个数. 记M=N1(i,k,p-1)+N2(l,j,q-1)为乘车方案中公汽的站数.根据公汽的站数加地铁站数不小于最小乘车站数,有M+nD(k,l) nSDS(i,j).,南京邮电大学数理学院杨振华制作 yangzhenhua,下界,将M=N1(i,k,p-1)+N2(l,j,q-1) 代入tSDS(i,j,p,q,k,l)= 3N1(i,k,p-1)+ 5(p-1)+ tD(k,l)+3N2(l,j,q-1)+ 5(q-1)+13 得tSDS(i,j,p,q,k,l)=3M+tD(k,l)+5(p+q)+3 由于tD(k,l)=2.5nD(k,l)或2.5nD(k,l)+4, 有tSDS(i,j,p,q,k,l) 3M+ 2.5nD(k,l) +5(p+q)+3 =0.5M+2.5M+ 2.5nD(k,l) +5(p+q)+3 M+nD(k,l) nSDS(i,j),南京邮电大学数理学院杨振华制作 yangzhenhua,下界,tSDS(i,j,p,q,k,l) 0.5M+2.5M+ 2.5nD(k,l) +5(p+q)+3 再由M+nD(k,l) nSDS(i,j)得 tSDS(i,j,p,q,k,l) 0.5M+2.5nSDS(i,j)+ 5(p+q)+3 另外,M表示乘公汽的站数,显然Mp+q,(一共乘了p+q次公汽,每次至少一站). 我们最终得到 tSDS(i,j,p,q,k,l) 2.5nSDS(i,j)+ 5.5(p+q)+3 根据这一下界, 搜索不多的p,q就得到最小时间.,南京邮电大学数理学院杨振华制作 yangzhenhua,最小乘车时间模型求解,对第一个点对, i=3359, j=1828, nSDS(i,j)=12(由于增加了地铁,最小站数小了). (1)p+q=2,p=