Berth joint scheduling based on quantum genetic hybrid algorithm
CAI Yun1,2, LIU Pengqing1,2, XIONG Hegen1,2
1. Key Laboratory for Metallurgy Equipment and Control Units, Ministry of Education(Wuhan University of Science and Technology), Wuhan Hubei 430081, China; 2. Hubei Key Laboratory of Mechanical Transmission and Manufacturing Engineering(Wuhan University of Science and Technology), Wuhan Hubei 430081, China
Abstract：In order to improve the efficiency of container port services and reduce the tardiness costs of ship services, a new mathematical model was established with the objective of minimizing the sojourn time of the ships and the total tardiness for the tug-berth joint scheduling problem under the established conditions of port hardwares (berths, tugboats, quay cranes), and a hybrid algorithm was designed for solving it. Firstly, the serial hybrid strategy of Quantum Genetic Algorithm (QGA) and Tabu Search (TS) algorithm was analyzed and determined. Secondly, according to the characteristics of the joint scheduling problem, the update strategy of dynamic quantum revolving gate was adopted when solving key problems in the executing process of the hybrid algorithm (chromosome structure design and measurement, genetic manipulation, population regeneration, etc.). Finally, the feasibility and effectiveness of the algorithm were verified by the production examples. The experimental results show that compared with results of manual scheduling, the sojourn time of the ships and total tardiness of the hybrid algorithm are reduced by 24% and 42.7% respectively; compared with the results of genetic algorithm, they are reduced by 10.9% and 22.5% respectively. The proposed model and algorithm can not only provide optimized operation schemes for berthing, unberthing as well as loading and unloading operations of port ships, but also increase the port competitiveness.
[1] 段文秀. 基于入侵野草算法的泊位分配方式研究[D]. 杭州:浙江工业大学,2017:9-31. (DUAN W X. Research on berth allocation based on invasive weed optimization[J]. Hangzhou:Zhejiang University of Technology,2017:9-31.) [2] DULEBENETS M A. A novel memetic algorithm with a deterministic parameter control for efficient berth scheduling at marine container terminals[J]. Maritime Business Review,2017,2(4):302-330. [3] XIANG X,LIU C,MIAO L. A bi-objective robust model for berth allocation scheduling under uncertainty[J]. Transportation Research Part E:Logistics and Transportation Review,2017, 106:294-319. [4] 刘志雄, 李俊, 邵正宇, 等. 拖轮动态调度的混合演化策略算法设计[J]. 计算机工程与设计,2016, 37(2):519-524,529.(LIU Z X,LI J,SHAO Z Y,et al. Design of hybrid evolutionary strategy algorithm of dynamic tugboat scheduling problem[J]. Computer Engineering and Design,2016,37(2):519-524,529.) [5] 王维. 某港口企业拖轮燃油成本控制研究[D]. 北京:北京理工大学,2016:5-9. (WANG W. Study on the control of fuel costs of certain port enterprise tug[J]. Beijing:Beijing Institute of Technology,2016:5-9.) [6] HU Z. Multi-objective genetic algorithm for berth allocation problem considering daytime preference[J]. Computers and Industrial Engineering,2015,89:2-14. [7] 王军, 郭力铭, 杜剑, 等. 基于动态学习的泊位调度方案优化[J]. 交通运输系统工程与信息,2018,18(5):197-203.(WANG J,GUO L M,DU J,et al. Berth scheduling scheme optimization based on dynamic learning[J]. Journal of Transportation Systems Engineering and Information Technology,2018,18(5):197-203.) [8] 王颖. 拖轮与离散泊位的协同调度[D]. 大连:大连海事大学, 2014:16-18. (WANG Y. Research on port tugboat scheduling optimization and simulation[D]. Dalian:Dalian Maritime University, 2014:16-18.) [9] 白洁. 拖轮和泊位的协同调度研究[D]. 大连:大连海事大学, 2013:18-32. (BAI J. Research on tugboat-berth scheduling[D]. Dalian:Dalian Maritime University,2013:18-32.) [10] 杨劼, 高红, 刘涛, 等. 基于改进遗传算法的泊位岸桥协调调度优化[J]. 计算机应用,2016,36(11):3136-3140.(YANG J, GAO H,LIU T,et al. Integrated berth and quay-crane scheduling based on improved genetic algorithm[J]. Journal of Computer Applications,2016,36(11):3136-3140.) [11] 曲志坚, 陈宇航, 李盘靖, 等. 基于多算子协同进化的自适应并行量子遗传算法[J]. 电子学报,2019,47(2):266-273.(QU Z J,CHEN Y H,LI P J,et al. Cooperative evolution of multiple operators based adaptive parallel quantum genetic algorithm[J]. Acta Electronica Sinica,2019,47(2):266-273.) [12] SERVRANCKX T,VANHOUCKE M. A tabu search procedure for the resource-constrained project scheduling problem with alternative subgraphs[J]. European Journal of Operational Research, 2019,273(3):841-860. [13] 李昆仑, 关立伟. 实数编码量子共生演算法及其在云任务调度中的应用[J]. 计算机应用研究,2019,36(3):786-791. (LI K L,GUAN L W. Real-coded quantum SOS algorithm and its application in cloud task scheduling[J]. Application Research of Computers,2019,36(3):786-791.) [14] ALAM T,RAZA Z. Quantum genetic algorithm based scheduler for batch of precedence constrained jobs on heterogeneous computing systems[J]. The Journal of Systems and Software,2018,135:126-142. [15] XIONG H,WU Z,FAN H,et al. Quantum rotation gate in quantum-inspired evolutionary algorithm:a review,analysis and comparison study[J]. Swarm and Evolutionary Computation,2018, 42:43-57.
2020, Vol. 40 
