计算机应用 ›› 2020, Vol. 40 ›› Issue (3): 897-901.DOI: 10.11772/j.issn.1001-9081.2019071242

• 应用前沿、交叉与综合 • 上一篇    下一篇

基于量子遗传混合算法的泊位联合调度

蔡芸1,2, 刘朋青1,2, 熊禾根1,2   

  1. 1. 冶金装备及其控制教育部重点实验室(武汉科技大学), 武汉 430081;
    2. 机械传动与制造工程湖北省重点实验室(武汉科技大学), 武汉 430081
  • 收稿日期:2019-07-18 修回日期:2019-09-25 出版日期:2020-03-10 发布日期:2019-10-25
  • 通讯作者: 刘朋青
  • 作者简介:蔡芸(1970-),女,江苏南通人,副教授,博士,主要研究方向:优化算法、生产调度;刘朋青(1995-),男,湖北黄冈人,硕士研究生,主要研究方向:智能算法、调度优化;熊禾根(1966-),男,江西丰城人,教授,博士,主要研究方向:智能算法、制造系统调度。
  • 基金资助:
    国家自然科学基金资助项目(51875422)。

Berth joint scheduling based on quantum genetic hybrid algorithm

CAI Yun1,2, LIU Pengqing1,2, XIONG Hegen1,2   

  1. 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
  • Received:2019-07-18 Revised:2019-09-25 Online:2020-03-10 Published:2019-10-25
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51875422).

摘要: 为了提高集装箱港口服务效率,减少船舶服务的拖期费用,针对港口硬件(泊位、拖轮、岸桥)既定条件下的拖轮-泊位联合调度问题,新建了以最小化总体船舶在港时间和总拖期时间为目标的数学模型,设计了一种混合算法进行求解。首先,分析确定了将量子遗传算法(QGA)和禁忌搜索(TS)算法进行串行混合的策略;然后,依据该联合调度问题特点,在解决算法实施中的关键技术问题(染色体结构设计和测量、遗传操作、种群更新等)的同时,采用了动态量子旋转门更新机制;最后,用生产实例验证了算法的可行性及有效性。算法实验结果表明,与人工调度结果相比,混合算法的总体船舶在港时间和总拖期时间分别减少了24%和42.7%;与遗传算法结果相比,分别减少了10.9%和22.5%。所提模型及算法不仅能为港口船舶的入泊、离泊和装卸作业环节提供优化作业方案,而且能增强港口竞争力。

关键词: 联合调度, 拖期, 量子遗传算法, 禁忌搜索, 动态量子旋转门

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.

Key words: joint scheduling, tardiness, Quantum Genetic Algorithm (QGA), Tabu Search (TS), dynamic quantum revolving gate

中图分类号: