集装箱船舶装箱排序问题的两阶段算法

交通运输系统工程与信息 ›› 2017, Vol. 17 ›› Issue (1): 183-190.

集装箱船舶装箱排序问题的两阶段算法

李俊，张煜*，计三有，田维

武汉理工大学物流工程学院，武汉430063

收稿日期:2016-07-12 修回日期:2016-08-25 出版日期:2017-02-25 发布日期:2017-02-27
作者简介:李俊（1989-），男，湖北钟祥人，博士生.
基金资助:
国家自然科学基金/ National Natural Science Foundation of China（71372202）.

Two-phase Algorithm for Containership Sequencing and Bin Packing Problem

LI Jun, ZHANG Yu, JI San-you, TIANWei

School of Logistics Engineering,Wuhan University of Technology,Wuhan 430063, China

Received:2016-07-12 Revised:2016-08-25 Online:2017-02-25 Published:2017-02-27

摘要/Abstract

摘要：

集装箱船舶装箱排序问题综合集装箱装船顺序与船舶贝内排箱，是一类典型的组合优化问题.考虑堆场发箱顺序和船舶配载之间的关联，构建集装箱船舶装箱排序问题的数学模型.针对构建的优化模型，鉴于已有方法难以直接对其进行求解，基于两阶段分层求解思想设计SWO-HES两阶段算法.算法第1 阶段利用吱呀轮算法(SWO)大邻域导向式搜索的特点优化集装箱装船顺序问题；第2 阶段将SWO的结果作为输入，基于启发式规则和演化策略算法(ES)构造混合演化策略算法(HES)优化船舶贝内排箱问题.最后，通过不同规模算例的研究，将SWO-HES与常见智能算法、基于实际装船规则的启发式算法进行对比分析，验证模型与算法的有效性.

关键词: 水路运输, 装箱排序, 两阶段算法, 集装箱码头, 吱呀轮算法, 演化策略算法

Abstract:

Sequencing and bin packing problem (SBPP) is a kind of typical combinatorial optimization problem including containership loading sequence problem (CLSP) and slot plan problem (SPP). The mathematical model of SBPP is established considering the relationship between CLSP and SPP. As the existing methods are hardly used to optimize SBPP, SWO-HES two-phase algorithm is designed based on the two-phase hierarchical solving method. CLSP is optimized based on the large neighborhood guiding search characteristic of squeaky wheel algorithm (SWO). Then the heuristic evolutionary strategy algorithm (HES) is designed based on evolutionary strategy (ES) and heuristic rules to optimize SPP with the result of SWO as input. Finally, through the research of different scale examples, SWO-HES is contrasted with common optimization algorithm and heuristic algorithm based on actual loading rule to verify the model and algorithm.

Key words: waterway transportation, sequencing and bin packing, two- phase algorithm, container terminal, squeaky wheel algorithm, evolutionary strategy algorithm

中图分类号:

U169.6

李俊，张煜，计三有，田维. 集装箱船舶装箱排序问题的两阶段算法[J]. 交通运输系统工程与信息, 2017, 17(1): 183-190.

LI Jun, ZHANG Yu, JI San-you, TIANWei. Two-phase Algorithm for Containership Sequencing and Bin Packing Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(1): 183-190.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract19361.shtml

http://www.tseit.org.cn/CN/Y2017/V17/I1/183

参考文献

[1] 靳志宏，兰辉，边展，等．基于现实约束的集装箱装船顺序优化[J]．大连海事大学学报，2011，37(1)：71-74. [JIN Z H, LAN H, BIAN Z, et al． Optimization on containership loading scheduling based on actual constraints[J]. Journal of Dalian Maritime University, 2011, 37(1): 71-74.]

[2] JI M J, GUO W W, ZHU H L, et al． Optimization of loading sequence and rehandling strategy for multiquay crane operations in container terminals[J]. Transportation Research Part E, 2015(80): 1-19．

[3] 祝慧灵，计明军，郭文文，等. 基于配载计划的集装箱提箱顺序和倒箱策略优化[J]. 交通运输系统工程与信息，2016，16(2)：191-199．[ZHU H L, JI M J, GUO W W, et al. Optimization of the container retrieving sequence and rehandling strategy based on stowage plan[J]．Journal of Transportation Systems Engineering and Information Technology, 2016, 16(2): 191-199.]

[4] 黎明，翟金刚．集装箱装船顺序的多目标整数规划优化模型[J]. 计算机应用研究，2012，29(10)：3636- 3639. [LI M, ZHAI J G． Multi- objective integer programming optimization model for loading sequence of container ship[J]． Application Research of Computers, 2012, 29(10): 3636-3639．]

