基于改进遗传算法的泊位岸桥协调调度优化

doi:10.11772/j.issn.1001-9081.2016.11.3136

计算机应用 ›› 2016, Vol. 36 ›› Issue (11): 3136-3140.DOI: 10.11772/j.issn.1001-9081.2016.11.3136

基于改进遗传算法的泊位岸桥协调调度优化

杨劼¹, 高红², 刘涛³, 刘巍²

1. 大连海事大学交通运输管理学院, 辽宁大连 116026;
2. 大连海事大学数学系, 辽宁大连 116026;
3. 中北大学计算机与控制工程学院, 太原 030051

收稿日期:2016-05-18 修回日期:2016-07-05 出版日期:2016-11-10 发布日期:2016-11-12
通讯作者: 杨劼
作者简介:杨劼(1987-),女,山西临汾人,博士研究生,主要研究方向:进化计算、调度优化;高红(1976-),女,辽宁抚顺人,副教授,博士,主要研究方向:图论、计算语言学;刘涛(1988-),男,山东临沂人,讲师,博士,主要研究方向:虚拟现实、进化计算;刘巍(1955-),男,辽宁大连人,教授,硕士,主要研究方向:可拓学理论与应用、运输优化。

Integrated berth and quay-crane scheduling based on improved genetic algorithm

YANG Jie¹, GAO Hong², LIU Tao³, LIU Wei²

1. Transportation Management College, Dalian Maritime University, Dalian Liaoning 116026, China;
2. Department of Mathematics, Dalian Maritime University, Dalian Liaoning 116026, China;
3. School of Computer Science and Control Engineering, North University of China, Taiyuan Shanxi 030051, China

Received:2016-05-18 Revised:2016-07-05 Online:2016-11-10 Published:2016-11-12

摘要/Abstract

摘要： 针对集装箱码头资源调度不合理造成资源浪费的问题，在考虑岸桥装卸成本的基础上，以在港集装箱船总的作业成本最小为优化目标，建立了基于非线性混合整数规划的泊位岸桥协调调度优化模型。为使模型更加接近码头操作的实际情况，模型假设船舶装卸时间依赖于为其分配的岸桥数。采用基于可拓关联函数的改进遗传算法对模型进行求解。改进算法强调了不可行解的重要性，用可拓关联度来衡量种群中不可行解的优劣程度，通过在种群迭代中始终保持一定数量的不可行解来维持种群多样性，从而克服传统算法局部搜索能力较差的缺陷。数值实验验证了模型和算法的可行性和有效性，与不考虑岸桥装卸成本的模型相比，能够有效减少港口资源的浪费。

关键词: 集装箱码头, 泊位岸桥协调调度, 遗传算法, 可拓关联函数, 非线性混合整数规划

Abstract: A strategy for integrated berth and quay-crane scheduling was proposed to cope with unreasonable allocation of port resources in container terminals. First, a nonlinear mixed integer programming model which aims at minimizing the port operational cost was presented. And the loading and unloading cost of quay-crane was considered in the objective of our model. To make the model more realistic, the handling time of a vessel was assumed to depend on the number of assigned quay-cranes. Second, an improved genetic algorithm based on extenics dependent function was used to solve this model. In this algorithm, infeasible solutions play an important role. They were evaluated by their extenics dependent degrees. Some infeasible solutions were always contained in the population to maintain the diversity of the population. This improved local search ability of traditional genetic algorithm. At last, the effectiveness and efficiency of the proposed model and algorithm were testified by several test instances. Compared with the model without considering the loading and unloading cost of quay-crane, the waste of resource is effectively reduced.

Key words: container terminal, integrated berth and quay-crane scheduling, genetic algorithm, extenics dependent function, nonlinear mixed integer programming

中图分类号:

杨劼, 高红, 刘涛, 刘巍. 基于改进遗传算法的泊位岸桥协调调度优化[J]. 计算机应用, 2016, 36(11): 3136-3140.

YANG Jie, GAO Hong, LIU Tao, LIU Wei. Integrated berth and quay-crane scheduling based on improved genetic algorithm[J]. Journal of Computer Applications, 2016, 36(11): 3136-3140.

参考文献

[1] 韩骏,孙晓娜,靳志宏.集装箱码头泊位与岸桥协调调度优化[J].大连海事大学学报(自然科学版),2008,34(2):117-121. (HAN J, SUN X N, JIN Z H. Coordinated optimization method for berth and quay crane allocation in container terminal[J]. Journal of Dalian Maritime University (Natural Science Edition), 2008, 34(2):117-121.)
[2] 谭盛强,朱瑾.基于混合算法的多目标连续泊位-岸桥集成调度研究[J].宁夏大学学报(自然科学版),2015,36(2):131-139. (TAN S Q, ZHU J. Study of multi-objective consecutive berth integrated scheduling of quay based on hybrid algorithm[J]. Journal of Ningxia University (Natural Science Edition), 2015, 36(2):131-139.)
[3] 李明伟,康海贵,耿静,等.基于多目标混沌云粒子群算法的泊位-岸桥分配研究[J].水运工程,2014(1):90-96. (LI M W, KANG H G, GENG J, et al. Berth and quay-crane allocation based on multi-objective chaos cloud particle swarm optimization algorithm[J]. Port & Waterway Engineering, 2014(1):90-96.)
[4] MEISEL F, BIERWIRTH C. Heuristics for the integration of crane productivity in the berth allocation problem[J]. Transportation Research Part E:Logistics and Transportation Review, 2009, 45(1):196-209.
[5] ZHANG C, ZHENG L, ZHANG Z, et al. The allocation of berths and quay cranes by using a sub-gradient optimization technique[J]. Computers & Industrial Engineering, 2010, 58(1):40-50.
[6] HE J. Berth allocation and quay crane assignment in a container terminal for the trade-off between time-saving and energy-saving[J]. Advanced Engineering Informatics, 2016, 30(3):390-405.
[7] KARAM A, ELTAWIL A B. A new method for allocating berths, quay cranes and internal trucks in container terminals[C]//Proceedings of the 2015 International Conference on Logistics, Informatics and Service Sciences. Piscataway, NJ:IEEE, 2015:1-6.
[8] BIERWIRTH C, MEISEL F. A follow-up survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research, 2015, 244(3):675-689.
[9] IMAI A, CHEN H C, NISHIMURA E, et al. The simultaneous berth and quay crane allocation problem[J]. Transportation Research Part E Logistics & Transportation Review, 2008, 44(5):900-920.
[10] LEE D, WANG H Q. Integrated discrete berth allocation and quay crane scheduling in port container terminals[J]. Engineering Optimization, 2010, 42(8):747-761.
[11] 毕娅,李文锋.集装箱港口集群下多港口多泊位联合调度方法[J].计算机应用,2012,32(2):448-451. (BI Y, LI W F. Multi-port and multi-berth integrated scheduling based on container port cluster[J]. Journal of Computer Applications, 2012, 32(2):448-451.)
[12] 张红菊,乐美龙.基于多目标粒子群算法的泊位-岸桥分配研究[J].武汉理工大学学报,2012,34(2):59-64. (ZHANG H J, LE M L. Research on container berth-quay crane allocation based on multi-objective PSO[J]. Journal of Wuhan University of Technology, 2012, 34(2):59-64.)
[13] SAMMARRA M, CORDEAU J F, LAPORTE G, et al. A tabu search heuristic for the quay crane scheduling problem[J]. Journal of Scheduling, 2007, 10(4):327-336.
[14] YANG C Y, CAI W. Extenics Theory, Method and Application[M]. Beijing:Science Press, 2013:87-105.
[15] 杨春燕,蔡文.可拓集中关联函数的研究进展[J].广东工业大学学报,2012,29(2):7-14. (YANG C Y, CAI W. Recent research progress in dependent functions in extension sets[J]. Journal of Guangdong University of Technology, 2012, 29(2):7-14.)
[16] 蒋大培,胡志华,胡少龙.考虑偏好泊位的泊位和岸桥集成分派问题[J].广西大学学报(自然科学版),2014,39(3):663-672.(JIANG D P, HU Z H, HU S L. Berth-crane allocation problem based on the preferences of berthing position[J]. Journal of Guangxi University (Natural Science Edition), 2014, 39(3):663-672.)
[17] 乐美龙,刘秀玲.基于泊位偏好与服务优先级的泊位和岸桥分配[J].辽宁工程技术大学学报(自然科学版),2013,32(5):709-712. (LE M L, LIU X L. Berth and quay crane allocation based on berth preference and service priority[J]. Journal of Liaoning Technical University (Natural Science), 2013, 32(5):709-712.)

基于改进遗传算法的泊位岸桥协调调度优化

Integrated berth and quay-crane scheduling based on improved genetic algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[4]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[5]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[6]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[7]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[8]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[9]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[10]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[11]	杨华龙, 王美玉, 辛禹辰. 横向整合战略下异质车辆库存路径优化模型[J]. 计算机应用, 2021, 41(10): 3040-3048.
[12]	黄晓祥, 胡咏梅, 吴丹, 任力杰. 基于变分自编码器的异常颈动脉早期识别和预测[J]. 计算机应用, 2021, 41(10): 3082-3088.
[13]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.
[14]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[15]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.