第六讲-固定行车计划

第六讲车辆行车计划编制I：固定行车计划

车辆计划/车次链(Block)：是运营车辆有序的工作计划。一个车次链包含了一条线路在一天内有次序地进行车辆调度的时刻表，参与运营的车辆从驶出车场开始，到驶回同一个车场结束。

什么是车辆调度？行车计划编制是在已知发车时间表的条件下将车辆分配到每一条线路中去。考虑的目标是：最小车辆数和最小车辆运营成本，减小车辆运营成本的方法主要通过减少车辆空驶时间和停站时间。行车计划编制的目标甘特图运行图其他行车计划编制方法本讲主要内容第一节可持续发展与交通运输3基于逆差函数车队规模计算方法2多线路车辆调度问题1单线路车队规模的确定方法

4插入空驶车次的车队规模计算方法6有场站约束的车辆行车计划编制5构建行车计划7插入空驶车次的启发式算法1单线路车队规模的确定方法

前提条件：不允许跨线调度和空驶的情形，并且每条线路都单独运营。最小车队规模：设表示一条基本路线r（出发和到达站点相同）的平均往返运行时间，包括停站时间和运行时间，则线路的最小车队规模等于时间内发出的最大车辆数。

1单线路车队规模的确定方法

假设线路有两个场站：a和b。和分别表示从点a和点b在和时刻发出的车辆在线路上的平均运营时间，包括在各自终点站的停站时间。设表示在至时段（此时段[,)）内在a站发车的车次数。因此，ia到达场站b，然后执行车次jb，车次jb是从b站到a站的第一个可行的发车车次，其发车时间大于或等于时刻；为自a站发向b站的第一个可行车次的发车时间,其大于或等于时刻。类似地，可以定义为从b站发出对应车次时段的发车车次数。1单线路车队规模的确定方法

引理7.1：对于线路的时刻表中的所有车次ia和ib，如果没有空驶车次(DH)，必然被a站不同的车辆执行，必然被b站不同的车辆执行。定理7.1：如果不允许跨线调度和插入空驶车次，线路需用的最小车辆数目可用下式表示：

求解实例233344322--32125544332--45max（4，5）=5车队规模的求解实例：

例如：b站发车五个车次链如下：[5:00(b)-6:00(a)-6:30(b)-6:45(a)-7:05(b)-7:20(a)-7:40(b)-8:00(a)];[5:30(b)-6:15(a)-6:50(b)-7:10(a)-7:30(b)];[6:00(b)-6:30(a)-7:10(b)-7:25(a)-8:00(b)];[7:00(a)-7:15(b)-7:40(a)];[7:20(b)]。

车次链构造：FIFO（先到先发）规则

车队规模的求解实例：

车次链之间可以交换车次。上述b站发车五个车次链可另外表示如下：[5:00(b)-6:00(a)-6:30(b)-6:45(a)-7:10(b)-7:25(a)-8:00(b)];[5:30(b)-6:15(a)-6:50(b)-7:10(a)-7:30(b)-8:00(a)];[6:00(b)-6:30(a)-7:05(b)-7:20(a)-7:40(b)];[7:15(b)-7:40(a)];[7:20(b)]。

[5:00(b)-6:00(a)-6:30(b)-6:45(a)-7:05(b)-7:20(a)-7:40(b)-8:00(a)];2多线路车辆调度问题--MDVSP问题

前提：允许跨线调度和空驶车次如果两条线路拥有相同的终点站，跨线调车可在站内实现，也可通过空驶车次实现。公交线网中的车辆行车计划编制问题最困难的部分是在满足时刻表需求的基础上使需用车辆数目最少，这一问题属于最小费用问题。包含多终点站（多线路）的车辆行车计划编制问题可以归结为多场站调度问题（MDVSP）。2多线路车辆调度问题--MDVSP问题

目标函数:费用函数cij:2多线路车辆调度问题--MDVSP问题

目标函数:约束：

使行车计划中车辆从驻车场站至首车次发车场站，以及从末车次到达场站至驻车场站所需的行驶费用最小。限制条件：(1)多于2500车次的调度问题；（2）有足够多的车型执行行车计划；（3）公交车的加油需求；（4）司机的用餐需求；（5）司机所处的位置和是否可以准时到岗。

2多线路车辆调度问题--MDVSP问题

多线路车辆调度求解方法

—最大流法

车辆调度任务：在完成时刻表中所有车次的基础上，得到最小需用车辆数。多线路车辆调度求解方法

—最大流法

最大流问题的建模及其变换：问题P1约束条件：

多线路车辆调度求解方法

—最大流法

下述定理证明问题P1中的目标函数最大化等价于最小化有n个车次的行车计划形成的车次链数目。定理7.2：

