基于启发式算法的自动化跨运车作业调度

doi:10.12066/j.issn.1007-2861.1688

上海大学学报(自然科学版) ›› 2017, Vol. 23 ›› Issue (3): 443-451.doi: 10.12066/j.issn.1007-2861.1688

基于启发式算法的自动化跨运车作业调度

尧雨琴, 胡志华

上海海事大学物流研究中心, 上海 201306

收稿日期:2015-06-12 出版日期:2017-06-30 发布日期:2017-06-30
通讯作者: 胡志华(1977—), 男, 教授, 博士生导师, 博士, 研究方向为港航与物流运作优化. E-mail: zhhu@shmtu.edu.cn
作者简介:胡志华(1977—), 男, 教授, 博士生导师, 博士, 研究方向为港航与物流运作优化. E-mail: zhhu@shmtu.edu.cn
基金资助:
国家自然科学基金青年基金资助项目(71101088); 国家自然科学基金面上资助项目(71471109)

Scheduling of automated straddle carrier based on heuristic algorithm

YAO Yuqin, HU Zhihua

Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China

Received:2015-06-12 Online:2017-06-30 Published:2017-06-30

摘要/Abstract

摘要：

针对自动化集装箱码头自动化跨运车(automated straddle carrier, ASC)的调度问题, 首先建立混合整数规划模型, 基于ASC 可以独立完成集装箱在岸边和堆场之间的运输作业这一特性, 将自动化集装箱码头ASC 的作业调度问题转化为同时取货送货问题, 并提出一种先完成先执行(first finished first insert, FFFI)启发式算法进行求解, 实现集装箱任务分配, 确定ASC 的作业序列, 计算每辆ASC 的使用率. 最后, 通过改变集装箱任务数和ASC 数量验证该算法的有效性和可行性.

关键词: 调度, 同时取货送货, 先完成先执行启发式算法, 自动化跨运车, 自动化集装箱码头

Abstract:

For automatic scheduling of automated straddle carrier (ASC) of a container terminal, a mixed integer programming model is established. Considering that ASC can be done in a separate container transport between the shore and yard work independently, this paper turns the ASC container terminal scheduling into a simultaneous pickup and delivery problem, and proposes a first finished first insert (FFFI) heuristic algorithm to solve it. Thus the sequence of ASC is assured. Utilization per ASC is calculated. With the numbers of tasks and ASCs changed, utilization of ASC is calculated to verify effectiveness of the algorithm.

Key words: automated straddle carrier (ASC), first finished first insert (FFFI) heuristic algorithm, scheduling, simultaneous pickup and delivery, automated container terminal

尧雨琴, 胡志华. 基于启发式算法的自动化跨运车作业调度[J]. 上海大学学报(自然科学版), 2017, 23(3): 443-451.

YAO Yuqin, HU Zhihua. Scheduling of automated straddle carrier based on heuristic algorithm[J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(3): 443-451.

参考文献

[1] Cao J X, Lee D H, Chen J H, et al. The integrated yard truck and yard crane scheduling problem: Benders’ decomposition-based methods [J]. Transportation Research Part E: Logistics
and Transportation Review, 2010, 46(3): 344-353.

[2] Homayouni S M, Tang S H, Motlagh O. A genetic algorithm for optimization of integrated scheduling of cranes, vehicles, and storage platforms at automated container terminals [J]. Journal of Computational and Applied Mathematics, 2014, 270: 545-556.
[3] Gelareh S, Merzouki R, McGinley K, et al. Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals [J]. Transportation
Research Part C: Emerging Technologies, 2013, 33: 1-21.
[4] 梁承姬, 张松波. 集装箱港口装卸作业设备集成调度[J]. 辽宁工程技术大学学报(自然科学版), 2015, 34(2): 262-266.
[5] Yuan S, Skinner B T, Huang S D, et al. Mathematical modelling of container transfers for a fleet of autonomous straddle carriers [C]// IEEE International Conference on Robotics and
Automation. 2010: 1261-1266.
[6] Yuan S, Skinner B T, Huang S D, et al. A job grouping approach for planning container transfers at automated seaport container terminals [J]. Advanced Engineering Informatics, 2011,
25(3): 413-426.
[7] Skinner B T, Yuan S, Huang S D, et al. Optimisation for job scheduling at automated container terminals using genetic algorithm [J]. Computers & Industrial Engineering, 2013,
64(1): 511-523.
[8] Cai B, Huang S D, Liu D, et al. Optimisation model and exact algorithm for autonomous straddle carrier scheduling at automated container terminals [C]// 2011 IEEE/RSJ International
Conference on Intelligent Robots and Systems. 2011.
[9] Cai B, Huang S D, Liu D, et al. Multiobjective optimization for autonomous straddle carrier scheduling at automated container terminals [J]. Transactions on Automation Science and
Engineering, 2013, 10(3): 711-724.
[10] Cai B, Huang S D, Liu D, et al. Rescheduling policies for large-scale task allocation of autonomous straddle carriers under uncertainty at automated container terminals [J]. Robotics
and Autonomous Systems, 2014, 62(4): 506-514.
[11] Montan´e F A T, Galvão R D. A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service [J]. Computers & Operations Research, 2006, 33(3): 595-619.
[12] Zhao F G, Sun J S, Li S J, et al. A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery [J]. International Journal of Automation and Computing, 2009, 6(1): 97-102.
[13] 姚锦宝, 夏禾,贺兴东,等.同时取货送货车辆路径问题的改进的蚁群算法[J].技术与方法, 2010(S1): 76-78.
[14] 贾方方, 孔德成. 同时取送货车辆路径问题的改进粒子群优化算法[J]. 技术与方法, 2012, 19: 108-111.
[15] Zachariadis E E, Tarantilis C D, Kiranoudis C T. A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service [J]. Expert Systems
with Applications, 2009, 36(2): 1070-1081.
[16] Zachariadis E E, Kiranoudis C T. A local search metaheuristic algorithm for the vehicle routing problem with simultaneous pick-ups and deliveries [J]. Expert Systems with Applications, 2011, 38(3): 2717-2726.

基于启发式算法的自动化跨运车作业调度

Scheduling of automated straddle carrier based on heuristic algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	彭运芳1, 高雅1, 夏蓓鑫2. 不确定条件下基于遗传算法的作业车间调度问题[J]. 上海大学学报(自然科学版), 2016, 22(6): 793-803.
[2]	张靖1, 刘小龙2, 高洋1, 姜艳兴1, 李双1, 罗文芸1, 汪福顺1. 百花水库水质模拟及季节性水质恶化控制对策[J]. 上海大学学报(自然科学版), 2013, 13(5): 441-447.
[3]	胡越黎王尧明. 单芯片多处理器系统任务并行处理设计[J]. 上海大学学报(自然科学版), 2009, 15(5): 501-505.
[4]	王佳张金艺林峰江燕辉. Wrapper扫描链均衡与系统芯片测试调度的联合优化算法[J]. 上海大学学报(自然科学版), 2009, 15(4): 336-341.
[5]	沈丽;汪敏. EPON 动态带宽分配算法[J]. 上海大学学报(自然科学版), 2007, 13(3): 237-244 .