基于鲁棒软时间窗的铁路集装箱空箱调运优化研究

段 刚， 陈 莉， 李引珍， 何瑞春， 朱昌锋

(1. 兰州交通大学 交通运输学院， 甘肃 兰州 730070; 2. 西北交通经济研究中心， 甘肃 兰州 730070; 3. 兰州城市学院 数学学院， 甘肃 兰州 730070)

由于我国自然资源分布不均，生产力水平、区域经济发展和贸易不平衡，集装箱办理站集装箱到发量不均衡以及点线能力不匹配等原因，导致铁路适箱货源和箱源分布不平均，进而导致集装箱运输的不平衡，由此产生大量空箱，不得不进行空箱调运。

频繁进行空箱调运不但浪费铁路运能，而且在运输途中支出的各种费用也给铁路运输企业增加了负担。中铁集装箱运输有限责任公司向国家铁路支付的费用共有9项，其中有5项付费涉及空箱运输，分别是车辆租用费、车辆编解服务费、机车牵引费、车辆挂运费和线路使用费。因此，优化空箱调运方案，对于减少成本，提高运能和运量具有重要意义。

目前全路共有上百个集装箱办理站，由于适箱货源不足且去向不稳定，重箱和空箱运输主要采取混编形式。为加快铁路集装箱运输业务的发展，铁路总公司相继规划建设上海、昆明、西安、武汉、青岛、郑州、重庆、深圳、哈尔滨、大连、兰州、沈阳、广州、成都、乌鲁木齐、天津、北京、宁波等铁路集装箱物流中心(以下简称中心)。由于中心间集装箱运量大且货源稳定，故采用集装箱班列形式组织运输，空箱回送也以整列形式进行，极大地加快集装箱周转速度，提高集装箱利用率。

铁路空箱调运优化问题主要解决的是空箱调运的数量、时间以及路径问题。在现有运输组织方式下，全路空箱调配分为2个层次：一是全路范围(局间)的集装箱排空计划，这是硬性规定，各铁路局必须完成；二是铁路局内部的空箱调配计划。两者根据重箱的流向和流量制定。各路局在“一卸二排三装”的原则下，首先保证完成局间排空任务，然后再对铁路局内部的空箱进行调整。本文主要研究局内空箱调配优化方案，且假定集装箱运输的OD路径已经确定，根据重箱的流量和流向，在现有运输能力的基础上，制定科学合理的空箱调运方案，优化空箱调运的数量和时间。

国外学者对海运空箱调配问题研究较多，对铁路空箱调运具有一定的借鉴意义。Le-Griffin[1]研究美国西海岸近海航运空箱调运问题，为建立区域港口系统提供适当的制度框架，以协调国家和私人投资近海航运。研究结果显示近海航运是可行的策略，在美国西海岸实施区域港口体系发展战略可有效减轻由大城市主要通道频繁的商业活动引起的交通拥挤；Song[2]考虑动态与随机环境下空箱配送问题，将其划分为空箱装载与卸载2部分，制定灵活的配送策略，即空箱配送的目的地和数量事先不确定，而在途中根据港口最新的即时信息确定。当贸易不均衡时明显优于传统优化方法，可以降低22%成本。灵敏度分析表明其优势受贸易不平衡方式、船队规模和边界值因素影响很大，但对需求分布类型和船舶容量并不敏感；Lam[3]同样采用动态随机规划模型研究拥有2个港口和2条航线的海运系统空箱调运问题，通过时间差模拟方法获得近似最优解，与精确解进行比较，最后将结论推广至多港口多航线；Moon[4]研究空箱最优分配以减少港口间集装箱的不平衡性，将运输费用、处理费用和存贮费用之和极小化作为目标。同时构造混合整数规划模型，对采购及租赁集装箱的数量进行研究，采用混合遗传算法求解；Moon[5]对可折叠集装箱与一般集装箱空箱在调运过程中产生的费用进行比较，该费用包括折叠费用、存贮费用、集装箱进货成本与调运费用，通过灵敏度分析揭示集装箱进货成本与调运费用对可折叠集装箱调运的影响；Chou[6]建立混合模糊决策模型，将空箱配送问题分为2个阶段：第1阶段应用模糊缺货存贮模型，将最优缺货量作为港口的最优租箱量，将最优定货量作为港口的最优空箱需求量。第2阶段采用网络模型，基于以上2个最优结果，优化多个港口之间的空箱调运问题。通过横跨太平洋航线，包括高雄港、香港港、基隆港、神户港、横滨港和洛杉矶港的真实案例，证明该模型的有效性。最后指出香港港的最优租箱率为10.08%，低于实际20%～25%的租箱率；Li[7]将港口的空箱调运问题看成非标准的存贮问题，当进口空箱时需求量为正，出口空箱时需求量为负，以期望空箱调运成本、期望租箱成本和期望搬运成本之和最小为目标，分别对短期和长期规划求出最佳策略。

