公交转车问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,公交转车问题,1,公交转车问题,针对市场需求，某公司准备研制开发一个解决北京市公交线路选择问题的自主查询计算机系统。,为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。,公交：指公共交通工具 ，包括公共汽车与地铁。,2,公交转车问题,1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线 (1)S3359S1828 (2)S1557S0481 (3)S0971S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676,2、同时考虑公汽与地铁线路，解决以上问题。,3,基本参数设定,相邻公汽站平均行驶时间(包括停站时间)： 3分钟,相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟,公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟),地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟),地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟),公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟),公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元,地铁票价：3元（无论地铁线路间是否换乘）,注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。,4,公汽线路信息,公汽运行方式,（1）环形,（2）上下行（有可能上下行路线一致）,公汽收费方式,（1）分段计价,（2）单一票制1元,5,公汽线路信息,文件列出了520条公汽线路，下面是其中的一条：,L001,分段计价。,S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710,该线路是分段计价，且上下行路线一致的。,6,地铁线路信息,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,7,地铁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,8,地铁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,9,问题分析,从实际情况考虑，不同的查询者有不同的要求。在数学上体现出目标的不同。,一般可以考虑转车次数、乘车费用、乘车时间这3个目标。,问题可以归结为多目标优化问题。,10,问题分析,如何处理上面的多个目标？,多目标的处理最常用的方法是单目标化，即采用加权平均等方法将多个目标结合形成一个单一的目标。,本问题中，单目标化并不合适，比较适当的方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。,11,模型建立,我们先仅考虑公汽线路的情况。,设,N,表示问题中的公汽站点数,即,N,=3957,A,0,(,a,(,i,j,0),N,N,是直达最小站数矩阵，当存在公共汽车从站点直达站点时，表示从直达的最小站数。否则该元素取为+。,12,模型建立,令,A,m,(,a,(,i,j,m,),N,N,是,m,次转乘最小站数矩阵，其元素,a,(,i,j,m,)表示,m,次转车情形下，从,S,i,到,S,j,的最小站数。,显然,13,最小转车次数模型,对于给定的公汽站点,S,i,与,S,j,，最小转车次数模型可以写为,14,最小乘车时间模型,转车次数为,m,时，从,S,i,到,S,j,的总时间为,5,m,+3,a,(,i,j,m,),（转一次车5分钟，每乘一站，用时3分钟）,下面是最小乘车时间模型：,15,最小乘车费用模型,最小乘车费用模型可以写为如下的形式：,该模型是形式上的，对于求解没有实质性的作用。,16,最小转车次数模型求解,对于给定的公汽站点,S,i,与,S,j,，只要逐次求出(,a,(,i,j,m,)，直到其为有限值即可。,在实际求解时，先根据公汽线路的数据将,a,(i,j,0)的数据存储在矩阵,A,0,中。,17,最小转车次数模型求解,算法一（逐次查找）,对于给定的i,j,(1)若,a,(,i,j,0)+,表明转车次数为0,否则转(2);,(2),k,从1到,N,进行搜索,若,a,(,i,k,0)+,a,(,k,j,0) +,则转车次数为1,否则转(3);,(3),k,1,k,2,从1到,N,进行搜索,若a(,i,k,1,0)+,a,(,k,1,k,2,0)+,a,(,k,2,j,0) +,则转车次数为2.,18,最小转车次数模型求解,逐次查找算法的复杂度,若只要转一次车,则循环的步数为,N,;,若要转2次车,循环的步数为,N,2,;,若要转3次车,循环的步数为,N,3,由于,N,=3957,N,3,6.210,10,普通计算机运行时间较长，,若要转4次车，很难承受计算量!,19,最小转车次数模型求解,算法二（存储逐次查找）,(1)若,a,(,i,j,0)+,表明转车次数为0,否则转(2);,(2) 求出矩阵,A,1,(,a,(,i,j,1),N,N,其每个元素通过上面的表达式,用,k,从1到,N,循环求得.若对给定的,i,j,有,a,(,i,j,1)1)的计算工作量与,A,1,一致!,有可能计算转多次车.,21,最小转车次数模型求解,在前面的两个算法中,每次循环都要进行,N,次.事实上,对给定的,i,满足,a,(,i,k,0)+的,k,是很少的,我们只要对这些,k,进行循环.,在实际问题中,任何一个城市中,任何一个公汽站点所能到达的公汽站点只是城市中的一些“线”,相对于整个城市而言,数目是比较少的.,22,最小转车次数模型求解,算法三（有限搜索逐次查找）,给出矩阵B,其第i行记录的是满足,a,(,i,k,0),t,S,(,i,j,1).,因此,我们可以将,m,的范围放在0到12内求最优.,32,最小乘车时间模型求解,若m的范围过大,求解会有一定困难.,能否缩小,m,的范围?,在上页的讨论中,不等式,a,(,i,j,m,),m,+1的含义是总站数比转车次数至少大一.,我们可以给出,a,(,i,j,m,) 更好的下界,从而缩小,m,的范围.,33,两站点之间的最小站数,a,(,i,j,m,)表示,m,次转车下,从,S,i,到,S,j,的最小站数.,设,n,S,(,i,j,)表示站点,S,i,到,S,j,的最小站数(可以转车任意次).,显然,a,(,i,j,m,),n,S,(,i,j,),我们有,t,S,(,i,j,m,) = 5,m,+3,a,(,i,j,m,),5,m,+3,n,S,(,i,j,),34,两站点之间的最小站数,将公汽站点设为有向图中的结点.若,S,i,乘公汽1站可以到达,S,j,我们就设一条有向边从结点,i,指向结点,j.,对于每一条有向边,指定其权为1,显然求,n,S,(,i,j,)就转化为有向图中结点到结点的最短路径问题 .,对任意给定的,i,j,我们可以采用,Dijkstra,算法求得,n,S,(,i,j,).,35,最小乘车时间模型求解,对于第一对公汽站点,i,=3359,j,=1828,n,S,(,i,j,)=13,我们给出求解过程.,a,(,i,j,0) = ,t,S,(,i,j,0)=;,a,(,i,j,1) = 32,t,S,(,i,j,1)=101;,m,2时,t,S,(,i,j,m,),52+313=49.,因此,最小乘车时间在区间49,101上.,为求精确的最优解,必须接着求解.,36,最小乘车时间模型求解,a,(,i,j,2) = 18,t,S,(,i,j,2)=64;,m,3时,t,S,(,i,j,m,),53+313=54.,最优解位于区间54,64;,a,(,i,j,3) = 18,t,S,(,i,j,3)=69;,m,4时,t,S,(,i,j,m,),54+313=59.,最优解位于区间59,64;,37,最小乘车时间模型求解,a,(,i,j,4) = 17,t,S,(,i,j,4)=71;,m,5时,t,S,(,i,j,m,),55+313=64.,重复上述过程:,t,S,(,i,j,0)=,t,S,(,i,j,1)=101,t,S,(,i,j,2)=64,t,S,(,i,j,3)=69,t,S,(,i,j,4)=71,m,5时,t,S,(,i,j,m,),64.,可以看出,最小乘车时间为64,在转2次车时可以在此时间到达.,38,最小乘车时间模型求解算法,由上面的例子, 我们只要找到一个转车次数,m,转车次数不大于,m,时,最小乘车时间为,T,S,(,i,j,m,)=min,t,S,(,i,j,k,) |,k,m,转车次数大于,m,时, 乘车时间的下界为,5(,m,+1)+3,n,S,(,i,j,),若,T,S,(,i,j,m,) 5(,m,+1)+3,n,S,(,i,j,),则,T,S,(,i,j,m,) 为最优解.,39,最小乘车时间模型求解算法,Step1 用Dijkstra算法求出,n,S,(,i,j,) ,令,m,=0;,Step2 求出,a,(,i,j,m,),令,t,S,(,i,j,m,) = 5,m,+3,a,(,i,j,m,);,Step3 若,T,S,(,i,j,m,)=min,t,S,(,i,j,k,) |,k,m, 5(,m,+1)+3,n,S,(,i,j,), 则,T,S,(,i,j,m,)即为最短乘车时间;,否则令,m,:=,m,+1，转Step2.,40,最小乘车时间模型求解,第四对公汽站点S0008S0073的求解过程可以用下面的表格表示(,n,S,(,i,j,)=13) :,m,0,1,2,3,4,t,s,(i,j,m),83,67,63,59,T,s,(i,j,m),83,67,63,59,5(,m,+1)+3,n,s,(,i,j,),44,49,54,59,64,最小乘车时间为59,需转4次车.,其它答案参见评阅要点(该要点给出的答案中包含了起始的3分钟),41,综合考虑公汽与地铁,(1)最小转车次数,将地铁线路看成公汽线路.,最小转车次数这一目标的讨论难度没有增加,只是增加了几条公汽线路.,对于题中给的六组站点,其前5组站点都不在地铁边,因此增加地铁后,最小乘车次数没有变化,仍然是原来的1或2.,第6组2个站点都在地铁线上,最小转乘次数为0.,42,综合考虑公汽与地铁,(2)最小乘车费用,对于一般的两个站点之间的最小乘车费用,仅考虑公汽时讨论就很复杂,增加了地铁之后讨论还是差不多复杂,要用枚举法来求解.,也可以说,难度没有增加.,对于题中给的六组站点,仅考虑公汽时,最小费用为2元或3元,因此在综合考虑公汽与地铁时依然是最优解(乘一次地铁3元),43,综合考虑公汽与地铁,(3)最小乘车时间,增加了地铁后乘车时间的讨论变得相当复杂.,注:如果假设换成次数最多为2或3,会将问题大大简化.,在此,为了将问题合理的简化,我们首先研究这样一个问题：在考虑时间最少时，线路中是否存在先乘地铁，再转公汽，再乘地铁这样的乘车方案？,44,地铁-公汽-地铁?,考察下面两种方案,（A）从地铁站,D,k,乘地铁到地铁站,D,k,1,然后由公汽站,S,s,1,乘到公汽站,S,s,2,，再转地铁站,D,l,1,，乘地铁到地铁站,D,l,；,（B）直接乘地铁由地铁站,D,k,到,D,l,。,直观认识:(A)的时间(B)的时间,45,地铁-公汽-地铁?,设,t,DB,(,i,j,)表示乘地铁由地铁站,D,i,到地铁站,D,j,的最短时间，,n,SA,(,i,j,)表示可以由地铁站,D,i,转乘的公汽站乘公汽到可以由地铁站,D,j,转乘的公汽站的最小公汽站数。,于是,T,B,=,t,DB,(,k,l,),如果(A)方案中没有公汽转车,T,A,=,t,DB,(,k,k,1,)+3,n,SA,(,k,1,l,1,)+,t,DB,(,l,1,l,)+13,13表示换车时间,如果有公汽转车,等号要换成大于等于号,46,地铁-公汽-地铁?,T,A,-,T,B,t,DB,(,k,k,1,)+3,n,SA,(,k,1,l,1,)+,t,DB,(,l,1,l,)+13-,t,DB,(,k,l,),= 3,n,SA,(,k,1,l,1,) +13-,t,DB,(,k,1,l,1,),+,t,DB,(,k,k,1,) +,t,DB,(,k,1,l,1,)+,t,DB,(,l,1,l,)-,t,DB,(,k,l,),最后一个中括号中的式子是非负的.,因此,T,A,-,T,B,3,n,SA,(,k,1,l,1,) +13-,t,DB,(,k,1,l,1,),如果右式非负,则有,T,A,-,T,B,0.,47,地铁-公汽-地铁?,3,n,SA,(,k,1,l,1,) +13-,t,DB,(,k,1,l,1,),0?,一共有39个地铁站,我们通过计算机程序（,k,1,l,1,对从1到39进行遍历搜索）来判断上式左边的值,发现有四组地铁站对应的值为负,分别是(13,30),(16,30),(30,15),(30,16),这四组站点对应的,n,SA,(,k,1,l,1,) 值均为1.,对这四组点,再观察,T,A,-,T,B,t,DB,(,k,k,1,)+3,n,SA,(,k,1,l,1,)+,t,DB,(,l,1,l,)+13-,t,DB,(,k,l,),右端的值,48,地铁-公汽-地铁?,t,DB,(,k,k,1,)+3,n,SA,(,k,1,l,1,)+,t,DB,(,l,1,l,)+13-,t,DB,(,k,l,),=,t,DB,(,k,k,1,)+,t,DB,(,l,1,l,)+16-,t,DB,(,k,l,),对于前面四组,k,1,l,1,对,k,l,进行循环搜索,可以得到,t,DB,(,k,k,1,)+,t,DB,(,l,1,l,)+16-,t,DB,(,k,l,)的最小值都是2.,最终得到,T,A,-,T,B,0.,结论:对于题中给的数据,为了时间最省,不存在“,地铁-公汽-地铁”这种换乘方案.,换言之:地铁一次乘完!,49,最小乘车时间模型,对于任意两个公汽站点,不乘地铁的时间最小方案在问题一中已经求得.下面考虑必须乘地铁的方案:,乘,p,次（转,p,-1次）公汽，再乘地铁，最后乘次,q,（转,q,-1次)公汽到达终点的方案，下面将这样的方案记为,pDq,。,注:该方案包含了仅乘地铁的情况(,p,=,q,=0).,50,最小乘车时间模型,下面主要针对题中前5组站点进行研究.这五组站点均不能由地铁站直接转乘,因此,p,q,1.,求任意公汽站点,S,i,到公汽站点,S,j,在方案下的最短时间,即对任意的,p,q,以及任意的地铁站,D,k,D,l,求出起点乘,p,次公汽到可以直接转乘地铁站,D,k,的公汽站的最短时间,加上,D,k,到,D,l,的最短时间,再加上可以由地铁站,D,l,直接转乘的公汽站乘,q,公汽次到达终点公汽站的最短时间.,51,最小乘车时间模型,(1)站数:,N,1,(,i,k,p,-1),乘车时间: 3,N,1,(,i,k,p,-1),转车时间5(,p,-1),S,i,D,k,S,j,D,l,(1)p次,(3)q次,(3)站数:,N,2,(,l,j,q,-1),乘车时间: 3,N,2,(,l,j,q,-1),转车时间5(,q,-1),(2),(2)乘车时间:,t,D,(,k,l,),(4)公汽转地铁,地铁转公汽时间:13,总时间:,t,SDS,(,i,j,p,q,k,l,)= 3,N,1,(,i,k,p,-1)+ 5(,p,-1)+,t,D,(,k,l,)+3,N,2,(,l,j,q,-1)+ 5(,q,-1)+13,52,最小乘车时间模型,数学模型,min,t,SDS,(,i,j,p,q,k,l,)|1,p,q,1 ,k,l,39,k,l,在,t,SDS,(,i,j,p,q,k,l,)表达式中,地铁乘坐时间,t,D,(,k,l,)是很容易计算的.,若没有转车,t,D,(,k,l,)=2.5,n,D,(,k,l,)(每站2.5分钟),若转1次车,t,D,(,k,l,)=2.5,n,D,(,k,l,)+4.,不存在转2次以上的情况.,53,最小乘车时间模型求解,t,SDS,(,i,j,p,q,k,l,)=,3,N,1,(,i,k,p,-1)+ 5(,p,-1)+,t,D,(,k,l,)+3,N,2,(,l,j,q,-1)+ 5(,q,-1)+13,对于固定的,i,j,我们要遍历,p,q,k,l,来求上式的最小值.,对于,k,l,进行遍历是比较简单的.,为了缩小,p,q,的取值范围,可以类似于问题一来给出站数(公汽与地铁)的下界.,54,下界,设,n,SDS,(,i,j,)表示从,S,i,乘车(公汽或地铁,可以转车任意次)到,S,j,的最小乘车站数.我们可以用Dijkstra求最短路径来求出这个数.,记,M,=,N,1,(,i,k,p,-1)+,N,2,(,l,j,q,-1)为乘车方案中公汽的站数.根据公汽的站数加地铁站数不小于最小乘车站数,有,M,+,n,D,(,k,l,),n,SDS,(,i,j,).,55,下界,将,M,=,N,1,(,i,k,p,-1)+,N,2,(,l,j,q,-1),代入,t,SDS,(,i,j,p,q,k,l,)=,3,N,1,(,i,k,p,-1)+ 5(,p,-1)+,t,D,(,k,l,)+3,N,2,(,l,j,q,-1)+ 5(,q,-1)+13,得,t,SDS,(,i,j,p,q,k,l,)=3,M,+,t,D,(,k,l,)+5(,p,+,q,)+3,由于,t,D,(,k,l,)=2.5,n,D,(,k,l,)或2.5,n,D,(,k,l,)+4,有,t,SDS,(,i,j,p,q,k,l,),3,M+,2.5,n,D,(,k,l,) +5(,p,+,q,)+3,=0.5,M,+,2.5,M+,2.5,n,D,(,k,l,) +5(,p,+,q,)+3,M,+,n,D,(,k,l,),n,SDS,(,i,j,),56,下界,t,SDS,(,i,j,p,q,k,l,),0.5,M,+,2.5,M+,2.5,n,D,(,k,l,) +5(,p,+,q,)+3,再由,M,+,n,D,(,k,l,),n,SDS,(,i,j,)得,t,SDS,(,i,j,p,q,k,l,),0.5,M,+2.5,n,SDS,(,i,j,)+ 5(,p,+,q,)+3,另外,M,表示乘公汽的站数,显然,M,p,+,q,(一共乘了,p,+,q,次公汽,每次至少一站).,我们最终得到,t,SDS,(,i,j,p,q,k,l,),2.5,n,SDS,(,i,j,)+ 5.5(,p,+,q,)+3,根据这一下界, 搜索不多的,p,q,就得到最小时间.,57,最小乘车时间模型求解,对第一个点对,i,=3359,j,=1828,n,SDS,(,i,j,)=12(由于增加了地铁,最小站数小了).,(1)p+q=2,p=1,q=1,t=84.5,p,+,q,3时,下界2.5,n,SDS,(,i,j,)+ 5.5(,p,+,q,)+3=49.5,(2) p+q=3,p=1,q=2,t=71;p=2,q=1,t=75.5,p,+,q,4时,下界2.5,n,SDS,(,i,j,)+ 5.5(,p,+,q,)+3=55,58,最小乘车时间模型求解,(3) p+q=4,p=1,q=3,t=76;,p=2,q=2,t=62;,p=3,q=1,t=80.5,p,+,q,5时,下界2.5,n,SDS,(,i,j,)+ 5.5(,p,+,q,)+3=60.5,59,最小乘车时间模型求解,(3) p+q=5,p=1,q=4,t=77;,p=2,q=3,t=67;,p=3,q=2,t=67,p=4,q=1,t=85.5,p,+,q,6时,下界2.5,n,SDS,(,i,j,)+ 5.5(,p,+,q,)+3=66,p,+,q,5时,t*=62,p,+,q,6时,t 66,因此,最优解在p=q=2时取得.,60,最小乘车时间模型求解,Step1 用Dijkstra算法求出,n,SDS,(,i,j,) ,令,h,=2;,Step2 计算下界,A,(,h,+1,i,j,)=,2.5,n,SDS,(,i,j,)+ 5.5(,h+,1)+3;,Step3 p从1到h-1循环,q=h-p,计算,t,SDS,(,i,j,p,q,k,l,),对,k,l,遍历求出,f,(,p,h,),=,min,t,SDS,(,i,j,p,q,k,l,) |,1,k,l,39,k,l,T,SDS,(,i,j,h,),=,min,f,(,p,r,),|2,r,h, ;,Step4 若,T,SDS,(,i,j,h,) ,A,(,h,+1,i,j,)停止;否则令,h,:=,h,+1，转Step3.,61,求解结果,用上述算法,针对题中的数据进行求解,除去第二对站点,计算到p+q=5时可以求出最优解.,对第二对站点,可以加大搜索量求得最优解.另外还可以求得更好的下界来压缩搜索范围,比如考虑起点到整个地铁线的最小站数,这样,M,的取值相应的增加,从而下界增大.再结合不乘地铁的情况,对第二对站点,也只要搜索到p+q=5就可以了.,62,求解结果,仅考虑公汽时的求解过程和结果,63,求解结果,乘地铁时的求解结果,点对,3359-1828,1557-0481,0971-0485,0008-0073,0148-0485,t,SDS,(,p+q,),1+1,84.5,116.5,96,53.5,87.5,1+2,71,110,95,58.5,86.5,2+1,75.5,118.5,101,54,92.5,1+3,76,107,100,63.5,91.5,2+2,62,112,100,59,91.5,3+1,80.5,117.5,105.5,56,97.5,1+4,77,112,105,68.5,96.5,2+3,67,109,105,64,96.5,3+2,67,114,104.5,61,96.5,4+1,85.5,122.5,110.5,59.5,102.5,T,SDS,(,i,j,5),62,107,95,53.5,86.5,A,(6,i,j,),66,98.5,96,63.5,91,64,求解结果,时间最少的乘车方案(仅考虑公汽),65,求解结果,时间最少的乘车方案(结合地铁),66,求解结果,最小乘车时间表,67,