重箱协调下的单一空箱调运模型与算法

陈小红

（西安铁路职业技术学院 陕西 西安710014）

集装箱运输中存在着大量的空箱运输， 造成运输资源的极大浪费，使铁路集装箱运输业蒙受了重大损失。 关于铁路空箱调运的问题已引起了很多学者的重视，并进行了相应的研究。 张得志、谢如鹤等学者从铁路集装箱运输市场的实际情况出发, 建立了基于顾客偏好的模糊规划模型和带时间窗的规划模型，并应用遗传算法对其进行了求解[1]。 彭华、朱庆生教授等以最大限度地提高区域内空箱的利用率和减小空箱调度的成本为目标，建立了在一个计划期内的铁路集装箱空箱动态优化调度模型， 运用遗传算法对模型进行求解，解决了在一个计划期内，如何最优化地对每个工作日的空箱进行区域性调度的问题[2]。 由于空车调配和空箱调配的相似性，空车调配问题的文献[3-5]也有借鉴作用。

上述模型多以空箱调运费用最低为目标[1-2，6]，且未给出具体算法[6]；而在实际生产中，铁路部门空箱调运的目的还是减少运营成本，追求效益最大化，所以应该建立以效益最大化为目标的模型。 本文以效益最大化为目标函数建立了重箱协调下的单一箱型空箱调运模型，设计了双决策变量下的遗传算法，最后给出了一个具体算例，对现场实际有一定的借鉴作用。

1 考虑重箱运输的空箱调运模型的建立

1.1 参数及决策变量描述

在一个区域内，有n 个集装箱办理站，每个车站每天将从区域外运输到本站的集装箱卸货后， 会产生a 个空箱，而当天该站又有货物需要运出，该车站的最大发送量为b。当该车站的最大货运需求b 大于空箱产生量a 时，就需要从其他有多余空箱的车站调配。 如何运送集装箱货物及如何调配空箱使铁路运输部门收益最大。

1) 决策变量

xij：从i 站运往j 到达站的集装箱重箱数；

yij：从i 站调配到j 站进行装箱的空箱数；

2)参数

ai：第i 个车站产生的集装箱空箱数；

bij：i 站到j 站的集装箱货运需求，也就是i 站到j 站的最大发送量；

cij：从i 站到j 站调配单位空箱所产生的调运费用；

dij：从i 站到j 站运送集装箱货物的单位收益；

Mij：i 站到j 站之间的集装箱运输能力限制。

1.2 目标函数与约束条件的确定

1)目标函数的确定

在实际运输生产中，铁路作为一个企业，其最终目标是要追求效益最大化。 当集装箱重箱发送量不能满足货运需求时，还应考虑产生的运输收益损失。 运输收益损失与请求箱兑现率及每类货物的财务影子价格有关， 货物价值越高，影子价格就越高。

对于整个系统的重空箱数调配， 目标还是谋求效益最大化。 这时，效益影响因素则包括：①集装箱重箱运输收入；②空箱运输费用；③未满足运输需求的运输收益损失。目标函数可表述为：

ρij为i 站到j 站的集装箱单位运量的影子价格；bij-xij为i站到j 站的未满足货运需求的集装箱量。

2)约束条件

①对空箱供给站I 的约束条件

对供给站i 来说，应该满足空箱供给不小于空箱需求。也就是该站的空箱产生量应不小于本站的空箱需求量(重箱发送量)加上运往需求站J(由供给站i 所供应的需求站集合)的空集装箱量。 即：

②对空箱需求站J 的约束条件

同样， 对于需求站j， 应该满足空箱供给不小于空箱需求。 也就是该站的空箱产生量加上由需求站调运到本站的空箱量，应不小于本站的空箱需求量。 即：

③对重箱发送量的约束条件

优化后的计划装箱数应该不大于该站的集装箱货运需求。 即：

④运输能力约束条件

考虑重箱协调下的空箱调运时， 空箱源站至需求站之间的运输能力限制应该包括空箱运输能力限制和重箱运输能力限制。

⑤非负约束及整数约束

