基于混合启发式算法的集装箱货轮装配策略研究

秦媛媛 （江苏财经职业技术学院 智能工程技术学院，江苏 淮安 223003）

0 引 言

当今世界70%以上的价值贸易是通过海运进行的。由于大量的一般货物是由集装箱运输，而为了满足具有竞争力的航运公司选择服务的实际需求，甚至有更大的集装箱船。此外，班轮航运网络可能包括几十个船舶航线和港口，这取决于船队的能力。由于海上运输需求的不断增加，港口活动和航线不能再被视为独立于海运之外。尽管如此，近年来关于海运的管理科学文献主要集中在海运码头进出口集装箱流动中所需的优化技术或航运的改善服务。然而，许多研究者也都认识到，装卸作业和配载规划对码头的效率和班轮航运选择有很大的影响。最近的许多论文开始致力于对集装箱船配载方案加以优化的研究。

事实上，配载规划是由航运线路协调器和码头规划器决定的。在计划层面上，控制中心对船舶的整个行程有一个视图，汇总信息以作出决策，航运线路协调器接收o-d运输需求并验证是否可以接受运输需求。然后，航运线路协调器为船舶航行的港口定义一个配载计划，并在收到和接受对该船舶的需求时及时更新该计划。在船抵达港口之前，船长必须给出一份可行的计划，根据目的地、类型、大小和装载重量不同的集装箱做出一般指示。航运线路协调器表明集装箱是船舶的一部分。

码头规划器能够在运营层面作出更为详细的决策。装卸工作是在收到船长的装卸指示后开始的。具体来说，码头规划器必须按照从航运线路协调器收到的装载前指示，为每个要装上船的集装箱定义确切的位置。然后，码头采用的详细积载计划被传达给航运线路协调器，航运线路协调器更新船舶当前的货物，并开始新的规划阶段，将新的货物与航线船舶上相继港口的运输需求结合起来。在船舶抵达港口之前(即航运线路协调器发送到码头的积载计划)，需要将船舶货物组成与船舶离港后的实际货物(即the码头规划器定义的积载计划)合并起来，这是由于两个计划的详细程度不同。事实上，由航运线路协调器给出了码头的一般指令，而码头规划器定义了每个集装箱装船的确切位置。例如，一旦航运线路协调器确定“10个A1-10类集装箱、标准、轻量级、目的港AI必须装入10号舱”，码头规划器就决定在10号舱装入10个A1类集装箱的每个集装箱的行和层索引。

积载计划的研究从单一港口问题开始，即主舱规划问题。王崇等人最近的一项研究试图将堆场管理纳入到主港湾平面图问题当中。在对于多港口主港湾平面图问题的研究中，大多数论文通常会提出分解方法，提出一种生成多港口航程集装箱船配载计划的方法，并将决策过程分解为两个规划子过程：战略和战术。杨欣宇等人提出了一个包括主稳定性和应力矩计算的压载舱线性模型，用于处理可变位移。张晓林等人考虑到集装箱船的舱口和不规则龙骨，提出了求解多港口主港湾平面图问题的两个混合整数规划模型。本文在一个新的解决方案的基础上提出的混合整数规划模型。这项工作为多港口提出并评估了一种新的混合整数规划启发式方法，该方法利用了放松和修复原理，以迭代的方式解决了混合整数规划模型的松弛问题，逐步修复了二进制变量的子集，详细介绍了一个实验活动，以显示所提出的方法的能力，包括在一个有效的工具确定配载计划的供应链。本文结构组织如下：正在研究的问题在第1节中详细介绍。对问题的基本混合整数规划模型进行简短的提示之后，第5部分给出提议混合整数规划启发式的主要步骤。假设结果在第7部分给出，而第5部分得出了工作的主要结论和概要。

1 船舶的结构特点

航线(按要访问的港口的循环顺序描述)和当前货物的问题在于为一组不同尺寸、类型和重量的特定集装箱以及根据装载港和目的港的具体要求确定装载计划，以便所有集装箱都能装上船，同时满足结构和操作限制，并将船舶在港口进行装卸作业的时间降至最低。

在更详细的定义中，多港口主港湾平面图问题考虑了以下因素:

一艘具有特定结构的船舶，其拥有的属性分别为港湾、行、层和舱口的集合，即i、j、k和h(见图1)。

图1 集装箱船的结构

