一种基于改进LHL算法的客滚船配载优化方法

摘要

本发明公开了一种基于改进LHL算法的客滚船配载优化方法，本发明针对客滚船的单层甲板配载优化决策问题，为了保证船舶航行安全和装载车辆的安全，在充分考虑配载过程中船舶的稳性安全、船舶额定载重量以及车辆间的安全距离等因素的基础上，建立一种考虑多因素的客滚船配载优化方法。该方法综合考虑了各因素对客滚船配载的影响，借助遗传算法作为渡海车辆定序的基本算法，得到船舱面积利用率最大的最优解，运用LHL算法进行辅助决策，确定车辆在船舱甲板上的确切位置，生成客滚船配载决策方案。该方法可对客滚船配载进行优化决策，为甲板调度指挥的工作人员提供更加精确的参考，以充分利用船舱有效面积，从而提高航次收益，提高整个工作流程的效率。

说明书

技术领域

本发明属于客滚船配载技术领域，具体涉及一种基于改进LHL算法的客滚船配载优化方法。

背景技术

在国内现有的客货滚装港口中，传统的客货滚装船车辆配载，大多采用船舶的额定配载长度和人工经验相结合的方式进行配载，人为因素影响较大且船舶空间利用率不高，制约客货滚装码头的生产作业效率的提高。国内客货滚装港口的车辆配载方法仅将车长和船舶额定配载长度作为配载依据，其配载决策维度仅为一维，并未拓展成二维甚至三维，需要较大的人工干预，否则无法进行合理配载。配载模式较为单一和僵化，自动化程度较低，配载优化程度很难得到保证。目前的客货滚装船在进行车辆配载时，配载方法不给出初步配载车位，完全凭借人工经验确定摆放位置，无法全局掌握车辆的动态配载情况，不利于工作人员确定位置，工作效率较低，难以做到优化配载。

矩形件排样优化问题，指的是将若干个大小尺寸不尽相同的小矩形件，按照特定的顺序，以及根据某一摆放规则，要保证在互不干涉的情况下，将矩形件垂直或水平摆放在一块指定的矩形板材中，该矩形板材长度和宽度固定，使得能够充分利用矩形板材，损耗降到最小。

针对客滚船配载问题而言，与矩形件排样优化问题相似，即存在若干个待配载车辆和一艘待发的客滚船，所有待配车辆可以视为长、宽固定的若干个不同的小长方形，船舱甲板可视为一个长宽固定的板材；车辆从船尾依次装入船舶并合理进行配载，配载完成时使得船舱面积利用率最大或者单航次的收益最大，即将小矩形件从上往下寻找最佳位置依次排入大矩形件，使得船舱面积利用率最大。

目前国内外对于矩形件排样优化问题研究的重点内容一般是将所有矩形件排入矩形板材中，其目标或是使得板材面积利用率最低，或是排入固定宽度无限高度的矩形板材中使得高度不限的矩形板材使用的高度最低，矩形件本身无质量、价值等约束。然而针对客滚船配载决策问题，需要考虑的不仅仅是使得单航次船舶的收益最大化，或是船舱面积利用率最大，还需要考虑渡海车辆从待渡场上船的顺序以及车辆在甲板上停放的具体位置，为甲板调度指挥的工作人员提供更加精确的参考，以充分利用船舱有效面积，从而提高航次收益，提高整个工作流程的效率。

发明内容

本发明的目的是针对现有技术存在的问题，提供一种基于改进LHL算法的客滚船配载优化方法。

为实现上述目的，本发明采用的技术方案是：

一种基于改进LHL算法的客滚船配载优化方法，包括以下步骤：

S1，采用遗传算法确定待渡车辆进入客滚船的顺序；

S2，采用改进的LHL算法确定每一辆待渡车辆在客滚船中的位置；

S3，以客滚船面积利用率最大为目标，建立客滚船配载优化模型，通过所述客滚船配载优化模型确定客滚船配载优化方案。

