李永军，段刚，陈莉，田丽娜，苏旺辉

(1.兰州城市学院 数学学院，甘肃 兰州 730070;兰州交通大学 交通运输学院，甘肃 兰州 730070)



基于技术站改编作业的集装箱空箱调运鲁棒优化

李永军1，段刚2，陈莉1，田丽娜1，苏旺辉1

(1.兰州城市学院 数学学院，甘肃 兰州 730070;兰州交通大学 交通运输学院，甘肃 兰州 730070)

摘要:对一般的集装箱办理站，考虑到技术站改编时间和运输走行时间对空箱需求站时间窗的影响，以集结费用、技术站改编费用、车辆走行费用以及空箱早到库存成本或延误损失成本之和最小为目标，以车站作业能力和线路通过能力为约束条件，建立基于技术站改编作业的空箱调运模型。针对集装箱空箱运输过程中走行时间不确定的特点，建立鲁棒软时间窗组合优化模型。通过等价变换和对偶变换，将鲁棒软时间窗组合优化模型转换为线性规划模型，极大地简化了模型。然后构造基于技术站改编作业的空箱调运鲁棒优化模型，并将其转换为一般的整数线性规划模型。算例表明，该方法简单有效。最后对不确定走行时间的个数p进行灵敏度分析，结果表明其存在一个较小的上界。

关键词：铁路运输；优化；鲁棒软时间窗；空箱调运；技术站改编作业；不确定走行时间

集装箱运输是铁路货物运输发展方向之一。北美的铁路集装箱运输收入早已高居第一，然而我国铁路集装箱运输却发展缓慢，集装箱运输量仅占铁路货物发送量的3%。这既有铁路运能紧张等客观因素的影响，也受到集装箱运输作业组织等方面的制约。科学合理的空箱调运是提高集装箱周转率、增加铁路集装箱运量和顺利完成集装箱运输作业组织的重要保证，具有重要意义。Li等[1]对海运业在绿色供应链中的责任问题进行了分析，揭示了空箱的合理调运不但可以增加公司利润，而且还能够减少供应链中的浪费。Song等[2]考虑动态与随机环境下的空箱配送问题，制定了一个灵活的配送策略：即空箱配送的目的地和数量事先不确定，而是在途中根据港口最新的即时信息来确定。灵敏度分析表明这一策略受贸易不平衡方式、船队规模和边界值因素的影响很大，但对需求分布类型和船舶容量并不敏感。Long等[3]通过样本均值逼近方法求解随机空箱调运问题，将拉丁超立方设计和过饱和设计相结合，可以得到满意的逼近结果。通过对一些非独立同分布数据的计算检验表明，该方法不仅适用于随机空箱调运问题，而且能够得到高质量的解。闫海峰等[4]建立了结点站间基于径路选择的空箱调配优化模型，利用二级耦合反馈系统来设计算法。朱德辉等[5]以运输费用最小为目标，对罐式集装箱重箱流和空箱流调配进行了综合优化。张得志等[6]则分别建立了基于顾客偏好的模糊运输规划模型与带时间窗的运输规划模型。段刚等[7]考虑技术站改编作业对空箱调运的影响，建立了基于软时间窗的铁路空箱调运优化模型，但却忽视了走行时间不确定这一重要因素。虽然可以采用随机规划的方法建立模型，但求解却非常复杂。在缺乏统计数据或统计数据不准确时，难以确定随机变量的概率分布，这时可以采用鲁棒优化方法。在已知走行时间变化范围的情况下，鲁棒优化假设这些不确定的走行时间都按照最坏的情况发生。这样的假设过于保守，因为现实中很少出现所有走行时间都是不确定的情况，即使走行时间都不确定，也不一定都按最坏情况。Bertsimas等[8]放松了这一要求，认为最多有Γ个不确定参数会发生变化，而其余参数都是确定的，取其均值。而且从理论上证明，即使那些确定的参数也发生变化时，原来得到的鲁棒解仍会以较大的概率保证其可行性。该方法不但具有很大的灵活性，而且鲁棒优化模型与对应的确定型模型具有相同的计算复杂度。本文利用该方法，将走行时间分为确定的和不确定的2类，并只对不确定的时间采用鲁棒优化方法。Bertsimas等[8]所建立的模型中，其不确定参数位于约束条件中，而所考虑的不确定的走行时间则位于目标函数中的时间窗里，因此，将其称为鲁棒软时间窗模型。由于集装箱中心站或运量较大的办理站间，其空箱调运大多通过集装箱班列组织运输，空箱调运也是以整列直达方式运行。而对大多数二级和三级集装箱办理站来说，由于货源不足且去向不稳定，无法组织专列，空箱调运也只能采取混编形式，这样就会在前方技术站进行改编中转作业，从而增加了调运时间，而且只能按指定径路运输。在编组计划确定的条件下，本文对后一种情况进行优化，以集结费用、技术站改编费用、车辆走行费用以及空箱早到库存成本或延误损失成本之和最小为目标，以集装箱办理站作业能力和线路通过能力为约束，建立了基于技术站改编作业的空箱调运鲁棒优化模型。

