本讲主要内容 0 HERN 4OTONO 1固定行车计划车队规模下限的确定 2可变车次发车时间 3可变行车计划车队规模下限的确定 4缩减车队规模的过程 5均衡载客量时刻表的检验和思考
本讲主要内容 第一节 可持续发展与交通运输 3 可变行车计划车队规模下限的确定 2 可变车次发车时间 1 固定行车计划车队规模下限的确定 4 缩减车队规模的过程 5 均衡载客量时刻表的检验和思考
固定行车计划车队规模下限的确定口复习：利用插入空驶车次方法求车队规模下限。口其中： R=2
复习：利用插入空驶车次方 法求车队规模下限。 其中：R=2 1 固定行车计划车队规模下限的确定
示例8.1：问题的输入数据空驶时间发车时到达场发车场空驶发出车次号到达时间（上下行相同间站站到达场站220分钟16:006:30a-bca2b6:206:50a3b7:1010分钟6:40aa-c47:207:00aa560分钟7:107:30a-daC68:107:40ca730分钟d7:50d8:10b-c8d8:008:3030分钟b-dc9dd8:108:40c-d20分钟
车次号 发车场 站 发车时 间 到达场 站 到达时间 空驶发出 到达场站 空驶时间 （上下行相同 ） 1 a 6:00 c 6:30 a-b 20分钟 2 a 6:20 b 6:50 3 b 6:40 a 7:10 a-c 10分钟 4 a 7:00 a 7:20 5 c 7:10 a 7:30 a-d 60分钟 6 c 7:40 a 8:10 7 d 7:50 d 8:10 b-c 30分钟 8 d 8:00 c 8:30 b-d 30分钟 9 d 8:10 d 8:40 c-d 20分钟 示例8.1：问题的输入数据
时间[1-5][4-DH,-6XFIFO车次链：[2-DH -712[3-DH, -9固定行车计划432D(a)-3示例d(a,t)14DH,D(b)=18.12d(b,t)空驶发出空驶时间到达场站（上下行相同）DH,!20分钟a-bD(c)DH,10分钟a-c60分钟a-d30分钟b-cDd30分钟b-d20分钟c-d
b c c a a d a a a a b a d 2 6 5 1 3 4 7 c b 9 d d 8 c 固 定 行 车 计 划 d (a , t ) d (b , t ) d (d , t ) 432103210 d ( c , t ) 3210 - 13210 - 1 6 : 0 0 6 : 2 0 6 : 4 0 7 : 0 0 7 : 2 0 7 : 4 0 8 : 0 0 8 : 2 0 8 : 4 0 9 : 0 0 时 间 B D (a ) = 3 D (b ) = 1 D ( c ) = 1 D ( d ) = 2 DH 1 DH 2 DH 3 01 [ 1 5 ] [ 2 DH 7 ] 1 [ 3 DH 9 ] 2 [ 4 DH 6 ] 3 [ 8 ] 示例 8.1 空驶发出 到达场站 空驶时间 (上下行相同 ) a-b 20分钟 a-c 10分钟 a-d 60分钟 b-c 30分钟 b-d 30分钟 c-d 20分钟
AM3D(a)=32d(a,t)101DH24I32D(b)=1八d(b,t)1+IVOIDH33全21DHiD(b)=X 0B示例d(c,t)0-1+8.1432D(b)=2 1d(d,t)IM01413g(t)2G-84106:006:206:407:007:207:408:008:208:409:00时间
d (a , t ) d (b , t ) d (d , t ) 432103210 d ( c , t ) 3210 - 13210 - 1 g ( t ) 43210 6 : 0 0 6 : 2 0 6 : 4 0 7 : 0 0 7 : 2 0 7 : 4 0 8 : 0 0 8 : 2 0 8 : 4 0 9 : 0 0 时 间 D H 2 / B D H 1 D (a ) = 3 D (b ) = 1 D H 3 D ( b ) = 1 0 D ( b ) =/2 1 G = /3 4 示例 8.1
如何严格确定车队规模？一-车次延伸的方法将车次的到达时间延伸至可能存在连接车次的一个可行发车时间，或者至T，可以得到计划车次集合S总逆差函数DF，g't,S)及其最大值G(S)。若干车次到达点可被延伸至相同的发车点，构成它们的口第一个可行连接口在最小化车辆数问题的最终解中，只存在一个能够与该发车点连接的到达延伸。口在既保证生成所有可能的连接组合，文使车队规模维持在其下限水平的前提下，这种情况使得通过人工方式进一步延伸某些车次的到达点成为可能
如何严格确定车队规模？ 若干车次到达点可被延伸至相同的发车点，构成它们的 第一个可行连接。 在最小化车辆数问题的最终解中，只存在一个能够与该 发车点连接的到达延伸。 在既保证生成所有可能的连接组合，又使车队规模维持 在其下限水平的前提下，这种情况使得通过人工方式进一 步延伸某些车次的到达点成为可能。 -车次延伸的方法
严格确定车队规模下限的问题（1）对于同一发车点而进行多种延伸的情形时间6:306:457:157:307:458:008:156:006:157:001111a(i)a在这个临界点车次1比车次2更有机会进行空驶连接
严格确定车队规模下限的问题 a c a a b b c c 1 3 2 4 (i) 时间 6:00 6 :15 6 :30 6:45 7:00 7 :15 7:30 7:45 8:00 8:15 对于同一发车点而进行多种延伸的情形（1） 在这个临界点 ,车次1 比 车次2更有机会进行空驶连接
严格确定车队规模下限的问题情形(2)原有车次链：[1-3],[2-4](ii)2现有车次链：[1]，[2-3]，[4]1st2nd可行连接3rd说明情形（1）的处理方法不适用于来自多个不同到达场站的连接
严格确定车队规模下限的问题 情形（2） b c c a a a 2 3 1 b 4 c T2 1st 2nd 可行连接 3rd (ii) 原有车次链：[1-3]，[2-4] 现有车次链：[1]，[2-3]，[4] 说明情形（1）的处理方法不适用于来自多个不同到达场站的连接
严格确定车队规模下限的问题情形（3）原有车次链：[1-5]，[2-3-4]因此，只有在第一种情况下，Gs}可以被进一步改进。3rd(iii)4a现有车次链：[1-3-4]，[2]，[5]6:006:158:15时间说明情形（3）不适用手更早到达时间车次的延伸
严格确定车队规模下限的问题 情形（3） 1st 2nd 可行连接 3rd b b a a 2 3 b 4 c a 1 c c 5 a (iii) 时间 6:00 6:15 6:30 6:45 7:00 7:15 7:30 7 :45 8:00 8 :15 原有车次链：[1-5]，[2-3-4] 现有车次链：[1-3-4]，[2]，[5] 说明情形（3）不适用于更早到达时间车次的延伸
严格确定车队规模下限的问题确定步骤：1.构建S2、选出以下情形，即对于场站第次发车的发车时间，有多于一个延伸能与其连接。如果不存在这种情形则过程停止。否则选择具有相同到达场站的一组也可以是（两组或更多）延伸，并采用下述步骤2a.搜索一个车次满足：min这icE.（t一tu），E,表示到达场站u并能延伸到t的所有车次集合，表示车次在站的到站时间：2b.除了在步骤2α中被选择的车次，对于其它车次iEE.执行第二种可行延伸。转到步骤2
严格确定车队规模下限的问题 确定步骤：