2.1　目标函数

模型以提高旅客出行服务质量为目标，一方面应尽可能减少列车旅行时长，另一方面应使周期内列车均衡服务各OD出行旅客。列车总旅行时长如式(1)所示，表示为列车经过有向弧的时间费用之和。表示为OD服务列车出发时间间隔方差之和，如式(2)所示，该值越小，说明OD列车服务越均衡。OD对的有序列车集，为该OD对的实际服务列车数，为集合中任意2列相邻列车的理想服务时间间隔。通过引入2个权重因子与，便可将目标函数表示为式(3)。

(1)

(2)

(3)

2.2　约束条件

模型除了考虑一般的列车区间运行时长约束、停站时长约束、安全间隔约束外，还进一步考虑了OD最小服务列车数量约束和列车最大旅行时长约束。

1) OD最小服务列车数量约束

(4)

OD对的服务列车数为经过O、D站进站弧的列车总数，其服务列车数越多，OD旅客期望出行时间和实际出行时间的偏差就越小，式(4)保证了OD服务列车数不小于设定的最小值。此外，不同OD的最小服务列车数需根据OD实际客流设定，避免OD出行客流量和列车服务频率不匹配，导致资源浪费问题。

2) 最大慢行时分约束

(5)

列车在区间的运行时间为列车经过该区间的运行弧和慢行弧时间费用之和。不同种类运行弧的时长即为相应进出区间方式的最小运行时分，无论选择哪条区间运行弧，均满足相应的区间最小运行时分要求。此外，考虑到实际编图过程中允许列车在区间慢行，式(5)保证了慢行时分不超过允许的最大值。

3) 列车停站时长约束

(6)

列车的停站时间为列车经过该车站的停站弧时间费用之和。式(6)保证了列车在车站的停站时长满足最小最大停站时长要求，其中，若列车在s站停站，，否则为0。

4) 列车间出发安全时间间隔约束

(7)

当2列列车从同一车站相继进入同一区间时，根据2列列车在车站是否停车，可将出发安全间隔分为通-发、通-通、发-发、发-通4种类型，其最小安全值分别记为。式(7)保证了相邻列车的出发时间间隔大于相应最小安全值，其中，为极大值。

5) 列车间到达安全时间间隔约束

(8)

当2列列车从同一区间相继到达同一车站时，根据2列列车在车站是否停车，可将进站安全间隔分为通-到、通-通、到-到、到-通4种类型，其对应的最小安全值分别记为。式(8)保证了相邻列车的到达时间间隔大于等于相应最小安全值。

6) 列车最大旅行时长约束

(9)

列车旅行时间为列车经过有向弧的时间费用之和。式(9)保证了列车旅行时长不超过其允许的最大值，避免因列车旅行时长增加而导致列车服务质量降低。

7) 流量平衡约束

(10)

(11)

(12)

流量平衡约束保证了一条路径在时空网络中的可行性。式(10)和式(11)分别满足了列车在起始站的必出和终点站的必回要求，式(12)保证了中间节点的入弧数等于出弧数。

3.1　考虑列车差异的弧权体系设计

时空网络中各有向弧的权值体现了列车使用该弧的成本，其大小直接影响列车的路径搜索。为了引导列车选择特定路径，除了为每条有向弧设置时间权外，还添加均衡惩罚权、安全间隔惩罚权、停站惩罚权3类权，且允许针对不同列车为此3类权设置不同权值。

1) 均衡惩罚权。针对以车站出发节点为起点的运行弧设置均衡惩罚权，以此引导相关OD的服务列车尽可能等间隔均匀发车。以图3(a)中的列车2为例，其服务OD仅有(s₁,s₃)，同时服务该OD的列车1和列车3的出发时刻分别为0和5，周期T=7，则列车2在该OD的均衡发车时刻，故列车2子网络中有向弧的均衡惩罚权如图3(b)所示，显然，有向弧距离车站均衡发车时刻越远，相应该有向弧的均衡惩罚权就越大，当有向弧在车站均衡发车时刻出发时，该弧的均衡惩罚权为0。

图3全屏查看

停站惩罚权和均衡惩罚权示意图

2) 安全间隔惩罚权。当一列列车占用某条路径后，为防止其他列车继续使用该路径占用弧，需要在其他列车子网络中为这些占用弧添加安全间隔惩罚权。对于列车子网络中的任意有向弧，为避免列车使用弧与列车产生安全冲突而在列车子网络中为该弧添加的安全间隔惩罚权。将防止列车使用弧与其他所有列车路径产生安全冲突而添加的安全间隔惩罚权求和便可得到列车子网络中有向弧的总安全惩罚权。