具体地，步骤S1中，遗传算法(Genetic Algorithm，简称GA)，是一种通过模拟达尔文进化论中自然选择学说以及生物遗传进化过程的计算模型，能够通过模拟生物的一个自然进化的过程来求得最优解。将实际问题进行数学化，并利用计算机进行仿真运算，问题的求解过程就转换成了生物在自然进化中生物体自身染色体交叉和基因变异的过程。当研究对象是一个复杂的组合优化问题，对问题进行求解时，遗传算法能够在较短时间内求出优秀的可行解。

所述遗传算法包括以下步骤：

S11，采用二进制的方法对待渡车辆进行基因编码；

S12，随机生成N个个体作为初始种群；随机程度越高，就不易使得算法陷入局部最优，即初始化种群整个遗传算法的解的性能有着直接的影响；

S13，计算适应度值；适应度，即生物在遗传进化过程中，种群中个体对于环境适应能力的大小，适应度大的个体，即对于环境适应能力强，其保存下来的概率更大，适应度小的个体无法适应环境，则大概率将会被淘汰。在算法中，适应度代表了每个个体在优化计算过程中可能达到最优解的优良程度；

S14，选择操作，即从父代种群中按照既定的方式进行子代的选择，将父代中优秀的个体或者基因保留至子代；交叉个体的确定，及子代规模的大小均由选择操作这一步来确定；选择操作所依据的标准就是适应度函数，即可避免基因的缺失又能够提高全局的收敛性，避免过早陷入局部最优；

常用的选择操作有：轮盘赌选择(Roulette Wheel Selection)、随机竞争选择(Stochastic Tournament)、最佳保留选择、无回放随机选择(也叫期望值选择ExceptedValue Selection)、确定式选择、无回放余数随机选择、均匀排序、最佳保存策略、随机联赛选择、排挤选择等选择策略；

S15，交叉操作；交叉操作模拟有性生殖过程中两个相互配对的染色体四分体时期，同源染色体的非姐妹染色单体交叉互换，交换其部分基因，从而形成两个新的个体。遗传算法的交叉操作有效地防止随机操作可能对有效解的破坏；交叉操作是子代中产生新个体的主要方法；

S16，变异操作，产生下一代种群；遗传算法中的变异操作，指的是某个体染色体的某个基因位以一定的概率发生了变异，新的个体就由此产生了；当种群特性趋于一致时，无法通过交叉操作产生新个体，为了避免算法过早收敛，变异操作操作产生的新个体，从而有效地增加了全局优化特质；

S17，判断是否满足终止条件，若不满足，则返回步骤S13继续迭代运算；若满足，则终止迭代运算，输出最佳排序方案。遗传算法通过模拟种群进化而设计，通过每一次的适应度计算、选择、交叉变异操作，反复迭代。当最优个体的适应度到达设定的阈值或最优个体的适应度和群体适应度均趋于稳定不再上升时，算法终止；或为了避免出现无限迭代导致计算时间过长的情况时，一般预设好迭代代数，一般为100～500代。

具体地，步骤S2中，将所有车辆近似为矩形件，将客滚船近似为矩形箱；

由于车辆经配载上船后不存在叠放的情况，且能上船的车辆必定在船舱限高的安全范围内，故可弱化车辆高度对于客滚船配载的影响，仅考虑渡海车辆的长和宽对于配载方案的影响，故假设渡海车辆为规则的矩形。实际客滚船甲板形状往往由于船舶自身结构等原因不是规则的多边形，基于定量分析的可行性和便利性，假设客滚船船舱甲板可配载区域同样为规则的矩形。假设车辆及客滚船质量均匀，几何中心即为其重心。假设待渡场内等待渡海的车辆数量大于单艘船舶最大可装载容量，且已知所有渡海车辆的信息(包括尺寸信息和重量信息)。

