基于最短距离优先的集装箱空箱调度优化算法

田昌彪， 王晓峰

(上海海事大学 信息工程学院，上海 201306)

0 引 言

由于集装箱具有运输量大、便于机械化操作、能减少物品破损等优点，世界海运货物的集装箱化已成为不可阻挡的发展趋势.然而由于国际贸易不平衡及集装箱管理等方面的原因，每天都有大量的集装箱空箱由箱源充裕地区运往箱源匮乏地区，随即产生集装箱空箱调运问题.

对经济危机下的船公司来讲，一个好的空箱调度算法不仅能降低成本、提高经济效益，而且能提高运输设备的利用率、改善服务质量.同时，空箱最优化问题的本身就是对资源的最优化配置，解决一类问题，就可以解决很大一部分相似资源的最优化配置问题.

国内外学者对空箱调度问题进行大量研究，取得一系列成果，为实际运营过程提供有益的参考.施欣[1-2]对海上集装箱空箱调运过程进行分析，建立系统优化模型；刘恒江[3-4]把航线经营人作为主体，建立空箱调运的Petri网模型；周红梅等[5]借鉴铁路空车调度优化模型，建立海运空箱调运优化模型；刘建军等[6]基于广义费用目标函数提出从港口到货主企业间不同运输方式的集装箱组织优化模型.武振业等[7]建立需求不确定的海运集装箱路径随机规划模型.国外研究方面，FLOREZ[8]建立利润优化模型研究远洋航运企业空箱租赁和重新配置问题；SHEN等[9]构建海运空箱调运决策支持系统；WHITE等[10]通过构造一个空间-时间模型描述现实中的集装箱空箱调运问题；CHOONG等[11]建立以美国五大湖区为实际调运背景的空箱多式联运调运整数规划模型，分析规划周期长短对多式联运中空箱管理的影响；JULA等[12]建立线性规划模型解决洛杉矶/长滩复合港的交通拥挤问题，并提出线性规划问题的求解方法和优化解.然而这些研究在建立模型时进行大量假设，与实际系统相差较远.本文拟在考虑多箱种的情况下，结合大型船公司的实际情况，提出新的空箱调度优化算法，并运用实验进行验证.

1 建立模型

1.1 模型假定

假定港口运输网络中一共有U个港口，其中m个港口多余空箱，n个港口缺少空箱.模型用到的变量：设X(k,i,j,t)表示时刻t空箱经船k由多箱港口i调往缺箱港口j的空箱量，其中，k=1,2,…,K，i=1,2,…,U，j=1,2,…,U，t=1,2,…,T；T(k,i,j,t)表示时刻t空箱经船k由多箱港口i调往缺箱港口j的时间；D(k,i,j,t)表示时刻t经船k由多箱港口i调往缺箱港口j的距离；Z(k,i,j,t)表示时刻t经船k从港口i运往港口j的重箱量；O(i,t)表示租箱量；Q(i,t)表示空箱存量；Ti(i,t)表示堆场存放时间；Tr(i,t)表示租箱时间.

模型用到的参数：C(k,i,j,t)表示时刻t经船k由多箱港口i调往缺箱港口j的单位空箱单位距离运输成本；Y(k,i)表示船k运输能力限制；Ch(i,t)表示单位空箱装卸成本；Cr(i,t)表示单位空箱单位时间的租箱费率；Ci(i,t)表示单位空箱单位时间的存箱成本；T表示整个空箱调度的周期，为常数；K表示船舶数量；N表示箱型数量.

1.2 数学模型

空箱调度成本一般包括牵引成本、维修成本、管理成本、托运成本、空箱装卸成本、运输成本、堆场成本、租箱成本等.为简化模型，只考虑空箱装卸成本、运输成本、堆场成本、租箱成本.

空箱装卸成本=调箱量×单位空箱装卸成本=

(1)

运输成本=调箱量×经过的距离×单位空箱单位距离运输成本=

(2)

堆场成本=空箱存量×单位空箱单位时间的堆场成本×堆场存放时间=

(3)

(4)

因此，航线成本最小化的目标函数为

(5)

判定某一确定缺箱港口与某一确定多箱港口之间选择空箱调度的方法：单位空箱装卸成本+单位空箱调运成本+单位空箱堆场成本<单位租箱成本，则调箱，即

Ch(i,t)+D(k,i,j,t)·C(k,i,j,t)+

Ci(i,t)·Ti(i,t)

约束函数为

X(k,i,j,t)+Z(k,i,j,t)≤Y(k,i)[13]

(6)

T(k,i,j,t)+Ti(i,t)≤T

(7)

(8)

式(6)表示空箱量和重箱量应小于船舶的最大装载量；式(7)表示空箱调运时间和占用堆场时间之和在调度期限之内；式(8)表示空箱调运量小于空箱的总存量.

2 调度算法

国内大型船公司的箱管部门一般按照人工经验[14]调度空箱，目前以最短距离优先调度为主，即把多余的空箱运输到距离最近的缺箱港口，从而实现时间最少、距离最短，达到节约成本的目的.

2.1 最短距离优先调度

