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

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分钟分钟)公汽票价：分为单一票价与分段计价两种，

4、标记于线路后；公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：其中分段计价的票价为：020站：站：1元；元；2140站：站：2元；元；40站以上：站以上：3元元地铁票价：地铁票价：3元（无论地铁线路间是否换乘）元（无论地铁线路间是否换乘）注：以上参数均为简化问题而作的假设，未必与实际数据完注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。全吻合。南京邮电大学数理学院杨振华制作 公汽线路信息 公汽运行方式公汽运行方式（1）环形）环形（2）上下行（有可能上下行路线一致）上下行（有可能上下行路线一致）公汽收费方式公汽收费方式（1）分段计价）分段计价（2）单一票制）

5、单一票制1元元南京邮电大学数理学院杨振华制作 公汽线路信息文件列出了文件列出了520条公汽线路，下面是其中的一条：条公汽线路，下面是其中的一条：L001分段计价。分段计价。S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710该线路是分段计价，且上下行路线一致的。该线路是分段计价，且上下行路线一致的。南京邮电大学数理学院杨振华制作 地铁线路信息T1票价票价3元，本线路使用，并可换乘元，本线路使用，并可换乘T2。D01-D02-D03-D04-D05-D06-D07-D08

6、-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：S0303，S0302D04：S0566D05：S0436，S0438，S0437，S0435D06：S0392，S0394，S

7、0393，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，S0239，S0238，S0236，S0540D18：S0668D19：S0180，S0181D20：S2079，S2933，S

8、1919，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，S0630D30：S3874，S1426，S1427D31：S0211，S0539，S0541，S0540D32：S0978，S0497，S

9、0498D18：S0668D33：S1894，S1896，S1895D34：S1104，S0576，S0578，S0577D35：S3010，S0583，S0582D36：S3676，S0427，S0061，S0060D37：S1961，S2817，S0455，S0456D38：S3262，S0622D39：S1956，S0289，S0291南京邮电大学数理学院杨振华制作 问题分析从实际情况考虑，不同的查询者有不同的要从实际情况考虑，不同的查询者有不同的要求。在数学上体现出目标的不同。求。在数学上体现出目标的不同。一般可以考虑转车次数、乘车费用、乘车时一般可以考虑转车次数、乘车费用、乘车时间这

10、间这3个目标。个目标。问题可以归结为多目标优化问题。问题可以归结为多目标优化问题。南京邮电大学数理学院杨振华制作 问题分析如何处理上面的多个目标？如何处理上面的多个目标？多目标的处理最常用的方法是单目标化，即多目标的处理最常用的方法是单目标化，即采用加权平均等方法将多个目标结合形成一采用加权平均等方法将多个目标结合形成一个单一的目标。个单一的目标。本问题中，单目标化并不合适，比较适当的本问题中，单目标化并不合适，比较适当的方法是对每个目标寻求最佳线路，然后让乘方法是对每个目标寻求最佳线路，然后让乘客按照自己的需求进行选择。客按照自己的需求进行选择。 南京邮电大学数理学院杨振华制作 模型建立我们

