计算机科学 ›› 2021, Vol. 48 ›› Issue (11A): 22-29.doi: 10.11896/jsjkx.201200167

• 智能计算 • 上一篇    下一篇

集装箱码头岸桥最优调度理论研究和高效算法

高熙, 孙未未   

  1. 复旦大学计算机科学技术学院 上海201203
    上海市数据科学重点实验室(复旦大学) 上海201203
    上海智能电子与系统研究院 上海200433
  • 出版日期:2021-11-10 发布日期:2021-11-12
  • 通讯作者: 孙未未(wwsun@fudan.edu.cn)
  • 作者简介:xgao18@fudan.edu.cn
  • 基金资助:
    国家自然科学基金(61772138)

Theoretical Research and Efficient Algorithm of Container Terminal Quay Crane Optimal Scheduling

GAO Xi, SUN Wei-wei   

  1. School of Computer Science,Fudan University,Shanghai 201203,China
    Shanghai Key Laboratory of Data Science,Fudan University,Shanghai 201203,China
    Shanghai Institute of Intelligent Electronics and Systems,Shanghai 200433,China
  • Online:2021-11-10 Published:2021-11-12
  • About author:GAO Xi,born in 1996,postgraduate.His main research interests include intelligent transport and so on.
    SUN Wei-wei,born in 1973,Ph.D,professor,is senior member of China Computer Federation.His main research interests include intelligent transport and big spatial-temporal data.
  • Supported by:
    National Natural Science Foundation of China(61772138).

摘要: 岸桥调度问题是集装箱码头中最核心的调度问题之一。现有研究成果无法在可行时间内计算出对较大规模业务的最优调度,因此现有岸桥调度算法普遍采用启发式策略,以保障在可行时间内计算出一种调度。首先从理论角度证明了完工时间下界的正确性,设计了一种最优调度构造方法,完备了岸桥调度问题的理论体系;其次,在此理论工作基础上,设计了线性时间复杂度的算法求出最优调度;最后,用实验验证了所提方法在解的质量和效率上显著优于现有方法。

Abstract: Quay crane scheduling problem is one of the most important scheduling problems in container terminals.The existing research results can not calculate the optimal scheduling of large-scale business in the feasible time,so the existing quay crane scheduling algorithms generally adopt heuristic strategies to ensure that scheduling can be calculated in the feasible time.In this paper,firstly,the correctness of the lower bound of completion time is proved theoretically,an optimal scheduling construction method is designed and the theoretical system of quay crane scheduling problem is completed.Secondly,based on the theoretical work,an algorithm of linear time complexity is designed to find the optimal scheduling.Finally,experiments show that the proposed method is significantly better than the existing methods in terms of solution quality and efficiency.

Key words: Quay crane scheduling, Lower bound of completion time, Optimal solution, Linear algorithm

中图分类号: 

  • TP399