的承载能力，即分别对应于舱内下的舱口位置(舱口位置)和甲板上上的舱口位置(甲板舱口位置)可用的数量，详细说明冷冻箱和开放式顶部容器的装载能力；关于船舶稳定性的一些要求，以最大交叉平衡公差1和最大水平平衡公差1表示；船舶循环航线所包括的港口组和船舶考虑行程中的船舶组；运输节点的要求，以大小为、类型为、重量等级为的集装箱数量表示，以便在目的港装运。

然后，多港口主港湾平面图问题包括如何将每组集装箱分配到船舶舱口上方/下方的位置。组是一组同质的集装箱，涉及尺寸(10或70集装箱)、类型、重量级和装货港()和卸货港()。确定集装箱分配的主要目标是满足货运需求，同时满足船舶装载不同类型的集装箱的能力，并尽量减少船舶在港口进行装卸作业所花费的时间。通过减少每个港口并行工作的起重机的重新把手(即非生产性运动)的数量和装卸作业之间的不平衡，可以使得船舶停留在港口时间最短。后一个目标是合理的事实，一个港口的时间取决于所需的时间起重机执行最大数量的装卸作业。为此，假定在p港口平行服务于船舶的码头起重机的集合类型和在c港口服务于舱口的子集是已知的。

主要的决定，表示的变量报告如下所定义的模型中提出的氨水等。以及它们受到的主要限制如下：在船舶的舱/甲板舱口的位置分配给定组的集装箱数量(具有固定的大小、类型、重量等级、起点港和目的港)，由整数变量表示，以满足每组集装箱的运输需求。集装箱到舱口位置的分配必须遵守船舶结构的容量条件，容量条件指装载在船上的所有集装箱，但也包括不同类型的集装箱(标准集装箱、敞口集装箱和冷藏集装箱)。此外，稳定性条件也必须通过指派得到重视，特别是水平和交叉平衡必须得到满足。在货舱/甲板的舱口位置到目的地d的港口p的指派，由二元变量表示。这个指派在每个港口执行，它可以随着旅程的变化而改变，但在每个港口，只有具有相同目的地的集装箱才能装载到每个舱口相同的位置。

在p口处，重新安排可能发生在舱口h上方甲板上的位置，用于装载集装箱前往p口并存放在舱口h下方的货舱中，用于装载集装箱在舱口h下方货舱的自由位置偏离p口(见图1)。在p端口过舱口h要执行的重新处理操作的数量等于船舶抵达p端口时装载在甲板舱位置h而不是运往p的集装箱的数量，即装载在起点和目的地的集装箱的数量。通过二元辅助变量和在甲板舱口位置h上，每个港口p处执行的重新处理的确切数目h，来模拟在甲板舱口位置h中执行重新处理的需要，由整数变量。如前所述，第二个目标使船舶在港口花费的时间最小化，这与工作起重机的平衡有关。因此，通过变量计算每个港口每台起重机的装卸作业总次数；再通过变量计算每个港口的每台起重机c的装卸作业次数之间的绝对差；通过最大变量表示每个港口每对起重机的装卸作业次数之间的最大差异，表明船舶前方最大起重机的作业不平衡。

图2 卸货装货示意图

2 模型假设和求解

本节描述了求解多港口主港湾平面图问题的两级渐进随机固定程序，该程序基于张晓林等人提出的混合整数规划模型而提出，其变量和主约束已在前一节中简要描述。以作为多港口主港湾平面图问题的混合整数规划模型。其运作方式类似于放松和修复启发式。尤其是多港口主港湾平面图问题的特点是两种主要类型的决策：由二进制变量建模的目的地位置分配，以及由整数变量建模的容器位置分配，其值取决于其中一个变量。因此，把变量看作最重要的变量，然后在第一步中，通过最优解决一个显然更简单的混合整数规划问题来确定它们的值，这个问题中所有的变量都是线性松弛的。然后，启发式继续尝试寻找一个可行的解决方案，通过解决原来的问题，所有的位置决定，对应的变量是固定在第一步得到的值。然而，第二步可能仍然是相当耗时的，所以它被划分为一个简单的步骤序列，遵循一种潜水和固定的策略:因为，正如观察到的一样，对于多港口主港湾平面图问题许多变量假设整数值在第一步的解决方案，这些变量暂时固定在以下步骤。一般而言，这种固定汇率制度不能有可行的解决方案，或产生的解决方案不够理想，即与第一步所得的下限之间的差距过大。当这种情况发生时，变量修正被认为是约束性过大的，并且对于随机选择的一个变量子集它在被逐渐移除。这种策略导致要解决一系列越来越难的混合整数规划问题，这些问题要么在一个可行且足够好的解决方案时终止。

