(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210922452.X (22)申请日 2022.08.02 (71)申请人 上海交通大 学 地址 200240 上海市闵行区东川路80 0号 申请人 上海国际港务 （集团） 股份有限公司 (72)发明人 张战罗　李维廉　朱霁月　王无印　 秦威　方怀瑾　邹鹰　凌强　田宇　 杨靖培　 (74)专利代理 机构 上海交达专利事务所 31201 专利代理师 王毓理　王锡麟 (51)Int.Cl. G06Q 10/02(2012.01) G06Q 10/06(2012.01) G06Q 50/26(2012.01) G06F 30/20(2020.01)G06F 111/04(2020.01) (54)发明名称 基于动态规划的集装箱船舶配载箱位预留 方法 (57)摘要 一种基于动态规划的集装箱船舶配载箱位 预留方法， 根据集装箱码头约束建立港口箱位预 留模型， 使用基于动态规划的整列寻优算法， 得 到动态规划状态表和标记表后， 使用方案搜索算 法得若干不重复的箱位预留方案， 最后根据方案 评价函数计算出最优箱位预留方案。 本发明能有 效减少配载需耗费的时间， 也可以在评估方案前 快速给出可行的方案。 后经过评估 给出符合业务 的最佳箱位预留方案， 减少由人工因素带来的影 响。 权利要求书3页 说明书5页 附图4页 CN 115271140 A 2022.11.01 CN 115271140 A 1.一种基于动态规划的整列寻优的集装箱码头船舶配载优化方法， 其特征在于， 根据 集装箱码头约束建立港口箱位预留模型， 使用基于动态规划的整列寻优算法， 得到动态规 划状态表和标记表后， 使用方案搜索算法得若干不重复的箱位预留方案， 最后根据方案评 价函数计算出最优箱位预留方案； 所述的集装箱码头约束包括： ①集装箱只 能预留在对应属性组的箱位； ②优先按照整 列预留箱 位， 考虑重量的合理分布， 并且保证所留列总数最少； ③箱位预留应考虑船体的平 衡， 减少大批量预留在船的同一侧； ④特种箱下方不能进行箱 位预留；⑤预留的箱 位上方箱 位不可用于放关箱选位； ⑥箱位预留应考虑集装箱尺寸及轻重的合理分配， 其中： 约束 ①、 约束④及约束⑤为必须满足， 其他则作为评价箱 位预留方案优劣的指标， 包括约束 ②、 约束 ③及约束⑥； 所述的港口箱位预留模型包括： 表征所预留列数之和、 预留数与总箱位数差值f1及预留重箱数f2与总重箱数差值f3的 总和的目标函数min  f＝f1+f2+f3， 其中： 即带权重α1的预留列之和； 即带权重α2的箱位预留数与需要预留数之差； 即带权重α3的重箱箱位预留数与需要预留重箱数之差； 约束条件 即预留的箱位数应不小于需要预留的箱 位数量且预留的重箱箱位数应不小于需要预留的重箱箱位数量， αm为函数fm的权重， N为需 要预留的箱位数， NH为需要预留的重箱箱位数， si为可配箱位集合中第i列的可配箱位数， 为可配箱 位集合中第i列的可配重箱箱 位数， S＝{s1,s2,s3,…,si}为可配箱 位集合， 通过 i索引， 为可配重箱 箱位集合， 通过i索引， 2.根据权利要求1所述的基于动态规划的整列寻优的集装箱码头船舶配载优化方法， 其特征是， 所述的基于动态规划的整列寻优算法， 采用动态规划方法计算给定箱位在给定 的预留数 下考虑整列预留的搜索结果， 具体包括： 步骤1： 输入属性组可配箱位 集合S(共n个非零项)、 箱位预留数m； 步骤2： 创建状态 矩阵V、 状态标记fla g， i＝0,1,2, …,m， j＝0,1,2, …,n； 步骤3： 初始化V， flag， 对于i＝0且j＝0， 令V(i,j)＝0， flag(i,j)＝0； 对于i≠0且j＝ 0， 令V(i， j)＝ ‑1000代表不存在可 行方案， fla g(i， j)＝0； 步骤4： j从1到n， i从0到m， 计算V： 1)当选定S中的前j列， 其总数比当前预留数i小， 则V (i， j)赋值为 ‑1000； 2)当选取第 j列或第j列与前面的几列作为预留方案， 比当前预留数i多 出a个箱位， 则V(i， j)赋值为 ‑a； 3)当选取第j列或第j列与前面的几列作为预留方案， 且可 配箱位数量之和正 好等于当前 预留数i， 则V(i， j)赋值 为0； 步骤5： 计算fla g， 当V(i， j)的值 不是由V(i， j ‑1)得到时， 标记为0， 否则为1； 步骤6： 返回状态 矩阵V及状态标记fla g。 3.根据权利要求1所述的基于动态规划的整列寻优的集装箱码头船舶配载优化方法，权　利　要　求　书 1/3 页 2 CN 115271140 A 2其特征是， 所述的基于动态规划的整列寻优算法中： 所述的动态规划状态表V为一个(m+1) ×(n+1)的矩阵， V中的数值表示出当前是否有满 足优化目标的方案， 其中每个元素V(i， j)记录在箱 位预留数为i时， 选取S中的前j列中的几 列作为预留方案时的状态， 该状态包括： ①‑1000： 说明在当前预留数i的情况下， 即使选定S中的前j列， 其总数也比预留数小， 说明当前不存在可 行方案； ②负数a小于0， 大于 ‑max(S)： 说明在当前预留数i的情况下， 当选取第j列或者第j列与 前面的几列 作为预留方案， 则多出a个箱位； ③0： 说明在当前预留数i的情况下， 当选取第j列或者第j列与前面的几列作为预留方 案， 则这几列的可配箱位数量之和正 好等于i； 所述的标记表fl ag是一个大小与V一致的矩阵， 其取值为0或1， 与V的每个值相对应， 作 为标记， 当V(i， j)的值 不是由V(i， j ‑1)得到时， 则标记为0， 否则为1。 4.根据权利要求1所述的基于动态规划的整列寻优的集装箱码头船舶配载优化方法， 其特征是， 所述的方案搜索算法， 结合标记表搜索状态表获得若干不重复的箱 位预留方案， 具体包括： 步骤1： 输入状态 矩阵V、 状态标记fla g、 属性组可配箱位 集合S、 箱位预留数m； 步骤2： 初始化预留方案Planall， 表示预留数为m的部分较优预留方案集 合； 步骤3： 初始化plancurr， 为一个1×n的0数组； 步骤4： 在状态 表中与预留数对应的行寻找状态为0的列， 并添加到Planall； 步骤5： 重复步骤3、 4， 直至 搜索完所有方案， 得到较优箱位预留方案Planall； 步骤6： 返回预留数为m的较优箱位预留方案Planall。 5.根据权利要求1所述的基于动态规划的整列寻优的集装箱码头船舶配载优化方法， 其特征是， 所述的方案评价函数， 考虑约束 ②、 约束③及约束⑥的方案打分并计算出最优箱 位预留方案， 其中方案评价函数f＝f4+f5+f6， 其中： f4为对方案所提供预留箱位数和方案所 使用列数进行评分， f5为对方案所能提供重箱数量进行评分， f6为对方案采用的列在甲板上下的情况进行评分， α4、 α5、 α6分别表示f4、 f5、 f6在适应度中的权重， β 为箱位预留数系数 (0＜β ＜1)， 为在属性组j的可配箱位集合Sj中， 第i列被选为预留的箱位数， nj为属性 组j需要预留的箱位数； 因此当所预留的箱位数与需要预留的箱位数越接近时， f4得分越 大； ω为重箱箱位预留系数(0＜ω＜1)， 为在属性组j的可配箱位集合Sj中， 第i列被 选为预留的重箱箱 位数， 示属性组j的未放关箱中的重箱数量； 因此当所预留的重箱箱 位 数与对应属性组未放关箱中的重箱数量越接近时， f5得分越大； Q1和Q2分别为所预留箱 位在 甲板上和舱内的系数且Q1＞Q2； 和 分别为在属性组j的可配箱位集合Sj中， 第i 列甲板上和舱内被选为预留的箱位数， 和 分别为第i列甲板上和舱内的可配箱位数； 因此当所 预留箱位中， 为甲板上的箱位占比更 大时时， f6得分越高。 6.根据权利要求5所述的基于动态规划的整列寻优的集装箱码头船舶配载优化方法，权　利　要　求　书 2/3 页 3 CN 115271140 A 3