最低水平线算法(Lowest horizontal Line algorithm)，简称LHL算法，LHL算法的核心思想在每次将待装矩形物品装入矩形箱子时，都需要确定矩形箱的最高轮廓线中最低的一段水平线的高度。在确定最高轮廓线中最低的一段水平线的高度后，将待装矩形物品的宽度与该段水平线的宽度进行对比，若待装矩形物品的宽度小于最低段水平线的宽度，则将该待装矩形物品放入；若待装矩形物品的宽度大于最低段水平线的宽度，则需要提升最低水平线的高度，继续对比二者的宽度关系，如此往复，直至待装矩形物品能够放入最低水平线处。

所述改进的LHL算法包括以下步骤：

S21，更新矩形箱内矩形件的最高轮廓线的水平线集合；在矩形件未装入矩形箱中时，矩形箱底部为最低水平线；

S22，选取待装矩形件a

S23，从步骤S22中挑选出的多条水平线中，选择水平线最低的一条作为待装矩形件a

S24，当待装矩形件a

S25，选择下一个待装矩形件a

进一步地，步骤S23中，若挑选出的多条水平线中，最低的水平线有多条，则挑选其中最靠近左侧或者右侧的一条作为待装矩形件a

具体地，步骤S3中，以客滚船的船舱俯视图可配置区域的左下角为原点建立xOy直角坐标系，船头至船尾的方向为y轴，客滚船从左至右为x轴；车辆以其左下角坐标为位置标识，即车辆装入船舱后，车辆左下角的坐标为(x

在考虑配载决策时，以船舱满舱为目标，不仅能够提高疏港效率，同时可以在一定程度上保证单航次收益。故本发明基于矩形件排样特性并保证船舶安全航行的现实约束条件下，以船舱甲板面积利用率最大为目标，构建客滚船配载优化模型。

所述客滚船配载优化模型为：

w

其中，f为客滚船面积利用率；I＝{i|i＝1,2,3,…,|I|}为待渡车辆进入客滚船的顺序集合；l

进一步地，所述客滚船配载优化模型的约束条件包括：

矩形排样约束，用于保证车辆头部均与船头同向、车辆之间无干涉以及车辆完全停放在船舱内；所述矩形排样约束为：

x

y

E

F

z

R为正无穷大的参数。

进一步地，所述客滚船配载优化模型的约束条件包括：

现实约束，用于保证船舶安全航行，即保证所有装入船舱的车辆总重量小于船舶额定载重量的90％，在装入所有车辆后，船舶的纵横倾约束在安全的额定范围内，防止客滚船出现纵倾或横倾的风险，对航行安全及客滚船船体造成破坏；所述现实约束为：

其中，m

进一步地，所述客滚船配载优化模型的约束条件包括：

面积约束，用于保证所有装入船舱的车辆占用的总面积不超过船舱的可配载面积，所述面积约束为：

与现有技术相比，本发明的有益效果是：本发明针对客滚船的单层甲板配载优化决策问题，为了保证船舶航行安全和装载车辆的安全，在充分考虑配载过程中船舶的稳性安全、船舶额定载重量以及车辆间的安全距离等因素的基础上，建立一种考虑多因素的客滚船配载优化方法。该方法综合考虑了各因素对客滚船配载的影响，借助遗传算法作为渡海车辆定序的基本算法，得到船舱面积利用率最大的最优解，运用LHL算法进行辅助决策，确定车辆在船舱甲板上的确切位置，生成客滚船配载决策方案。运用所得方法可对客滚船配载进行优化决策，为甲板调度指挥的工作人员提供更加精确的参考，以充分利用船舱有效面积，从而提高航次收益，提高整个工作流程的效率。

附图说明

图1为本发明一种基于改进LHL算法的客滚船配载优化方法的流程示意框图。

图2为本发明实施例中改进LHL算法的步骤原理示意图。

图3为本发明实施例中一般场景下客滚船面积利用率折线图。

图4为本发明实施例中一般场景下客滚船面积利用率标准差折线图。

图5为本发明实施例中一般场景下M2-D-R1配载方案的可视化效果图。

图6为本发明实施例中特殊场景一下第8次配载方案的可视化效果图。

图7为本发明实施例中特殊场景二下淡季客滚船配载可视化效果图。

具体实施方式

下面将结合本发明中的附图，对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动条件下所获得的所有其它实施例，都属于本发明保护的范围。

如图1所示，本实施例提供了一种基于改进LHL算法的客滚船配载优化方法，包括以下步骤：

S1，采用遗传算法确定待渡车辆进入客滚船的顺序；

S2，采用改进的LHL算法确定每一辆待渡车辆在客滚船中的位置；

S3，以客滚船面积利用率最大为目标，建立客滚船配载优化模型，通过所述客滚船配载优化模型确定客滚船配载优化方案。

为了验证所构建的客滚船配载优化模型和算法的有效性，分别设计一般场景和特殊场景下的模拟实验，来验证客滚船配载优化方法。

一、一般场景下的客滚船配载优化

(1)场景设置

根据对琼州海峡客货滚装业务进行分析，由于配载对象为社会渡海车辆，其出行规律有一定的社会属性，渡海车辆中的客车由于规定仅能在白天渡海，且根据轮渡系统数据显示渡海的客车相比于货车和小汽车数量较少；货车大多为避免拥挤则选择晚上渡海；小汽车则由于旅游、工作等需求选择白天渡海。故分别设置白天(D)和晚上(N)两个场景：其中，白天(D)小车居多，货车次之，客车最少；晚上(N)无客车渡海，大货车较多，存在少部分小车选择晚上渡海，通过对车辆渡海场景及车型比例进行假设，如表1-1所示：

表1-1一般场景车型比例

车辆间的安全距离设置为0.2m(在进行模拟实验时，为了便于求解，将渡海车辆的车身长和车身宽均加了0.1m，以满足安全距离的需要)。典型渡海车辆的车型信息如表1-2所示：

表1-2典型渡海车辆的车型信息

典型实验客滚船船型数据如表1-3所示：

表1-3典型实验客滚船船型数据表

不同场景利用N/D-R1/R2-M/L的方式来表示，其中N/D表示配载业务是白天或是晚上，R1/R2表示不同情况下的各车型具体比例，M/L表示不同规格的客滚船，待渡车辆总数|I|根据具体问题规模而定，各类车按照具体各类车辆的具体数量根据总车数和相应的比例确定，货车由于货重的不确定性，从给定的实际重量范围内随机生成，其余车辆重量变化不大，按照给定的数据进行求解。各类车型的渡海费用根据有关部门制定的标准：客车，560元/辆；小车，374元/辆；货车，计重计费，约合40元/吨。

以实验场景M2-D-R1为例，即当船舱L长98m、舱宽W为19m的客滚船在白天停靠在港口等待配载，此时等待渡海的车辆一共有150辆，渡海车辆的各车型比例为客车∶小车∶货车＝1∶5∶4，各类车中的每种车型随机生成，各类型车辆的长l

其额定载重量Q为1500t，船舶装载车辆的实际载重与额定载重量的关系为：

横倾力矩D

构建的模型利用MATLAB 2019a求解，在利用K-邻域搜索的遗传算法对车辆上船顺序确定时，相关参数设置如下：算法种群规模设置为100，迭代次数设置为200，交叉概率为0.95，变异概率为0.2，模型最大求解时间设置为120s，基于矩形件排样优化理论的客滚船定位约束为：

x

y

具体定位流程如4.4.2节所述。为避免出现偶然性，每个场景进行10次方案输出，取其平均值。

如图2所示，具体定位流程为：

S21，更新矩形箱内矩形件的最高轮廓线的水平线集合；在矩形件未装入矩形箱中时，矩形箱底部为最低水平线；

S22，选取待装矩形件a

S23，从步骤S22中挑选出的多条水平线中，选择水平线最低的一条作为待装矩形件a

S24，当待装矩形件a

S25，选择下一个待装矩形件a

进一步地，步骤S23中，若挑选出的多条水平线中，最低的水平线有多条，则挑选其中最靠近左侧的一条作为待装矩形件a

(2)决策方案

16种不同场景下的实验结果如表1-4和图3、图4所示，f(avg)/％表示每个场景运行10次客滚船船舱甲板可载区域利用率的平均值，f(std)表示每个场景下10次实验结果的标准差，Value表示每个场景下单航次收益平均值，Weight表示单航次甲板上渡海车辆的总重的均值。

表1-4不同场景下客滚船渡海车辆装载情况

由表1-4和图3可知，对于M1、M2、L1、L2四艘不同规格的客滚船，在不同的时间、不同车辆种类及比例、不同待渡车辆规模的情况下客滚船的船舶面积利用率均达到了96％的左右。航次收益与琼州海峡某港口同规格的客滚船舶的单航次收益相比均维持在较高水平，且其载重量均维持在安全水平。说明本发明所设计的客滚船配载优化决策方法既能够在航行安全的基础上，保证客滚船舱容利用率，同时在一定程度上保证航次收益。由图4可知，16个场景的10次实验结果的标准差基本上在0.005左右，证明模型算法具有良好的稳定性，求解性能良好。

其中面积利用率在95％的场景均为小型客滚船M1和M2，这是由于晚间发船，货车比例大于小车比例，由于货车种类及型号众多，且面积较大，在配载时容易产生空隙，当小车数量多时可以填充这些空隙，而晚间发船，小车比例少，无法被小车完全填补，造成面积的小部分浪费，降低了船舶的面积利用率，而货车在船尾易形成空隙；而客滚船L1和L2在晚上进行发船作业时，其面积利用率能够维持在较高水平，这是由于客滚船L1和L2相比于客滚船M1和M2其面积稍大，对于面积较大且种类及型号繁杂的货车有更好的适应性，在侧面说明客滚船的大型化不仅能够提高单航次的收益，更能够在车型更杂的现实作业中提高船舱甲板的利用率。

图5为场景M2-D-R1中的一次求解结果的配载可视化方案，即客滚船M白天发船时的客滚船配载方案，待渡车辆的各车型比例为客车∶小车∶货车＝1∶5∶4，150辆待渡车辆到达了待渡场，经优化配载决策后，客滚船船舱面积利用率达到了97.04％，该航次车辆总运费65756元，车辆总重771.8t，处于安全航行的状态，车辆中所标示的数字为车辆到达序号，矩形所在位置即车辆上船后停放的具体位置，工作人员按照这个配载方案图，从船头往船尾处依次引导车辆陆续上船停放到指定位置即可，待所有车辆停放好后，本航次的配载工作也就结束了，即为最终的配载方案。

二、特殊场景下的客滚船配载优化

1)场景设置