3) 停站惩罚权。若当前车站因列车停站数较少，而未满足相关OD的最小服务列车数要求时，针对起点为该站通过节点的运行弧设置较大的停站惩罚权；否则，其承担的停站惩罚权可设为0。假设各列车当前路径如图3(a)所示，OD对(s₁,s₂),(s₁,s₃)和(s₂,s₃)的最小服务列车数分别为2、3、2，(s₁,s₂)和(s₂,s₃)的服务列车数不满足最小OD服务列车数要求，需要通过停站惩罚权来引导列车在s₂站停车。列车2子网络中有向弧的停站惩罚权如图3(b)所示。

3.2　基于弧惩罚权迭代优化的算法设计

算法首先初始化所有列车的路径，根据各列车初始路径分别为其他列车子网络初始化各有向弧的惩罚权，进而针对惩罚权最大，即冲突最严重、均衡性最差或不满足停站要求的列车重新搜索路径，并由此更新其他列车子网络中的弧惩罚权，直至满足算法终止条件而停止。其中终止条件为所有列车无安全间隔冲突且所有OD的服务列车数达到最小值要求。算法实现框架如图4所示。

图4全屏查看

算法框架图

3.2.1　各列车子网络的弧惩罚权初始化

在周期内随机选择一个时刻作为列车始发时刻，并假定列车在经由站均不停车，进而按照列车经由车站顺序，以区间最小运行时分要求逐站推算列车在各经由站的到发时刻，便可确定列车的初始路径。基于该初始路径，按以下方法分别为其他各列车子网络中的有向弧初始化各类惩罚权。

1) 均衡惩罚权。记列车除终到站外的停站集为，以为起点的服务OD集为。针对中的每个OD，列车具有不同的均衡发车时刻，对其求平均值便可得到列车在站的均衡发车时刻。记为弧起点时刻与均衡发车时刻的间隔，表示列车为各车站分配的总均衡惩罚权。列车子网络中有向弧的均衡惩罚权初始化如下：

(13)

2) 安全间隔惩罚权。记为列车路径占用弧集，为当列车使用有向弧时，其与列车路径的实际时间间隔距最小安全间隔的差值，该差值越大，说明列车使用弧将与列车产生的冲突越严重，故设置的惩罚权应更大。因此，列车子网络中弧因列车产生的安全惩罚权初始化如下：

(14)

其中，为列车为列车分配的初始总安全间隔惩罚权，其将根据大小分摊到中的有向弧。

针对列车子网络中的任意有向弧，将其他所有列车对列车产生的安全间隔惩罚权求和便可得到列车子网络中该弧的总安全惩罚权，即：

(15)

3) 停站惩罚权。记除首末站外的其他车站集为，在初始路径中列车在车站均不停车，故需要为中的所有车站初始停站惩罚权。分别为车站启停附加时长，由于列车在站停站会比通过增加至的旅行时长，若中有向弧的停站惩罚权小于，列车会选择通过站；若大于，列车会选择在站停车；否则，列车会根据具体路径选择在站停站或通过。因此，列车子网络中有向弧的停站惩罚权初始化如下：

(16)

3.2.2　各列车子网络弧惩罚权迭代更新

当列车基于当前弧惩罚权进行路径调整后，需要更新其他列车子网络中的各类弧惩罚权以引导列车路径的改变，具体更新策略如下：

1) 均衡惩罚权。列车子网络中有向弧的均衡惩罚权更新和初始化相同，均需要计算列车在车站的均衡发车时刻，基于此得到各有向弧的值，通过分配均衡惩罚权，具体如下：

(17)

2) 安全间隔惩罚权。对于列车子网络中的有向弧而言，若弧属于列车新路径占用弧，但不属于旧路径占用弧，则按式(14)对安全间隔惩罚权初始化；若弧不属于列车新路径占用弧，但属于旧路径占用弧，则直接令其关于列车的安全惩罚权为0；若弧既属于列车新路径占用弧，也属于旧路径占用弧，则说明当前弧的惩罚权不足以让列车改变路径，故需增大惩罚权，具体更新方法如下：

(18)

其中，表示列车路径对列车子网络中有向弧第n次迭代的惩罚权，α取值应大于1.00，m为列车搜索到包含弧路径的连续迭代次数。

3) 停站惩罚权。在更新列车子网络有向弧的停站惩罚权前，需要计算列车服务车站的最小停站列车相差数，即若要满足OD最小服务列车数，站至少还需的停站列车数。记最小停站列车相差数不为0的车站集为，停站惩罚权增加系数为，则列车子网络有向弧的停站惩罚权更新如下：

(19)

4.1　基础数据