[5] DELGADO A, JENSEN R M, JANSTRUP K, et al． A constraint programming model for fast optimal stowage of container vessel bays[J]. European Journal of Operational Research, 2012(220): 251-261．

[6] MONACO M F, SAMMARRA M, SORRENTINO G． The terminal-oriented ship stowage planning problems[J]. European Journal of Operational Research, 2014(239): 256-265．

[7] DING D, CHOU M C． Stowage planning for container ships：A heuristic algorithm to reduce the number of shifts[J]. European Journal of Operational Research, 2015(246): 242-249．

[8] 祝慧灵，计明军．集装箱船舶全航线配载优化模型与改进遗传算法[J]. 交通运输工程学报，2014, 14 (5)：59- 67. [ZHU H L, JI M J． Optimal model and improved genetic algorithm of containership stowage on full route[J]. Journal of Traffic and Transportation Engineering, 2014, 14(5): 59-67.]

[9] ØVSTEBØ B O, HVATTUM L M, FAGERHOLT K. Optimization of stowage plans for RoRo ships[J]. Computers & Operations Research, 2011(38): 1425- 1434．

[10] UMANG N, BIERLAIRE M, VACCA I． Exact and heuristic methods to solve the berth allocation problem in bulk ports[J]．Transportation Research Part E, 2013 (54): 14-31．

[1]	许波桅, 王玲玲, 李军军. 自动化码头多级作业超网络延误传导特性研究[J]. 交通运输系统工程与信息, 2022, 22(2): 280-289.
[2]	廖诗管, 翁金贤, 胡甚平. 液化天然气船通航模式下的航道通过能力评价方法[J]. 交通运输系统工程与信息, 2022, 22(2): 290-297.
[3]	靳志宏, 焉红, 王小寒, 邢磊, 徐奇. 滚装甩挂运输牵引车调度优化及作业模式类比分析[J]. 交通运输系统工程与信息, 2022, 22(1): 142-151.
[4]	李德昌, 杨华龙, 赵帅奇, 郑建风. 排放控制区下集装箱班轮运输船期设计与燃油补给联合优化[J]. 交通运输系统工程与信息, 2022, 22(1): 273-281.
[5]	邵斐, 张永锋, 真虹. 中国进口铁矿石海运网络抗毁性仿真[J]. 交通运输系统工程与信息, 2022, 22(1): 311-321.
[6]	彭子烜, 于滨. 内外贸同船运输下长江经济带穿梭巴士网络优化[J]. 交通运输系统工程与信息, 2022, 22(1): 322-331.
[7]	杨华龙, 赵帅奇, 方旭, 段静茹. 考虑海上意外时间和合作协议的班轮运输船期设计鲁棒优化[J]. 交通运输系统工程与信息, 2021, 21(6): 210-216.
[8]	严新平, 李晨, 刘佳仑, 游旭, 王树武, 马枫. 新一代航运系统体系架构与关键技术研究[J]. 交通运输系统工程与信息, 2021, 21(5): 22-29.
[9]	葛颖恩, 温馨. 环境可持续集装箱班轮运输管理研究综述[J]. 交通运输系统工程与信息, 2021, 21(4): 6-22.
[10]	楚金华, 李俊鹤, 王春娟, 陈超. 排放控制区下集装箱班轮航线路径规划与航速调度集成决策[J]. 交通运输系统工程与信息, 2021, 21(4): 230-238.
[11]	戈佳威, 袁克镖, 殷明, 王学锋. 传播动力学视角下集装箱海运网络关键港口节点识别[J]. 交通运输系统工程与信息, 2021, 21(4): 256-262.
[12]	戈艳艳，王姗姗. 考虑碳排放的港口全要素生产率及影响因素分析[J]. 交通运输系统工程与信息, 2021, 21(2): 22-29.
[13]	廖诗管，杨冬，白茜文，翁金贤. 基于船舶大数据的港口装卸效率值计算方法[J]. 交通运输系统工程与信息, 2021, 21(2): 217-223.
[14]	高天航，徐力，靳廉洁，葛彪. 考虑航艏向与数据变化差异的船舶轨迹预测[J]. 交通运输系统工程与信息, 2021, 21(1): 90-94.
[15]	房斯明，刘正江，封室丞，王新建. 船舶倾斜对不同行人流疏散效率影响的数值分析[J]. 交通运输系统工程与信息, 2021, 21(1): 201-206.