首先求解模型的部分线性松弛(多港口)，以求得初始解和在寻找整数可行解过程中利用的某些解。部分松弛是通过线性松弛变量来获得，这两个变量分别定义了给定集装箱的集装箱数量，分别用于存放和确定甲板舱口位置。注意，在链接到模型中，变量是线性松弛的。注意，由于这种松弛，如果某个变量假定非整数值，多港口的解可能不是的可行解。另一方面，在多港口的解中，其数目(通常很大)假定为整数值。然后，该启发式算法对模型的解进行迭代，其整数变量部分固定于求解多港口的整数值，每次迭代时，所有的二进制变量都固定于求解多港口的值，以及在解中值为整数的变量子集给定百分比百分位数。将值初始化为100%，并在迭代过程中降低。

这个过程被称为“渐进随机固定”，在迭代过程中，它试图解决模型固定了一个随机选择的整数变量子集，其基数逐渐减少。此外，在求解给定前缀的模型之前，考虑与所找到的第一个整数解相关的下界，对获得优质解的可能性进行评估。采用星期天条件，最长时间限制为5 600秒，或满足给定的容忍值。请注意，如果找到一个高质量的解决方案变得太困难，即当其逼近零时，公差值增加，因此放松了一个终止条件。然而，如果考虑的实例是可行的，启发式返回的最终解决方案总是模型m的可行解决方案，因此是多港口主港湾平面图问题的可行解决方案。

注意，在每次迭代中，要评估当前部分固定的模型多港口f是否可探索，即是否值得求解。这是通过检查与多港口f的第一个解相关的下界与多港口r解的目标值之间的绝对差是否小于给定的公差来完成的。当有迹象表明生产的溶液质量不能满足终止条件时，引入这样的测试来加速停止部分固定模型的溶液的计算。在这种情况下，百分比被降低，整个评估过程被重复。第八个步骤实现终止条件；具体来说，如果下列三个条件中的一个成功，则停止：

得到的解决方案的两个方案质量相当，即目标函数值在来自其的公差范围内；在解决可探索的多港口的最大迭代次数之后，终止条件()被放松，新的放松的终止条件包括验证下限是否在下限值的公差范围内；整数变量修正的百分比为零；这表明在模型多港口中，最后只有二进制变量是固定的。由于要固定的变量是随机选择的，因此步骤9的作用是允许一定数量的尝试，然后在每当为这样的百分比生成可探索的多港口时减少。最后，如果将最小正阈值设置为，则步骤10将其重置为1.0，并且在降低到以下时增加公差值。

计算结果上一节描述的混合启发式中实现，使用混合整数规划求解器cplex11.5。所有的测试都运行在一台1.7GHz的IntelCore1Twoe6 600计算机上，7gb内存。计算测试基于多港口主港湾平面图问题的随机生成实例，这些实例代表了真实场景。三艘容量分别为7 800、10 000和18 051标准杆的集装箱船进行这些测试。每艘集装箱船都有一定的容量来装载冷藏集装箱和开口集装箱。这些容量范围从800至1 680的冷藏集装箱和从1 560至1 576的开放式顶部集装箱。集装箱最常见的三种重量级:轻型、中型和重型。每个级别的重量限制对10和70集装箱是不同的，包括10集装箱，分别达到7吨、17吨和11吨，70集装箱，分别达到10吨、20吨和50吨。

每艘船行驶在一条有6个港口的圆形航线上，运输需求是随机产生的，对于航线上的每一个原产地以及对于航线上连续三个港口的标准、冷藏和开放顶部集装箱都有积极的需求。例如，在规划5号港口的配载时，船上的货物来自于在1、5和7号港口进行的装载作业。在5号港口，卸货作业完成后，装货过程涉及装往6号、1号、7号港口的集装箱，其中1号和7号港口表示船舶在第二回合期间到达的1号和7号港口。每艘集装箱船产生四个实例，每个实例与其他实例不同，以满足运输需求。无论如何，所有实例都是以这种方式产生的，以强调启发式方法在短时间内拥有获得可行和有效解决方案的能力。表1就每艘被考虑的船舶(即小型船舶、中型船舶和大型船舶)报告占用船舶的百分比水平离开所考虑航线的港口时，船舶所需容量的百分比与每个端口的装载需求相关联。请注意，船舶的占用水平是以船上的载重量与船舶载重量的比率来计算的。这两个参数给出了实例求解难度的一个概念：给定一定比例的船舶所需容量，船舶的占用率越高，实例求解的难度越大。

