Optimization on Loading Scheduling for Multiple Gantry Cranes Based on Two-stage Hybrid Dynamic Programming

Operations Research and Management Science ›› 2014, Vol. 23 ›› Issue (3): 56-63.

Previous Articles Next Articles

Optimization on Loading Scheduling for Multiple Gantry Cranes Based on Two-stage Hybrid Dynamic Programming

BIAN Zhan¹, YANG Hui-yun², JIN Zhi-hong¹

1. Dalian Maritime University, College of Transportation Management, Dalian 116026, China;
2. Dalian Port Logistics Technology Co. ,Ltd, Dalian 116601, China

Received:2012-05-12 Online:2014-03-25

基于两阶段混合动态规划算法的龙门吊路径优化

边展¹, 杨惠云2, 靳志宏¹

1.大连海事大学交通运输管理学院,辽宁大连 116026;
2.大连口岸物流科技有限公司,辽宁大连 116601

通讯作者: 靳志宏(1963-),男,辽宁沈阳人,教授,博士生导师,研究方向:物流系统优化。
作者简介:边展(1990-),女,山东菏泽人,博士研究生,研究方向:物流系统优化。
基金资助:
国家自然科学基金项目(71172108);教育部高等学校博士学科点专项科研基金(20122125110009)

Abstract

Abstract: This paper discusses the load scheduling problem of multiple yard cranes. The problem is to schedule two yard cranes at different container blocks which serve the loading operations of one quay crane so as to minimize the total distance of visiting paths and the make-span at stack area. A mathematical model, which considers interference between adjacent yard cranes, is provided by means of time-space network to formulate the problem and a two-stage hybrid algorithm composed of greedy algorithm and dynamic programming is developed to solve the proposed model. Numerical experiments show the effectiveness and practicability of the model and the algorithm in this study by means of the comparison with actual scheduling rules.

Key words: operations research, route planning, greedy algorithm, dynamic programming, two-stage hybrid algorithm

摘要： 产业界已出现利用多台轨道式龙门吊同时作业以提升集装箱码头装船效率的情况,由于需要确定每台龙门吊的取箱作业集合以及增加了“避免碰撞”、“顺次移动”等现实约束,故其移动路径规划问题在模型建立与求解上比单台轨道式龙门吊更为复杂。本文针对两台轨道式龙门吊同时作业的情形,建立了龙门吊移动路径网络模型,并开发了基于贪婪算法与动态规划的两阶段混合算法,并通过仿真算例,借助与基于实际调度规则所得到的调度方案的对比,验证了模型及优化算法的有效性与实用性。

关键词: 运筹学, 路径规划, 贪婪算法, 动态规划, 两阶段混合算法

CLC Number:

U695.22

BIAN Zhan, YANG Hui-yun, JIN Zhi-hong. Optimization on Loading Scheduling for Multiple Gantry Cranes Based on Two-stage Hybrid Dynamic Programming[J]. Operations Research and Management Science, 2014, 23(3): 56-63.

边展, 杨惠云2, 靳志宏. 基于两阶段混合动态规划算法的龙门吊路径优化[J]. 运筹与管理, 2014, 23(3): 56-63.

References

[1] Chung Y G, Randhawa S U, McDowell E D. A simulation analysis for a transtainer-based container handling facility[J]. Computers & Industrial Engineering, 1988, 14(2): 113-125.
[2] Kim K Y, Kim K H. A routing algorithm for a single transfer crane to load export containers onto a containership [J]. Computers & Industrial Engineering, 1997, 33(3-4): 673-676.
[3] Kim K H, Kim K Y. An optimal routing algorithm for a transfer crane in port container terminals[J]. Transportation Science, 1999, 33(1): 17-33.
[4] Kim K Y, Kim K H. Heuristic algorithm for routing yard-side equipment for minimizing loading times in container terminals[J]. Naval Research Logistics, 2003, 50(5): 498-514.
[5] Narasimhan A, Palekar U S. Analysis and algorithms for the transtainer routing problem in container port operations[J]. Transportation Science, 2002, 36(1): 63-78.
[6] Kim K H, Lee K M, Hwang H. Sequencing delivery and receiving operation for yard cranes in port container terminals[J]. International Journal of Production Economics, 2003, 84(3): 283-292.
[7] Kim K H, Young-Man P. A Crane Scheduling Method for port container terminals[J]. European Journal of Operational Research, Part E, 2004, 156(3): 752-768.
[8] Ng W C, Mark K L. Yard crane scheduling in port container terminals[J]. Applied Mathematical Modeling, 2005, 29(3): 263-267.
[9] Ng W C, Mark K L. An effective heuristic for scheduling a yard crane to handle jobs with different ready times[J]. Engineering Optimization, 2005, 37(8): 867-877.
[10] 韩晓龙.集装箱港口轨道式龙门吊的最优路径问题[J].上海海事大学学报,2005,26(2):39-41.
[11] 何军良,宓为建,严伟.基于爬山算法的集装箱堆场场桥调度[J].上海海事大学学报,2007,28(4):11-15.
[12] Zhang C, Wan Y W, Liu J Y, Linn R J. Dynamic crane deployment in container storage yards[J]. Transportation Research, Part B, 2002, 36(6): 537-555.
[13] Ng W C. Crane scheduling in container yards with inter-crane interference[J]. European Journal of Operational Research, 2005, 164(1): 64-78.
[14] Lee D H, Cao Z, Meng Q. Scheduling of two-transtainer systems for loading operation of containers using revised genetic algorithm[C]. In: TRB 85th Annual Meeting Compendium of Papers CD-ROM, Washington DC, 2006.
[15] Lee D H, Cao Z, Meng Q. Scheduling of two-transtainer systems for loading ooutbound containers in port container terminals with simulated annealing algorithm[J]. International Journal of Production Economics, 2007, 107(1): 115-124.
[16] 魏众,申金升,肖荣娜,张智文,石定寰.港口集装箱码头轮胎式轨道式龙门吊优化调度研究[J].中国工程科学,2007,9(8):22-24.
[17] 韩晓龙,丁以中.集装箱港口轨道式龙门吊配置优化研究[J].中国航海,2008,31(1):6-8,14.

Optimization on Loading Scheduling for Multiple Gantry Cranes Based on Two-stage Hybrid Dynamic Programming

基于两阶段混合动态规划算法的龙门吊路径优化

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	DENG You-jun, MU Yun-fei, JIA Hong-jie, ZHANG Yong-xi. Logistics Distribution Route Planning and Dis/Charging Management of Electric Vehicles Considering Customer Satisfaction Level [J]. Operations Research and Management Science, 2021, 30(7): 136-145.
[2]	WANG Lei, BAI Qing-guo, REN Jian-feng. Logistics Scheduling with Two Transportation Modes [J]. Operations Research and Management Science, 2021, 30(6): 1-5.
[3]	LI Zhen-ping, FU Hong-ye, BU Xiao-qi, ZHANG Guo-wei, WU Ling-yun. Research on Order Batching Problem of Intelligent Warehouse System Based on AGV [J]. Operations Research and Management Science, 2020, 29(9): 1-9.
[4]	LIANG Feng, XU Ping. Appointment Scheduling of Medical Examination Based on MDP and Dynamic programming [J]. Operations Research and Management Science, 2020, 29(5): 17-25.
[5]	LI Zhen-ping , FAN Xin-ran, WU Ling-yun. Study on the Storage Allocation Problem Under Cargo to Person Picking Mode [J]. Operations Research and Management Science, 2020, 29(2): 1-11.
[6]	Hong-tao WANG Hong-tao, ZHANG Xiang, WANG Ke. Operations Research 1996~2017: A Retrospective Statistical Analysis [J]. Operations Research and Management Science, 2020, 29(2): 229-239.
[7]	FENG Ai-lan, ZHANG Xiao-qing, KONG Ji-li. Combined Strategy Based on Clustering and Dynamic Programmingfor Picking Routing in warehouse [J]. Operations Research and Management Science, 2019, 28(8): 86-92.
[8]	WANG Nuo, DING Kai, WU Di, WU Nuan. Bidirectional Logistics Network Planning of Remote Islands and Reefs [J]. Operations Research and Management Science, 2019, 28(6): 118-128.
[9]	DUAN Yong-rui, XU Chao, HUO Jia-zhen. Dynamic Pricing and Inventory Management under Service Level Constraint [J]. Operations Research and Management Science, 2019, 28(5): 1-7.
[10]	LIU Chun-lai, WANG Jian-jun. Disruption Management for Single Machine Scheduling with Learning and Deteriorating Effect [J]. Operations Research and Management Science, 2019, 28(1): 94-100.
[11]	WANG Tian, DENG Shi-ming. Smart Grid Energy Procurement Strategies under the Supply of Wind Energy [J]. Operations Research and Management Science, 2018, 27(5): 95-103.
[12]	MA Ning, ZHOU Zhi-li, LIU Ya. Research on the Multi-period Cutting Stock Problem Coordinating with Production Planning [J]. Operations Research and Management Science, 2018, 27(10): 17-22.
[13]	ZHANG Yuan-kai, SUN Li-jun, HU Xiang-pei. Multi-compartment Vehicle Dispatching and Routing for Product Oil Distribution [J]. Operations Research and Management Science, 2017, 26(7): 1-9.
[14]	BAO Xiao-guang, LIU Zhao-hui, YU Wei. Single Vehicle Scheduling Problems with Cluster and Release Time Constraints on a Line [J]. Operations Research and Management Science, 2017, 26(5): 125-129.
[15]	LIU Le. Improved Heuristic Algorithm for a Single-machine Single-subcontractor Scheduling and Outsourcing Integrated Optimization Problem [J]. Operations Research and Management Science, 2017, 26(11): 49-58.