1时间窗的鲁棒优化

1.1基于技术站改编作业和时间窗的集装箱空箱调运模型

决策变量：xij为表示i站到j站调运的空箱数，(i,j)∈E。

基于技术站改编作业和时间窗的集装箱空箱调运优化模型如下：

(1)

(2)

(3)

(4)

(5)

xij≤rij, (i,j)∈E

(6)

(7)

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

(8)

1.2鲁棒软时间窗模型

(9)

(10)

(11)

(12)

其中，式(9)中的βij表示走行时间不确定情况下空箱的最早到达时刻早于时间窗的时间；式(10)中的γij表示走行时间不确定情况下空箱的最晚到达时刻晚于时间窗的时间；式(11)中的ωij表示走行时间确定情况下空箱的最早到达时刻早于时间窗的时间；式(12)中的δij表示走行时间确定情况下空箱的最晚到达时刻晚于时间窗的时间。

由于鲁棒软时间窗模型不仅考虑早到和晚到时间，还考虑了它们的成本，所以也考虑早到和晚到成本。令

λij=max{ujβij,vjγij}, (i,j)∈E

(13)

μij=ujωij+vjδij, (i,j)∈E

(14)

其中，式(13)中的λij表示走行时间不确定情况下空箱的单位早到成本与单位晚到成本的最大值，式(14)中的μij表示走行时间确定情况下空箱的单位早到成本与单位晚到成本之和。

所以，得到鲁棒软时间窗模型：

(15)

2基于技术站改编作业的空箱调运鲁棒优化模型及等价变换

2.1基于技术站改编作业的空箱调运鲁棒优化模型

将鲁棒软时间窗模型加到式(1)中，替换目标里的早到或晚到成本，就得到基于技术站改编作业的空箱调运鲁棒优化模型：

(16)

s.t. yij≥xij, (i,j)∈E

(17)

式(2)-式(8)

式(16)为目标函数，式(17)是对变量yij的限制，其余约束与基于技术站改编作业和时间窗的集装箱空箱调运模型相同。

2.2鲁棒软时间窗的等价变换

令

(18)

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

(19)

(20)

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

(21)

定理1引理1中的线性规划问题式(19)～(21)的对偶问题为

(22)

(23)

q≥0

(24)

rij≥0, (i,j)∈E

(25)

证明：显然

(26)

所以，下述线性规划问题

(27)

s.t. 式(20)，式(21)

的对偶为

(28)

s.t. 式(23)-式(25)

证毕。

2.3基于技术站改编作业的空箱调运鲁棒优化模型的等价形式

定理2基于技术站改编作业的空箱调运鲁棒优化模型等价于下面的整数线性规划模型：

(29)

s.t. 式(2)～式(8)，式(23)～式(25)

定理2的证明见文献[9]。

由此，将基于技术站改编作业的空箱调运鲁棒优化模型转换为一般的整数线性规划模型，转换后的模型与基于技术站改编作业的空箱调运鲁棒优化模型相比，仅多了1个连续变量q，且除了非负限制，没有增加新的约束条件，但将基于技术站改编作业的空箱调运鲁棒优化模型目标中的组合优化部分转换成了线性函数，使之更易于求解。

3算例

某铁路局有8个空箱供应站，6个空箱需求站，5个技术站。供应站的空箱供应量、出发时间、作业能力和集结费用见表1，需求站的空箱需求量、时间窗、作业能力、早到库存成本和晚到机会损失如表2所示，供应站与需求站间走行时间范围及经过的技术站见表3，表4为空箱调运成本和线路间的集装箱通过能力，表5为技术站改编时间和改编费用。