距离是指两物体在空间或时间上相隔的长度.最短距离优先是指在空箱调度过程中总是优先调度距离缺箱港口最近的多箱港口的空箱.距离最近的两个港口之间实现空箱最优调度，不仅能减少运输成本和运输时间，还能有效提高运营效率.

将任意两港口之间的实际距离表示成矩阵，调度时只需在距离最近的两个港口之间进行按需分配即可实现最短距离优先调度.为叙述方便，给出32个港口的分布，见图1.

图1港口分布网络

为实现空箱调度成本的最低化，需要已知各港口之间的距离和各个港口对应空箱箱型的数量.

式中:dij表示港口i与港口j之间的距离，1≤i,j≤v.

式中:aij表示港口i，箱型为j的集装箱空箱数量(1≤i≤v,1≤j≤N),正负分别表示可供应或需求的空箱数目，0表示不缺少也不多余，但并不代表该港口一个空箱都没有，只表示该港口空箱只能满足自身的需要而且不能提供多余的空箱.假设f表示空箱最短距离优先调运函数，其中有2个参数D和A.{aij|i=1,2,…,v}表示各港口某一箱型j的空箱数量，数组S存储多箱港口的编号，数组E存储缺箱港口的编号,s表示多箱港口编号，e表示缺箱港口编号，算法步骤如下：

步骤1将箱型为1的各港口的空箱数量存入{ai1}数组.

步骤2将{ai1}中大于0的港口编号存入数组S，小于0的港口编号存入数组E.

步骤3找出{dij|i∈S,j∈E}的最小值，并把多箱港口编号赋值给s，缺箱港口编号赋值给e.

步骤4判断as1和ae1绝对值的大小，修改{ai1}，打印出s，e，该箱型空箱的数目.

步骤5判断数组S或E是否为空.若否，则执行步骤2；若是，跳出循环，执行步骤6.

步骤6将箱型加1，执行循环，直至N.

2.2 穷举路径

空间距离最短的两个港口之间往往有很多条路径，要求得成本最低的路径，需要穷举路径，从中择优.实际最短距离路径有时未必是最优路径，成本最低的路径才是最优路径，因此需要穷举路径以决定空箱调度方案.若图1中的2号港口多余很多空箱，4号缺少很多空箱，而且也满足最短距离的条件，但如果2号港口常年出口货物到4号港口，这时2号港口的空箱通过L001航线运输到4号港口就会大大增加成本，而一般的解决办法就是穷举路径.2号港口到4号港口的直达线路L001成本高，就可以取2号港口运输到12号港口、12号港口运输到4号港口的路径，或是其他的穷举出来的成本更低的路径.

尽管空箱调度一般需要几次中转才能到达目的港口，但也是有限制的.随着中转港口增多，中转过程的装卸费用、运输成本会大大增加.一般中转次数不超过一个固定的常数.此处只给出中转3次以内的穷举路径算法.设F表示穷举路径函数，其中有3个参数：多箱港口编号s，缺箱港口编号e，航线L；m1表示中转港口编号，m2表示另一中转港口编号.具体算法如下.

步骤1判断港口s和e是否在同一航线上.是则执行步骤2，否则执行步骤3.

步骤2查航线表L，将港口s与e之间的时间和距离累加.根据距离计算运输费用，装卸费用按1次计算，堆场费用为0，租箱费用已知，生成结果集.

步骤3在港口s所在的航线上找中转港口m1及m1所在的航线，判断m1与e是否在同一航线上.是则执行步骤4，否则执行步骤5.

步骤4分别查航线表，将港口s与m1，m1与e之间的时间和距离累加.根据距离计算运输费用，装卸费用按2次计算，按航期表计算堆场时间，得出堆场费用，租箱费用已知，生成结果集.

步骤5在m1所在的航线上再找一中转港口m2及m2所在的航线，判断m2与e是否在同一航线上,是则执行步骤6，否则放弃.

步骤6分别查航线表，将s与m1，m1与m2，m2与e之间的时间和距离累加.根据距离计算运输费用，装卸费用按3次计算，按航期表计算堆场时间，得出堆场费用，租箱费用已知，生成结果集.

步骤7将结果集按成本进行排序并输出.

2.3 堆场时间计算和配船方案

对于某一固定的班轮，基本上有固定的挂靠时刻和挂靠港口，用一个固定的航期表表示.船期表中所列项目包括港口编号、上一港口到下一港口的时间和距离.

假定A和B是同一时刻某航线上两端的港口，i和j表示需要进行空箱调度的两个港口，i表示起始港口，j表示终点港口，若A→B,B→A方向上各有一班轮，设初始时刻为0，班轮周期为T1.用tij表示i到j所用的时间.

(1)如果i和j都在AB航线上，则：A→B方向，船舶到i的所有时刻ti=tAi+K1T1，K1=0,1,2，…；B→A方向，船舶到i的所有时刻ti=tBi+K1T1，K1=0,1,2，….查船期表，将时间字段和距离字段相加可得i到j所需要的总时间tij和总距离，由于不经过中转，堆场时间为0，把完整的装一次、卸一次看作装卸一次，用成本分析就可算得装卸成本、运输成本、堆场成本.配船方案为AB航线的(K1+1)航次.

