在线环境下客货滚装船多目标动态配载决策

张 煜 熊得鹏 马少康 贺利军 李 斌

(武汉理工大学交通与物流工程学院1) 武汉 430063) (福建工程学院交通运输学院2) 福州 350118) (中交集团智慧研究院3) 武汉 430000) (武汉理工大学韶关研究院4) 韶关 512100)

0 引 言

客货滚装(以下简称“客滚”)运输是一种旅客和渡海车辆相混合的运输模式，客滚船配载作为客滚码头生产作业的核心环节，其配载效率和决策水平直接关系港口运作效率及其收益.与一般滚装船配载相比，客滚船配载对象涉及小车、货车和客车，且配载具有二维装箱[1]、两阶段、实时动态等特点.

已有研究聚焦一般滚装船配载问题(以规格尺寸相近的商品车为主)，将船舶配载视为背包问题[2]或者二维装箱问题[3]，未具体考虑车辆在船舱中的摆放位置，不适用于客滚船配载场景.Zhang等[4]假设配载时所有渡海车辆信息已知，针对问题存在的两阶段、二维装箱等特点，以船舱面积利用率最大为目标，设计了偏随机密钥混合算法.但在实际港口运作过程中，渡海车辆到港与船舶配载同步进行，配载时车辆信息是逐步获取且无法完全已知.因此，客滚船配载还具有实时动态特点，需要引入在线决策，可借鉴在线车间调度[5]、在线装箱[6-7]等方面的研究成果.

文中基于客滚船配载的现实需求，考虑问题的实时动态特点，将整个配载过程划分为多个决策阶段，构建基于车辆滚动窗口的客滚船多目标在线配载决策模型，设计了融合灰熵并行分析和混合遗传算法的多阶段动态决策框架及其算法，通过多组对比实验来验证模型和算法的有效性.

1 问题描述

客滚船配载的两阶段是指配载前中期车辆需全部装入船舱，记为主体配载阶段(main stowage planning phase, MSPP)；配载后期挑选部分车辆装船，记为补充配载阶段(supplemental stowage planning phase, SSPP)，此阶段允许小车旋转放置.二维装箱是指配载作业的维度、规则和目标与二维装箱问题的装箱维度、装箱规则和装箱目标一致.此外，配载时还需考虑船舶稳性和车辆间的安全距离，以保证船舶安全航行.以琼州海峡为例，客滚船配载过程中，港方动态获取抵港车辆信息，实时配载客滚船，直至船舱装满或达到额定载重量的90%，停止配载.以往研究中，针对此类在线决策问题，多采用滚动策略进行求解[8].为此，本文设计了一种滚动推进策略，将一个完整的配载过程划分为多个耦合的决策阶段，根据每个阶段的车辆信息生成一个滚动窗口，进行局部最优求解，并将上一阶段的船舱最终状态作为下一阶段的初始状态，利用车辆到港数量驱动窗口信息更新和决策阶段前进，见图1.

图1 客货滚装船在线动态配载决策

为实现滚动推进策略的数学化描述，定义以下概念：车辆序号集合I为按到港顺序依次编号，I={i|i=1,2,…,|I|}；I1为MSPP车辆序号集合，I1={i|i=1,2,…,|I1|}；I2为SSPP车辆序号集合，I2=I-I1；Sd(t)为第t阶段滚动窗口中的车辆集合；H为滚动窗口最大长度即Sd(t)中的车辆数量.配载过程可描述为：初始，渡海车辆依次到港进入滚动窗口，当车辆数量达到H时，开始配载；在MSPP的第一个窗口决策阶段，从Sd(1)中挑选车辆登船配载；后续车辆补充进入滚动窗口形成Sd(2)，通过不断配载并更新Sd(t)，船舱状态不断向前推进(记为S-1阶段).为符合配载两阶段性，MSPP临近进入SSPP阶段前，增设过渡阶段，将MSPP剩余车辆全部装船(记为S-2阶段)；进入SSPP，先按照S-1阶段配载作业，直至船舱装满或达到载重量要求时停止配载(记为S-3阶段).此外，船舱是否装满取决于S-3阶段配载完成后是否有车辆能够继续装入.因此，为高效利用船舱面积，增设延迟验收阶段，在S-3阶段配载完成后，等待Q辆车，判断是否有车辆能够装入船舱(记为 S-4阶段).

在线动态配载问题在各窗口决策阶段，整体配载尚未完成，无法以船舱面积利用率最大为目标，但各阶段均追求车辆摆放高度低且形成的配载面平滑；同时，由于货车收费远高于小车和客车，以航次收益为目标会导致优先选择货车，不合港口服务宗旨.因此，本文以各决策阶段的客滚船配载面高度最低和平滑度最高为目标，采用多目标优化策略使各阶段配载车辆尽量紧凑且配载面尽量平滑，其落脚点仍在于船舱面积利用率的最大化.

2 客滚船多目标在线动态配载决策模型

2.1 基本假设

1) 以船舶可配载区域的左下角建立xoy坐标系，见图2.

