2多线路车辆调度问题--MDVSP问题n+ln+lMMMin目标函数：cjyjyi=lj=约束：使行车计划中车Z"y, = l, j =1,2,:辆从驻车场站至首车Zy, = 1,i = 1,2,..次发车场站，以及从末车次到达场站至驻车场站所需的行驶费Z用最小。J-I yn+1,j = l;Z二i=lyi,n+1
2 多线路车辆调度问题-MDVSP问题 目标函数: 约束： ij n i n j ij y Min c y 1 1 1 1 ∑ ∑ + = + = 1, 1,2 , , , 11 y j n ni ∑ ij = = L += 1； 1 , 1 , 2 , , ; 1 1 1 , 1 1 = = = ∑ ∑ + = + + = n j n j n j ij y y i L n 1 1 1 ∑ , 1 = += + ni i n y 使行车计划中车 辆从驻车场站至首车 次发车场站，以及从 末车次到达场站至驻 车场站所需的行驶费 用最小
2多线路车辆调度问题--MDVSP问题限制条件：（1）多于2500车次的调度问题；（2）有足够多的车型执行行车计划：（3）公交车的加油需求；（4）司机的用餐需求；(5）1司机所处的位置和是否可以准时到岗
限制条件： (1) 多于2500车次的调度问题； （2）有足够多的车型执行行车计划； （3）公交车的加油需求； （4）司机的用餐需求； （5）司机所处的位置和是否可以准时到岗。 2 多线路车辆调度问题-MDVSP问题
多线路车辆调度求解方法一最大流法车辆调度任务：在完成时刻表中所有车次的基础上，得到最小需用车辆数。单一车辆允许执行多个连续的车次是一种有效的解决办法，如果可行，则问题的第二部分是寻找车队中分配给每一车辆的车次集合。如果执行完车次i之后立即执行车次，那么要满足：(a)车次，的发车时间一定大于或等于车次i的到达时间：(6)车次；的发车站点和车次i的到达站点相同。如果该条件不能满足，允许车辆在，的到达场站和，的发车场站之间空驶。如果这一空驶车次能在车次；发车时间之前到达，那么这两个车次可以出现在同一车次链中，可以被同一车辆执行
多线路车辆调度求解方法 —最大流法 车辆调度任务：在完成时刻表中所有车次的基 础上，得到最小需用车辆数
多线路车辆调度求解方法一最大流法最大流问题的建模及其变换：用i行代表车次的到达时间，」列代表车次／的发车时间，相关的行和/列构成了车次连接数组S。如果将1和/连接是可行的，则单元(,J)可允许连接，否则(（,J)不允许连接。设是与单元（,J)有关的0-1变量，为所需车次的集合；考虑如下问题：MИXMaxZ1 =问题P1jelielZX,≤l,jeIZX, ≤l,iel约束条件：jelielX《ij= 1,(i,j)为可允许连接[×，=0.（,)为不允许连接
多线路车辆调度求解方法 —最大流法 最大流问题的建模及其变换： 问题P1 ∑ ∑ ∈ ∈ = i I I j MaxZ X ij 1 ∑∈ ≤ ∈ j I ij X 1,i I ∑∈ ≤ ∈ i I ij 约束条件： X 1, j I ( ) ⎪ ⎩ ⎪ ⎨ ⎧ = = 为不允许连接 （ 为可允许连接 0 , i, j ij X 1, i, j ) ij X 时间 时间
多线路车辆调度求解方法一最大流法下述定理证明问题P1中的目标函数最大化等价于最小化有n个车次的行车计划形成的车次链数目。定理7.2：N和n分别表示车次链的数目和车次的数目，则MinN=n-Maxz,问题P1的解对应于最大流问题中的一个特定解。求解插入空驶车次的车辆调度问题的最大流算法叫做增广路径法。问题可以转换为一个有个n节点（发车次数）和m个弧的单位容量对分网络
多线路车辆调度求解方法 —最大流法 下述定理证明问题P1中的目标函数最大化等价于最 小化有 n个车次的行车计划形成的车次链数目。 定理7.2： 问题P1的解对应于最大流问题中的一个特定解。求解 插入空驶车次的车辆调度问题的最大流算法叫做增广路径 法 。 问题可以转换为一个有个 n节点（发车次数）和 m个弧 的单位容量对分网络