(2)如果i和j不在同一航线上，并且两航线有共同港口M，i在AB航线上，j在CD航线上，且初始时刻都为0，AB航线的周期为T1，CD航线的周期为T2，则：A→B方向，船舶到i的所有时刻ti=tAi+K1T1，K1=0,1,2，…；C→D方向，船舶到j的所有时刻tj=tCj+K2T2，K2=0,1,2，…；由i到j所需要的时间t=tj-ti=tCj-tAi+K2T2-K1T1.船舶运输时间tiM+tMj.堆场堆放时间tAM+K2T2-tCM-K1T1(≥0).配船方案为AB航线的(K1+1)航次，和CD航线的(K2+1)航次.

3 实 验

表1 各航线的船期表

3.1 实验步骤

假定一个有32个港口、7条航线的港口运输网络，见图1.对某一特定类型的空箱，1号港口缺少100个，2号港口多余400个，3号港口缺少100个，4号港口多余50个，7号港口缺少100个，12号港口缺少80个，25号港口缺少70个，其他港口空箱数目为0.其中部分航线的船期见表1.

为简述方便，中转费用常数假定为4，单位距离运输费用为5，单位空箱单位时间堆场费用为1，租箱费用为65.

3.2 实验结果

表2 最短距离优先调度结果

第一步给出以最短距离优先的某一箱型的调度结果，包括起始港口和目的港口及需运输的空箱数量，见表2.

确定起始港口为2号港口、目的港口为7号港口后，计算出排序后2号港口到7号港口的穷举3次中转限制内的路径结果集合，见表3.

3.3 结果分析

当单位租箱成本小于单位空箱调度成本时，选择租箱，否则选择空箱调度.如，表5中第1条路径空箱调度比较划算，而其他7条选择租箱比较划算.

与以人工经验调度为主的空箱调度比较，该算法按距离远近给出调度先后顺序，能有效给出空箱调度优化路径，并按成本大小排序，同时对是否租箱给出辅助决策.

结果不仅可以按照成本排序，还可以按照时间进行排序，得出空箱调运最短时间调运方案.

由于空箱调运系统复杂，根据单一的排序后的成本或时间空箱调运方案，并不能得出最优方案，二者不可兼得，最终还需要箱管部门结合其他因素制订空箱调度计划.

4 总结和展望

该空箱调度算法不仅能有效给出空箱调度最优路径，而且对是否租箱给出辅助决策，使空箱调度变得有章可循.与实际人工经验调度比较，该算法能简化调度过程、提高调度效率.

该算法适用于航线较多的情况，但对实际中特定的情况并不适用.比如，对于同样是出口为主的港口上海港和宁波港，基本上没有空箱调运，该方法失效.为更好地应用，还需要进一步改进算法.

表3 穷举3次中转限制内的路径结果

参考文献：

[1] 施欣. 集装箱海运空箱调运优化分析[J]. 系统工程理论与实践, 2003, 4(4): 70-76.

[2] 施欣. 基于Petri网的航运业务流程的仿真优化[J]. 系统仿真学报, 2001, 11(6): 767-780.

[3] 刘恒江. 集装箱空箱调运分析[J]. 集装箱化, 2001, 12(10): 11-13

[4] 刘恒江. 集装箱空箱调运Petri网模型仿真分析[D]. 上海: 上海海运学院, 2002.

[5] 周红梅, 方芳. 航运集装箱空箱调运优化模型的研究[J]. 武汉理工大学学报: 交通科学与工程版, 2003(3): 384-387.

[6] 刘建军, 杨浩. 港口枢纽集装箱运输的组织优化研究[J]. 土木工程学报, 2004, 37(10): 99-103.

[7] 武振业, 宋天生, 赵柯. 海运集装箱运输路径选择[J]. 西南交通大学学报, 2006, 41(3): 269-272.

[8] FLOREZ H. Empty container repositioning and leasing:an optimization model[D]. New York: Polytechnic Institute of New York, 1986.

[9] SHEN W S, KHONG C M. A DSS for empty container distribution planning[J]. Decision Support System, 1955, 15(1): 75-82.

[10] WHITE W W，BOMBERAWLT A M. A network algorithm for empty freight car allocation[J]. IBM System J, 1969, 15(2): 147-169.

[11] CHOONG S T, COLE M H, KUTANOGLU E. Empty container management for intermodal transportation networks[J]. Transportation Res Part E: Logistics & Transportation Rev, 2002, 38(6): 423-438.

[12] JULA H, CHASSIAKOS A, IOANNOU P. Port dynamic empty container reuse[J]. Transportation Res Part E: Logistics & Transportation Rev, 2006, 42(1): 43-60.

[13] 刘大镕, 贺斌, 蒋良奎, 等. 随机(单箱种)陆上空箱调运模型[J]. 上海海运学院学报, 2000, 21(3): 8-18.

[14] 杨洋. 班轮公司空箱合作调运优化模型[J]. 上海海事大学学报, 2010, 31(3): 68-73.