1.2.2 对照组 在基础疾病治疗的基础上,给予1.25×102 mg美多巴,口服,3次/d。3 w为1疗程。

表1　空箱供应站信息

表2　空箱需求站信息

表3供应站与需求站间走行时间范围(h)及经过的技术站

Table 3 Transportation time and technique station between OD

供应站需求站1234561[7,9]/1[3,7][8,12]/1[5,9][4,6][2,6]2[4,8]/4[7,9]/3[5,9][9,15][3,5][7,8]/33[3,5][5,9][3,7]/5[5,6][2,6]/4[4,8]4[4,6][1,5]/2[5,7]/2[5,8]/1[4,6][8,10]5[9,11]/2[7,8][2,4][3,5][5,7]/4[3,5]/56[3,5][6,8][7,11][6,9][3,4][5,7]/47[2,4]/3[7,14]/2[5,9][3,8]/3[4,10][2,6]8[5,8][5,7][6,8]/5[7,9][4,6]/1[2,5]

注：分子表示走行时间范围，分母表示经过的技术站。

表4空箱调运成本(元·箱-1)和线路的集装箱通过能力(箱)
Table 4 Empty container allocation cost and transportation ability between OD

供应站需求站123456140/5060/3020/4030/4070/3030/40270/4040/3020/2030/2050/2090/30320/3070/2090/2060/2030/2040/10430/3020/3070/3030/2040/6060/20510/2040/2060/3020/3030/3020/20690/3030/3070/3040/1060/1090/20760/4050/4040/3020/2030/2090/30830/4060/3020/3060/4090/1070/10

注：分子表示调运成本，分母表示线路的集装箱通过能力。

表5　技术站改编时间和改编费用

最优解中共有12个xij大于零，即发生了12次空箱调运。由于p= 4，所以只有4个rij取值大于0，分别为r31= 65,r45= 438,r73= 246,r83= 230。由互补松弛定理[10]知，在最优解中，当rij>0时，式(20)中与rij对应的约束条件等式成立，即对应的变量zij=1，也就是说与这4个rij对应的走行时间tij是不确定的。在不确定的走行时间中，供应站3向需求站1调运的空箱，走行时间取其最短时间3 h，6∶00从供应站3出发，因此到达需求站1的时间为9∶00，早于时间窗3 h。其余3个不确定走行时间都取其最大值，因此空箱到达需求站的时间都晚于各自需求站的时间窗。其中，供应站4向需求站5调运的空箱，到达需求站5的时间比时间窗晚2 h；供应站7向需求站3调运的空箱，到达需求站3的时间比时间窗晚6 h；供应站8向需求站3调运的空箱，由于在技术站5进行改编，多消耗了6 h，因此到达需求站3的时间比时间窗晚3 h。

由于在改编站作业会增加运到时间，因此，为满足时间窗要求，应尽量减少改编作业发生。在最优调运方案中，仅有2次调运发生改编，供应站4向需求站2调运的空箱在改编站2进行改编，供应站8向需求站3调运的空箱在改编站5进行改编，且只有第2个调运发生延误。共有3条OD路径的空箱调运量达到了通过能力上限，分别是供应站2到需求站3(20个空箱)，供应站6到需求站2(30个空箱)，供应站8到需求站3(30个空箱)。

p的取值不同时，最优解显然也会变化，下面p值做灵敏度分析。图1给出了总成本F，q与p的关系，显然，总成本F是p的增函数，而q则是p的减函数。但当p= 5时，总成本就不再增加，达到最大值12 910，所以p的上界是5。也就是说，仅有5个不确定走行时间对最优解的影响最大，并使得总成本达到最大。当p≥5时，q= 0。

当p= 0时，所有走行时间都是确定的，此时成本最小，为11 861元，其中F1= 1747，F2= 380，F3= 8 080，F4= 1 654，F5= 0，F6= 0，q= 448。图2为成本F1,F2,F3,F4,F5,F6随p的变化情况，可以看出：F2随p减少；F5随p增加；F1，F3和F6随p先增后减；F4则先减后增。

图1　总成本F和q与p的关系Fig.1 Relationship between total cost F and p

图2　成本F1, F2, F3, F4, F5和 F6与p的关系Fig.2 Relationship between cost F1, F2, F3, F4, F5 , F6 and p

