Ship stowage optimization centered on automated terminal

doi:10.11772/j.issn.1001-9081.2020121897

Abstract

Abstract:

Aiming at the low efficiency of ship stowage in automated terminals， a new Fixed Set Search （FSS） algorithm based on ship stowage characteristics was proposed in order to improve the utilization of equipment resources. Firstly， on the basis of considering the general principles of ship stowage， by introducing the block operation balance factor and taking the minimization of the number of rehandles and total loading on board time with as much block operation balance as possible as the objectives， a mixed integer programming model of ship stowage in automated terminals was established based on the quay crane working plan. Then， the optimal solution was searched by fixing the elements that appeared repeatedly in the better solutions. Experimental results show that， under the instances with different scales， compared with Cplex， the proposed FSS algorithm has the rehandle number and unbalanced container number reduced by 22.3% and 11.7% on average respectively， and the objective function value optimized by 6.5% on average.Compared with the Particle Swarm Optimization （PSO） algorithm， Genetic Algorithm （GA） and Ant Colony Optimization （ACO） algorithm， the proposed FSS algorithm has the objective function value optimized by 2.1% on average， highlighting the higher stowage efficiency of the FSS algorithm. In order to increase the diversity of instances， the distribution and proportion of block stacks were adjusted. Under this circumstance， compared with the above three algorithms， the FSS algorithm has the number of unbalanced containers reduced by 19.3% on average， and has higher utilization of equipment resources.

Key words: automated terminal, ship stowage, block operation balance, rehandle, Fixed Set Search (FFS)

摘要：

针对自动化码头船舶配载效率较低的问题，为了提高设备资源利用率，提出了一种基于船舶配载特点设计的固定集搜索（FSS）算法。首先，在考虑一般船舶配载原则的基础上，以桥吊作业计划为依据，引入箱区作业均衡因素，将最小化箱区翻箱量、总装船时间以及尽可能的箱区作业均衡作为目标，建立自动化码头船舶配载混合整数规划模型；其次，通过固定较优解中多次出现的元素来寻求最优解。实验结果表明，不同规模的实例下，FSS算法相较于Cplex，翻箱量和不均衡箱数分别平均减少了22.3%和11.7%，目标函数值平均优化了6.5%；所提固定集搜索算法与粒子群优化（PSO）算法、遗传算法（GA）和蚁群优化（PSO）算法相比，目标函数值平均优化了2.1%，凸显了FSS算法更高的配载效率。而为了增加案例的多样性，对箱区堆栈分布和比例进行了调整。在这个情况下，FSS算法的不均衡箱数相较上述三种算法平均减少了19.3%，设备资源利用率更高。

关键词: 自动化码头, 船舶配载, 箱区作业均衡, 翻箱, 固定集搜索

CLC Number:

TP391.9

Yi DING, Cong WANG. Ship stowage optimization centered on automated terminal[J]. Journal of Computer Applications, 2021, 41(11): 3385-3393.