本式的意义为： 该模型中所有决策变量均大于等于零且为整数，否则无意义。

1.3 空箱调运优化模型

通过以上的分析， 可以得到一个空箱调运优化模型[SECRM]1：

2 模型的算法设计

2.1 解的编码和初始化

本模型具有两个决策变量，故染色体由两部分组成，需要对这两个决策变量分别进行编码。 本文采用十进制基因矩阵对其编码，如下所示。

其中，Yp代表第p 个染色体1 部分，yij是相应的决策变量，表示从i 站发往j 站的空箱数量； Xp代表第p 个染色体2部分，xij是相应的决策变量，表示从i 站发往j 站的重箱运量。若xij和yij满足模型的约束条件(1)、(2)、(3)和(4)，则由此构成的染色体编码(矩阵YX)，表示了原问题的一个可行解。 显然，由此构成的染色体的基因型与其表现型是完全一致的， 它不仅具有编码简单、直观，而且易于遗传操作算法实现的特点。

初始化算法具体构造如下：

假定约束条件只有空重箱供给与需求的约束， 运输能力约束条件暂不考虑，只需在实际求解中加入约束判断就行，使其初始解满足所有约束条件。

输入参数：第i 车站的空箱产生数；第i 车站至第j 车站的货运需求，并可求出第i 车站的总货运需求bi，其中i∈[1,n]，j∈[1,n]。

输出结果：空箱调配矩阵Y，Y=yij，i，j∈[1,n]

重箱发送矩阵X，X=xij，i，j∈[1,n]，

算法1：对yij初始化

步骤1：随机产生行号i，i∈[1,n]，随机产生列号j，j∈[1,n]。

步骤2：计算矩阵Y 中的元素Yij

If i=j or ai≤biyij=0

//保证空箱不能从富余站运往富余站，即两次调运

步骤3：更新ai=ai-yij，aj=aj+yij

步骤4：重复步骤1～3，直到所有的行列都设置完毕。 保留新的ai，aj。

算法2：对xij初始化

步骤1：随机产生行号i，i∈[1,n]，随机产生列号j，j∈[1，n]。

步骤2：计算矩阵Y 中的元素xij

If i=j or ai≤bixij=0

Else if ai≥bixij=bij//此时的ai是对yij初始化后的ai。

Else xij=min{bij，ai}

步骤3：更新ai=ai-xij，bi=bi-xij

步骤4：重复步骤1～3，直到所有的行列都设置完毕。

易知：由初始化算法得出的每组空重箱运输量xij和yij都满足约束条件(1)式、(2)式、(3)式，故计算出的染色体YX 为原问题的一个可行解。该算法采用随机数自动生成行号和列号，使得初始种群更加具有广泛性和多样性， 并能保证初始解相对于目标函数而言得出的是一个适中的解。

2.2 适应度函数的计算

用目标函数值评价染色体适应度的大小。

2.3 染色体交叉算子设计

对染色体1 部分的交叉：

从上式可知，rij是0-1 矩阵，因为Rem 矩阵存储是否需要取整即除以2 的余数(0 或1)。

也就是使

从上易知，余数矩阵Rem 有多个分解法，且经上述交叉操作后的后代都是可行的[1-2]。

对染色体2 部分的交叉：

因为染色体1 部分改变， 染色体2 部分就会相应改变，他们之间有着一一对应的关系。 故对染色体1 部分进行交叉操作，就意味着对染色体2 部分进行交叉操作，只要再对染色体2 部分根据新的集装箱空箱产生量进行一下重新分配。 具体步骤如下：

对染色体1 部分的变异：

步骤2：计算子矩阵Vp×q中的发送量和需求量。

步骤3：重新对Vp×q分配空箱，按初始算法1 生成新的子矩阵。

对染色体2 部分的变异：

同理，对染色体2 部分不用再设计算法变异，只要再对染色体2 部分根据新的集装箱空箱产生量进行一下重新分配。具体步骤如下：

3 具体算例