国内学者对铁路空箱调运问题进行有益的研究。朱德辉[8]对罐式集装箱重箱流和空箱流调配进行综合优化，以罐箱运输费用最小为目标，建立铁路罐式集装箱空箱调配优化多商品网络流模型，并构造嵌入模拟退火操作的遗传算法进行求解；闫海峰[9]根据集装箱班列开行特点，以混合箱流的输送时间、距离和费用3者的综合最优为目标，建立结点站间基于径路选择的空箱调配混合0-1规划模型，将模型模拟为二级耦合反馈系统设计算法；张得志[10]通过对铁路集装箱运输市场的调研，建立基于顾客偏好和时间窗的模糊机会约束规划模型，采用遗传算法求解；文献[11,12]根据空箱需求的时间要求，建立基于软时间窗的铁路集装箱空箱调运模型，但没有考虑走行时间的不确定性。

若知道该参数的确切概率分布，则可使用随机优化方法进行建模[13]，但求解比较困难。当缺乏统计数据或统计数据不准确时，难以确定他的概率分布，这时可应用鲁棒优化的方法[14]。当走行时间变化范围和均值已知时，鲁棒优化方法假设这些不确定的走行时间均按照最坏的情况发生，即要么是最长走行时间、要么是最短走行时间，主要取决于需求站时间窗要求。比如，某需求站的时间窗为[10:00,14:00]，某供应站到该需求站的走行时间在3～8 h，若出发时间为10:00，则按最短走行时间计算，到达需求站的时间为13:00，刚好位于时间窗内，而若按最长走行时间计算则将晚到4 h。因此考虑最坏情况，我们取2站的走行时间为最长走行时间。

这些假设虽然使求出的鲁棒解适用于所有可能发生的情况，但过于保守，因为现实中很少出现所有走行时间都是不确定的情况，即便如此，也不一定都是最坏情况。Bertsimas[15]将该条件放松，认为出现在约束条件中的不确定参数最多有P个(不一定为整数)将发生变化，其余参数为确定的，取其变化的均值。而且从理论上给出证明，即使取均值的参数也发生变化时，鲁棒解仍以很大的概率保证其可行性。该方法不但具有很强的灵活性，而且最吸引人的是鲁棒优化问题与对应的确定型问题保持相同的计算复杂性。

采用该思想，将全部走行时间分为确定和不确定2类，并只对不确定的时间采用鲁棒优化方法，这样可以改善传统鲁棒优化过于保守的缺陷。在Bertsimas[15]建立的模型中，鲁棒部分在约束条件中，而考虑的不确定走行时间则位于目标函数的时间窗里。因此，将其称为鲁棒软时间窗(Robust Soft Time Window，RSTW)模型。在此基础上，建立基于鲁棒软时间窗的空箱调运(Empty Container Allocation with Robust Soft Time Window，ECARSTW)优化模型，为解决不确定走行时间问题提供通用模型和一般框架。

1 时间窗的鲁棒优化

1.1 基于软时间窗的集装箱空箱调运

首先构造基于软时间窗的集装箱空箱调运(Empty Container Allocation with Soft Time Window, ECASTW)模型。以空箱调运成本、提前到达产生的集装箱库存成本和延误到达产生的机会损失成本之和最小为目标函数

vjmax{ti+tij-lj,0})}

( 1 )

式中：[ej,lj]为j站空箱需求的时间窗，j∈V，V为空箱需求站集合；ti为i站空箱的出发时间，i∈W，W为空箱供应站集合；tij为i站到j站的走行时间，(i,j)∈E，E=W×V有向边集合；cij为i站到j站的单位空箱运输成本；uj为空箱提前到达j站产生的积压库存费用；vj为空箱延误到达j站产生的损失费用；xij为i站到j站调运的空箱数。

