基于计算物流和群集智能的多集装箱码头泊位分配

doi:10.3778/j.issn.1002-8331.2304-0278

摘要/Abstract

摘要： 以港口运营方统一整合多集装箱码头作业空间资源为背景，探讨了考虑泊位水深约束和出口集装箱可转港作业的多码头动态连续泊位分配问题（multi-terminal dynamic and continuous berth allocation problem，MDC-BAP）。基于计算物流将MDC-BAP抽象为异构多背包问题进行运筹建模，建立了同时考虑港航双方作业总成本最小化的混合整数规划模型，进而设计了一类融合计算物流和群集智能的二阶段改进帝国竞争算法（two-stage improved imperialist competitive algorithm，TSI-ICA）对模型进行求解。采用三种计划周期12个大规模MDC-BAP算例执行数值实验，比较了多种改进帝国竞争算法和多种启发式规则在MDC-BAP模型上的综合求解性能，TSI-ICA设计的“元启发式算法+启发式规则”框架在大规模算例上的表现明显优于“启发式规则+启发式规则”的资源分配模式，并从运作成本和运营韧性两方面阐明了多码头协同生产优于单码头独立作业模式，从而为多集装箱码头泊位协同分配提供了较好的智能决策支持解决方案。

关键词: 多集装箱码头, 泊位分配问题, 联合生产运营, 异构多背包问题, 计算物流, 帝国竞争算法, 排队论

Abstract: Based on the integration and synergy of multiple container terminal operating space resources by port operators, this paper makes an in-depth discussion on the multi-terminal dynamic and continuous berth allocation problem（MDC-BAP） by considering berth depth constraint and export container transferable operations. The MDC-BAP is abstracted as a heterogeneous multiple knapsack problem for operation modelling by computational logistics, and then a mixed integer linear programming model is established to minimize the total running cost of both sides of port and shipping. Subsequently, a kind of two-stage improved imperialist competitive algorithm（TSI-ICA） is designed to solve the MDC-BAP model by the integration of computational logistics and swarm intelligence. Finally, the numerical experiments of twelve large-scale MDC-BAP examples in three planning periods are executed intensively, and the comprehensive solving performance of diversiform improved imperialist competitive algorithms and multifarious heuristic rules on the MDC-BAP model are compared and analyzed. The computing framework of “meta-heuristic algorithm + heuristic rule” designed by TSI-ICA is obviously superior to the resource allocation mode of “heuristic rule + heuristic rule” on large-scale examples. Moreover, it illustrates that multi-terminal cooperative production is superior to single-terminal independent service mode from two aspects of operating costs and running toughness. Consequently, it provides a favorable intelligent decision support solution for collaborative berth allocation of multiple container terminals.

Key words: multiple container terminal, berth allocation problem, joint production and operation, heterogeneous multiple knapsack problem, computational logistics, imperialist competitive algorithm, queuing theory

李斌, 唐志斌. 基于计算物流和群集智能的多集装箱码头泊位分配[J]. 计算机工程与应用, 2023, 59(16): 262-284.

LI Bin, TANG Zhibin. Multi-Container Terminal Berth Allocation Based on Computational Logistics and Swarm Intelligence[J]. Computer Engineering and Applications, 2023, 59(16): 262-284.

参考文献