表1 所考虑的集装箱船的平均占用特征

在生成的例子中，在每个港口装载的货物需要占船舶容量的75%。每个港口装载的集装箱有75%是10英尺集装箱。此外，平均80%的货物与标准货柜有关，10%为冷藏货物，10%为敞口货柜，平均入住率超过85%。模型适用于所考虑的情况有一些变量，从最小的船舶的95 511到最大的船舶的159 501，以及相应的一些约束，从16 708到71 618。

为了评估所提出的启发式算法的有效性，将1和1参数与稳定性条件相关，分别固定在不同的和更强的数值上，范围从船舶总重量的0.1%到0.01%。更准确地说，在定义配载计划时，稳定性十分很重要；在目前的研究中，稳定性条件对应船舶离开其航线每个港口时在船上货物上计算的水平和交叉平衡。固定在总重量的0.01%的稳定性值可以被视为一个相当不现实的情况，例如，最大船允许的最大稳定性公差对应于一个10英尺或70英尺的重型集装箱，两个10英尺或一个70英尺轻型集装箱。然而，这种限制性的公差值仅仅是为了强调拟议的混合整数规划的启发式能力。

所执行的测试比较了其启发式和混合整数规划求解器所产生的启发式的性能。这两种方法的最大时间限制是固定值5 600秒。目标函数中的权重以这种方式确定，比以考虑重新处理起重机不平衡更不理想的十倍。启发式的公差相当于接受一个绝对最优间隙等于1的解决方案作为最优解(即，一次操作的最大起重机不平衡)。表1列出了由其得到的结果，显示了三种类型的集装箱船和不同稳定公差(1-1)的整体目标函数()、重新处理的数量()、最大起重机操作不平衡()和计算时间()的值。表1的每一行报告了四个已解决实例的平均值。特别是部分放松（多港口）和部分固定（多港口）模型产生的解决方案，以及其()的总计算时间。

与混合整数规划的比较可以通过观察表1中的最后一列来完成，该列报告了由其获得的时间，相对于混合整数规划solver所需的时间的百分比偏差，以产生完全相同的结果。时间列中显示破折号的单元格，表示混合整数规划求解器在计算一小时内无法找到可行解的实例。在灰数的情况下(相同的实例的情况)，数据是在5 600秒的时间限制内由模型解决的那些实例的平均值(即7个实例中的5个)。可以观察到其高计算性能，它能够找到所有情况下的最优解(由于最终下界严格大于零，因此对于那些没有被混合整数规划解算器解决的情况也可以证明最优性)。对于所有和实例，其需要的计算时间小于170秒，而实例的平均时间为1 571秒，结果表明更难求解，但是启发式所需的总体时间561秒是可以接受的，除了较难的7种情况外，它可以降低到161秒。表2报告了在5 600秒的时间限制内求解模型所获得的结果。对于三种类型的集装箱船和两个不同的稳定性公差值(1-1=0.100%和0.050%)，如表1所示，整体目标函数()的值、重新处理的数量()、最大起重机操作不平衡()和计算时间()。

表2 启发式程序得到的结果

3 结 语

多港口主港湾规划问题(多港口主港湾平面图问题)是海运物流中一个非常关键的优化问题，尤其是对于海运码头和港口作业的效率而言。多港口主港湾平面图问题涉及两个决策者，即船舶协调员和终端规划员，他们有不同的观点和信息，都能够快速和良好地解决方案。为了支持这些决策过程，文章提出了一种混合整数规划启发式方法，目的是确定集装箱船循环航线的配载计划，即不同类型、大小和目的地的集装箱必须装船运往目的地。以船舶的最小停泊时间为目标函数，并考虑了船舶和航线所涉及码头的结构和操作约束。该启发式算法依赖于文献中最近提出的一个非常有效的混合整数规划模型，可以在非常短的计算时间内得到18000艘集装箱船的可行解。在已有计算结果的基础上，我们相信在一个合适的工具中实现这种混合整数规划启发式可以真正有效地支持和改进配载计划的定义。