丁一, 王聪. 以自动化码头为中心的船舶配载优化[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3385-3393.

Figures/Tables 17

References 16

1	计明军，曲田.集装箱船舶配载策略的比较分析［J］.航海技术，2012（1）：28-32. 10.3969/j.issn.1006-1738.2012.01.011
	JI M J， QU T. Comparison and analysis of the ways of container ship stowage ［J］. Marine Technology， 2012（1）： 28-32. 10.3969/j.issn.1006-1738.2012.01.011
2	乐美龙，洪严.考虑桥吊工作时间和翻箱次数的配载［J］.系统工程，2014，32（7）：87-93.
	YUE M L， HONG Y. Containership stowage considering rehandles and crane working time ［J］. Systems Engineering， 2014， 32（7）： 87-93.
3	SERBAN D， CARP D. Optimization of container stowage in a yard block using a genetic algorithm ［J］. Studies in Informatics and Control， 2016， 25（1）： 123-130. 10.24846/v25i1y201613
4	田维，张煜，程惠敏.船舶实配现实约束下的装箱排序问题研究［J］.武汉理工大学学报（交通科学与工程版），2016，40（3）：509-513. 10.3963/j.issn.2095-3844.2016.03.024
	TIAN W， ZHANG Y， CHENG H M. Research on sequencing and bin packing problem with practical vessel stowage constraints ［J］. Journal of Wuhan University of Technology （Transportation Science and Engineering）， 2016， 40（3）： 509-513. 10.3963/j.issn.2095-3844.2016.03.024
5	ROBERTI R， PACINO D. A decomposition method for finding optimal container stowage plans ［J］. Transportation Science， 2018， 52（6）： 1444-1462. 10.1287/trsc.2017.0795
6	WANG D D. Dynamic optimization model of container route loading for international logistics ships ［J］. Journal of Coastal Research， 2019， 93（sp1）： 1111-1116. 10.2112/si93-161.1
7	郑斐峰，蒋娟，梅启煌.最小化集装箱运输成本的配载优化［J］.计算机科学，2019，46（6）：239-245. 10.11896/j.issn.1002-137X.2019.06.036
	ZHENG F F， JIANG J， MEI Q H. Study on stowage optimization in minimum container transportation cost ［J］. Computer Science， 2019， 46（6）： 239-245. 10.11896/j.issn.1002-137X.2019.06.036
8	黄森佳，姜桂艳，张露.基于集装箱倒箱和岸桥作业均衡的集装箱船配载优化［J］.宁波大学学报（理工版），2019，32（4）：109-114. 10.3969/j.issn.1001-5132.2019.04.018
	HUANG S J， JIANG G Y， ZHANG L. Optimization of container ship stowage based on container re-handling and balanced operation of quay crane ［J］. Journal of Ningbo University （Natural Science and Engineering Edition）， 2019， 32（4）： 109-114. 10.3969/j.issn.1001-5132.2019.04.018
9	孙俊清，陈忱，刘凤莲.考虑船舶稳定性的多港口集装箱配载问题［J］.计算机工程与应用，2012，48（32）：236-243. 10.3778/j.issn.1002-8331.1104-0575
	SUN J Q， CHEN C， LIU F L. On stowage planning for multi-port container transportation based on stability constrain ［J］. Computer Engineering and Applications， 2012， 48（32）： 236-243. 10.3778/j.issn.1002-8331.1104-0575
10	黎明，翟金刚.集装箱装船顺序的多目标整数规划优化模型［J］.计算机应用研究，2012，29（10）：3636-3639. 10.3969/j.issn.1001-3695.2012.10.009
	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. 10.3969/j.issn.1001-3695.2012.10.009
11	张兆民.基于船舶最少作业时间的集装箱码头操作策略［J］.港口科技，2015（3）：42-46. 10.3969/j.issn.1673-6826.2015.03.013
	ZHENG Z M. Strategy of shortest operating time in container terminal ［J］. Science and Technology of Ports， 2015（3）： 42-46. 10.3969/j.issn.1673-6826.2015.03.013
12	祝慧灵，计明军，郭文文，等.基于配载计划的集装箱提箱顺序和倒箱策略优化［J］.交通运输系统工程与信息，2016，16（2）：191-199. 10.3969/j.issn.1009-6744.2016.02.030
	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. 10.3969/j.issn.1009-6744.2016.02.030
13	ZHAO N， GUO Y C， XIANG T Y， et al. Container ship stowage based on monte Carlo tree search ［J］. Journal of Coastal Research， 2018， 83（sp1）： 540-547. 10.2112/si83-090.1
14	李隋凯，励益韬，孙未未，等.一种自动化集装箱码头出口箱进箱选位算法［J］.计算机工程，2019，45（5）：272-278，284. 10.19678/j.issn.1000-3428.0050566
	LI S K， LI Y T， SUN W W， et al. A storage space allocation algorithm for export containers in automated container terminal ［J］. Computer Engineering， 2019， 45（5）： 272-278， 284. 10.19678/j.issn.1000-3428.0050566
15	周宇涛，宋海涛，王吉升，等.集装箱自动化码头配载系统应用［J］.水运工程，2019（10）：21-25. 10.3969/j.issn.1002-4972.2019.10.004
	ZHOU Y T， SONG H T， WANG J S， et al. Application of auto-stow system in Qingdao automated container terminal ［J］. Port and Waterway Engineering， 2019（10）： 21-25. 10.3969/j.issn.1002-4972.2019.10.004
16	LU Q K， HERMANS T. Modeling grasp type improves learning-based grasp planning ［J］. IEEE Robotics and Automation Letters， 2019， 4（2）： 784-791. 10.1109/lra.2019.2893410

角度	文献来源	考虑因素	模型	方法
船公司	文献［1］	船舶稳性、强度、吃水差和倒箱率	无	比较研究了四种配载方式
	文献［2］	翻箱次数和桥吊的工作时间	整数规划模型	启发式算法和遗传算法
	文献［3］	船舶靠泊时间	多目标规划模型	遗传算法
	文献［4］	装船时间以及翻倒箱时间	多目标规划模型	分支定界
	文献［5］	装卸集装箱的时间	混合整数规划模型	启发式和精确定价算法
	文献［6］	航线动态分配	回归模型	定量回归分析和仿真
	文献［7］	翻箱费用和堆栈使用费用	混合整数规划模型	Cplex、遗传和贪婪算法
	文献［8］	装船作业时间、岸桥均衡	多目标规划模型	遗传算法
	文献［9］	船舶稳性、倒箱数量	0-1规划数学模型	改进遗传算法
码头	文献［10］	堆场翻箱率、船舶稳性	多目标规划模型	粒子群算法
	文献［11］	装船时间	无	分级堆场堆存策略
	文献［12］	翻箱量	3种倒箱策略下的提箱顺序模型	遗传算法
	文献［13］	堆场周转、轮胎吊跨箱区作业和轮胎吊移动	多目标优化模型	蒙特卡洛树搜索
	文献［14］	翻箱量	状态转移模型	动态规划和遗传算法
	文献［15］	翻箱率和配载时间	无	逻辑算法和配载策略

角度	文献来源	考虑因素	模型	方法
船公司	文献［1］	船舶稳性、强度、吃水差和倒箱率	无	比较研究了四种配载方式
	文献［2］	翻箱次数和桥吊的工作时间	整数规划模型	启发式算法和遗传算法
	文献［3］	船舶靠泊时间	多目标规划模型	遗传算法
	文献［4］	装船时间以及翻倒箱时间	多目标规划模型	分支定界
	文献［5］	装卸集装箱的时间	混合整数规划模型	启发式和精确定价算法
	文献［6］	航线动态分配	回归模型	定量回归分析和仿真
	文献［7］	翻箱费用和堆栈使用费用	混合整数规划模型	Cplex、遗传和贪婪算法
	文献［8］	装船作业时间、岸桥均衡	多目标规划模型	遗传算法
	文献［9］	船舶稳性、倒箱数量	0-1规划数学模型	改进遗传算法
码头	文献［10］	堆场翻箱率、船舶稳性	多目标规划模型	粒子群算法
	文献［11］	装船时间	无	分级堆场堆存策略
	文献［12］	翻箱量	3种倒箱策略下的提箱顺序模型	遗传算法
	文献［13］	堆场周转、轮胎吊跨箱区作业和轮胎吊移动	多目标优化模型	蒙特卡洛树搜索
	文献［14］	翻箱量	状态转移模型	动态规划和遗传算法
	文献［15］	翻箱率和配载时间	无	逻辑算法和配载策略

实例	箱量	箱区数	LD	RU	2D/%	3D/%
A1	100	6	（1 132，313）	（3 712，703）	31	16
A2	200	9	（810，237）	（3 613，696）	11	24
A3	300	14	（721，211）	（3 511，731）	29	26
A4	400	19	（511，176）	（3 413，652）	33	22
A5	500	23	（172，116）	（2 891，631）	21	15
A6	600	26	（121，157）	（3 291，781）	27	17

实例	箱量	箱区数	LD	RU	2D/%	3D/%
A1	100	6	（1 132，313）	（3 712，703）	31	16
A2	200	9	（810，237）	（3 613，696）	11	24
A3	300	14	（721，211）	（3 511，731）	29	26
A4	400	19	（511，176）	（3 413，652）	33	22
A5	500	23	（172，116）	（2 891，631）	21	15
A6	600	26	（121，157）	（3 291，781）	27	17

实例		目标函数值（/min）		翻箱次数		不均衡箱数		求解时间/s
序号	箱量	Cplex	FSS	Cplex	FSS	Cplex	FSS	Cplex	FSS
A1	100	396	354	11	5	22	19	178.1	18.7
A2	200	781	707	19	14	36	34	391.5	31.3
A3	300	1 151	1 091	42	36	47	42	881.8	69.7
A4	400	1 538	1 479	61	57	59	53	1 791.8	116.9
A5	500	1 892	1 829	73	66	70	57	2 589.8	132.2
A6	600	—	2 218	—	83	—	59	—	161.6