严格确定车队规模下限的问题用gt,S"）表示延伸后车次集合"的总逆差函数，g（t,S"）I的最大值用G(S")表示。下述定理表明G(S")是比G(S)更低的下限定理8.1：用N.(S)表示有插入空驶车次的计划S的最小车队规模，用G(S）和G"S"）分别表示计划S"和S"的总逆差函数的最大值。那么：G"(S")≥G(S")G"(S")≤ N.(S)(1)(2)
严格确定车队规模下限的问题 定理8.1： G(S) G(S) ( ) ( ) （1） （2） G S N0 S '' ( , ) S '' '' g t S ( , ) '' '' g t S ( ) '' '' G S ( ) '' '' G S ( ) ' ' G S
时间示例8.36:008:208:409:006.206:407:007:207:408:001O-C行车计划S？空驶时间空驶发出（上下行相同）到达场站G(S')=420分钟a-b10分钟a-c60分钟a-d30分钟b-c30分钟b-d120分钟c-d6:206:407:007:207:408:008:208:409:00
g’(t, S’) 4 3 2 1 0 G’(S’)= 4 6:00 6:20 6:40 7:00 7:20 7:40 8:00 8:20 8:40 9:00 a 4 b c c a d a a a a b a d 2 6 5 1 3 7 c b 9 d c d 8 6:00 6:20 6:40 7:00 7:20 7:40 8:00 8:20 8:40 9:00 时间 示例8.3 行车计划S /？ 空驶发出 到达场站 空驶时间 (上下行相同) a-b 20分钟 a-c 10分钟 a-d 60分钟 b-c 30分钟 b-d 30分钟 c-d 20分钟
时间示例8.36:007:208:208:409:006.206:407:007:408:00COaC行车计划S0空驶时间空驶发出（上下行相同）到达场站20分钟a-bG"(S")=510分钟a-c60分钟a-d30分钟b-c30分钟b-d20分钟6:206:407:007:207:408:008:208:409:00c-d
a 4 b c c a d a a a a b a d 2 6 5 1 3 7 c b 9 d c d 8 行车计划 S`` 6:00 6:20 6:40 7:00 7:20 7:40 8:00 8:20 8:40 9:00 时间 √ √ g”(t, S”) 5 4 3 2 1 0 6:00 6:20 6:40 7:00 7:20 7:40 8:00 8:20 8:40 9:00 G”(S”)= 5 示例8.3 空驶发出 到达场站 空驶时间 (上下行相同) a-b 20分钟 a-c 10分钟 a-d 60分钟 b-c 30分钟 b-d 30分钟 c-d 20分钟
基于第1、2改进过程的车队规模下限比较+G(S)= 332g(t, S)0G'(S")=44432(t,s"gG"(S")=5G"(S")= D(S)= 54321g3(t,s"06:006:206:407:007:207:408:008:208:409:00
基于第1、2改进过程的车队规模下限比较 g(t, S) 4 3 2 1 0 g’(t, S’) 4 3 2 1 0 g”(t, S”) 5 4 3 2 1 0 6:00 6:20 6:40 7:00 7:20 7:40 8:00 8:20 8:40 9:00 G(S)= 3 G’(S’)= 4 G”(S”)= 5 G(S) D(S) 5
插入空驶车次往往可变行车计划是两难问题缩减车队规模的方法有哪些？问：你猜我们家刚出生的孩子是男孩还是女孩？答：男的。问：：再猜？答：：女孩。惊叫说：谁告诉你的？可变行车计划：即在满足相关约束的条件下口调整发车时间以缩减车队规模
可变行车计划：即在满足相关约束的条件下 调整发车时间以缩减车队规模。 可变行车计划 调整发车时间 缩减车队规模的方法有哪些？ 问：你猜我们家刚出生的孩子是男孩还 是女孩？ 答：男的。 问：再猜？ 答：女孩。 惊叫说：谁告诉你的？ 插入空驶车次往往 是两难问题