铁路枢纽空车调配多目标优化模型及算法

李菲菲，肖旭航，金启明

（兰州交通大学 交通运输学院，甘肃 兰州730070）

0 引言

在铁路货物运输中的空车调配，是指由卸大于装的车站向装大于卸的车站进行车辆排空，以保证装车站能够有足够的空车进行装车［1］。

针对空车调配问题，王铁君［2］等针对求解大规模空车调配问题提出混沌自适应变异的粒子群算法。程学庆［3］建立了空车调配的多目标优化模型并利用Lingo求解。张红斌［4］等建立了能力约束下的动态优化模型，并使用融合K短路的模拟退火算法求解。闫建文［5］等建立了以空车到达时间可靠性最大和空车走行成本最小为优化目标的模型。李立［6］等建立了评价空车调配效率的数学模型。于横［7］等在考虑节点车流平衡、货车保有量等约束条件下，建立了以铁路最大收益为优化目标的数学模型。蒋灵明［8］等用电磁铁吸附效应理论构造了空车调配算法。从上述文献可以看出，已有的研究集中在模型与算法优化方面，但存在着优化角度单一或建模时没有考虑到车种代用、路径运输能力等情况，且多为路网层面的空车调配研究。为此，本文在综合考虑空车调配成本、货主满意度、路径运输能力限制、车种代用等因素下，建立枢纽内空车调配问题的多目标优化模型，并提出相应的求解算法。

1 空车调配问题分析

1.1 影响空车调配成本的因素分析在空车调配过程中，影响调配成本的因素主要有：空车的运输成本；车种代用时产生的成本，如加固费用、加篷布费用等；由于空车提前到达装车需求站所产生的积压库存成本，以及空车过晚到达需求站所产生的延误损失费用。

1.2 货主（客户）满意度本文以空车到达时间可靠性作为衡量客户满意度的标准［9］，即在货主满意的时段内到达的空车越多，系统的到达时间可靠性越大，货主满意度越高。

1.3 路网运输能力限制在空车调配过程中，铁路为了降低空车运输成本，通常会选择最短的路径来运输空车，但这样往往会造成路网中某些路段的流量超出其运输能力，使路网流量分布不均衡，故在空车调配过程中需要考虑路径调整。

2 空车调配多目标优化模型的构建

2.1 条件假设一是不考虑机车运用情况；二是空车需求站不考虑以重代空情况；三是各车种之间的代用费用为已知。

2.2 符号定义S为空车供应站集合，i∈S，i=1，2，...，n；D为空车需求站集合，j∈D，j=1，2，...，m；Si站能提供的空车总数为表示Si站所能提供的车种q辆数；Dj站需求的空车总数为表示Dj站所需求的车种r辆数表示车站Si至车站Dj所有可行路径集合，其中表示Si至Dj的第k条路径，λ（i，j）表示Si至Dj的可行路径数为Si至Dj第k条路径的最大空车运输能力；ν为供应和需求所涉及的空车种类数为Si至Dj在第k条路径上的空车运输数为Si至Dj在第k条路径上q种空车代用r种空车的运输辆数为Si至Dj在第k条路径上每辆空车的运输成为车种q代用车种r的单位成本；Pj为Dj站的空车到达时间可靠性；ej为Dj站货主满意的最早装车时间；lj为Dj站货主满意的最晚装车时间；αj、βj分别为需求站Dj在单位时间内每辆空车的积压库存成本、延误损失费用为Si至Dj在路径k上运输的出发时刻为Si至Dj在路径k上的运输时间为Si至Dj在路径k上运输的到达时刻；Punj为在货主满意的装车时段内到达Dj站的空车数。

2.3 建立模型

式（1）~式（4）为目标函数。式（1）为总运输成本最小；式（2）为空车总的积压库存费用及延误损失费用最小；式（3）为总车种代用费用最小；式（4）为空车调配系统的到达时间可靠性最大。

式（5）表示Si站发往各需求站的空车总数等于其空车供应量；式（6）表示Dj站从各供应站接收到的空车总数等于其空车需求量；式（7）为路径运输能力约束，表示各路径的空车运输量不得超过该路径的最大运输能力；式（8）为空车运达时刻的计算公式；式（9）为Dj站的到达时间可靠性计算公式；式（10）为各车种间的代用费用。

3 模型的求解算法

3.1 单目标处理首先分别求目标函数Z1、Z2、Z3、Z4的上界，然后将各目标函数通过式（11）转化为一个总的目标函数Z，这样即可将Z1、Z2、Z3、Z4转化为具有相同量纲的单目标函数。式中：ηi为权重系数，

ηi≥0且η1+η2+η3+η4=1；

3.2 改进的和声搜索算法和声搜索算法是Geem Z W等人在2001提出的智能优化算法［10］，具有适用范围广、原理简单、调整参数少等优点，本文选取改进的和声搜索算法对模型进行求解。

3.2.1 算法设计

1）和声记忆库的规模HMS。HMS为记忆库中和声的个数，HMS越大，算法的全局搜索能力越强，但运算时间也会变长，本文取HMS=30。