[1] LEE C Y，SONG D P.Ocean container transport in global supply chains：overview and research opportunities[J].Transportation Research Part B：Methodological，2017，95：442-474.
[2] 王帆，黄锦佳，刘作仪.港口管理与运营：新兴研究热点及其进展[J].管理科学学报，2017，20（5）：111-126.
WANG F，HUANG J J，LIU Z Y.Port management and operations：emerging research topics and progress[J].Journal of Management Sciences in China，2017，20（5）：111-126.
[3] 常祎妹，朱晓宁，王力.集装箱码头集成调度研究综述[J].交通运输工程学报，2019，19（1）：136-146.
CHANG Y M，ZHU X N，WANG L.Review on integrated scheduling of container terminals[J].Journal of Traffic and Transportation Engineering，2019，19（1）：136-146.
[4] WEERASINGHE B A，PERERA N H，BAI X W.Optimizing container terminal operations：a systematic review of operations research applications[J].Maritime Economics & Logistics，2023.DOI：10.1057/s41278-023-00254-0.
[5] RAEESI R，SAHEBJAMNIA N，MANSOURI S A.The synergistic effect of operational research and big data analytics in greening container terminal operations：a review and future directions[J].European Journal of Operational Research，2023，310（3）：943-973.
[6] HENDRIKS M P M，ARMBRUSTER D，LAUMANNS M，et al.Strategic allocation of cyclically calling vessels for multi-terminal container operators[J].Flexible Services and Manufacturing Journal，2012，24（3）：248-273.
[7] 徐亚，杜玉泉，龙磊.支持多码头协调运作的泊位调度模型和算法[J].系统工程，2015，33（1）：128-138.
XU Y，DU Y Q，LONG L.Berth scheduling models and algorithm for coordinated operation of multiple container terminals in a port[J].Systems Engineering，2015，33（1）：128-138.
[8] LEE D H，JIN J G，CHEN J H.Terminal and yard allocation problem for a container transshipment hub with multiple terminals[J].Transportation Research Part E：Logistics and Transportation Review，2012，48：516-528.
[9] TAN C M，HE J L，YU H.Mathematical modeling of yard template regeneration for multiple container terminals[J].Advanced Engineering Informatics，2019，40：58-68.
[10] HU X Y，LIANG C J，CHANG D F，et al.Container storage space assignment problem in two terminals with the consideration of yard sharing[J].Advanced Engineering Informatics，2021，47：101224.
[11] TAO J H，QIU Y Z.A simulation optimization method for vehicles dispatching among multiple container terminals[J].Expert Systems with Applications，2015，42（7）：3742-3750.
[12] 范厚明，郭振峰，李阳.考虑碳排放和预约机制的送箱集卡多码头调度问题[J].同济大学学报（自然科学版），2018，46（9）：1241-1252.
FAN H M，GUO Z F，LI Y.Truck scheduling in delivering containers from an outside yard to multiple container terminals considering carbon emission and the truck appointment system[J].Journal of Tongji University（Natural Science），2018，46（9）：1241-1252.
[13] SCHEPLER X，BALEV S F，MICHEL S，et al.Global planning in a multi-terminal and multi-modal maritime container port[J].Transportation Research Part E：Logistics and Transportation Review，2017，100：38-62.
[14] GHAREHGOZLI A H，KOSTER R D，JANSEN R.Collaborative solutions for inter terminal transport[J].International Journal of Production Research，2017，55（21）：6527-6546.
[15] 丁一，何乐媚，沙梅.基于时空拓展图模型的多码头间集装箱运输优化[J].中国航海，2021，44（1）：81-87.
DING Y，HE L M，SHA M.Optimization of inter-terminal container transportation with space-time expansion graph model[J].Navigation of China，2021，44（1）：81-87.
[16] LI B.Container terminal logistics scheduling and decision-making within the conceptual framework of computational thinking[C]//Proceedings of the 54th IEEE Annual Conference on Decision and Control，Osaka，2015：330-337.
[17] 李斌.集装箱码头作业系统层次化、并行、异构与可重构计算模型[J].交通运输工程学报，2019，19（2）：136-155.
LI B.Hierarchical，parallel，heterogeneous and reconfigurable computation model of container terminal handling system[J].Journal of Traffic and Transportation Engineering，2019，19（2）：136-155.
[18] TANG J，LIU G，PAN Q T.A review on representative swarm intelligence algorithms for solving optimization problems：applications and trends[J].IEEE/CAA Journal of Automatica Sinica，2021，8（10）：1627-1643.
[19] 顾清华，徐青松，李学现.基于距离优势关系的高维多目标进化算法[J].计算机科学与探索，2022，16（11）：2642-2652.
GU Q H，XU Q S，LI X X.Many-objective evolutionary algorithm based on distance dominance relation[J].Journal of Frontiers of Computer Science and Technology，2022，16（11）：2642-2652.
[20] 李珺，段钰蓉，郝丽艳，等.混合优化算法求解同时送取货车辆路径问题[J].计算机科学与探索，2022，16（7）：1623-1632.
LI J，DUAN Y R，HAO L Y，et al.Hybrid optimization algorithm for vehicle routing problem with simultaneous delivery-pickup[J].Journal of Frontiers of Computer Science and Technology，2022，16（7）：1623-1632.
[21] 董明望，黄麟富，辜勇.集装箱码头绿色作业调度优化研究综述[J].重庆交通大学学报（自然科学版），2022，41（11）：7-14.
DONG M W，HUANG L F，GU Y.Review on green job scheduling optimization of container terminals[J].Journal of Chongqing Jiaotong University（Natural Science），2022，41（11）：7-14.
[22] PARK H J，CHO S W，LEE C.Particle swarm optimization algorithm with time buffer insertion for robust berth scheduling[J].Computers & Industrial Engineering，2021，160：107585.
[23] CHEN S M，ZENG Q C，LI Y T.Integrated operations planning in highly electrified container terminals considering time-of-use tariffs[J].Transportation Research Part E：Logistics and Transportation Review，2023，171：103034.
[24] 李丹.改进群智能优化算法的海上物流配送路径优化方法[J].舰船科学技术，2020，42（8A）：184-186.
LI D.Optimization method of marine logistics distribution path based on improved swarm intelligence optimization algorithm[J].Ship Science and Technology，2020，42（8A）：184-186.
[25] 李斌，黄起彬.面向资源约束项目调度的二阶段帝国竞争算法[J/OL].计算机科学与探索[2023-03-12].http：//kns.cnki.net/kcms/detail/11.5602.TP.20221124.0931.004.html.
LI B，HUANG Q B.Two-stage imperialist competitive algorithm oriented resource-constrained project scheduling problem[J/OL].Journal of Frontiers of Computer Science and Technology[2023-03-12].http：//kns.cnki.net/kcms/detail/11.5602.TP.20221124.0931.004.html.
[26] 李斌，唐志斌.面向异构多背包问题的多级二进制帝国竞争算法[J].计算机应用，2022.DOI：10.11772/j.issn.1001-9081.2022081189.
LI B，TANG Z B.Multiple binary imperialist competitive algorithm for solving heterogeneous multiple knapsack problem[J].Journal of Computer Applications，2022.DOI：10.11772/j.issn.1001-9081.2022081189.
[27] DENNING P J，MARTELL C H.Great principles of computing[M].Cambridge：MIT Press，2015：19-28.
[28] IMAI A，NISHIMURA E，PAPADIMITRIOU S.The dynamic berth allocation problem for a container port[J].Transportation Research Part B：Methodological，2001，35（4）：401-417.
[29] GUO L M，ZHENG J F，LIANG J P，et al.Column generation for the multi-port berth allocation problem with port cooperation stability[J].Transportation Research Part B：Methodological，2023，171：3-28.
[30] 薛松.集装箱港区多码头整合下泊位-岸桥集成调度研究[D].大连：大连海事大学，2020.
XUE S.Study on collaborative scheduling of berths and quay cranes under the integration of multiple quays in single container port area[D].Dalian：Dalian Maritime University，2020.
[31] 周鹏飞，康海贵.面向随机环境的集装箱码头泊位-岸桥分配方法[J].系统工程理论与实践，2008，28（1）：161-169.
ZHOU P F，KANG H G.Study on berth and quay-crane allocation under stochastic environments in container terminal[J].Systems Engineering-Theory & Practice，2008，28（1）：161-169.
[32] ATASHPAZ-GARGARI E，LUCAS C.Imperialist competitive algorithm：an algorithm for optimization inspired by imperialistic competition[C]//Proceedings of the 2007 IEEE Congress on Evolutionary Computation，Singapore，Sep 25-28，2007.Piscataway：IEEE，2007：4661-4667.
[33] LI D S，ZHANG C Y，TIAN G D.Multiobjective program and hybrid imperialist competitive algorithm for the mixed-model two-sided assembly lines subject to multiple constraints[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2018，48（1）：119-129.
[34] 贺毅朝，王熙照，赵书良，等.基于编码转换的离散演化算法设计与应用[J].软件学报，2018，29（9）：2580-2594.
HE Y C，WANG X Z，ZHAO S L.Design and application of discrete evolutionary algorithm based on encoding transformation[J].Journal of Software，2018，29（9）：2580-2594.
[35] 杨小东，康雁，柳青，等.求解作业车间调度问题的混合帝国主义竞争算法[J].计算机应用，2017，37（2）：517-522.
YANG X D，KANG Y，LIU Q，et al.Hybrid imperialist competitive algorithm for solving job-shop scheduling problem[J].Journal of Computer Applications，2017，37（2）：517-522.
[36] 王贵林.基于改进帝国竞争算法的农村电商物流最后一公里配送路径优化[D].福州：福建工程学院，2022.
WANG G L.Optimization of last mile distribution path of rural e-commerce logistics based on improved imperialist competitive algorithm[D].Fuzhou：Fujian University of Technology，2022.
[37] 陈孟辉，刘俊麟，徐健锋，等.求解旅行商问题的多样化搜索帝国竞争算法[J].计算机应用，2019，39（10）：2992-2996.
CHEN M H，LIU J L，XU J F，et al.Imperialist competitive algorithm based on multiple search strategy for solving traveling salesman problem[J].Journal of Computer Application，2019，39（10）：2992-2996.
[38] LI B，TANG Z B.Double-assimilation of prosperity and destruction oriented improved imperialist competitive algorithm with computational thinking[C]//Proceedings of the 2022 IEEE Congress on Evolutionary Computation，Padova，Jul 18-23，2022.Piscataway：IEEE，2022：1-8.
[39] ZHANG G H，MA X J，WANG L.Elite archive-assisted adaptive memetic algorithm for a realistic hybrid differentiation flowshop scheduling problem[J].IEEE Transactions on Evolutionary Computation，2022，26（1）：100-114.
[40] 唐世轩，金建钢，卢春霞，等.考虑多种类干扰事件的集装箱码头泊位分配问题[J].大连海事大学学报，2021，47（4）：30-38.
TANG S X，JIN J G，LU C X，et al.Berth allocation problem of container ports considering multiple kinds of interference events[J].Journal of Dalian Maritime University，2021，47（4）：30-38.
[41] ALI I M，ESSAM D，KASMARIK K.Novel binary differential evolution algorithm for knapsack problems[J].Information Sciences，2021，542：177-194.
[42] 吴发民.考虑泊位水深的多码头泊位协调分配策略[D].大连：大连海事大学，2017.
WU F M.Coordinated allocation strategy of multiple quay berths with considering berth depth[D].Dalian：Dalian Maritime University，2017.
[43] LIU S C，CHEN Z G，ZHAN Z H，et al.Many-objective job-shop scheduling：a multiple populations for multiple objectives-based genetic algorithm approach[J].IEEE Transactions on Cybernetics，2023，53（3）：1460-1474.