考虑路径冲突的AGV配置与调度优化

doi:10.12005/orms.2020.0117

运筹与管理 ›› 2020, Vol. 29 ›› Issue (5): 43-51.DOI: 10.12005/orms.2020.0117

考虑路径冲突的AGV配置与调度优化

范厚明, 岳丽君, 李荡, 马梦知

大连海事大学交通运输工程学院,辽宁大连 116026

收稿日期:2018-11-25 出版日期:2020-05-25
作者简介:范厚明(1962-),男,山东蓬莱人,博士,教授,博士生导师,研究方向:交通运输规划与管理;岳丽君(1995-),女,河南濮阳人,硕士研究生,研究方向:物流工程;李荡(1994-),男,湖南常德人,硕士研究生,研究方向:物流工程;马梦知(1989-),女,河北唐山人,讲师,博士,研究方向:交通运输规划与管理。
基金资助:
国家自然科学基金资助项目(61473053);辽宁省重点研发计划指导计划(2018401002)

Optimization of AGV Dispatching and Configuration Considering Path Conflict

FAN Hou-ming, YUE Li-jun, LI Dang, MA Meng-zhi

The College of Transportation Engineering, Dalian Maritime University, Dalian, 116026

Received:2018-11-25 Online:2020-05-25

摘要/Abstract

摘要： 合理调度有限的码头资源以满足船舶的装卸时间要求是自动化集装箱码头的重要目标之一。针对自动化集装箱码头自动导引车(automated guided vehicle,AGV)配置与调度问题,考虑船舶装卸时间要求和AGV运输过程中的路径冲突,提出分阶段调度策略。将船舶装卸作业分为卸船阶段、装卸同步阶段、装船阶段三个阶段,在每个阶段中,建立以最小化最大完工时间和最小化AGV空载和等待时间为双目标的调度优化模型,并设计基于NSGA-Ⅱ的启发式算法求解。根据本阶段的实际完工时间,从最优解集中选择下一阶段AGV的配置与调度方案。最后对比其他调度方案表明本文调度方案能够满足集装箱船的装卸时间要求,且提高了AGV的利用率,更符合码头实际作业要求。

关键词: 船舶装卸, 路径冲突, AGV调度, 分阶段调度策略

Abstract: Reasonable scheduling for limited terminal resources to meet the laytime of ship is one of the important objectives of automated container terminals. Aiming at the problem of automatic guided vehicle (AGV) configuration and scheduling, considering the ship discharging and loading time requirements and the path conflict in the AGV transportation process, a new staged scheduling strategy is proposed. The container handling operation is divided into three stages: discharging stage, discharging and loading synchronization stage and loading stage. In each stage, a scheduling optimization model is established to minimize the maximum completion time and minimize the AGV no-load and waiting time. An improved heuristic algorithm based on NSGA-II is used to solve the model. According to the actual completion time of this phase, the configuration and scheduling scheme of the next phase AGV is selected from the optimal solution set. Finally, compared with other scheduling schemes, the scheduling scheme of this paper can meet the requirements of laytime, and the utilization rate of AGV is improved, which is more in line with the actual operational requirements of the terminal.

Key words: ship discharging and loading, path conflict, AGV dispatching, staged scheduling strategy

中图分类号:

TP18

范厚明, 岳丽君, 李荡, 马梦知. 考虑路径冲突的AGV配置与调度优化[J]. 运筹与管理, 2020, 29(5): 43-51.

FAN Hou-ming, YUE Li-jun, LI Dang, MA Meng-zhi. Optimization of AGV Dispatching and Configuration Considering Path Conflict[J]. Operations Research and Management Science, 2020, 29(5): 43-51.

参考文献