2）初始解（和声）的构造方法。为便于编程，本文设各空车供应站可选择的空车运输路径数目均为c，当某供应站可选择的运输路径小于c时可建立虚拟路径将路径数目补充至c，并令虚拟路径的空车运输能力为0。首先根据各车站各车种的供需关系以及路径信息细分，生成一个cνn×νm的矩阵，该矩阵中每个元素用yij表示，然后按照以下步骤生成初始解：

Step1随机生成i、j，

其中i∈［1，cvn］，j∈［1，vm］。

Step2若当前元素所对应的车种冲突，则令yij=0，返回Step1；否则进行Step3。

Step7若矩阵中所有元素均被赋值，则停止步骤；否则返回Step1。

3）记忆库取值概率HMCR。HMCR通常取0~1之间较大的数，本文取0.8。

4）微调概率PAR。传统的和声搜索算法PAR为一个固定值，具有一定的局限性，本文对PAR的取值设计进行了动态调整改进，如式（12）所示。

式中：PARmin为PAR的初始值，本文取0.4；PARmax为PAR的上限值，本文取0.9；Tmax为最大迭代次数，本文取50；t为当前的迭代次数。

从式（12）可以看出PAR在算法迭代过程中会随着迭代次数增加而逐渐增大，这样做的好处在于：较小的PAR在算法迭代初期会提高算法的局部寻优质量，较大的PAR在算法中后期有助于跳出局部最优情况。

5）微调规则。

①随机生成i、j，其中i∈［1，cνn］，j∈［1，νm］。

②若yij=0：在第i行中随机挑选一个非0元素yih，在第j列中随机挑选一个非0元素ygj，令ygh+θ、yij=yij+θ;若无法找到满足上述条件的yih和ygj，则重新生成i，j进行微调。

③若yij≠0，在第i行中随机挑选一个除yij之外的非零元素记为yij，然后在第h列中随机挑选一个非零元素记为ygh；若第i行中无非零元素则在第j列中随机挑选一个非零元素记为ygj，然后在第g行中随机挑选一个非零元素记为ygh。令θ=min{yif，yij-θ；若无法找到满足上述要求的ygh，则重新生成i，j进行微调。

6）解的评价。本文选取总的目标函数值Z作为解的评价，即Z越小，解的评价越优。

3.2.2 算法步骤描述

Step1初始化算法参数，令迭代次数t=1，随机生成HMS个初始和声构成记忆库HM。

Step2生 成 一 个 随 机 数rand1∈［0，1］，若rand1＜HMCR，转Step3；否则转Step4。

Step3在HM中随机选出一和声记为Xnew，生成一个随机数rand2∈［0，1］，若rand2＜PAR，则对Xnew进行微调，转Step5；否则不需进行此微调。

Step4用初始和声的构造方法生成新的和声记为Xnew。

Step5若Xnew优于HM中最差的和声，则将Xnew替换掉HM中最差的和声。

Step6令t=t+1，若t＞Tmax则终止迭代，输出HM中最好的和声；否则返回Step2。

4 算例分析

某铁路枢纽内有3个空车供应站，分别用S1，S2，S3表示；4个空车需求站，分别用D1，D2，D3，D4表示；共有3种类型的空车。表1为各车站的空车供需情况；表2为各车站之间的运输成本、运输时间及路径信息；表3为各供应站空车的出发时间；表4为各空车需求站对空车到达时间的要求；表5为各需求站的积压库存成本及延误损失费用；表6为各车种之间的代用成本。试制定合理的空车调配方案。

表1 各车站的空车供需情况 辆

表2 各车站之间的运输成本、运输时间及路径信息 单位：h

表3 各空车供应站的空车出发时间

表4 空车需求站对空车到达时间要求

表5 各空车需求站的积压库存成本及延误损失费用元/（车·h）

表6 车种代用费用 单位：元/车

算例在3.4GHZ的PC端，利用C++编程实现。取η1=η2=η3=η4=0.25，HMS取30，HMCR取0.8，PARmin取0.4，PARmax取0.8，最 大 迭 代 次 数Tmax取100。由于空车供应总量与空车需求总量不相等，故需要引入一个虚拟需求站D5将原问题转换为产销平衡问题，设D5到所有供应站的运输成本为0，空车需求数为8辆。程序运行10次的平均运行时间为0.6s，求得的最优调配方案如表7所示，最佳方案的运输成本为2760元，积压库存费用为12元，车种代用成本为739元，整个调配系统的空车到达时间可靠性为98.5%，调配方案满足路径能力约束。

表7 算例仿真结果

5 结束语

空车调配是铁路货物运输生产中的重要环节，将铁路效益、货主满意度、路网运输能力综合考虑优化符合铁路的发展方向。对于建立的多目标优化模型，改进的和声搜索算法对模型的求解效果良好，可根据实际需求来调整权重系数及算法参数，以应对复杂多样的实际情况。下一步将针对动态空车调配的综合优化问题进行研究。