Optimal model and improved genetic algorithm of containership stowage on full route
-
摘要: 以集装箱船舶稳性、强度、载荷为约束条件, 以全航线倒箱量最小和吃水差最优为目标函数, 建立了集装箱船舶全航线多目标配载优化模型。利用启发式算法获得初始可行解, 利用改进了的遗传算法进行优化, 并用1 841TEU、3开口的集装箱船舶进行实例验证。计算结果表明: 与传统遗传算法相比, 改进的遗传算法能在1.967s内求得全航线上5个挂靠港口的配载计划, 并能求得5个港口的满意解; 在求得的满意解中, 船舶倒箱量均为0, 吃水差的绝对值分别为0.003 5、0.000 8、0.109 7、0.001 1、0.371 2m, 均在船舶行驶的合理范围0~0.5m内; 对于不同挂靠港数量的其他航线, 改进的遗传算法能在5s内快速获得合理的配载计划。可见, 优化模型与改进的遗传算法可行。Abstract: The stability, strength and load of containership were taken as constraint conditions, the minimum shift and the optimal trim on full route were taken as objective functions, and the multi-objective optimal model of containership stowage on full route was established.The initial feasible solution was obtained by using heuristic algorithm and was optimized by using improved genetic algorithm, and the example verification was carried out on the practical containership with capacity of 1 841 TEU and 3 hatches.Calculation result shows that by using the improved genetic algorithm, the stowage plans of 5 call ports can be obtained within 1.967 s, and the reasonable solution in each port can be obtained compared with traditional genetic algorithm.In the obtained reasonable solutions, all the shift amounts are 0, and the absolute values of trim are 0.003 5, 0.000 8, 0.109 7, 0.001 1 and 0.371 2 mrespectively, which are within a reasonable range between 0 to 0.5 m.For the other routes of call ports with different amounts, the reasonable stowage plan can be highly achieved within 5 s by using the improved genetic algorithm.So, the optimal model and improved genetic algorithm are feasible.
-
Key words:
- container transportation /
- route stowage /
- genetic algorithm /
- full route /
- trim
-
图 8 传统遗传算法与改进遗传算法优化结果比较
Figure 8. Comparison of optimal results for general GA and improved GA
-
[1] AVRIEL M, PENN M, SHPIRER N, et al. Stowage planning for container ships to reduce the number of shifts[J]. Annals of Operations Research, 1998, 76 (1): 55-71. [2] AVRIEL M, PENN M, SHPIRER N. Container ship stowage problem: complexity and connection to the coloring of circle graphs[J]. Discrete Applied Mathematics, 2000, 103 (1): 271-279. [3] WILSON I D, ROACH P A. Principles of combinatorial optimization applied to container-ship stowage planning[J]. Journal of Heuristics, 1999, 5 (4): 403-418. doi: 10.1023/A:1009680305670 [4] WILSON I D, ROACH P A. Container stowage planning: a methodology for generating computerized solutions[J]. Journal of the Operational Research Society, 2000, 51 (11): 1248-1255. doi: 10.1057/palgrave.jors.2601022 [5] WILSON I D, ROACH P A, WARE J A. Container stowage pre-planning: using search to generate solutions, a case study[J]. Knowledge-Based System, 2001, 14 (3): 137-145. [6] IMAI A, SASAKI K, NISHIMURA E, et al. Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks[J]. European Journal of Operational Research, 2006, 171 (2): 373-389. doi: 10.1016/j.ejor.2004.07.066 [7] TIERNEY K, PACINO D, JENSEN R M. On the complexity of container stowage planning problems[J]. Discrete Applied Mathematics, 2014, 169 (2): 225-230. [8] DELGADO A, JENSEN R M, JANSREUP K, et al. A constraint programming model for fast optimal stowage of container vessel bays[J]. European Journal of Operational Research, 2012, 220 (1): 251-261. doi: 10.1016/j.ejor.2012.01.028 [9] AMBROSINO D, SCIOMACHEN A, TANFANI E. Stowing a containership: the master bay plan problem[J]. Transportation Research Part A: Policy and Practice, 2004, 38 (2): 81-99. doi: 10.1016/j.tra.2003.09.002 [10] AMBROSINO D, SCIOMACHEN A, TANFANI E. A decomposition heuristics for the container ship stowage problem[J]. Journal of Heuristics, 2006, 12 (3): 211-233. doi: 10.1007/s10732-006-5905-1 [11] PACINO D, DELGADO A, JENSEN R M. Fast generation of near-optimal plans for eco-efficient stowage of large container vessels[C]//Springer. Proceedings of the Second International Conference on Computational Logistics. Berlin: Springer, 2011: 286-301. [12] JOHN A, YANG Zai-li, RIAHI R, et al. Application of a collaborative modelling and strategic fuzzy decision support system for selecting appropriate resilience strategies for seaport operations[J]. Journal of Traffic and Transportation Engineering: English Edition, 2014, 1 (3): 159-179. doi: 10.1016/S2095-7564(15)30101-X [13] SCIOMACHEN A, TANFANI E. A 3D-BPP approach for optimizing stowage plans and terminal productivity[J]. European Journal of Operational Research, 2007, 183 (3): 1433-1446. doi: 10.1016/j.ejor.2005.11.067 [14] MONACO M F, SAMMARRA M, SORRENTINO G. The terminal-oriented ship stowage planning problem[J]. European Journal of Operational Research, 2014, 239 (1): 256-265. doi: 10.1016/j.ejor.2014.05.030 [15] 孙晓雅, 林焰. 集装箱船多港Bay位排箱的优化方法[J]. 大连海事大学学报, 2011, 37 (1): 9-13. https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS201101020.htmSUN Xiao-ya, LIN Yan. Multi-port bay layout optimization method for container ships[J]. Journal of Dalian Maritime University, 2011, 37 (1): 9-13. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-DLHS201101020.htm [16] 曾庆成, 杨忠振, 陆靖. 集装箱码头同贝同步装卸调度模型与算法[J]. 交通运输工程学报, 2010, 10 (1): 88-93. doi: 10.3969/j.issn.1671-1637.2010.01.016ZENG Qing-cheng, YANG Zhong-zhen, LU Jing. Scheduling model and algorithm of integrating loading and unloading operations in same ship-bay at container terminal[J]. Journal of Traffic and Transportation Engineering, 2010, 10 (1): 88-93. (in Chinese). doi: 10.3969/j.issn.1671-1637.2010.01.016 [17] DUBROVSKY O, LEVITIN G, PENN M. A genetic algorithm with a compact solution encoding for the container ship stowage problem[J]. Journal of Heuristics, 2002, 8 (6): 585-599. doi: 10.1023/A:1020373709350 [18] 靳志宏, 兰辉, 郭贝贝. 基于现实约束的集装箱配载优化及可视化[J]. 系统工程理论与实践, 2010, 30 (9): 1722-1728. https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201009028.htmJIN Zhi-hong, LAN Hui, GUO Bei-bei. Optimization and visualization of the container loading problems with realistic constraints[J]. Systems Engineering—Theory and Practice, 2010, 30 (9): 1722-1728. (in Chinese). https://www.cnki.com.cn/Article/CJFDTOTAL-XTLL201009028.htm [19] 孙俊清, 陈忱, 刘凤连. 考虑船舶稳定性的多港口集装箱配载问题[J]. 计算机工程与应用, 2012, 48 (32): 236-243. doi: 10.3778/j.issn.1002-8331.1104-0575SUN Jun-qing, CHEN Chen, LIU Feng-lian. On stowage planning for multi-port container transportation based on stability constraint[J]. Computer Engineering and Applications, 2012, 48 (32): 236-243. (in Chinese). doi: 10.3778/j.issn.1002-8331.1104-0575 -
下载:
点击查看大图
图(8) / 表(5)
计量
- 文章访问数: 820
- HTML全文浏览量: 217
- PDF下载量: 1043
- 被引次数: 0