2) 假设船舱和车辆为质量均匀的矩形.

3) 将船舱划分成若干网格，进行离散化描述，单元格采用二元组(j,k)进行标识，j、k分别表示第j列和第k行.

4) 假设待配载车辆数大于船舶最大容量，车辆信息未知.

图2 船舱状态离散化描述

2.2 符号及变量说明

符号与集合：DIt,DIst,DIbt为当前决策窗口t中的车辆序号集合、小车序号集合、大车(客车和货车)序号集合；i为待配载车辆序号，i∈DIt；j,k为船舱单元格的横、纵坐标；

其他参数：mi为车辆i的质量，t；R为一个大数；G为船舶的额定载重量，t；Gt为在t阶段，船舶的载重量，t；Ttx为在t阶段，船舶的横倾力矩，kN·m；Tty为在t阶段，船舶的纵倾力矩，kN·m；Tx为船舱在x轴方向的最大横倾力矩，kN·m；Ty为船舱在y轴方向的最大纵倾力矩，kN·m；N1为每次配载的车辆数；C1为过渡阶段剩余车辆数.

2.3 模型建立

若将配载面上单元格看成质点，则整个配载面由大量质点组成，以其下方单元格坐标作为该质点的位置标识，记为配载面质点，坐标表示为

(1)

(2)

则相邻配载面两质点间的曼哈顿二范式距离为

(3)

相邻配载面质点在y轴方向上的浮动程度越大，则平滑程度越低.因此利用式(3)计算相邻配载面质点的曼哈顿距离，并通过式(4)求和得到总距离来表征整个配载面的平滑程度δ.δ值越小，配载面越平滑.

(4)

由于S-1、 S-3阶段的配载方式相同，针对S-1、 S-3阶段的第t个滚动窗口，构建的基于车辆滚动窗口的客滚船在线配载决策模型，记为SPMS-1(t)或SPMS-3(t)，具体如下：

目标函数：

(5)

(6)

约束条件：

xijk≤ri+(1-si),∀i∈

DI(s)t,j,k∈(M-Mi)

(7)

xijk≤(1-ri)+(1-si),

(8)

xijk≤(1-si)，∀i∈DI(b)t,j,k∈(M-Mi)

(9)

(10)

(11)

(12)

xijk≤yij′k′+(1-ri),∀i∈DI(s)t,j,

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(rili+(1-ri)wi-1-W)/2)+T(t-1)x≤Tx

(23)

(1-ri)li-1-L)/2)+T(t-1)y≤Ty

(24)

xijk,yijk∈{0,1},∀i∈DIt,j,k∈M

(25)

si,ri,jri∈{0,1},∀i∈DIt

(26)

S-2阶段滚动窗口中车辆数量为C1，且所有车辆经过一次决策全部登船配载，则S-2阶段的决策模型为

SPMS-2(t){f1(t),f2(t):(7)～(20),

(27)

模型目标为式(5)～式(6)，约束条件为式(7)～式(20)和式(22)～式(27)，式(27)保证过渡阶段剩余车辆全部装船.

3 算法设计

3.1 多阶段动态决策框架

针对配载的S-1阶段设计首层和主体动态配载，并结合针对S-2、S-3、S-4阶段设计的过渡、补充动态配载和延迟配载，形成多阶段动态决策框架实现求解，见图3.

图3 多阶段动态决策框架

3.2 基于灰熵并行分析的混合遗传算法

本文基于GA算法，融合GEPA方法，设计了HGA-GEPA，算法流程见图4.

图4 HGA-GEPA寻优流程图

染色体编码见图5.染色体长度对应滚动窗口长度，编码采用随机数编码的方式分别排序，一个染色体表征一种装船序列.

图5 染色体编码

放置启发式需要得到满足二维装箱和稳性等约束且效果良好的配载方案，是算法设计中的难点.本文的放置启发式包括初始解构造和稳性调整两部分.

1) 初始解构造 为确定当前决策集中车辆在船舱中的摆放位置，本文利用文献[1]多阶段启发式中的评分策略评判配载优劣，生成初始解，见图6.

图6 基于评分策略的配载方案

2) 稳性调整 为保证配载时横倾处于较理想的范围，沿y轴方向将船舶等分为左侧和右侧空间，当装入车辆评分为0时，若此时横倾小于0，则将车辆放置在船舱右侧空间；反之放置在左侧空间.

适应度评估是多目标决策算法的关键步骤，GEPA[9-10]是一种新颖的适应度评估方法，它将灰色理论和信息熵理论融合，以灰熵并行关联度作为衡量多目标解与理想解相似度的依据，并将其作为适应度值指导算法进化.灰熵并行关联度越大，表示当前解越接近于理想解，解的质量越好.本文以GEPA作为算法的适应度评估方法，优化目标有2个.假设种群个数为P个，则GEPA步骤总结如下：

步骤1构造理想解序列 以GA对种群实现配载面高度最低和平滑度最高的多目标并行优化，得到由2个目标函数优化值组成的理想解(参考)序列Y0={f1(0),f2(0)}.