约束条件

空箱供应约束

( 2 )

式中：ai为i站的空箱供应量。

空箱需求约束

( 3 )

式中：bj为j站的空箱需求量。

OD路径上的集装箱通过能力约束

xij≤dij(i,j)∈E

( 4 )

式中：dij为运输路径(i,j)上换算为集装箱的通过能力。

变量声明

xij≥0 且为整数 (i,j)∈E

( 5 )

1.2 RSTW模型及性质

1.2.1RSTW模型

令|E|=r，则在全部r个走行时间中，最多有p(0≤p≤r)个是不确定的。令

由于ECASTW模型不仅考虑提前到达和延误到达，还需考虑他们的成本，所以也需考虑库存成本和机会损失成本。令

RSTW模型为

( 6 )

式中：yij为空箱调运数量。

1.2.2 模型性质

( 7 )

且Δyi0,j0>0。

令S*为满足下式的集合

( 8 )

即S*是式( 6 )达到最大的集合。

(i0,j0)与S*的关系存在2种可能：(i0,j0)∈S*或者(i0,j0)∈E/S*。

第1种可能(i0,j0)∈S*

且S*也必定满足

( 9 )

否则，假设存在集合S**，满足

如果(i0,j0)∈S**，那么一定有

模型的准确程度与拟颗粒的大小密切相关，拟颗粒越小，颗粒越多，计算结果越准确，但工作量也就越大，计算能力是该模型发展的一个重要限制。气体拟颗粒在流动过程中不断破裂、混合，是瞬时性的，拟合时人为确定，局限于理想状况，目前发展还不成熟。

第2种可能为 (i0,j0)∈E/S*，结论同样成立。

综上，有式( 7 )成立。

证毕。

定理1表明在式( 6 )中，yij越大，则

越大，反之则越小。

2 ECARSTW模型及等价变换

2.1 ECARSTW模型及性质

2.1.1 模型

我们将RSTW加到式( 1 )中，替换目标中库存成本或机会损失成本，得到ECARSTW模型

(10)

yij≥xij(i,j)∈E

(11)

2.1.2 性质

下面我们给出ECARSTW模型最优解的性质。

所以

2.2 RSTW的等价变换

令

(12)

下面给出鲁棒软时间窗R(yij,p)的等价线性规划形式。

(13)

(14)

0≤zij≤1 (i,j)∈E

(15)

定理4定理3中的线性规划即式(13)～式(15)的对偶问题为

(16)

(17)

q≥0

(18)

wij≥0 (i,j)∈E

(19)

式中：q、wij为式(14)、式(15)对应的对偶变量。

证明：由于

(20)

所以，下述线性规划问题

(21)

s.t. 式(14)和式(15)

的对偶为

(22)

s.t. 式(17)～式(19)

2.3 ECARSTW模型的等价整数线性规划形式

根据上述定理，可将ECARSTW模型转换为等价的整数线性规划形式。

定理5ECARSTW模型等价于

(23)

s.t. 式(2) ～式(5)，式(17)～式(19)

证明：由定理4知，ECARSTW模型等价于

(24)

s.t. 式( 2 )～式( 5 )，式(17)～式(19)

≤min

另一方面，由于

所以

由此

由此，我们将ECARSTW模型转换为一般的整数线性规划模型，转换后的模型与ECARSTW模型相比，仅多了1个变量q，且没有增加新的约束条件(非负限制除外)，但将ECARSTW模型目标中的非线性RSTW部分转换为线性函数，因此更易于求解。

3 算例

我们通过实例验证所提模型的正确性。某铁路局有20个空箱供应站，12个空箱需求站。供应站的空箱供应量和出发时间见表1，需求站的空箱需求量、时间窗、库存成本和机会损失见表2，供应站与需求站间走行时间范围见表3，空箱调运成本见表4，空箱运输OD路径间通过能力见表5。取p= 10，利用LINGO 15.0软件求解，得到最优解为x13=27,x19=2,x24=25,x27=20,x35=26,x42=10,x4,10=1,x53=4,x58=11,x6,11=32,x71=14,x77=66,x86=15,x8,10=50,x91=6,x10,10=23,x10,11=5,x11,9=16,x12,12=30,x13,1=12,x14,3=25,x15,7=17,x15,8=25,x16,11=8,x17,5=22,x17,12=5,x18,10=18,x19,12=35,x20,7=22,w42=21,w4,10=5,w6,11=44,w86=56,w8,10=446,w13,1=32,w14,3=146,w15,7=30,w17,5=51,w20,7=84,q=4。

