跨区域远洋航线空集装箱动态调运优化模型

芦立华 ，张恒振 ，王晓峰

1.复旦大学 计算机科学技术学院，上海市智能信息处理重点实验室，上海 200433

2.上海电机学院 电子信息学院，上海 201306

3.上海海事大学 信息工程学院，上海 201306

1 引言

近年来，随着全球一体化进程的发展，国际贸易快速增长，集装箱运输在国际运输体系，尤其是海上运输体系中的地位日益增高。据不完全统计，2013年国际贸易货物运输总量中，77%的货物是通过海运完成的，而海运中超过23.7%以上的货物又是通过集装箱运输的[1]。另外，由于世界经济发展的不平衡以及国家间进出口贸易的差异，导致了在集装箱导入国的各个港口（多箱港）集聚了大量的空集装箱，如欧洲和美洲区域的港口。与此同时，在集装箱导出国的各个港口（需箱港）又急需大量的空集装箱，如东南亚区域的港口。以太平洋航线为例：2013年从亚洲到北美运输的货物量大约为13.3百万TEUs（20尺标准箱），而从北美到亚洲仅运送了6.9百万TEUs货物[1]。

此外，据不完全统计，每年全球集装箱空箱调运量占全部集装箱总运量的20%左右，部分航线空箱调运的比率甚至接近50%。巨大的空箱调运费用、存储费用和租借费用大大降低了航运企业的利润，甚至进一步威胁到其在航运企业的生存状况。因此，为增加市场竞争力，对空集装箱进行合理调运和优化管理越来越成为各个航运企业亟待解决的问题。

通常说来，一个大型的航运企业经营多条航线，其中包括远洋航线和近洋航线。前者一般指跨越大洋连接两个或多个大洲的航线，后者一般指距离较短的近陆港口间的海上运输航线，包括内河航线、和邻近国家间航线。远洋航线和近洋航线又通过枢纽港（hub port）和支线港（feed port）交织形成了一个复杂的航运网络。如何针对这两种航线进行空箱调运优化操作是本文研究的关键问题。

2 相关研究

国内外学者对于集装箱空箱调运问题进行了诸多研究，主要集中在两个方面：一方面主要是基于建立港口空集装箱安全库存管理体系[2-4]，另一方面则主要是利用动态网络方法进行集装箱空箱调运优化研究[5-7]。施欣[8]通过对集装箱海上空箱调运过程的剖析，建立了相应的系统优化模型。Cheung和Chen[9]建立了海上空箱调运的两阶段随机优化模型，第一阶段是多箱港口可提供的空集装箱数量、需箱港口需要的空集装箱数量和船舶可装载集装箱量等诸多参数是确定的；第二阶段则将上述这些参数看作是随机变量，然后在此基础上建立优化模型。Lam[10]提出了在操作层面上的近似动态集装箱空箱调运优化方法，并且根据航运公司实际航线网络，将通用网络技术应用到航运业中。Meng和Wang[11]融合中心辐射模式和多港直靠模式，设计航线服务网络和开发混合整数线性规划模型。Crainic等[12]研究了空集装箱的动态随机分配问题，并将长期租箱问题作为其中的要素加以考虑。Li等[2]从减少空箱调运的数量这个角度出发，研究了港口间的空箱调运问题。石玉峰[13]采用随机机会约束规划方法建立战时运输路径优化模型，设计了基于随机模型获取适应度的遗传算法求解问题。综合考虑航运公司战略层、策略层和操作层运营规划，Song和Dong[14]提出了综合远洋班轮航线设计、船舶部署和空集装箱调运三层次的最小成本优化模型。Long等[15]从集装箱供需不确定性的角度出发设计了一个两阶段随机规划模型，目标是优化集装箱空箱调运成本。Song和Dong[16]在多航线、多船舶部署和多班轮航次，整体规划重箱运输线路和空箱调运，以达到相关运营成本最小。

传统的研究主要集中在将港口划分为多箱港和需箱港，调度计划在港口-港口间这种点-点的模式下发生，因此存在如下三个问题：（1）集装箱调运计划往往是提前制定的，由于远洋航线距离较长，船舶离开多箱区域始发港，到达需箱区域目的港时，需箱区域各个港口需箱量或多箱量都发生了较大变化，这种计划调运和实施调运的不同步性直接导致调运成本剧增和调运效率低下。（2）传统的港口-港口的调运计划，受港口业务波动影响较大，进而产生了相应的存储成本和租赁成本。（3）大量的决策变量和无用的约束条件，导致模型复杂，优化求解时间较长。