京津城际铁路全线长166 km，设7个车站，分别为北京南站、亦庄站(暂不办理客运业务)、武清站、天津站、军粮城北站、塘沽站和滨海站。选取京津城际铁路现行运行图中在11:10至14:40出发的20列列车作为本案例高峰时段开行列车，各列车运行区段如图5所示。各OD最小服务列车数取现行运行图中的实际服务列车数。车站到-到、通-到、到-通和通-通安全时间间隔值分别为2，3，2和2 min，发-发、通-发、发-通和通-通安全时间间隔值分别为2，1，3和2 min。列车在各车站和区间的参数如表2所示。算例中运行图的周期为1 h。

图5全屏查看

列车运行区段示意图

4.2　结果分析

算法求解的迭代过程如图6所示。初始路径中列车在经由车站均不停车，因此，在算法迭代前期，较多列车选择停站导致运行时间增加，且列车停站方式频繁发生改变使OD服务均衡的优化微乎其微，故在迭代前期优化结果出现急剧上升趋势；在算法迭代中期，各OD最小服务列车数几乎得到满足，列车停站方式改变频次变少，OD服务均衡得到一定优化，但列车运行时间的增加和OD服务均衡的优化相互抵消，使得优化结果大致未变；在算法迭代后期，停站方式几乎不发生改变，列车运行时间变化很小，而OD服务均衡得到改善，使得优化结果逐渐变小直至运算第105 s、迭代结果150次未发生变化时得到较优解，优化后目标值为711.0。生成的高峰单元周期运行图如图7(b)所示，初始运行图如图7(a)所示。

图6全屏查看

算法迭代过程

图7全屏查看

列车运行图

初始运行图和优化运行图的相关指标见表3中的方案1和方案5，2张运行图均铺画20列车，优化运行图增加了2次停站，但列车未因躲避冲突而过多延长停站或区间运行时间，故列车旅行时长得到一定优化，详见图8(a)，此外，优化运行图的均衡性提高了57%。初始运行图和优化运行图中OD服务列车出发时间间隔方差见图8(b)中的方案1和方案5，因以北京站为起点的OD较多，各OD的均衡发车时刻不尽相同且相互嵌套，故以北京为起点的OD服务均衡相对较差，其他OD的列车服务时间间隔较为均衡。

图8全屏查看

目标函数值分析

为了进一步验证所提方法的优化性能，仍以京津城际为背景分别进行单目标优化时间、单目标优化OD服务均衡和固定列车停站优化，得到方案2、3、4。此外，方案1为初始运行图，方案5为考虑停站的运行图优化，5个方案的结果对比见表3。各运行图均铺画20列列车，方案2中列车不考虑OD服务均衡，单一追求旅行时长最短，故列车总旅行时间最少，但OD服务均衡最差；方案3中，列车追求OD服务均衡最优，使得停站次数增多，列车旅行时间变长；方案4中列车旅行时间和OD服务均衡均得到优化，但固定停站使得OD服务均衡的优化受到一定限制；方案5中列车旅行时间和OD服务均衡得到了最大程度的优化。利用所提方法优化后的方案2至方案5的目标函数值均低于初始运行图，且方案5的目标函数值最小，说明所提方法能够有效提高列车旅行时间和OD服务均衡的整体效益，且考虑停站进行优化可以更大程度发挥作用。

为了更详细地证实所提方法对OD服务均衡的优化，图8(b)对上述5种方案中的OD服务列车出发时间间隔方差进行了对比。可以看出，考虑了均衡优化的方案3至方案5的OD服务较未考虑均衡优化的方案1和方案2更为均衡。方案5中各OD服务均衡基本优于方案4，进一步说明了固定停站不利于OD服务均衡的优化；方案3为了提高OD服务均衡而使列车停站增多，导致其大多OD服务均衡优于方案5，证明了所提方法对OD服务均衡优化的有效性，但因OD对7、8、9的最小服务列车数为1，其他方案相应的服务列车出发时间间隔方差为0，而方案3的服务列车数大于1，故其服务列车出发时间间隔方差大于其他方案。

方案2至方案5中各OD列车服务频次详见图9。假设周期T内各OD客流均为800且均匀分布，计算得到不同方案中各OD旅客平均期望出行时间与实际出行时间偏差和服务列车平均运行时间如图9所示。在方案2、4、5中，各OD列车服务频率相似，方案5因OD服务均衡较优，其OD旅客平均期望出行时间和实际出行时间偏差较小，旅客随机到达车站，不需要等待过长时间便会有相应OD服务列车到站，提高了旅客出行便利性和候车体验。方案3中OD服务列车数较多，其大多OD旅客期望出行时间和实际出行时间偏差小于方案5，但因其未优化列车旅行时长，导致OD服务列车平均运行时间较长，故方案5中OD旅客整体出行效率最高。

图9全屏查看

OD旅客出行效率对比分析