[1] 韩晓龙,张少凯,于航.基于仿真的集装箱港口装卸工艺对比研究[J].系统仿真学报,2014,26(5):1170-1175.
[2] Zeng Q, Yang Z, Lai L. Models and algorithms for multi-crane oriented scheduling method in container terminals[J]. Transport Policy, 2009, 16(5): 271-278.
[3] Kim K H, Bae J W. A look-ahead dispatching method for automated guided vehicles in automated port container terminals[J]. Transportation Science, 2004, 38(2): 224-234.
[4] 陶莎,胡志华,盛昭瀚.基于关键资源优先的三级装卸搬运分时协调策略[J].控制与决策,2015,30(8):1441-1446.
[5] Homayouni S M, Tang S H, Ismail N, et al. Using simulated annealing algorithm for optimization of quay cranes and automated guided vehicles scheduling[J]. International Journal of Physical Sciences, 2011, 6(27): 6286-6294.
[6] Luo J, Wu Y. Modelling of dual-cycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 79(7): 49-64.
[7] Lim Y F, Zhang Y, Wang C. A quay crane system that self-recovers from random shocks[J]. Flexible Services and Manufacturing Journal, 2015, 27(4): 561-584.
[8] 常祎妹,朱晓宁.不确定因素下的集装箱码头车船间装卸作业集成调度[J].交通运输工程学报,2017,17(6):115-124.
[9] Azevedo A T, Anibal Tavares de, Chaves A A, et al. Solving the 3D stowage planning problem integrated with the quay crane scheduling problem by representation by rules and genetic algorithm[J]. Applied Soft Computing, 2018, 65(4): 495-516.
[10] Yang Y, Zhong M, Dessouky Y, et al. An integrated scheduling method for AGV routing in automated container terminals[J]. Computers & Industrial Engineering, 2018, 126(12): 482-493.
[11] Zhang L W, Ye R, Huang S Y, et al. Mixed integer programming models for dispatching vehicles at a container terminal[J]. Journal of Applied Mathematics and Computing, 2005, 17(1-2): 145-170.
[12] 韩晓龙,樊加伟.自动化港口AGV调度配置仿真分析[J].重庆交通大学学报(自然科学版),2016,35(5):151-154,164.
[13] Nishi T, Hiranaka Y, Grossmann I E. A bilevel decomposition algorithm for simultaneous production scheduling and conflict-free routing for automated guided vehicles[J]. Computers & Operations Research, 2011, 38(5): 876-888.
[14] Kim J, Choe R, Ryu K R. Multi-objective optimization of dispatching strategies for situation-adaptive AGV operation in an automated container terminal[C]// Proceedings of the 2013 Research in Adaptive and Convergent Systems. ACM, 2013. 1-6.
[15] Choe R, Kim J, Ryu K R. Online preference learning for adaptive dispatching of AGVs in an automated container terminal[J]. Applied Soft Computing, 2016, 38(1): 647-660.
[16] Wang Y, Jiang X, Lee L H, et al. Tree based searching approaches for integrated vehicle dispatching and container allocation in a transshipment hub[J]. Expert Systems with Applications, 2017, 74(3): 139-150.
[17] 鲁渤,吕家智,曾庆成.集装箱码头ALV调度与堆场位置分配集成优化模型[J].系统工程理论与实践,2017,37(5):1349-1359.
[18] Roy D, Gupta A, De Koster R B M. A non-linear traffic flow-based queuing model to estimate container terminal throughput with AGVs[J]. International Journal of Production Research, 2016, 54(2): 472-493.
[19] 张素云,杨勇生,梁承姬,等.自动化码头多AGV路径冲突的优化控制研究[J].交通运输系统工程与信息,2017,17(2):83-89.
[20] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[21] Kalyanmoy D, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[22] Lau H Y K, Zhao Y. Integrated scheduling of handling equipment at automated container terminals[J]. International Journal of Production Economics, 2008, 112(2): 665-682.
[23] 添玉,王建彬,范会方.自动化码头起重机和自带提升功能的AGV的集成调度[J].上海海事大学学报,2017,38(3):52-60.

考虑路径冲突的AGV配置与调度优化

Optimization of AGV Dispatching and Configuration Considering Path Conflict

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics