考虑泊位偏好和岸桥移动的泊位岸桥联合调度

doi:10.3778/j.issn.1002-8331.2009-0410

摘要/Abstract

摘要： 为了更高效地利用码头资源，同时考虑泊位资源和岸桥资源，建立了考虑泊位偏好和岸桥移动频数的泊位岸桥联合调度两阶段模型。第一阶段模型采用船舶到港时间可变的到港策略，建立了以船舶等待成本、泊位偏离成本、延迟离港成本之和最小为目标的混合整数规划模型。第二阶段模型考虑了岸桥的干扰约束，建立了以岸桥移动频数最小为目标的整数规划模型。使用MATLAB设计改进的自适应变异粒子群算法对模型进行求解，并将结果与CPLEX和原始粒子群算法的求解结果对比，证明该算法的高性能。在两阶段模型中引入泊位偏离因子[β]来表示泊位偏离对船舶工作量的间接影响，分析[β]变化对船工作情况的影响。发现在计划期内，岸桥资源一定的情况下，船舶偏离偏好泊位会影响总的工作成本，尤其是当所有船舶总工作量较大时，[β]增加会造成总成本的激增。结果表明该模型和算法在解决泊位-岸桥的联合调度问题方面的有效性。

关键词: 集装箱码头, 连续泊位分配, 岸桥调度, 联合调度, 粒子群算法

Abstract: To use the terminal resources more efficiently, this paper considers the berth resource and quay crane resource simultaneously, and establishes a two-stage model for joint scheduling of berths and quay cranes considering berth preference and quay-crane movement frequency. The first-stage model adopts the variable-in-time arrival strategy of the ship. A mixed-integer programming model is developed with the goal of minimizing the sum of ship waiting cost, deviation cost, and delay cost. The second-stage model considers interference constraints of the quay crane, and establishes an integer programming model with the minimum moving frequency of quay cranes. MATLAB is used to design an improved adaptive mutation particle swarm algorithm to solve the model. Compared with CPLEX and the original particle swarm algorithm, the proposed algorithm shows the high performance. In the two-stage model, a berth deviation factor[β]is introduced to express the indirect impact of berth deviation on the ship’s workload, and the impact of[β]changes on the ship’s working conditions is analyzed. It is found that under the circumstance of certain quay crane resources during the planned period, the deviation of the ship from the preferred berth will affect the total work cost, especially when the total work load of all ships is large, the increase of[β]will cause a sharp increase in the total cost. The results show that the model and algorithm are effective in solving the problem of berth-quay crane joint scheduling.

Key words: container terminal, continuous berth allocation, quay crane scheduling, joint optimization, particle swarm optimization

梅益群, 韩晓龙. 考虑泊位偏好和岸桥移动的泊位岸桥联合调度[J]. 计算机工程与应用, 2022, 58(6): 241-249.

MEI Yiqun, HAN Xiaolong. Joint Scheduling of Berths and Quay Cranes Considering Berth Preference and Quay Crane Movement[J]. Computer Engineering and Applications, 2022, 58(6): 241-249.

参考文献