(1)场景一

本实验模拟当港口受极端天气影响时，港口出现车辆积压问题，为加快港口运作效率，尽快发送车辆和旅客，为港口车辆配载工作提供可行且高效的配载方案。故本场景是模拟当待渡车辆数目不足时的客滚船配载，此时港口积压着数量足够多的不同类型的车辆在待渡场内等待上船渡海。

(2)场景二

本实验模拟客滚运输业务淡季(淡季一般为5月至11月，旺季一般为12月至次年4月，超旺季为春运高峰期，约为正月初四至初九)时，渡海车辆数目较少，且由于琼州海峡客滚运输班轮化运营模式，无法再保证每个航次都能满舱满载，故本场景是模拟当待渡车辆数目不足时的客滚船配载实际。

各待渡车辆的车型以及各项参数按照表1-2中数据设定，客滚船舶选取目前在航线“海口—海安”营运的客滚船舶“紫荆二十二号”、“宝岛12号”两艘客滚船进行场景模拟实验，其具体参数如下。

“紫荆二十二号”：船舶总长127.5m，型宽20.88m，设计水线长117.4m，夏季满载吃水4.2m，空载吃水3.3m，满载排水量7021.9t，空载排水量4672.9t，额定载货量3150t，总吨12005t，载客总额999位。