步骤2构造比较解序列 对当代种群中的任意个体j，j∈{1,2,…,P}，分别计算2个优化目标的函数值，构成比较解序列Yj={f1(j),f2(j)}，进而得到种群的比较解序列Y={Y1,Y2,…,Yi,…,YP}.

步骤3灰关联度分析 计算群体中任意个体的灰关联度r(Y0,Yj)，j∈{1,2,…,P}.

步骤4熵值权重 计算比较解序列子目标的信息熵ei(j)和熵值权重Wj(i)，i∈{1,2}，j∈{1,2,…,P}.

借鉴文献[11]的偏随机密钥遗传算法，通过复制、交叉和变异3种操作，各产生一定比例的群体构成下一代种群，见图7.

图7 进化操作

4 实验设计与分析

4.1 算例设计

本文参照文献[1]进行算例设计，选取两艘典型客滚船作为实验对象，并分为晚间(记为N)和日间(记为D)两个场景，三种车辆均考虑多种车型，客滚船具体参数(见表1)和两个场景下的车辆比例(见表2)，车辆类型和数据均与文献[1]中应用实验相同.为表明不同滚动窗口长度H和每次决策车辆数对配载结果的影响，设置若干组滚动窗口长度H和每次决策的车辆数(H的25%、50%和75%)，见表3.为保证待配载车辆数量与实际船舱可配载车辆之间的差距较小，将文献[1]中p=0.9时确定的车辆数量作为此次实验的待配载车辆数量，并以此形成待配载车辆发生源，模拟实际客滚船配载流程.

车辆重量按实际随机生成，车辆间安全距离设为0.2 m.采用诸如A1-N-P1-S1的方式来表示不同算例，其中A1为船型；N为晚间作业场景；P1为车辆的比例；S1为决策窗口状态.每个配载决策长度下有24个算例，实验共计72个算例.

表1 实验客滚船信息

表2 实验场景及其车辆比例

表3 决策窗口设计

为测试HGA-GEPA的性能，设计人工配载启发式(Artificial Loading Heuristic，ALH)和常规HGA，将HGA-GEPA分别替换为ALH和常规HGA，作为对照组.ALH规则为：配载时先配船头和两侧，再配船舱中间位置，优先放置货车，货车留出的空隙放置小车.常规HGA的初始种群个数和迭代方式与HGA-GEPA一致，不同点在于常规HGA在迭代寻优时遵循以下规则进行群体排序：所有个体首先按照f1的值升序排列，若f1值相同，则按照f2的值升序排列，位于前10%的为精英种群.

4.2 参数设置

每个算例运行10次取平均值，HGA-GEPA和HGA的种群大小设为50，当所求最优解连续30代无改变或达到最大迭代次数100代时算法终止，精英保留率、交叉概率分别为0.1、0.7，随机生成变异个体比例为20%.延迟验收长度Q与配载决策长度H相等.GEPA方法中灰关联分析分辨系数ρ=0.5.

4.3 应用实验结果分析

以文献[1]中对应算例的算法求解结果作为动态在线问题的上界(upper bound for dynamic online problems, UBDOP).表4为在H=8下应用不同算法求解三种船型算例的结果(由于篇幅问题H=12,16略去).基于ALH的多阶段动态决策进行求解时由于单个滚动窗口决策时间太短，故此处T2不再列出.

表4 算例实验结果(H=8)

随着H的增大，三种算法求解结果均呈现上升趋势，且与UBDOP的平均gap值呈现下降趋势.主要原因在于当H增大，获取的车辆信息量增大，信息的不确定性对于船舶配载的影响减弱.随着H的增大，HGA和HGA-GEPA在整体求解时间上均有一定程度的上升.主要原因在于当H增大，决策维度明显增大，导致寻优收敛代数增加，收敛时间增加.图8为三种H下，不同算法求解24个算例的船舱整体面积利用率折线图.由图8可知：对于三种H，HGA-GEPA求解结果较ALH和HGA均具有明显的优越性，且对于同一H，其每次决策车辆数与船舱面积利用率之间无明显规律.

图8 面积利用率结果分析

对于不同的H，HGA-GEPA平均求解结果均达到90%以上，平均gap值保持在6%左右，均优于ALH和HGA，且单个决策窗口求解迅速，显示算法具有较强的适用性、实时性和鲁棒性.

5 结 束 语

文中针对客滚船配载作业的实时动态和二维装箱等特点，设计了一种滚动推进策略，构建了以各决策阶段的客滚船配载面高度最低和平滑度最高为目标函数的多目标在线配载决策模型.同时，鉴于复杂特性，设计了融合HGA-GEPA的多阶段动态决策框架对问题进行求解，以HGA-GEPA确定各决策阶段装船车辆及其配载方案.对比实验验证了模型和多阶段动态决策框架的有效性，且框架中的HGA-GEPA要优于人工配载启发式和常规HGA，可以实现配载方案的高效评估选择，得到较优的船舱面积利用率.