《公交转车问题》由会员分享，可在线阅读，更多相关《公交转车问题（67页珍藏版）》请在金锄头文库上搜索。
1、公交转车问题,南京邮电大学理学院杨振华制作 ,南京邮电大学数理学院杨振华制作 ,公交转车问题,针对市场需求，某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。 为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。 公交：指公共交通工具 ，包括公共汽车与地铁。,南京邮电大学数理学院杨振华制作 ,公交转车问题,1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线 (1)S3359S1828 (2)S1557S0481 (3)S09
2、71S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676 2、同时考虑公汽与地铁线路，解决以上问题。,南京邮电大学数理学院杨振华制作 ,基本参数设定,相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元
3、；2140站：2元；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-D23 T2 票价3元，本线路使用，并可换乘T1。 环行：D24-D25-D26-D12-D27-D28-D29-D30-D31-D32-D18-D33-D34-D35-D36-D37-D38-D39-D24,南京邮电大学数理学院杨振华制作 ,地铁T1线换乘公汽信息,D01：S0567，S
5、0042，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
6、，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,南京邮电大学数理学院杨振华制作 ,地铁T2线换乘公汽信息,D24：S0537，S3580 D25：S0526，S0528，S0527，S0525 D26：S3045，S0605，S0607 D12：S0609，S0608 D27：S0087，S0088，S0
7、086 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，S029
8、1,南京邮电大学数理学院杨振华制作 ,问题分析,从实际情况考虑，不同的查询者有不同的要求。在数学上体现出目标的不同。 一般可以考虑转车次数、乘车费用、乘车时间这3个目标。 问题可以归结为多目标优化问题。,南京邮电大学数理学院杨振华制作 ,问题分析,如何处理上面的多个目标？ 多目标的处理最常用的方法是单目标化，即采用加权平均等方法将多个目标结合形成一个单一的目标。 本问题中，单目标化并不合适，比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。,南京邮电大学数理学院杨振华制作 ,模型建立,我们先仅考虑公汽线路的情况。 设N表示问题中的公汽站点数,即N=3957, A0(a(
9、i,j,0)NN 是直达最小站数矩阵，当存在公共汽车从站点直达站点时，表示从直达的最小站数。否则该元素取为+。,南京邮电大学数理学院杨振华制作 ,模型建立,令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
11、) k1, k2从1到N进行搜索,若a(i,k1,0)+, a(k1,k2,0)+, a(k2,j,0) +,则转车次数为2.,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,逐次查找算法的复杂度 若只要转一次车,则循环的步数为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 ,其每
12、个元素通过上面的表达式,用k从1到N循环求得.若对给定的i,j,有a(i,j,1)+,表明转车次数为1; 类似可以计算多次转车的情况 注:矩阵A0,A1等计算后存储在计算机中,南京邮电大学数理学院杨振华制作 ,最小转车次数模型求解,存储逐次查找算法的复杂度 矩阵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. 一般的计算机可以实现.,南京邮
14、电大学数理学院杨振华制作 ,最小转车次数模型求解,对于题目中给出的六组公汽站点,其最小转车次数分别为 (1)S3359S1828 1 (2)S1557S0481 2 (3)S0971S0485 1 (4)S0008S0073 1 (5)S0148S0485 2 (6)S0087S3676 1,南京邮电大学数理学院杨振华制作 ,转车次数,由于算法复杂性的问题,许多参赛队都假设“最多转2次车”,少数参赛队考虑转3次车,个别的参赛队考虑转4次车或更多. 由于所给的6组站点最小转车次数为1或2,似乎假设最多转2次车是合理的. 根据题目中的数据,北京市的任意两个公汽站点之间一般需转几次车?,南京邮电大学数理学院杨振华制作 ,转车次数,N=3957,一共有N(N-1) =15653892对公汽站点,我们给出它们的最小转车次数,根据题目中的数据,北京市的公汽站点转5次车可以全部到达.,根