表1 空箱供应站信息

表2 空箱需求站信息

在最优调运方案中，共有3条OD路径的空箱调运量达到通过能力上限，分别为供应站4至需求站2(10个空箱)，供应站8至需求站10(50个空箱)，供应站12至需求站12(30个空箱)。如果提高这些路径的集装箱通过能力，将进一步降低空箱调运成本。

最优解中共有29个xij大于0，即发生29次空箱调运。由于p= 10，所以只有10个wij取值为正，说明与这10个wij对应的走行时间是不确定的，他们与剩下的19个确定的走行时间使得RSTW达到最大。在不确定的走行时间中，有8个空箱调运到达时间早于时间窗，分别对应w42、w4,10、w6,11、w8,10、w13,1、w14,3、w15,7、w20,7；2个到达时间晚于时间窗，分别对应w86和w17,5。在确定的走行时间中，共有3个到达时间早于时间窗，分别对应w19、w58、w15,8只有1个到达时间晚于时间窗，对应w10,11。

在全部240个走行时间中，若均按不确定走行时间计算，共有57个到达时间早于时间窗，82个到达时间晚于时间窗；若都按确定的走行时间计算，有48个到达时间早于时间窗，61个到达时间晚于时间窗。显然，增加不确定走行时间的数量p，将增加成本。下面对p值进行灵敏度分析。

图1给出总成本与p的关系，显然，总成本是p的增函数。但当p≥ 12时，总成本不再增加，达到最大值145 301元，所以p的上界是12。该取值与问题的规模以及不确定走行时间的数量相比非常小。图2～图5分别给出目标中4个成本与p的关系，可以看出，f1和f3是p的增函数，f2是p的减函数。但f4与p没有这样的单调关系，所以我们对q与p的关系进行分析，见图6，显然，q是p的减函数。而且当成本达到最大或最小时，p的取值不完全相同。当p= 10时，f1和f2分别达到最大和最小；当p= 13时，f3达到最大，q达到最小值0，f4重新为0。

表3 供应站与需求站间走行时间范围

表4 空箱调运成本 元·箱-1

表5 OD路径的集装箱通过能力 箱

当p分别取值12和13时，虽然总成本相等，且二者的xij值都相同，但wij的取值却不同，主要原因为q值不同。当p= 12时，q= 3，而p= 13时，q= 0，为使目标达到极小，式(17)必然等式成立，因此导致wij的不同。且当p= 12或p=13时，二者的不确定走行时间的个数都小于p，分别为11个和12个。因此，在最优解中，不确定走行时间的个数可以小于p值，而且当p越接近上界，才越有可能发生这种情况。尽管不确定走行时间的数量可能很多，但对成本产生影响的却是有限的几个，或者说只有很少的不确定走行时间将影响目标。所以，在确定p的数值时，应从较小的开始，一旦找到其上界，就可确定出那些起作用的不确定走行时间，并尽可能保证这些空箱调运按时完成，以减少成本。

当p= 0时，所有走行时间均为确定的，此时成本最小，为144 323元。其中，f1= 139 593，f2=4 730，f3= 0，f4= 0，q= 450。从图2和图3可以看出，当0≤p≤3时，f1和f2的值均不变。说明变量xij的值相同，而wij的值不同。其原因还是由于q的取值不同。

4 结论

集装箱运输是现代化货物运输发展方向。在北美洲，铁路集装箱运输收入早已超过煤炭运输收入而高居第1位。我国铁路集装箱运输发展却相对缓慢，目前运输量仅占铁路货物发送量的3%左右，这既受到铁路运能紧张等客观因素的制约，也受到运输作业组织等管理因素的影响。空箱的科学合理调运是提高集装箱周转率、增加运量和顺利完成运输作业组织的重要保证。因此空箱调运优化具有重要的理论和实际意义。在传统基于软时间窗的集装箱空箱调运模型基础上，考虑铁路运输过程中走行时间不确定对空箱调运的影响，首先构造基于鲁棒软时间窗的空箱调运通用模型，得到解的一些性质，然后建立解决这类问题的一般框架。模型具有建立简单，方便计算的特点，既避免随机约束规划的复杂性，又克服传统鲁棒优化过于保守的不足性。算例表明不确定走行时间的个数存在1个较小的上界。该优化方法对中铁集装箱运输有限公司制定日常空箱调运计划，具有一定的借鉴意义。