设某路局管辖6 个大型集装箱办理站，各车站的空箱产生和最大需求情况如表1 所列，各车站至其它车站的重箱运输收入和空箱调运费用分别如表2 和表3 所列，规定重箱单位收益损失和空箱运输单位收入相同，各车站之间的运输能力假定不受限制。 假定遗传参数： 交叉概率pc=0.6，pm=0.1， 种群大小colony-size=30。 求空箱调运和重箱发送的最优调度方案。

可知，车站1、4 是空箱源站，车站2、3、5、6 是空箱目的站。 经计算机仿真，计算模型()，得最大运输收益为54 320元， 空箱调运和重箱发送的最优调度方案如表4 和表5 所示。

4 结束语

模型[SECRM]1 具有如下的特点：

表1 各车站的空箱产生和最大需求情况Tab.1 The supply and maximum demand of empty container in the stations

表2 各车站至其他车站的重箱运输单位收入Tab. 2 Heavy container transportation unit revenue from one station to the other stations

表3 各车站至其他车站的空箱调运费用Tab.3 The stations’ cost of empty container reposition

表4 各站的空箱调运数Tab.4 The stations’ empty container reposition number

1)目标是谋求效益最大化，考虑了装箱运输收入，空箱调运费用和未满足运输需求的收益损失，其中装箱运输收入对目标值具有正效应，其他两项对目标值具有负效应。

2) 在考虑运输能力时把重箱运输能力和空箱运输能力同时考虑进来，符合现场实际。

3)考虑的是单一标准箱型下的模型，以后的模型可以在此基础上扩展到不同尺寸不同类型的集装箱。

4)对空箱供需量与重箱装卸量进行了合理衔接，重箱的装卸差决定了空箱的供给量，空箱需求的满足量又反过来影响了重箱装运量。 显然，将重箱和空箱联合纳入优化要比单纯的空箱优化更准确。

表5 各站的重箱发送数Tab.5 The stations’ heavy container sending number

当然，该模型只是考虑单一箱型的空箱调运，实际货物运输当中存在多种运输路径，不同尺寸的箱型间有无可替代性，时效性对箱源的影响等,可建立较为复杂的考虑多方面影响因素的空箱调运模型。

[1] 张得志,谢如鹤,黄孝章.铁路集装箱空箱调度模型及求解算法[J].中国铁道科学,2003,24(3):125-129.

ZHANG De-zhi,XIE Ru-he,HUANG Xiao-zhang.Dispatch model and solution algorithm of railway empty container[J].China Railway Science,2003,24(3):125-129.

[2] 彭华.铁路集装箱空箱动态优化调度研究[D].重庆：重庆大学机电学院，2008.

[3] 李宗平，夏剑锋.基于时间约束的铁路空车调配模型与算法[J].西南交通大学学报，2005,3（40）：361-365.

LI Zong-ping XIA Jian-feng.Time restraint-based model and algorithm for raiway empty wagon distribution[J].Journal of Southwest Jiaotong University,2005,3(40):361-365.

[4] 梁栋,林柏梁，严贺祥，等.车种代用情况下的铁路空车调配研究[J].铁道学报，2005，4(27)：1-5.

LIANG Dong,LIN Bo-liang,YAN He-xiang,et al.Study of raiway empty car distribution with substitution of empty car types[J].Journal of the China Railway Society,2005,4(27):1-5.

[5] 雷中林,何世伟，宋瑞，等.铁路空车调配问题的随机机会约束模型及遗传算法[J].铁道学报,2005，27(5):1-5.

LEI Zhong -lin,HE Shi -wei,SONG Rui,et al.Stochastic chance-constrained model and genetic algorithm for empty car distribution in raiway transportaton[J].Joural of the China Railway Society,2005,27(5):1-5.

[6] 计明军，王清斌，张新宇，等.沿海港口集装箱空箱调运策略的优化模型[J].运筹与管理，2014,1（23）：80-89.

JI Ming-jun,WANG Qing-bin,ZHANG Xin-yu,et al.Optimal model for allocation and transportation strategies of empty containers between coastal ports [J].Operations Research and Management Science,2014,1(23):80-89.