求解集装箱码头岸桥调度问题的化学反应算法

doi:10.16182/j.issn1004731x.joss.201712009

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (12): 3001-3009.doi: 10.16182/j.issn1004731x.joss.201712009

求解集装箱码头岸桥调度问题的化学反应算法

王旭^1,2, 刘士新², 张瑞友², 王佳³

1.河北环境工程学院经济学院, 秦皇岛 066102;
2.东北大学信息科学与工程学院流程工业综合自动化国家重点实验室,沈阳 110819;
3.东北大学秦皇岛分校经济学院,秦皇岛066004

收稿日期:2015-10-28 发布日期:2020-06-06
作者简介:王旭(1982-),男,辽宁沈阳,博士生,研究方向为仿真优化建模;刘士新(1968-),男,辽宁调兵山,教授,研究方向为项目管理与优化调度。
基金资助:
国家自然科学基金(71601040, 61573089,61333006,71471034)

Chemical Reaction Optimization Algorithmfor Solving QuayCrane Scheduling Problems of Container Terminal

Wang Xu^1,2, Liu Shixin², Zhang Ruiyou², Wang Jia³

1. SchoolofEconomics, Hebei University of Environmental Engineering, Qinhuangdao 066102, China;
2. College of Information Science & Engineering,Northeastern University, State Key Laboratory of Synthetical Automation for Process Industries, Shenyang 110819, China;
3. SchoolofEconomics, NortheasternUniversity atQinhuangdao, Qinhuangdao 066004, China

Received:2015-10-28 Published:2020-06-06

摘要/Abstract

摘要： 研究了集装箱码头卸船作业中的岸桥调度问题。考虑岸桥的时间窗约束,建立了岸桥卸船作业的仿真优化模型,设计了一类基于双链分子结构的化学反应算法。该算法的编码包含两部分,分别为任务的优先关系和为任务分配的岸桥序列,解码过程采用离散事件动态仿真方法进行。针对问题的特点,设计了4种分子碰撞算子。通过算例生成器生成的仿真数据对模型和算法进行了仿真测试,结果表明：与CPLEX和遗传算法相比,该算法可在很短的时间内求得稳定的满意解,验证了模型和算法的有效性。

关键词: 卸船作业, 化学反应算法, 双链分子结构, 离散事件动态仿真

Abstract: This paper researches on quay crane scheduling for unloading operations in container terminal. Considering quay crane work within its time window, an unloading scheduling simulation model is established.According to the characteristics of the unloading scheduling simulation model,a DoubleList Molecular Structure-based Chemical Reaction Optimization(DLMCRO) algorithm is developed. There are two parts in coding: one is the priority relation of the task, and the other is the task-to-quay-node mapping.Discrete Event Dynamic Simulation(DEDS)is used to simulate the decoding process. Four elementary chemical reaction operations against the problem are designed. The simulation experiment is madeby using data generator.The results of simulation show that DLMCRO can get a stable and satisfactory solution more quickly than CPLEX and GA. And it^'s proved that the model and algorithm are effective.

Key words: unloading operation, chemical reaction optimization, double list molecular structure, discrete event dynamic simulation

中图分类号:

C934

王旭, 刘士新, 张瑞友, 王佳. 求解集装箱码头岸桥调度问题的化学反应算法[J]. 系统仿真学报, 2017, 29(12): 3001-3009.

Wang Xu, Liu Shixin, Zhang Ruiyou, Wang Jia. Chemical Reaction Optimization Algorithmfor Solving QuayCrane Scheduling Problems of Container Terminal[J]. Journal of System Simulation, 2017, 29(12): 3001-3009.

参考文献

[1] Kim K H, Park Y M.A crane scheduling method for port container terminals[J]. European Journal of Operational Research (S0377-2217), 2004, 156(3): 752-768.
[2] Bierwirth C, Meisel F.A fast heuristic for quay crane scheduling with interference constraints[J]. Journal of Scheduling (S1094-6136), 2009, 12(4): 345-360.
[3] Legato P, Trunfio R, Meisel F.Modeling and solving rich quay crane scheduling problems[J]. Computers and Operations Research (S0305-0548), 2012, 39(9): 2063-2078.
[4] Fu Y M, Diabat A, Tsai I T.A multi-vessel quay crane assignment and scheduling problem: Formulation and heuristic solution approach[J]. Expert Systems with Applications (S0957-4174), 2014, 41(15): 6959-6965.
[5] Lee D H, Wang H Q, Miao L X.Quay crane scheduling with non-interference in port container terminals[J]. Transportation Research Part E (S1366-5545), 2008, 44(1): 124-135.
[6] Lam A, Li V.Chemical-reaction-inspired meta heuristic for optimization[J]. IEEE Transactions on Evolutionary Computation (S1089-778X), 2010, 14(3): 381-399.
[7] Sun J, Wang Y T.Hybrid algorithm based on chemical reaction optimization and Lin-Kernighan local search for the traveling salesman problem[C]//2011 Seventh International Conference on Natural Computation, 2011: 1518-1521.
[8] Pan B, Lam A, Li V.Network coding optimization based on chemical reaction optimization[C]//2011 IEEE Global Telecommunications Conference, 2011: 1-5.
[9] Xu Y M, Li K L, He L G.A DAG scheduling scheme on heterogeneous computing systems using double molecular structure based chemical reaction optimization[J]. Journal of Parallel and Distributed Computing (S0743-7315), 2013, 73(9): 1306-1322.
[10] Tung K T, Li L K, Xu Y M.Chemical reaction optimizations with greedy strategy for 0-1 knapsack problem[J]. Applied Soft Computing (S1568-4946), 2013, 13(4): 1774-1780.
[11] Assadipour G, Ke G Y, Verma M.An analytical framework for integrated maritime terminal scheduling problems with time windows[J]. Expert Systems with Applications (S0957-4174), 2014, 41(16): 7415-7424.
[12] Meisel F, Bierwirth C.A unified approach for the evaluation of quay crane scheduling models and algorithms[J]. Computerand Operations Research (S0305-0548), 2011, 38(3): 683-693.
[13] 范志强. 考虑任务优先约束的同类岸桥作业调度优化[J]. 运筹与管理, 2013, 22(2): 235-242.
Fan Z Q.Modeling and solving uniform quay crane scheduling problem with task precedence constraints[J]. Operation Research and Management Science, 2013, 22(2): 235-242.

求解集装箱码头岸桥调度问题的化学反应算法

Chemical Reaction Optimization Algorithmfor Solving QuayCrane Scheduling Problems of Container Terminal

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价