基于GASA的带时间窗航运空箱调运模型

闵德权，孙海萍

(大连海事大学 交通运输工程学院，辽宁 大连 116026)

0 引 言

各个国家之间因经济、贸易、社会生产力发展的不平衡导致了世界范围内各个港口的集装箱分布不均。特别是受新冠疫情影响，许多国家的生产能力处于很低的水平，这让率先步入生产正轨的中国在短时间内成为了世界工厂的中心。在上海、宁波、青岛、连云港等大型港口中，集装箱严重短缺导致了船舶的延迟停泊，而在欧美国家的许多港口却因集装箱激增导致了货物运输的拥堵[1]。基于此，应通过合理的空箱调运，及时将集装箱过剩港口的空箱运往缺少集装箱的港口。这样不仅降低了集装箱空箱库存成本，提高了空箱、码头等资源的利用率；而且还及时满足了客户对集装箱的需求，降低了集装箱租赁成本和公司信誉损失。因此，研究空箱调运问题具有非常现实的意义。

目前，学界对航运集装箱空箱调运进行了大量研究。孙佳庆等[2]在尽量降低系统成本和重箱分配计划的前提下，对航运公司剩余的可用空箱和舱位进行集中分配；徐姗等[3]从航运公司角度出发，建立了考虑空箱调运的集装箱网络路径优化模型；WANG Hua等[4]在同时考虑船舶航线的最佳出发时刻表和货物分配方案的情况下，对空箱调运问题进行了研究；连峰等[5]根据集装箱投入使用的年限对集装箱生命周期进行了区分，并对班轮航线网络的空箱调运进行了优化；陈俊军等[6]在低碳背景下通过考虑空箱需求的不确定性，建立了港口空箱调运和航速的决策模型；计明军等[7]针对沿海港口之间的集装箱空箱调运问题，建立了以调运成本最小为目标的数学模型；A.G.WESPARP等[8]提出一种解决重、空集装箱调运问题的模糊优化方法；丁敏等[9]采用优化策略的启发式算法，计算了各港口的具体空箱调度方案； S.W.LAM等[10]利用优化模型给出了各港口空箱库存上下限来求解空箱调度问题，采用启发式算法求解以总成本最小化为目标的空箱调度优化模型；谢新连等[11]根据MDA分析法对特征变量重要性进行分析，建立了基于随机森林算法的预测模型，并以大连港为案例进行验证，得出随机森林算法对预测港口集装箱吞吐量准确性更高的结论；张欣等[12]研究了全球集装箱海运网络的脆弱性，运用复杂网络理论在分析海运网络拓扑结构特征的基础上，模拟了港口失效连锁反应。

综合以上研究可看出，这些学者在对航运集装箱空箱调运研究时，较少考虑因缺少集装箱港口时间窗造成的堆积成本和机会损失成本。基于此，笔者针对集装箱种类和运输方式的多样性，建立了以集装箱空箱调运成本为优化目标，带时间窗的航运集装箱空箱调运模型；采用改进遗传模拟退火算法(GASA)求解所建立的数学模型。引入模拟退火算法对遗传算法进行改进后，既保留了遗传算法全局搜索的特性，又提高了局部搜索能力，确保了搜寻结果是全局最优解，实现了航运集装箱的空箱调运最少成本方案。

1 模型构建

1.1 问题描述

假设在一个航运服务运输网络中，有n个港口需要k类集装箱空箱，有m个港口有多余的k类集装箱空箱。各集装箱需求港对集装箱到港时间有一定要求，当空箱过早到达目的港口时会产生一定的港口堆积成本；当空箱过晚到达目的港口时会影响信誉度进而损失部分客户，产生机会成本。笔者需要在有时间约束情况下制定出使总运输成本最少的航运集装箱空箱调运方案。

1.2 符号变量

1.3 目标函数建立

建立目标函数如式(1)～式(7)：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

目标函数式(1)由3部分组成，分别是不考虑时间约束的集装箱调运成本、因集装箱过早到达造成的集装箱港口堆积成本、集装箱过晚到达所产生的机会成本。在班轮运输中，班轮公司很少因延迟交货而对托运人进行补偿，但由于船舶到达的正点率低或频繁的延误交货，会影响船公司的服务水平和客户信誉度，从而损失一部分客户，影响其市场占有率，因此集装箱延期到达会产生机会成本。

式(2)中：t时段从港口i通过运输方式l运输k类集装箱到港口j的数量等于t时段港口j缺少k类集装箱的数量。

式(3)中：t时段港口i提供k类集装箱的数量不小于t时段从港口i通过运输方式l运输k类集装箱到港口j的数量。

式(4)中：t时段港口i对k类集装箱的供给量不超过t时段在港口i上k类集装箱的产量。

式(5)中：t时段港口i存储k类集装箱的数量不超过t时段港口i存储k类集装箱的能力。

式(6)中：t时段从港口i到港口j通过运输方式l运输k类集装箱的数量不超过t时段从港口i到港口j通过运输方式l对k类集装箱运输的最大运输数量。

式(7)中：t时段从港口i到港口j通过运输方式l运输第k类集装箱的数量不小于0。

2 算法求解

遗传算法是一种全局随机优化算法，适用于求解带有复杂多约束条件的数学模型。在优化目标函数时，可用更大的概率搜索全局最优解，它具有全局寻优和隐式并行的特性，但存在早熟收敛从而陷入局部最优解的弊端。模拟退火算法出发点是源于物理学中固体物质的退火过程，它能以一定概率跳出局部最优解，最终逼近全局最优解。该算法不仅能朝目标函数的优化方向迭代，还可以接受目标函数以一定概率的恶化，从而避免陷入局部最优解。但当搜索范围变大时，存在收敛速度慢、执行时间长、容易受参数影响等缺点。遗传模拟退火搜寻最优解过程如图1。