“宝岛12号”：船舶总长106m，型宽19.8m，水线长98m，夏季满载吃水4.0m，空载吃水3.3m，额定载货量1574t，总吨6815t，载客总额988位。

2)决策方案

(1)场景一

为充分模拟港口出现大量待渡车辆积压在港的场景，假定港口不同类型待渡场均停满了渡海车辆，根据港口总平面布置图，货车、小车、客车的停车位分别约为260个、160个、60个，在高峰车辆积压严重时，港口待渡场内共有约480辆不同类型的车辆在等待上船，生成客滚船舶“紫荆二十二号”的客滚船配载方案。为了减少随机性，分别进行10次模拟实验，具体实验结果如表2-1所示，第8次的配载方案如图6所示。

表2-1场景一实验结果

通过表2-1知，利用“紫荆二十二号”进行模拟港口出现大量待渡车辆积压在港实验时，船舱面积利用率基本上能够维持在97％以上，高于一般场景下的实验结果。说明当港口出现待渡车辆挤压问题时，由于港口各类型的积压车辆数目均较为充足，在选择车辆时，偏向于选择同类型的车，可以最大限度利用甲板可载区域，以避免不同类型的车由于车型差异性太大，容易产生无法利用的小区域，造成甲板可载区域的浪费。通过本发明所设计的模型及算法来指导客滚船的配载工作，能够在短时间内生成有效地配载方案，选择工作人员在进行船舶配载决策时提供参考，以实现在短时间内有序地指挥调度车辆进行登船作业，快速发送车辆，在一定程度上协助解决港口车辆的积压问题。同时，10次实验的标准差在0.3％左右，再次证明了模型及算法的稳定性。