11、先我们先仅考虑公汽线路的情况仅考虑公汽线路的情况。设设N表示问题中的公汽站点数表示问题中的公汽站点数,即即N=3957,A0(a(i,j,0)NN是直达最小站数矩阵，当存在公共汽车从站是直达最小站数矩阵，当存在公共汽车从站点直达站点时，表示从直达的最小站数。否点直达站点时，表示从直达的最小站数。否则该元素取为则该元素取为+。 南京邮电大学数理学院杨振华制作 模型建立令令Am(a(i,j,m)NN是是m次转乘最小站数矩次转乘最小站数矩阵，其元素阵，其元素a(i,j,m)表示表示m次转车情形下，从次转车情形下，从Si到到Sj的最小站数。的最小站数。显然显然 ,1 | ) 1,()0 ,(min),

12、(jkikNkmjkakiamjia南京邮电大学数理学院杨振华制作 最小转车次数模型对于给定的公汽站点对于给定的公汽站点Si与与Sj ，最小转车次数模，最小转车次数模型可以写为型可以写为),(|minmjiam南京邮电大学数理学院杨振华制作 最小乘车时间模型转车次数为转车次数为m时，从时，从Si到到Sj的总时间为的总时间为5m+3a(i,j,m),（转一次车（转一次车5分钟，每乘一站，用时分钟，每乘一站，用时3分钟）分钟）下面是最小乘车时间模型：下面是最小乘车时间模型：),(35),(min0mjiammjitSm南京邮电大学数理学院杨振华制作 最小乘车费用模型最小乘车费用模型可以写为如下的形

13、式：最小乘车费用模型可以写为如下的形式：,|),(),(),(min21211互不相等nnmmnnnnkkkjikkfjkfkif该模型是形式上的，对于求解没有实质性的该模型是形式上的，对于求解没有实质性的作用。作用。南京邮电大学数理学院杨振华制作 最小转车次数模型求解对于给定的公汽站点对于给定的公汽站点Si与与Sj ，只要逐次求出，只要逐次求出(a(i,j,m)，直到其为有限值即可。，直到其为有限值即可。),(|minmjiam,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia在实际求解时，先根据公汽线路的数据将在实际求解时，先根据公汽线路的数据将a(i,j,0)的

14、数据存储在矩阵的数据存储在矩阵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.,1 | ) 1,()0 ,(min),(jkikNkmjkakiamj

15、ia),(|minmjiam南京邮电大学数理学院杨振华制作 最小转车次数模型求解逐次查找算法的复杂度逐次查找算法的复杂度若只要转一次车若只要转一次车,则循环的步数为则循环的步数为N;若要转若要转2次车次车,循环的步数为循环的步数为N2;若要转若要转3次车次车,循环的步数为循环的步数为N3由于由于N=3957, N3 6.21010,普通计算机运行普通计算机运行时间较长，时间较长，若要转若要转4次车，很难承受计算量次车，很难承受计算量!南京邮电大学数理学院杨振华制作 最小转车次数模型求解算法二（存储逐次查找）算法二（存储逐次查找）(1)若若a(i,j,0)+,表明转车次数为表明转车次数为0,否则

16、转否则转(2);(2) 求出矩阵求出矩阵A1(a(i,j,1)NN ,其每个元素通其每个元素通过上面的表达式过上面的表达式,用用k从从1到到N循环求得循环求得.若对给若对给定的定的i,j,有有a(i,j,1)1)的计算工作量与的计算工作量与A1一致一致!有可能计算转多次车有可能计算转多次车.南京邮电大学数理学院杨振华制作 最小转车次数模型求解在前面的两个算法中在前面的两个算法中,每次循环都要进行每次循环都要进行N次次.事实上事实上,对给定的对给定的i,满足满足a(i,k,0)+的的k是很少是很少的的,我们只要对这些我们只要对这些k进行循环进行循环.在实际问题中在实际问题中,任何一个城市中任何一

17、个城市中,任何一个公汽任何一个公汽站点所能到达的公汽站点只是城市中的一些站点所能到达的公汽站点只是城市中的一些“线线”,相对于整个城市而言相对于整个城市而言,数目是比较少的数目是比较少的.,1 | ) 1,()0 ,(min),(jkikNkmjkakiamjia南京邮电大学数理学院杨振华制作 最小转车次数模型求解算法三（有限搜索逐次查找）算法三（有限搜索逐次查找）给出矩阵给出矩阵B,其第其第i行记录的是满足行记录的是满足a(i,k,0)tS(i,j,1).因此因此,我们可以将我们可以将m的范围放在的范围放在0到到12内求最优内求最优.),(35),(min0mjiammjitSm南京邮电大学

18、数理学院杨振华制作 最小乘车时间模型求解若若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的最小站数的最小站数(可以转车可以转车任意次任意次).显然

19、显然a(i,j,m) nS(i,j)我们有我们有tS(i,j,m) = 5m+3a(i,j,m) 5m+3nS(i,j)南京邮电大学数理学院杨振华制作 两站点之间的最小站数将公汽站点设为有向图中的结点将公汽站点设为有向图中的结点.若若Si乘公汽乘公汽1站可以到达站可以到达Sj ,我们就设一条有向边从结点我们就设一条有向边从结点i指指向结点向结点j.对于每一条有向边对于每一条有向边,指定其权为指定其权为1,显然显然求求nS(i,j)就转化为有向图中结点到结点的最短就转化为有向图中结点到结点的最短路径问题路径问题 .对任意给定的对任意给定的i,j,我们可以采用我们可以采用Dijkstra算法求算法

20、求得得 nS(i,j).南京邮电大学数理学院杨振华制作 最小乘车时间模型求解对于第一对公汽站点对于第一对公汽站点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上上.为求精确的最优解为求精确的最优解,必须接着求解必须接着求解.南京邮电大学数理学院杨振华制作 最小乘车时间模型求解a(i,j,2) = 18, tS(i,j,2)=64; m 3时

21、时,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;南京邮电大学数理学院杨振华制作 最小乘车时间模型求解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.可以看

22、出可以看出,最小乘车时间为最小乘车时间为64,在转在转2次车时可次车时可以在此时间到达以在此时间到达.南京邮电大学数理学院杨振华制作 最小乘车时间模型求解算法由上面的例子由上面的例子, 我们只要找到一个转车次数我们只要找到一个转车次数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) 为最优解为最优解.南京邮电大学数理学院杨振华制作 最小乘车时间模

23、型求解算法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.南京邮电大学数理学院杨振华制作 最小乘车时间模型求解第四对公汽站点第四对公汽站点S0008S0073的求解过程可的求解过程可以用下面的表格表示以用下面的表格表示(nS(i,j)=13) : m01234ts(i,

24、j,m)83676359Ts(i,j,m)836763595(m+1)+3ns(i,j) 4449545964最小乘车时间为最小乘车时间为59,需转需转4次车次车.其它答案参见评阅要点其它答案参见评阅要点(该要点给出的答案中该要点给出的答案中包含了起始的包含了起始的3分钟分钟)南京邮电大学数理学院杨振华制作 综合考虑公汽与地铁(1)最小转车次数最小转车次数将地铁线路看成公汽线路将地铁线路看成公汽线路.最小转车次数这一目标的讨论难度没有增加最小转车次数这一目标的讨论难度没有增加,只只是增加了几条公汽线路是增加了几条公汽线路.对于题中给的六组站点对于题中给的六组站点,其前其前5组站点都不在地组站点

25、都不在地铁边铁边,因此增加地铁后因此增加地铁后,最小乘车次数没有变化最小乘车次数没有变化,仍然是原来的仍然是原来的1或或2.第第6组组2个站点都在地铁线上个站点都在地铁线上,最小转乘次数为最小转乘次数为0.南京邮电大学数理学院杨振华制作 综合考虑公汽与地铁(2)最小乘车费用最小乘车费用对于一般的两个站点之间的最小乘车费用对于一般的两个站点之间的最小乘车费用,仅仅考虑公汽时讨论就很复杂考虑公汽时讨论就很复杂,增加了地铁之后讨增加了地铁之后讨论还是差不多复杂论还是差不多复杂,要用枚举法来求解要用枚举法来求解.也可以说也可以说,难度没有增加难度没有增加.对于题中给的六组站点对于题中给的六组站点,仅考

26、虑公汽时仅考虑公汽时,最小费最小费用为用为2元或元或3元元,因此在综合考虑公汽与地铁时因此在综合考虑公汽与地铁时依然是最优解依然是最优解(乘一次地铁乘一次地铁3元元)南京邮电大学数理学院杨振华制作 综合考虑公汽与地铁(3)最小乘车时间最小乘车时间增加了地铁后乘车时间的讨论变得相当复杂增加了地铁后乘车时间的讨论变得相当复杂.注注:如果假设换成次数最多为如果假设换成次数最多为2或或3,会将问题大会将问题大大简化大简化.在此在此,为了将问题合理的简化为了将问题合理的简化,我们首先研究这我们首先研究这样一个问题：在考虑时间最少时，线路中是样一个问题：在考虑时间最少时，线路中是否存在先乘地铁，再转公汽，

27、再乘地铁这样否存在先乘地铁，再转公汽，再乘地铁这样的乘车方案？的乘车方案？ 南京邮电大学数理学院杨振华制作 地铁-公汽-地铁?考察下面两种方案考察下面两种方案（A）从地铁站）从地铁站Dk乘地铁到地铁站乘地铁到地铁站Dk1然后由然后由公汽站公汽站Ss1乘到公汽站乘到公汽站Ss2 ，再转地铁站，再转地铁站Dl1，乘地铁到地铁站乘地铁到地铁站Dl； （B）直接乘地铁由地铁站）直接乘地铁由地铁站Dk到到Dl 。直观认识直观认识:(A)的时间的时间(B)的时间的时间南京邮电大学数理学院杨振华制作 地铁-公汽-地铁?设设tDB(i,j)表示乘地铁由地铁站表示乘地铁由地铁站Di到地铁站到地铁站Dj的的最短时

28、间，最短时间，nSA(i,j)表示可以由地铁站表示可以由地铁站Di转乘的转乘的公汽站乘公汽到可以由地铁站公汽站乘公汽到可以由地铁站Dj转乘的公汽转乘的公汽站的最小公汽站数。站的最小公汽站数。于是于是, TB = tDB(k,l)如果如果(A)方案中没有公汽转车方案中没有公汽转车TA = tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+1313表示换车时间表示换车时间如果有公汽转车如果有公汽转车,等号要换成大于等于号等号要换成大于等于号南京邮电大学数理学院杨振华制作 地铁-公汽-地铁?TA - TB tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13-

29、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.南京邮电大学数理学院杨振华制作 地铁-公汽-地铁?3 nSA(k1,l1) +13- tDB(k1,l1) 0?一共有一共有39个地铁站个地铁站,我们通过计算机程序（我们通过计算机程序（k1,l1对从对从1到到39进行遍历搜索）来判断上式

30、左边的值进行遍历搜索）来判断上式左边的值,发现有发现有四组地铁站对应的值为负四组地铁站对应的值为负,分别是分别是(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)右端的值右端的值南京邮电大学数理学院杨振华制作 地铁-公汽-地铁?tDB(k,k1)+3 nSA(k1,l1)+ tDB(l1,l)+13- tDB(k,l)=tDB(k,k1)+ tDB(l1,l)+16- t

31、DB(k,l)对于前面四组对于前面四组k1,l1,对对k,l进行循环搜索进行循环搜索,可以得可以得到到tDB(k,k1)+ tDB(l1,l)+16- tDB(k,l)的最小值都是的最小值都是2.最终得到最终得到TA - TB 0.结论结论:对于题中给的数据对于题中给的数据,为了时间最省为了时间最省,不存不存在在“地铁地铁-公汽公汽-地铁地铁”这种换乘方案这种换乘方案.换言之换言之:地铁一次乘完地铁一次乘完!南京邮电大学数理学院杨振华制作 最小乘车时间模型对于任意两个公汽站点对于任意两个公汽站点,不乘地铁的时间最小不乘地铁的时间最小方案在问题一中已经求得方案在问题一中已经求得.下面考虑必须乘地

32、下面考虑必须乘地铁的方案铁的方案:乘乘p次（转次（转p-1次）公汽，再乘地铁，最后乘次）公汽，再乘地铁，最后乘次次q（转（转q-1次次)公汽到达终点的方案，下面将公汽到达终点的方案，下面将这样的方案记为这样的方案记为pDq。注注:该方案包含了仅乘地铁的情况该方案包含了仅乘地铁的情况(p=q=0).南京邮电大学数理学院杨振华制作 最小乘车时间模型下面主要针对题中前下面主要针对题中前5组站点进行研究组站点进行研究.这五这五组站点均不能由地铁站直接转乘组站点均不能由地铁站直接转乘,因此因此p,q1.求任意公汽站点求任意公汽站点Si到公汽站点到公汽站点Sj在方案下的最在方案下的最短时间短时间,即对任意

33、的即对任意的p,q,以及任意的地铁站以及任意的地铁站Dk,Dl,求出起点乘求出起点乘p次公汽到可以直接转乘地次公汽到可以直接转乘地铁站铁站Dk的公汽站的最短时间的公汽站的最短时间,加上加上Dk到到Dl的最的最短时间短时间,再加上可以由地铁站再加上可以由地铁站Dl直接转乘的公直接转乘的公汽站乘汽站乘q公汽次到达终点公汽站的最短时间公汽次到达终点公汽站的最短时间.南京邮电大学数理学院杨振华制作 最小乘车时间模型(1)站数站数:N1(i,k,p-1),乘车时间乘车时间: 3N1(i,k,p-1),转车时间转车时间5(p-1)SiDkSjDl(1)p次(3)q次(3)站数站数:N2(l,j,q-1),

34、乘车时间乘车时间: 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南京邮电大学数理学院杨振华制作 最小乘车时间模型数学模型数学模型mintSDS(i,j,p,q,k,l)|1p,q,1 k,l 39,kl在在tSDS(i,j,p,q,k,l)表达式中表达式中,地铁乘坐时间地铁乘坐时间tD(k,l)是很容易计算的是很容易计算的

35、.若没有转车若没有转车, tD(k,l)=2.5nD(k,l)(每站每站2.5分钟分钟)若转若转1次车次车, tD(k,l)=2.5nD(k,l)+4.不存在转不存在转2次以上的情况次以上的情况.南京邮电大学数理学院杨振华制作 最小乘车时间模型求解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的取值范围的取值范围,可以类似于问

36、题一来可以类似于问题一来给出站数给出站数(公汽与地铁公汽与地铁)的下界的下界.南京邮电大学数理学院杨振华制作 下界设设nSDS(i,j)表示从表示从Si乘车乘车(公汽或地铁公汽或地铁,可以转车可以转车任意次任意次)到到Sj的最小乘车站数的最小乘车站数.我们可以用我们可以用Dijkstra求最短路径来求出这个数求最短路径来求出这个数.记记M=N1(i,k,p-1)+N2(l,j,q-1)为乘车方案中公汽的站为乘车方案中公汽的站数数.根据公汽的站数加地铁站数不小于最小乘车站数根据公汽的站数加地铁站数不小于最小乘车站数,有有M+nD(k,l) nSDS(i,j).南京邮电大学数理学院杨振华制作 下界

37、将将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)+3M+nD(k,l) nSDS(i,j)南京邮电大学数理学院杨振华制作 下界tSDS(i,

38、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就得到最小时间就得到最小时间.南京邮电大学数理学院杨振华制作 最小乘车时间模型求解对

39、第一个点对对第一个点对, i=3359, j=1828, nSDS(i,j)=12(由由于增加了地铁于增加了地铁,最小站数小了最小站数小了).(1)p+q=2,p=1,q=1t=84.5,p+q 3时时,下界下界2.5nSDS(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.5p+q 4时时,下界下界2.5nSDS(i,j)+ 5.5(p+q)+3=55南京邮电大学数理学院杨振华制作 最小乘车时间模型求解(3) p+q=4,p=1,q=3,t=76;p=2,q=2,t=62;p=3,q=1,t=80.5p+q 5时时,下界下界

40、2.5nSDS(i,j)+ 5.5(p+q)+3=60.5南京邮电大学数理学院杨振华制作 最小乘车时间模型求解(3) p+q=5,p=1,q=4,t=77;p=2,q=3,t=67;p=3,q=2,t=67p=4,q=1,t=85.5p+q 6时时,下界下界2.5nSDS(i,j)+ 5.5(p+q)+3=66p+q 5时时,t*=62, p+q 6时时,t 66因此因此,最优解在最优解在p=q=2时取得时取得.南京邮电大学数理学院杨振华制作 最小乘车时间模型求解Step1 用用Dijkstra算法求出算法求出nSDS(i,j) ,令令h=2;Step2 计算下界计算下界A(h+1,i,j)=

41、2.5nSDS(i,j)+ 5.5(h+1)+3;Step3 p从从1到到h-1循环循环,q=h-p,计算计算tSDS(i,j,p,q,k,l),对对k,l遍历求出遍历求出f(p,h)= min tSDS(i,j,p,q,k,l) | 1k,l39,kl TSDS(i,j,h)=min f(p,r) |2 r h ;Step4 若若TSDS(i,j,h) A(h+1,i,j)停止停止;否则令否则令h:=h+1，转转Step3.南京邮电大学数理学院杨振华制作 求解结果用上述算法用上述算法,针对题中的数据进行求解针对题中的数据进行求解,除去第除去第二对站点二对站点,计算到计算到p+q=5时可以求出

42、最优解时可以求出最优解.对第二对站点对第二对站点,可以加大搜索量求得最优解可以加大搜索量求得最优解.另另外还可以求得更好的下界来压缩搜索范围外还可以求得更好的下界来压缩搜索范围,比比如考虑起点到整个地铁线的最小站数如考虑起点到整个地铁线的最小站数,这样这样M的取值相应的增加的取值相应的增加,从而下界增大从而下界增大.再结合不乘再结合不乘地铁的情况地铁的情况,对第二对站点对第二对站点,也只要搜索到也只要搜索到p+q=5就可以了就可以了.南京邮电大学数理学院杨振华制作 求解结果仅考虑公汽时的求解过程和结果仅考虑公汽时的求解过程和结果点对ts(i,j,m)m*ns(i,j)5(m*+1)+3ns(i,j)T*1234563359182810164697141364641