集装箱空箱调运计划是建立在对未来某时期内需箱港口需箱量预测的基础上的。如果计划周期过长往往导致计划供需和实际供需之间波动较大，这样制定的调运计划往往有诸多弊端，产生的经济效益会大打折扣。因此，本文针对计划供需和实际供需时间的不同步性，根据港口历史数据和经济形势判断，设立港口安全库存量，由于该部分不在本文讨论的范围，因此在文中假设安全库存量为一个给定的值。其次，由于航运公司在某港口集装箱量是动态变化的，因此，建立了一个周期的跨区域远洋航线空箱动态调运优化模型。和以往研究者重点研究港口-港口之间调运优化模型不同，该模型是基于连接两个区域的远洋航线空箱调运计划。该模型将调运计划分为两个部分：第一部分是建立在区域之间一个与货物流相反的空箱调运流，即基于宏观区域调运，这样可以使得空箱调运受微观港口变化影响较小。第二部分建立动态调运优化模型，将调运计划分为两阶段。第一阶段制定调出计划，此时根据需箱区域的需箱量，利用成本优化算法计算调出港口的空箱数量，只确定调往的需箱区域，不确定具体卸载空箱的需箱港口。第二阶段，当班轮抵达需箱区域后，再根据各港口的需箱量利用成本最小算法做具体的分配计划。经过这两个阶段的处理，可以在一定程度上消除计划供需和实际供需时间上不同步带来的供需不一致问题，从而降低相应的租赁成本和存储成本。

3 集装箱空箱调运优化模型

3.1 问题描述

集装箱班轮运输是按事先制定的航线和船期表进行运营且短期内不发生变化的运输形式。远洋班轮一般为一周发一班。通常说来，3~6个月可能根据季节业务变化进行一些调整。一条航线由多个港口挂靠序列组成，航运网络由港口和航线组成。由于空箱调运问题牵涉的因素较多，如港口繁忙程度、船舶在航线上的部署情况、班轮装载量因子、班轮在港口挂靠时装卸集装箱情况、班轮重箱装载问题等等。因此该问题是一个典型的且复杂的优化问题[17]。

为便于建立优化模型，文中抽取了直接影响空箱调运的主要因素如下：

（1）港口集装箱的供给量和需求量。其中，供给主要包括客户还箱量、调入港口的集装箱量和租借集装箱量。当客户还箱量加上库存箱量和调入箱量均无法满足客户用箱需求量时，班轮公司采用租箱策略，即向集装箱租赁公司租借集装箱以满足用箱需求。需求主要是指客户需要租赁班轮公司的空集装箱来装载货物。

（2）调运费用。主要包括空箱装卸费用和运输费用。

（3）航线。航运网络中所有可以用来调运空箱的航线。

（4）安全库存。指航运公司在一个港口预先存储一定的空集装箱，以满足客户的用箱需求。文中在计算港口空箱多箱量的时候指的是空集装箱净多箱量，即已经考虑了安全库存之后的值。同样在计算港口需箱量的时候也是指空箱净需箱量。

（5）地理区域。根据航运企业远洋航线设计和贸易情况，文中把全球划分成几个重要的经济区域，包括东南亚区域（需箱区域）、欧洲区域（多箱区域）、北美区域（多箱区域）等。不失一般性地，由于贸易不平衡，多箱区域和需箱区域短期内其状态不会发生变化。文中的区域主要指地理位置上所属的经济区域，跨区域航线指的就是跨越上述两个区域的远洋航线。

（6）船舶可用舱位。因为空箱运输不会直接带来经济收益，因此利用船舶装载重箱之后所余的舱位进行空箱调运，以此降低调运成本。

本文设计了一个时间-空间网络模型来模拟跨区域空箱调运问题，如图1所示。图1表示两个区域K1和K2间的集装箱流，包括三条航线L1，L2，和L3。其中，L1是跨区域的航线，即远洋航线，部署在L1航线上的班轮在K1区域内依次挂靠A港、B港和C港，装载从K1区域调运的空集装箱进入区域K2，在K2内分别挂靠D港、E港和F港。从K1区域各港口调运的空集装箱根据K2区域实时需求分配到各个挂靠港口，班轮挂靠F港后再次返回K1区域的A港，重复此过程。L2和L3是区域内航线，即近洋航线，分别在K1和K2区域内循环航行，可以分别在K1和K2区域内进行空箱调运。由于区域内航线时间短，挂靠港口的频率较高，相应的费用也比较低，一般跨区域航线和区域内航线都能进行调运的情况下，优先选用区域内航线。如：从A港到B港的调运，既可以选择L1航线，也可以选择L2航线，此时后者优先。