4结论

1)根据一般集装箱办理站适箱货源少、去向分散、大多要在前方技术站进行改编作业的特点，并考虑走行时间不确定对需求时间窗的影响，建立了基于技术站改编作业的集装箱空箱调运鲁棒优化模型。

2)利用等价变换和对偶变换将空箱调运鲁棒优化模型目标中的组合优化部分转换成了线性函数，转换后的模型与原来的模型模型相比，仅多了1个连续变量，且没有增加新的约束条件，因此，极大地简化了计算难度。

3)算例表明了模型的正确性和有效性。在最优方案中，由于充分考虑到不确定走行时间、空箱改编时间和集结时间的影响，将这些成本降到了最低(共3 158元)，仅占总成本的1/4。且不确定走行时间的个数p的上界仅为6。

参考文献：

[1] Li Ling, Wang Bin. Enhancing green supply chain initiatives via empty container reuse[J]. Transportation Research Part E, 2014(70):190-204.

[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] Long Y, Chew E P, Lee L H. Sample average approximation under non-i.i.d. sampling for stochastic empty container repositioning problem[J]. OR Spectrum, 2015, 37(2): 389-405.

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

YAN Haifeng, DONG Shouqing. Optimization of the empty containers distribution among railway network container freight stations[J]. China Railway Science, 2009,30(1): 131-135.

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

ZHU Dehui, HE Shiwei. Optimization model of railway empty tank container allocation and genetic simulated annealing algorithm[J]. China Railway Science, 2008, 29(6): 104-110.

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

ZHANG Dezhi, XIE Ruhe, HUANG Xiaozhang. Dispatch model and solution algorithm of railway empty container[J]. China Railway Science, 2003,24(3):125-129.

[7] 段刚,李引珍,田丽娜,等.基于技术站中转作业的集装箱空箱动态调运优化模型与算法[J].交通运输系统工程与信息,2012,12(2):111-118.

DUAN Gang, LI Yingzhen, TIAN Lina, 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.

[8] Bertsimas D, Sim M. The price of robustness[J]. Operations Research, 2004, 52 (1):35-53.

[9] 段刚,陈莉,李引珍，等.基于鲁棒软时间窗的铁路集装箱空箱调运优化研究[J]. 铁道学报,2015,37(9):8-16.

DUAN Gang, CHEN Li, LI Yingzhen, et al. Optimization on railway empty container allocation with robust soft time window[J]. Journal of the China Railway Society, 2015,37(9):8-16.

[10] 李引珍.管理运筹学[M].北京：科学出版社,2012.

LI Yingzhen. Management operations research[M]. Beijing: Science Press, 2012.

(编辑阳丽霞)

Robust optimization on railway empty container allocation under reclassifying operationLI Yongjun1, DUAN Gang2, CHEN Li1, TIAN Lina1, SU Wanghui1

(1. Department of Mathematics, Lanzhou City University, Lanzhou 730070, China;2. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China)

Abstract:Taking the impact of reclassifying time and transport time on the time window of demand into consideration for common container terminal, an empty container allocation model based on reclassifying operation in technique station is proposed for minimizing the sum of reclassifying cost, transport cost, accumulation cost and inventory cost for early arriving or loss cost for delaying and subjects to container operating ability and routing transport ability, According to the uncertain transport time, a robust soft time window model of combinatorial optimization is proposed. Equivalent transformation and dual transformation methods were used to simplify the robust soft time window model to a linear programming one A robust optimization of empty container allocation with reclassifying operation in technique station was constructed for transforming it to integer linear programming model. A numerical example demonstrates that the model is simple and effective for improving the efficiency of railway container transportation.

Key words:railway transportation; optimization; robust soft time window; empty container allocation; reclassifying operation; uncertain transportation time

中图分类号：U292; U294

文献标志码：A

文章编号：1672-7029(2016)03-0583-07

通讯作者：段刚(1977-)，男，吉林吉林人，副教授，博士，从事交通运输系统分析研究；E-mail：dg_77@163.com

基金项目：国家自然科学基金资助项目(11261027，61364026)；甘肃省财政厅基本科研业务费资助项目(213060)；兰州交通大学青年科学研究基金资助项目(2011020)；兰州城市学院校长科研创新基金资助项目(LZCU-XZ2014-05)

收稿日期：2015-08-06