图1 遗传模拟退火搜寻最优解过程Fig. 1 Search process of optimal solution for GASA

笔者将遗传算法和模拟退火算法的优点相结合，在遗传算法中引入模拟退火，提出一种混合遗传模拟退火算法求解的集装箱空箱调运模型，将这两种算法的搜索能力得到相互补充，不仅提高了遗传算法的局部搜索能力，还避免了遗传算法陷入局部最优解，遗传模拟退火算法流程如图2。

图2 遗传模拟退火算法流程Fig. 2 Flow chart of GASA

2.1 初始种群

根据运输问题性质，笔者采用自然数编码产生初始可行解。用矩阵描述运输问题，分配矩阵如式(8)：

(8)

式中：Xp代表种群中第p个染色体矩阵；xij代表从港口i运输到港口j的集装箱数量。

将Xp的每行首尾相连，该个体的基因型可描述为如下串结构，即有：X′p=[x11,x12, …,x1j,x21,x22, …,x2j, …,xi1,xi2, …,xij]。考虑到由港口i运往港口j的k类集装箱和集装箱运输方式l不同，故将l和k插入到X′p中，即有：X″p=[x11,l,k,x12,l,k, …,x1j,l,k,x21,l,k,x22,l,k, …,x2j,l,k, …,xi1,l,k,xi2,l,k, …,xij,l,k]。

2.2 适应度函数

用目标函数值来评估染色体适应度大小，用eval(Xp)来表示染色体矩阵Xp的适应度函数值。故模型适应度函数可直接表达如式(9)：

(9)

2.3 约束条件处理

构造惩罚项，当满足约束条件时，惩罚项为0；当不满足约束条件时，加大惩罚，即加大不可行点处对应的目标函数值，使不可行点不能成为相应问题的最优解。不等式约束处理过程如图3，等式约束处理过程如图4。

图3 不等式约束处理过程流程Fig. 3 Flow chart of inequality constraint processing

图4 等式约束处理过程流程Fig. 4 Flow chart of equality constraint processing

2.4 交 叉

选择一个较优秀的个体(累加概率大于均值为0，方差σ2=1，标准差σ=1的正态分布的随机数)作为父亲和母亲，随机设置交叉点，然后在该点相互交换两个配对个体的部分染色体。交叉过程如图5。

图5 交叉过程Fig. 5 Cross process diagram

2.5 变 异

采用均匀变异且精英不参加的方法，分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各基因座上的原有基因值，变异流程如图6。

图6 变异流程Fig. 6 Variation flow chart

2.6 判 断

引入模拟退火判断是否变异。计算变异后的 种群适应度与变异前的适应度差值ε，若变异后的种群适应度优于变异前的种群适应度，则接受变异；若变异后的种群适应度劣于变异前的种群适应度，则以一定的退火概率exp(ε/T)来确定是否发生变异，退火流程如图7。

图7 退火流程Fig. 7 Annealing flow chart

3 算 例

设某航运运输网络有12个港口，其中6个港口有多余集装箱，6个港口缺少集装箱；现通过一般海运(L1)、海铁联运(L2)这两种运输方式进行空箱调运。假设各港口之间不管采用哪种运输方式，运输天数都一样，且船舶运输集装箱空箱数量不超过30 TEU。提前到达目的港口所产生的堆积费用为每个集装箱每天3元/箱，延期到达所产生的机会成本为6元/箱。各港口之间运输时间见表1，各供给港多余集装箱情况见表2，各需求港对集装箱的需求情况见表3。采用L1运输方式时，k1类集装箱的运输成本为50元，k2类为52元；采用L2运输方式时，k1类集装箱的运输成本为51元，k2类为58元。

表1 各港口之间的运输时间Table 1 Transport time between ports 天

表2 供给港多余集装箱情况Table 2 Surplus containers at supply port

表3 需求港需要集装箱情况Table 3 Container demand at demand port

根据改进遗传模拟退火算法对12个港口进行空箱调度。当种群规模Z=600，进化次数NP=100，交叉概率Pc=0.6，变异概率Pm=0.1，初始温度t0=100，结束温度tf=45，温度下降比例a=0.98时搜索效果较好。对上述实例，经MATLAB仿真得到模型的最优空箱调度方案如表4。

表4 改进遗传模拟退火算法得出的最优空箱调度方案Table 4 Optimal empty container scheduling scheme obtained by improved GASA

供给港提供20 GP箱型集装箱空箱总数为140箱，提供40 GP箱型集装箱空箱总数为40箱；需求港20 GP箱型集装箱空箱总接受量为125箱，40 GP箱型集装箱空箱总接受量为40箱。除S2港到D2港采用海铁联运外，其余港口均选择一般海运的运输方式。总调运成本为8 281元，其中过早到达港口的港口堆积成本为45元，过晚到达港口的机会成本为78元，满足约束条件。

4 结 语

笔者在传统遗传算法的基础上，引入模拟退火法，允许在迭代过程中以一定概率接受与迭代方向相反的解，避免了过早收敛陷入局部最优解；通过精英保留策略保证了最优个体不被破坏，提高了算法的收敛能力；最后通过实例验证了所构建的空箱调度模型为解决航运集装箱空箱调运提供了一个非常有效地解决方法。