3.2 模型假设

图1 两个区域（K1和K2）间的集装箱调运流

由于班轮公司进行集装箱空箱调运过程中，影响其调运决策的因素很多，为了简化问题，并最大限度地和实际运输业务相一致，文中对该模型作如下假设。模型内（包括租箱）所有集装箱大小尺寸相同，即，只考虑单一箱型，如20英尺箱。其他尺寸的箱型可以转化为20英尺的标准箱。如果自有集装箱不能满足需求，可以使用租赁策略且没有数量限制。任何港口在任何时刻存储集装箱的能力不受限制。多箱港口可以提供的可用空集装箱数量和需箱港口所需要的空集装箱数量都是满足本港口集装箱保有量的前提下给出的，即净需求或净供给。航线和船期是事先给定的。

3.3 模型参数

3.3.1 参数

gt,i,k：t周期内K区域内港口i空集装箱供给量。

ht,i,k：t周期内K区域内港口i空集装箱需求量。

i,j,l：港口标识符，i,j,l∈{1,2,…,P}，P是港口编号，其中，i,l∈K1，j∈K2。

t：周期，t∈{1,2,…,T}，T表示计划周期的长度。

k：港口所在的区域，k∈{1,2,…,Q}，Q是区域编号。

3.3.2 决策变量

ut,i：t周期内港口i卸载的集装箱数量。

wt,i：t周期内港口i装载的集装箱数量。

xt,i,j：t周期内从港口i到港口j运输集装箱数量。

yt,i：t周期内港口i存储集装箱数量。

zt,i：t周期内港口i租借集装箱数量。

3.4 数学模型

目标函数（1）包含两部分：Ct和Ct+1。其中，第一项表示在t周期内发生的费用，包括装载费用、区域内的运输费用和未调出的空集装箱的存储费用。Ct+1表示t+1周期内发生的费用，包括卸载费用、跨区域的运输费用、多余空集装箱的存储费用和通过调箱仍不能得到满足的空箱量而产生的租箱费用。

约束条件（2）表示多箱区域跨区运出的空集装箱量之和等于多箱区域各个港口装载的空集装箱量之和。约束条件（3）表示多箱区域内多箱港口多余的集装箱量之和等于调出的箱量和本地存储箱量之和。此约束确保集装箱总量保持不变。约束（4）保证t+1周期内港口i库存空集装箱量等于t周期内库存的空集装箱量加上t+1时间段内卸载的集装箱量（或者减去装载的空集装箱量）再加上租借的集装箱量和客户归还的集装箱量。约束（5）保证在t+1周期内，港口i装载的空集装箱量小于可利用的集装箱量。

3.5 远洋跨区域动态空箱调运算法

本节给出跨区域远洋航运动态空箱调运算法，其伪码如算法1所示。其中，第6行的第二项表示t周期的运输费用，这个阶段计算的运输费用是指从空箱装载港口到离开多箱区域K1的最后一个港口之间所发生的运输费用。如果空箱装载港口是多箱区域的最后一个港口，则运输费用为0。

算法1远洋跨区域动态空箱调运算法

第19行表示从K1区域调运的空箱量大于K2区域的需箱港口的需箱量之和。在这种情况下，跨区域调运的集装箱量大于新的需求，但是根据实际业务情况考虑，不可能再将多余的空集装箱返航调回，只能选择在需箱区域的各个港口进行卸载。本文对这些多余空箱分配策略采用的是：在满足重箱运载需求的情况下，将多余的空箱尽量卸载到成本最小的港口。

第20行的第二项表示运输费用，这里的运输费用是指从离开K1区域最后一个港口到空集装箱卸载港口之间发生的运输费用，也就是第二阶段的运输费用。第三项表示存储费用，它包含两部分，第一部分是从K1区域到K2区域多调的空箱所产生的存储费用，第二部分是指表示K2区域内多箱港口多出的空箱所产生的存储费用。

第21行表示所有港口存储的集装箱量等于从K1区域到K2区域多调的空箱量Trans-N′t+1,k2和K2区域内多箱港口多出的空箱量Nt+1,k2之和。

第23行表示K1区域调运的空集装箱量与K2区域内多箱港口多余的空集装箱之和小于K2区域需箱港口的需箱量，也就是不管区域间调运还是区域内调运都不能满足用箱需求，这种情况下就必须通过租箱来满足客户需求。

第28行表示K1区域调运的空集装箱量与K2区域内多箱港口多的空集装箱之和大于K2区域需箱港口的需箱量。

4 实验与数据分析

实验模拟了远洋航线连接的两个主要经济区域的航运网络，包括跨区域远洋航线2条，区域内航线4条，分别属于K1区域和K2区域，港口9个。其中，4个港口属于K1区域内港口，5个属于K2区域内港口。

根据两个阶段可能发生的情况列举了六种不同供需关系下的情况，如表1所示。第一阶段存在两种情况，情况1：K1区域港口能够提供的空集装箱总量大于K2区域港口估计需要的空集装箱量，此时，调运量等于K2区域港口的估计需求量。情况2：K1区域港口能够提供的空集装箱总量小于K2区域港口估计需要的空集装箱量，此时，调运量等于K1区域港口的供给量。第二阶段存在三种可能发生的情况，情况1：从K1区域运输到K2区域的集装箱量大于K2区域需箱港口实际需求量。情况2：从K1区域运输到k2区域的集装箱量小于K2区域需箱港口实际需求量，并且K2区域多箱港口调运仍然不能满足K2区域需箱港口的需要，K2需箱港口需要租箱。情况3：从K1区域运输到K2区域的集装箱量小于K2区域需箱港口实际需求量，但是K2区域多箱港口调运能够满足K2区域需箱港口的需要，K2需箱港口不需要租箱。将上述两个阶段的五种情况进行组合得出表1中的六种情况（case）。

本文利用CPLEX12.6求解数学模型，运行环境为win7 64位操作系统，Intel®CoreTM2 i5-2400 CPU，3.1 GHz，4 GB内存。经过实验表明，该算法的运行时间是秒级的，故而本文没有进行时间复杂度分析。

4.1 与传统的港口-港口模型对比（ECR-TM）

表1 两阶段供需关系情况细分图

基于表1的六种情况，将文中提出的ECR-RDM与ECR-TM进行了比较，在两个模型中，每个港口需箱量和多箱量、经t周期时间变化后每个港口多箱量或需箱量、每个港口存储成本、租箱成本、装载成本、卸载成本、港口间的运输费用、调运数量等数据均相同，实验结果如表2所示。

表2 跨区域动态空箱调运优化模型与传统港口-港口空箱调运优化模型各成本对比表

容易发现，ECR-RDM总营运成本明显低于ECR-TM，成本相差最大的是Case 4，大约节省29.3%的成本，成本相差最小的是Case 5，节省成本约11%。从租箱数量看，ECR-RDM的优势明显优于ECR-TM，其中对于Case 1两者差距最大，ECR-TM租箱数量占调运数量的20%，而ECR-RDM则无需租箱。这在一定程度上说明ECR-RDM可以加快航运公司自有空箱的周转率。在Case 5中，K2区域港口需箱港口总需箱量为2 509 TEU，从K1区域调运为1 904 TEU，K2区域多箱港口调运为180 TEU，租箱量为425 TEU，调运成本为75 434，租箱成本为25 500，在不考虑存储成本和季节变化的情况下，平均每个TEU租箱成本是调运成本的1.67倍，如果考虑存储成本和季节变化因素，租箱成本将是调运成本的2倍以上，因为在多箱港口由于存储仓库属于紧缺资源，一般存储费用比较高。而且在需箱高峰季节，比如圣诞节之前月份，东南亚很多出口为主的港口需箱量比较大，导致空集装箱成为紧缺资源，租箱成本也会大幅上涨。

通过对两模型六个情况比较，总结ECR-RDM优于ECR-TM的方面：

（1）ECR-RDM是基于港口集合-港口集合的，而ECR-TM是港口点-港口点模型，由于远洋航线周期比较长，计划调运开始到计划实施结束周期较长，港口用箱情况变化波动较大，ECR-RDM中港口集合内部会相互消除一些变化，导致总成本开销要比ECR-TM节省。

（2）ECR-RDM是调运开始时只确定调往区域，不确定调往的具体港口，到了目标区域后，再根据目标区域的用箱情况优化分配空箱，这样优化比ECR-TM更加贴合实际业务中用箱需求，调运计划更加高效，从表2可以看出，ECR-RDM减少很多租箱，从而使得租箱费用大大降低。

4.2 费用组成分析

表3中列举了ECR-RDM方法中各项成本在总成本中的权重，其中每一行代表表1中的一个case，列表示某项成本在这个case中总成本所占的比例。

表3 ECR-RDM各项成本在集装箱调运总成本所占比例 %

实验表明，在总成本中，所占比例最大是装卸成本，通常要达到总成本的50%，甚至高达65%，如case 4。其中，case 2和case 5除外，因为这两者空箱调运不足，要在需箱港口租借一些空集装箱，由于单位租箱成本较高，从而导致总租箱成本在总成本中所占比例达到25%左右。

此外，从表3可以看出，利用跨区域动态空箱调运策略已经使得运输成本和租箱成本达到最优，如果想进一步降低成本开销，可以从以下两方面出发：一是尽量减少装卸次数，即减少转运次数，在文中提出的模型中限制转运最多一次。二是从成本优化的角度，在满足业务需求的条件下，尽量在装卸成本较低的港口进行相应操作。对于case 1、case 2和case 3，他们的第一阶段情况相同，而第二阶段分为了三种不同情况，对比三个case发现运输成本与装卸成本成正比关系，运输费用、装载费用和卸载费用在总成本中的比例差距不大，最大不到5%。

5 结束语

班轮公司提高自有空箱周转率，减少短期租箱，对提高公司竞争力起着居住轻重的作用。本文主要在操作层面上提出了一个跨区域远洋航线空集装箱动态调运优化模型：ECR-RDM，并且对各种实际业务中可能发生的六种情况进行了实验和数据分析，而且将实验结果和传统的港口-港口的调运模型：ECR-TM进行了比较，结果显示ECR-RDM能够节省调运总成本11%~20%，大大减少了租箱。在实验中，通过分析ECR-RDM中各项成本在空箱调运总成本中所占的比例，发现在空箱相对宽裕的情况下，存储成本和租箱成本在总成本中所占的比例很小，而装载成本、卸载成本和运输成本各占总成本的1/3左右。但是在空箱紧缺的情况下，租箱成本要占总成本的1/4，如果需箱数量持续增加，租箱成本所占的比例也会相应增加。通过对这些数据进行分析，其结果可以为班轮公司在制定公司经营策略上提供决策支持。

[1]UNCTAD.Review of maritime transport[Z].United Nations Publication，2013.

[2]Li J A，Liu K，Leung S C H，et al.Empty container management in aport with long-run averagecriterion[J].Mathematical and Computer Modelling，2004，40（1/2）：85-100.

[3]Song D P.Characterizing optimal empty container reposition policy in periodic-review shuttle service systems[J].Journal of the Operational Research Society，2007，58（1）：122-133.

[4]Song D P，Earl C F.Optimal empty vehicle repositioning and fleeting-sizing for two-depot service systems[J].European Journal of Operational Research，2008，185（2）：760-777.

[5]Shintani K，Imai A，Nishimura E，et al.The container shipping network design problem with empty container repositioning[J].Transportation Research Part E，2007，43（1）：39-59.

[6]Liu X，Ye H Q，Yuan X M.A tactical planning model for liner shipping companies：managing container flow and ship deployment jointly[R].School of Business，National University of Singapore，2007.

[7]Erera A L，Morales J C，Savelsbergh M.Robust optimization for empty repositioning problems[J].Operations Research，2009，57（2）：468-483.

[8]施欣.集装箱海运空箱调度优化分析[J].系统工程理论与实践，2003，23（4）：70-75.

[9]Cheung R K，Chen C A.Two-stage stochastic network model and solution methods for the dynamic empty container allocation problem[J].Transportation Science，1998，32（2）：142-162.

[10]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.

[11]Meng Qiang，Wang Shuaiai.Liner shipping service network design with empty container repositioning[J].Transportation Research Part E：Logistics and Transportation Review，2011，47（5）：695-708.

[12]Crainic T G，Gendreau M，Dejax P.Dynamic and stochastic models for the allocation of empty containers[J].Operations Research，1993，41（1）：102-126.

[13]石玉峰.战时随机调运时间路径优化研究[J].系统工程理论与实践，2005，25（4）：133-136.

[14]Song Dongping，Dong Jingxin.Long-haul liner service route design with ship deployment and empty container repositioning[J].Transportation Research PartB，2013，55：188-211.

[15]Yin Long，Loo Hay Lee，Ek Peng Chew.The sample averageapproximation method forempty container repositioning with uncertainties[J].European Journal of Operational Research，2012，222（1）：65-75.

[16]Song Dongping，Dong Jingxin.Cargo routing and empty container repositioning in multiple shipping service routes[J].Transportation Research Part B，2012，46（10）：1556-1575.

[17]Meng Qiang，Wang Shuaian，Andersson H，et al.Containership routing and scheduling in liner shipping：overview and future research directions[J].Transportation Science，2014，48（2）：265-280.