问题P1的解对应于最大流问题中的一个特定解。求解插入空驶车次的车辆调度问题的最大流算法叫做增广路径法。问题可以转换为一个有个n节点（发车次数）和m个弧的单位容量对分网络.车次的表示：场站：每一个车次i：两个车次被同一车辆执行的条件：（a）（b）3车队规模计算方法—定义和符号如果i,j之间存在可行连接,则说明i是j的前序车次，j是i的后序车次。车次链：求解固定行车计划的最小车次链数问题可以被定义为最小化车队规模问题。两车次可连接的条件(a)(b)可以变化为：3车队规模计算方法—定义和符号3车队规模计算方法逆差函数（deficitfunction,DF）是一个阶跃函数，该函数在车次发车时加1，在车次到达时减1。优点：能够表示多个场站组成的公交系统中某一场站亏欠的需用车辆数目。所需的唯一信息是车次的行车计划。直观可视性。

—逆差函数模型表示方法：—逆差函数模型总逆差函数：含义3车队规模计算方法—逆差函数实例3车队规模计算方法—逆差函数实例3车队规模计算方法画一下场站b的逆差函数—逆差函数实例3车队规模计算方法车队规模计算公式定理7.3：—基于逆差函数车队规模计算公式定理7.3：—基于逆差函数证明：4插入空驶车次—基于逆差函数是否有空驶车次？空驶车次是一类插入行车计划、开行于两站之间的非载客车次。目的：使行车计划在每天开始和结束保持平衡；将车辆从不需用的场站调度到另一个需用的场站以满足车次需求；加油或保养。

-可最小化车队规模3DH1DH2原车队规模：4+1=5插入空驶车次后车队规模：3+1=44插入空驶车次--基本思路

初始空驶车次会在期望减少需用车辆数场站的第一个平峰时段到达.

同时，它必须从其它场站的平峰时段发出，而在该平峰时段的末端必须插入其它的空驶车次，以弥补该场站由于发出初始空驶车次引起的需用车辆数的不足。

该补偿空驶车次也会产生其它补偿车次，然而为了避免循环，相同的平峰时段只允许发出不超过一个空驶车次。当场站q到达最后一个平峰时段时插入空驶车次过程结束，此时不需要再次插入补偿空驶车次。

4插入空驶车次--基本思路松弛时间：可以用运营车次替代空驶车次如果则存在松弛时间，该时间段内空驶车次发车时间可以变更。实例DH1DH2DH3D(b)=1场站间空驶时间=30min服务车次运行时间=60min4插入空驶车次单位削减空驶车次链（URDHC）：4插入空驶车次URDHC搜索过程终止的条件：定理7.4与插入空驶车次之前相比，定理7.4表明通过插入空驶车次的方式，车队规模可以减少的程度。4插入空驶车次证明:（a）因为有：根据g(t)的定义和公式(7.9)，有4插入空驶车次证明:由(i)得，应用假设（b）有，

5构建行车计划（车次链或车次组）构建车次链原则：（1）FIFO规则

（2）车次链抽取过程规则将到达时间与发车时间最接近的两个车次（在同一场站）相连接。

算法持续构建车辆行车计划，直到无法产生新的连接为止。己考虑过的车次将被删除，算法继续。

允许在任何给定平峰时段内连接到达－发出车次对。已考虑的到达－发出车次对的连接将被删除，过程继续。5构建行车计划（车次链或车次组）采用FIFO规则：[（1—4），（2—5）,（3—6）]其他可能的连接规则：5构建行车计划（车次链或车次组）插入空驶车次后：[(1-DH1-8-9),(2-DH3-6),(3-DH2-7),(5-4)]图7.8实例插入空驶车次前：[(1-7),(2),(3-4),(5-6),(8-9)]6有场站约束的车辆行车计划编制平衡行车计划：每个场站k发出的车辆数应该等于返回的车辆数。定理7.5：当且仅当在行车计划结束时，每个逆差函数的值均为零的情况下车辆调度平衡。6有场站约束的车辆行车计划编制

--逆差函数平衡行车计划车次链？车次链？6有场站约束的车辆行车计划编制

--逆差函数平衡行车计划结论：6有场站约束的车辆行车计划编制

--逆差函数平衡行车计划问题P2在给定车次的行车计划中插入所需的空驶车次，使得：约束：6有场站约束的车辆行车计划编制

--逆差函数形式问题P2可重新描述为：约束：6有场站约束的车辆行车计划编制--数学规划模型6有场站约束的车辆行车计划编制

--数学规划模型6有场站约束的车辆行车计划编制

--数学规划模型约束：6有场站约束的车辆行车计划编制

--数学规划模型约束：=每天行车计划开始之前场站k的车辆数=每天行车计划结束之后场站k的车辆数。上述两值均等于场站的夜间停车数。6有场站约束的车辆行车计划编制

--数学规划模型定理7.6：问题P2和P3等价。P3的解是在满足场站容量约束和场站平衡约束条件下的需用最小车队规模。证明：将问题P3做如下变换：任何满足（7.22）和（7.23）的解也满足平衡约束。

6有场站约束的车辆行车计划编制

--数学规划模型定理7.6：问题P2和P3等价。P3的解是在满足场站容量约束和场站平衡约束条件下的需用最小车队规模。证明：7

插入空驶车次的启发式算法NT规则：被选场站第一个平峰时段最长。选择的对象是以前未被检验过的场站；已检验过的场站由于无法进行URDHC过程，因此选择对象不包括此类场站。对于多个场站，如果其最长第一平峰时段相同，则此选择将基于场站的总的高峰时