参考文献：

[1] LE GRIFFIN H D, GRIFFIN M T. Managing Empty Container Flows through Short Sea Shipping and Regional Port Systems[J]. International Journal of Shipping and Transport Logistics, 2010, 2(1): 59-75.

[2] SONG D P, DONG J X. Effectiveness of An Empty Container Repositioning Policy with Flexible Destination Ports[J]. Transport Policy, 2011, 18(1): 92-101.

[3] LAM S W, LEE L H, TANG L C. An Approximate Dynamic Programming Approach for the Empty Container Allocation Problem[J]. Transportation Research Part C, 2007, 15(4): 265-277.

[4] MOON I K, NGOC A D, HUR Y S. Positioning Empty Containers among Multiple Ports with Leasing and Purchasing Considerations[J]. OR Spectrum, 2010, 32(3): 765-786.

[5] MOON I K, NGOC A D, KONINGSC R. Foldable and Standard Containers in Empty Container Repositioning[J]. Transportation Research Part E, 2013, 49(1): 107-124.

[6] CHOU C C, GOU R H, TSAI C L, et al. Application of A Mixed Fuzzy Decision Making and Optimization Programming Model to the Empty Container Allocation[J]. Applied Soft Computing, 2010, 10(4): 1071-1079.

[7] LI J A, LIU K, LEUNG S, et al. Empty Container Management in A Port with Long-run Average Criterion[J]. Mathematical and Computer Modelling, 2004, 40(1-2): 85-100.

[8] 朱德辉, 何世伟. 铁路罐式集装箱空箱调配优化模型及遗传模拟退火算法[J]. 中国铁道科学, 2008, 29(6): 104-110.

ZHU De-hui, HE Shi-wei. Optimization Model of Railway Empty Tank Container Allocation and Genetic Simulated Annealing Algorithm[J]. China Railway Science, 2008, 29(6): 104-110.

[9] 闫海峰, 董守清. 铁路集装箱结点站间空箱调配的优化[J]. 中国铁道科学, 2009, 30(1): 131-135.

YAN Hai-feng, DONG Shou-qing.Optimization of the Empty Containers Distribution Among Railway Network Container Freight Stations[J]. China Railway Science, 2009, 30(1): 131-135.

[10] 张得志, 谢如鹤, 黄孝章. 铁路集装箱空箱调度模型及求解算法[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.

[11] 段刚, 陈志忠, 陈莉, 等. 基于技术站改编作业的集装箱空箱调运优化模型[J]. 铁道运输与经济, 2011, 33(10): 70-73.

DUAN Gang, CHEN Zhi-zhong, CHEN Li, et al. Empty Container Allocation Optimization Model Based on Technique Station Reclassifying Operation[J]. Railway Transport and Economy, 2011, 33(10): 70-73.

[12] 段刚, 陈莉, 陈志忠, 等. 基于技术站改编作业的集装箱空箱动态调运优化模型与算法[J]. 交通运输系统工程与信息, 2012, 12(2): 111-118.

DUAN Gang, CHEN Li, CHEN Zhi-zhong, et al. Dynamic Empty Container Allocation Model and Algorithm Based on Technique Station Transfer Operation[J]. Journal of Transportation Systems Engineering and Information Technology, 2012, 12(2): 111-118.

[13] 段刚, 卢跃荣, 陈莉, 等. 不确定环境下铁路集装箱空箱调运优化研究[J]. 兰州交通大学学报, 2012, 31(6): 97-102.

DUAN Gang, LU Yue-rong, CHEN Li, et al. Optimization on Railway Empty Container Allocation under Uncertain Environment[J]. Journal of Lanzhou Jiaotong University, 2012, 31(6): 97-102.

[14] BEN-TAI A, BERTSIMAS D, BROWN D. A Soft Robust Model for Optimization under Ambiguity[J]. Operations Research, 2010, 58 4(1): 1220-1234.

[15] BERTSIMAS D, SIM M. The Price of Robustness[J].Operations Research, 2004, 52 (1):35-53.