(2)场景二

为充分模拟淡季时客货滚装运输业务，假定由于渡海需求减少，预约等候上船的渡海车辆的数量由以下公式唯一确定：

各类车型比例随机生成，实验船舶利用“宝岛12号”客滚船舶进行。

在预约过海时间截止后，在分析登记的渡海车辆信息后，预估所有预约了该航次渡海的车辆总的面积，即计算

假设随机生成80辆待渡车辆，车型及规格参考表格1-2，通过计算这50辆待渡车辆的总面积，可确定λ约为0.63，则设μ为0.70即可，对模型和算法进行求解后，即可得到具体的配载方案。经求解，输出该航次的一种较优配载方案，其车辆总重643.2t，如图7所示，同种类型的渡海车辆从左至右均匀分布，保证船舶不会发生横倾的风险，从船头方向往船尾看，小车集中于在船头侧的甲板上，货车及少量的客车等大型车辆偏甲板中间停放，此时船舶纵倾约为8190KN·m，在最大横倾力矩范围内，能够充分保证船舶的航行安全，配载方案合理。

通过一般场景和特殊场景下的模拟实验分别验证了所构建的基于现实约束的客滚船配载优化决策模型和设计的求解方案的有效性。

在一般场景的模拟实验中，船舱面积利用率在96％左右，基本上达到了目前已知文献中对于客货滚装船舶配载优化决策研究的最新成果的水平，其船舱面积利用率也基本在95％左右，经多次实验得出的船舱面积利用率的平均标准差在0.005左右，算法及模型展现出较好的鲁棒性。

在特殊场景的模拟实验中，分别模拟了极端天气影响导致车辆大量积压在港口内的场景和淡季渡海车辆数量较少无法满足单航次满舱要求的场景：受极端天气影响时，仍然能够以97％左右的船舱面积利用率装载车辆，以尽快发送积压的渡海车辆，协助港口尽快解决渡海车辆大量积压的问题；淡季时，能够基于预约购票的信息，通过及时调整相关参数，仍然能够输出合理的配载方案，以供港方参考。

综上，所构建的模型和设计的相关求解方法能较好地适应不同的客滚船配载场景，对于不同场景下的客滚船配载决策均有一定的指导意义，从而以提升客滚运输业务的营运效率，提高港方的收益。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。