[1] GUAN Y P，CHEUNG R K.The berth allocation problem：models and solution methods[J].OR Spectrum，2004，26（1）：75-92.
[2] 韩晓龙，赵书杰.时间窗限制下泊位分配问题的约束规划模型[J].辽宁工程技术大学学报（自然科学版），2014，33（7）：983-987.
HAN X L，ZHAO S J.Modeling and solving berth allocation problem of time window constraints based on constraint programming[J].Journal of Liaoning Technical University（Natural Science），2014，33（7）：983-987.
[3] KIM K H，MOON K C.Berth scheduling by simulated annealing[J].Transportation Research Part B，2003，37（6）：541-560.
[4] CORRECHER J F，BOSSCHE T V，RAMON A V，et al.The berth allocation problem in terminals with irregular layouts[J].European Journal of Operational Research，2019，272（3）：1096-1108.
[5] LIU C C，XIANG X，ZHENG L.A two-stage robust optimization approach for the berth allocation problem under uncertainty[J].Flexible Services and Manufacturing Journal，2020，32（1）.
[6] JAKUB W，MACIEJ D，éRIC S.Selecting algorithms for large berth allocation problems[J].European Journal of Operational Research，2020，283（3）.
[7] 吴凌霄，马卫民.集装箱码头岸桥调度的时间—成本均衡模型与算法[J].工业工程与管理，2016，21（6）：38-44.
WU L X，MA W M.Model and algorithm of time-cost trade-off in quay crane scheduling problem[J].Industrial Engineering and Management，2016，21（6）：38-44.
[8] 乐美龙，徐根龙，文洪蕊.基于作业均衡的集装箱码头岸桥作业调度优化[J].重庆交通大学学报（自然科学版），2016，35（3）：155-161.
LE M L，XU G L，WEN H R.Quay crane scheduling optimization considering operation balance at container terminal[J].Journal of Chongqing Jiaotong University（Natural Science），2016，35（3）：155-161.
[9] 郑红星，王钟逸，朱徐涛.考虑故障的集装箱码头岸桥多阶段再调度决策[J].系统工程理论与实践，2021，41（12）：3321-3335.
ZHENG H X，WANG Z Y，ZHU X T.Multi-stage rescheduling decision of container terminal quay crane considering the fault[J].Systems Engineering-Theory & Practice，2021，41（12）：3321-3335.
[10] 陆书翔，吕长虹，秦涛.集装箱码头桥机调度问题基于完工时间下界的算法[J].运筹学学报，2020，24（3）：67-76.
LU S X，LV C H，QIN T.An algorithm based on makespan lower bound for quay crane schedule problem in container terminals[J].Operations Research Transactions，2020，24（3）：67-76.
[11] 赵虎，韩晓龙.船舶到港时间可变的泊位—岸桥联合调度[J].广西大学学报（自然科学版），2016，41（6）：1940-1948.
ZHAO H，HAN X L.Study on the scheduling of berth and quay cranes considering energy consumption[J].Journal of Guangxi University（Natural Science Edition），2016，41（6）：1940-1948.
[12] 杨劼，高红，刘巍.离散泊位布局下的泊位岸桥动态协调调度[J].计算机工程与应用，2018，54（3）：265-270.
YANG J，GAO H，LIU W.Integrated dynamic berth and quay-crane scheduling based on discrete berth layout[J].Computer Engineering and Applications，2018，54（3）：265-270.
[13] 吴迪，王诺，林婉妮，等.泊位-岸桥联合分配模型的模拟植物生长交替进化算法[J].交通运输工程学报，2018，18（3）：199-209.
WU D，WANG N，LIN W N，et al.Alternate evolution algorithm based on plant growth simulation for berth-quay crane joint allocation model[J].Journal of Traffic and Transportation Engineering，2018，18（3）：199-209.
[14] TüRKO?ULLARI Y B，TA?KIN Z C，ARAS N，et al.Optimal berth allocation and time-invariant quay crane assignment in container terminals[J].European Journal of Operational Research，2014，235（1）：88-101.
[15] 彭丽姣，韩晓龙.连续泊位下泊位分配与岸桥动态调度的联合优化[J].水运工程，2013（4）：83-88.
PENG L J，HAN X L.Coordinated optimization of continuous berth allocation and quay crane dynamic scheduling[J].Port and Waterway Engineering，2013（4）：83-88.
[16] 毛敏俐，梁承姬，胡筱渊.基于船时效率的岸桥配置优化[J].计算机应用，2020，40（4）：1223-1230.
MAO M L，LIANG C J，HU X Y.Optimization of quay crane assignment based on ship efficiency[J].Journal of Computer Applications，2020，40（4）：1223-1230.
[17] 田星，孟庆柱.集装箱码头泊位、岸桥和集卡协同调度优化[J].物流技术，2018，37（3）：32-36.
TIAN X，MENG Q Z.Study on coordinated scheduling of berths，quay cranes and harbor trucks at container terminals[J].Logistics Technology，2018，37（3）：32-36.
[18] HSU H P.A HPSO for solving dynamic and discrete berth allocation problem and dynamic quay crane assignment problem simultaneously[J].Swarm and Evolutionary Computation，2016，27：156-168.
[19] WANG T S，DU Y Q，FANG D B，et al.Berth allocation and quay crane assignment for the trade-off between service efficiency and operating cost considering carbon emission taxation[J].Transportation Science，2020，54（5）：1307-1331.
[20] 胡鸿涛，任淑珍，胡雄.考虑岸桥维护的集装箱码头泊位与岸桥集成调度[J].现代制造工程，2019（4）：14-19.
HU H T，REN S Z，HU X.Integrated scheduling of berth allocation and quay crane assignment with maintenance activities[J].Modern Manufacturing Engineering，2019（4）：14-19.
[21] 孙彬，孙俊清，陈秋双.基于鲁棒反应式策略的泊位和岸桥联合调度[J].系统工程理论与实践，2013，33（4）：1076-1083.
SUN B，SUN J Q，CHEN Q S.Integrated scheduling for berth and quay cranes based on robust and reactive policy[J].System Engineering Theory and Practice，2013，33（4）：1076-1083.