[1]ZHANG S,LV M Q,DAI J H,et al.Research on Quay Crane Scheduling Optimization Based on the Uncertainty of Operation Time[J].Industrial Engineering and Management,2020,25(5):54-62.
[2]Statistics of Container Terminal Throughput for Main Ports in China (Jul.,2020)[J].Containerization,2020,31(8):34-35.
[3]ZHAO C.The Way to Improve the Port[J].Industry City,2020(10):54-55.
[4]LU S X,LV C H,QING T.An Algorithm Based on Make Span Lower Bound for Quay Crane Schedule Problem in Container Terminals[J].Operations Research Transactions,2020,24(3):67-76.
[5]LIU J,WAN Y W,WANG L.Quay crane Scheduling at Container Terminals to Minimize the Maximum Relative Tardiness of Vessel Departures[J].Naval Research Logs,2006,53(1):60-74.
[6]MIAO W L.Quay Crane Scheduling with Non-Interference Constraints in Port Container Terminals[J]. Transportation Research Part E Logistics & Transportation Review,2008,44(1):124-135.
[7]KAVESHGAR N,NUYNH N,RAHIMIAN S K.An Efficient Genetic Algorithm for Solving the Quay Crane Scheduling Problem[J].Expert Systems With Applications,2012,39(18):13108-13117.
[8]CHUNG S H,FELIX T,CHAN S.A Workload Balancing Genetic Algorithm for the Quay Crane Scheduling Problem[J].International Journal of Production Research,2013,51(16):4820-4834.
[9] SU N Y,ZHANG M J,JOHNSTON M,et al.Hybrid Evolutionary Computation Methods for Quay Crane Scheduling Problems[J].Computers and Operations Research,2013,40(8):2083-2093.
[10]LEE D H,WANG H Q,MIAO L X.Quay Crane Schedulingwith Handling Priority in Port Container Terminals.Engineering Optimization,2008,40(2):179-189.
[11]KIM K H,PARK Y M.A Crane Scheduling Method for Port Container Terminals [J].European Journal of Operational Research,2004,156(3):752-768.
[12]ZHU Y,LIM A.Crane Scheduling with Non-Crossing Con-straint.Journal of the Operational Research Society,2006,57(12):1464-1471.
[13]PETERKOFSKY R I,DAGANZO C F.A Branch and Bound Solution Method for the Crane Scheduling Problem[J]. Transportation Research Part B Methodological,1990,24(3):159-172.
[14]MOCCIA L,CORDEAU J F,GAUDIOSO M,et al.A Branch-and-Cut Algorithm for the Quay Crane Scheduling Problem in a Container Terminal[J].Naval Research Logistics,2006,53(1):45-59.
[15]BIERWIRTH C,MEISEL F.A Fast Heuristic for Quay Crane Scheduling with Interference Constraints[J].Journal of Scheduling,2009,12(4):345-360.
[16]SONG Y T,WANG N,WU N.Optimization of Berth and Quay Crane Collaborative Scheduling Considering Both the Cost and Time Guarantee Rate[J].Operations Research and Management Science,2020,29(4):130-137.
[17]LE M L,ZHAO Y Y,LIU X L.Shore-Mounted Gantry Crane Scheduling for Single Vessel Under Time Window-Using Mathematical Programming and Rule Heuristic Algorithm[J].Computer Engineering and Applications,2014,50(9):242-248.
[1] 李玉, 段宏岳, 殷昱煜, 高洪皓. 基于区块链的去中心化众包技术综述[J]. 计算机科学, 2021, 48(11): 12-27.
[2] 廉文娟, 赵朵朵, 范修斌, 耿玉年, 范新桐. 基于认证及区块链的CFL_BLP_BC模型[J]. 计算机科学, 2021, 48(11): 36-45.
[3] 杨青, 张亚文, 朱丽, 吴涛. 基于注意力机制和BiGRU融合的文本情感分析[J]. 计算机科学, 2021, 48(11): 307-311.
[4] 代闯闯, 栾海晶, 杨雪莹, 过晓冰, 陆忠华, 牛北方. 区块链技术研究综述[J]. 计算机科学, 2021, 48(11A): 500-508.
[5] 刘彤彤, 杨环, 西永明, 郭建伟, 潘振宽, 黄宝香. 机器学习在脊柱疾病智能诊治中的应用综述[J]. 计算机科学, 2021, 48(11A): 597-607.
[6] 穆聪聪, 王一舒, 袁野, 乔百友, 马玉亮. 时序图中Top-k稠密子图查询算法研究[J]. 计算机科学, 2021, 48(10): 152-159.
[7] 陈圆圆, 严丽, 章哲庆, 马宗民. 基于邻域结构的时态RDF模型及索引方法[J]. 计算机科学, 2021, 48(10): 167-176.
[8] 王栋, 周大可, 黄有达, 杨欣. 基于多尺度多粒度特征的行人重识别[J]. 计算机科学, 2021, 48(7): 238-244.
[9] 刘荣, 张宁. 图片分析在电子商务中的应用现状与未来趋势——基于图片视觉和内容特征的研究综述[J]. 计算机科学, 2021, 48(6A): 137-142.
[10] 韩丽霞, 张占营. 基于树增益朴素贝叶斯网络的服务定价策略[J]. 计算机科学, 2021, 48(6A): 203-.
[11] 卓雅倩, 欧博. 噪声环境下的人脸防伪识别算法研究[J]. 计算机科学, 2021, 48(6A): 443-447.
[12] 王引娣, 章哲庆, 严丽. 基于双时态RDF模型的索引方法[J]. 计算机科学, 2021, 48(4): 63-69.
[13] 张少杰, 鹿旭东, 郭伟, 王世鹏, 何伟. 供需匹配中的非诚信行为预防[J]. 计算机科学, 2021, 48(4): 303-308.
[14] 陈玉平, 刘波, 林伟伟, 程慧雯. 云边协同综述[J]. 计算机科学, 2021, 48(3): 259-268.
[15] 邓丽, 武金达, 李科学, 卢亚康. 基于TPE的SpaRC算法超参数优化方法[J]. 计算机科学, 2021, 48(2): 70-75.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 史经启,杨庚,孙彦珺,白双杰,闵兆娥. 支持浮点运算的高效并行全同态加密算法[J]. 计算机科学, 2018, 45(5): 116 -122 .
[2] 桂逸男, 老松杨, 康来, 白亮. 基于视觉的地理定位中PnP算法的精度评估方法[J]. 计算机科学, 2018, 45(8): 13 -16 .
[3] 朱虎超, 虞慧群, 范贵生, 邓存彬. 燃气行业热线数据的情感分析[J]. 计算机科学, 2018, 45(9): 248 -252 .
[4] 李虹利, 蒙祖强. 运用信息增益和不一致度进行填补的属性约简算法[J]. 计算机科学, 2018, 45(10): 217 -224 .
[5] 曹峰,唐超,张婧. 一种结合二元蚁群和粗糙集的连续属性离散化算法[J]. 计算机科学, 2017, 44(9): 222 -226 .
[6] 祁建军,魏玲. 三元背景及概念三元格的简化[J]. 计算机科学, 2017, 44(9): 53 -57 .
[7] 李敬雯,刘宇雷,秦小麟. 一个情境相关的双层室内空间数据模型[J]. 计算机科学, 2017, 44(8): 187 -192 .
[8] 范艳芳. 协作环境下的时空约束强制访问控制模型[J]. 计算机科学, 2017, 44(8): 107 -114 .
[9] 涂玲,马跃,程诚,周彦晖. 基于协议混合变形的Web安全模糊测试与效用评估方法[J]. 计算机科学, 2017, 44(5): 141 -145 .
[10] 王珍,韩忠明,李晋. 大规模数据下的社交网络结构洞节点发现算法研究[J]. 计算机科学, 2017, 44(4): 188 -192 .