Simulation-based Optimization on Quay Crane Scheduling of Container

Terminals

Li Haoyuan, Sun Qi

Dalian Neusoft University of Information, Dalian 116023, China
E-mail: lihaovuan@neusoft.edu.cn

Abstract: By applying the object-oriented simulation modeling method of discrete event system, this paper establishes an simulating model of container terminal operating system, including vessels, anchorages, berths, gantry cranes, internal and external container trucks and gate system. In order to solve the quay crane scheduling problem of container terminal, a lot of stochastic factors in the problem are taken into account. Simulation-based optimization (SBO) method is proposed to solve the problem. Genetic algorithm, particle swarm algorithm and simulated annealing algorithm are used respectively as the superior optimizer, and their application performance is compared and analyzed.

Key Words: Simulation-Based Optimization; Container Terminal; Quay Crane Scheduling

1. INTRODUCTION

In the container terminal operating system, quay crane is not only the most expensive and importantly handling machinery, but also a major bottleneck restricting the working efficiency of the entire marina. All container terminals hope quay cranes can conduct operations at best efficiency. Container managers pay more and more attentions to improve operational efficiency by optimizing quay crane scheduling.

For quay crane scheduling^ Daganzo[l] divided ship handling tasks into several lifting area and established a mixed integer programming model to solve quay crane scheduling. By this method, the number of quay crane assigned to each lifting area is determined, with the objective of optimizing the shortest total delay time for all ships. Kimp] established a single-ship quay crane scheduling model, using branch and bound method and greedy random search algorithm as the solution methods. Lee[3] established a quay crane scheduling integer programming model and used genetic algorithms as the solution method. Wang Huiqiu[4] considered the factor of non-crossing and safe distance, and established a mixed integer programming model of the quay crane scheduling, and solved the problem by genetic algorithm. Tan Shengqiang[5] established a multi-objective integer programming model based on ship service priority. Legato [6] considered the factors such as the average operating rate, the preparation time, the delivery time, the safety requirements and so on. Chung[7] established a model considering the task priority and non-interference factors, and used an improved genetic algorithm to solve. These studies are based on the traditional analytic-based modeling method to solve the quay crane scheduling problem, mainly for the deterministic environment. However, many uncertainty factors (such as the operational efficiency of the quay crane, the operation of the external card in the yard) make the deterministic model cannot reflect the real system and affect the accuracy of the final decision-making scheme. In this paper, the influence of random factors of quayside operation is fully considered, and the quay crane scheduling problem is studied by simulation-based optimization method. Genetic algorithm, particle swarm algorithm and simulated annealing algorithm are used respectively as the superior optimizer, and their application performance is compared and analyzed.

1. SIMULATION MODEL
   1. Container terminal layout

Container terminal operating system simulation model is established in this paper based on the actual layout of a domestic container ports, as shown in Fig.l. Quay consists of four berths, each berth assigned several quay cranes, each quay crane is equipped with 10 internal container trucks; The yard consists of 36 operating areas, each area can accommodate 50 x 6 x 4 standard containers, each area is equipped with one gantry crane to complete the internal and

思爾E思爾M埋

Fig. 1 Layout of container terminal

external container truck loading and unloading operations, The gate of the yard is composed of 3 entrance channels and 3 exit channels. It is responsible for the procedures of handling external container trucks and the allocation of operating areas.

1. Quay Crane Scheduling Problem Description

When a container ship enters a berth, the ship will be allocated a certain number of quay cranes for loading and unloading operations. Figure 2 is a schematic diagram of quay crane scheduling. As shown in Figure 2, the ship is divided into several ship areas. The goal of dispatching is to assign the task vessel area for each quay crane and the sequence of operations in different areas. So that container ships can be completed as quickly as possible.

Sea Area

Fig. 2 A schematic diagram of quay crane scheduling

In the actual operation of the quay crane, some physical constraints must be taken into account.

Firstly, at any time during the operation, one ship area can be assigned to only one quay crane until it completes all operations in the area.

Secondly, quay cranes run on the same rail, so the quay cranes can not cross each other. This is also the most important constraint on the quay crane scheduling problem..

Thirdly, for safety reasons, any two quay cranes must maintain a certain distance to ensure the safety of the operation, in this chapter, it is assumed that the safety distance between the two quay cranes is more than two ship areas.

1. Simulation Parameters Setting

In this simulation model, considering only a single container ship unloading operation, and the container ship is divided into 20 areas, the unloading task of each area is (80,168,180,66,2⑻,180,220,60,50,1

基于仿真的集装箱码头起重机调度优化

码头

李浩源孙琦

大连东软信息大学，辽宁大连116023
电子邮件：lihaovuan@neusoft.edu.cn

摘要：应用离散事件系统的面向对象仿真建模方法，建立了集装箱码头操作系统的仿真模型，包括船舶，锚地，泊位，龙门起重机，内外集装箱卡车和闸门系统。为了解决集装箱码头的码头起重机调度问题，考虑了问题中的许多随机因素。提出了基于仿真的优化（SBO）方法来解决该问题。分别采用遗传算法，粒子群算法和模拟退火算法作为优化算法，并对其应用性能进行了比较和分析。

关键词：基于仿真的优化;集装箱码头;码头起重机调

1. 介绍

在集装箱码头操作系统中，码头起重机不仅是最昂贵，最重要的搬运机械，而且是制约整个码头工作效率的主要瓶颈。所有集装箱码头都希望码头起重机能够以最佳效率进行作业。通过优化码头起重机调度，集装箱管理人员越来越关注提高运营效率。

对于码头起重机调度^ Daganzo [l]将船舶处理任务划分为若干升降区域，并建立了混合整数规划模型来解决码头起重机调度问题。通过这种方法，确定分配给每个提升区域的码头起重机的数量，目的是优化所有船舶的最短总延迟时间。Kimp]建立了单船码头起重机调度模型，采用分支定界法和贪婪随机搜索算法作为求解方法。Lee [3]建立了码头起重机调度整数规划模型，并使用遗传算法作为求解方法。王惠秋[4]考虑了非交叉和安全距离因素，建立了码头起重机调度的混合整数规划模型，并通过遗传算法解决了该问题。Tan Shengqiang [5]建立了基于船舶服务优先级的多目标整数规划模型。Legato [6]考虑了平均开工率，准备时间，交货时间，安全要求等因素。Chung [7]建立了考虑任务优先级和非干扰因素的模型，并使用改进的遗传算法求解。这些研究是基于传统的基于分析的建模方法来解决码头起重机调度问题，主要针对确定性环境。然而，许多不确定因素（例如码头起重机的运行效率，院内外部卡的运行）使得确定性模型不能反映真实系统并影响最终决策方案的准确性。本文充分考虑了码头运行随机因素的影响，并采用基于仿真的优化方法研究了码头起重机调度问题。分别采用遗传算法，粒子群算法和模拟退火算法作为优化算法，并对其应用性能进行了比较和分析。

2模拟模型

2.2集装箱码头布局

基于国内集装箱港口的实际布局，建立了集装箱码头操作系统仿真模型，如图1所示。码头由四个泊位组成，每个泊位分配几个码头起重机，每个码头起重机配备10个内部集装箱卡车;该码头由36个操作区域组成，每个区域可容纳50 times;6times;4标准集装箱，每个区域配备一个龙门起重机，以完成内部和外部集装箱卡车装卸作业，院门由3个入口通道和3个出口通道组成。它负责处理外部集装箱卡车的程序和操作区域的分配。

图1集装箱码头的布局

2.2码头起重机调度问题描述

当集装箱船进入泊位时，船舶将被分配一定数量的码头起重机进行装卸作业。图2是码头起重机调度的示意图。如图2所示，该船分为几个船区。调度的目标是为每个码头起重机分配任务船只区域和不同区域的操作顺序。

图2码头起重机调度示意图

这样集装箱船就可以尽快完成。

在码头起重机的实际操作中，必须考虑一些物理限制。

首先，在操作期间的任何时间，只有一个船舶区域可以分配给一个码头起重机，直到它完成该区域的所有操作。

其次，码头起重机在同一轨道上运行，因此码头起重机不能相互交叉。这也是码头起重机调度问题最重要的制约因素。

第三，出于安全原因，任何两个码头起重机必须保持一定距离以确保操作的安全性，在本章中，假设两个码头起重机之间的安全距离超过两个船舶区域。

2.3模拟参数设置

在这个模拟模型中，只考虑单个集装箱船的卸载作业，而集装箱船分为20个区域，每个区域的卸载任务是（80,168,180,66,218，180,220,60,50,140，46,210,20,90,160，110,250,50,200,160），单位：TEU。船舶到货后，配置三台码头起重机参与运营。每个码头起重机配备10个内部集装箱卡车，用于水平运输。码头起重机从一个船区到另一个船区的行程时间为60秒。模拟时间设定为卸载集装箱船的整个过程。仿真模型模拟码头起重机的操作，龙门起重机的操作，内部集装箱卡车的水平运输操作，还包括在院子中的外部集装箱卡车的操作。其中，充分考虑了门式起重机和门式起重机的运行效率，外部集装箱卡车的影响等随机因素。每个随机参数设置如下：

1. 外部集装箱卡车的到达时间间隔呈指数分布，参数义= 0.45bull;
2. 码头起重机的处理效率通常是＃（34.6,2.69）。
3. 庭院门式起重机的运行效率通常为7V（60.2,69）。
4. 外部集装箱卡车在闸门处理时间，空车正常分布7 ^（40.43,2.69），载重车辆正常分布N（6l .28,2.69）。

3、基于仿真的算法

3.1算法原理

基于仿真的遗传算法原理如图3所示。首先，需要建立真实系统的模拟模型。通过优化算法，产生系统性能的初始参数。将初始参数放入系统模型中，将输出作为评估指标，并将其带回优化算法。然后通过进化搜索可以得到更好的性能参数。将它们作为新输入返回到系统模型，获取输出，重新评估并再次优化，直到结果符合停止标准。这样，就可以得到最终的系统优化参数。

图3 SBO算法原理

3.2遗传算法设计

1. 编码方案

过去，码头桥的操作顺序已被用作编码方法。以往的研究使用码头起重机操作的顺序作为编码方法。在本文中，船舶区域操作的顺序被用作编码方法。如图4所示，染色体中的基因代表船舶区域编号，当确定区域操作的顺序时，

CUmfisame S 18 20 15 5 13 2 :0 3 4 t 14 7 9 t 6 12 M 19 8

操作_{2 3 4 5 6 ? 8} 9 12 D 14 15 16 17 18 19 20序列

以上为染色体编码

因此确定码头起重机操作的顺序。

考虑到基于仿真的优化方法是运行仿真模型而不是数学模型来获得解的评估值，使用这种编码可以充分利用仿真程序的逻辑。在模拟过程中，通过模拟程序的操作，逐渐获得码头起重机的操作顺序。完成了码头起重机操作顺序的生成和仿真程序的运行过程。该编码方法可以满足非交叉约束和安全距离约束的要求。

1. 目标函数

选择集装箱船装载和卸载时间跨度作为目标函数值，如公式（1）所示。

Fitness = max F_b

1. 遗传算子

由于本文采用序列编码，使用传统的单点交叉或双切点交叉方法将产生合法代码。同时，为了修复不可行代码，为了更好地保持染色体基因之间的相邻关系，选择顺序交叉方法作为交叉算子。

突变是根据突变概率选择群体中的基因数量，突变算子可以使群体跳出局。为了解决这个问题，根据概率随机选择染色体中的两个基因，并交换两个基因的船面积数。

3.3粒子群优化（PSO）设计

1. 编码方案

类似地，在顺序编码中，船舶区域的操作顺序被视为粒子的表达。码头起重机的操作顺序与3.2（1）相同。

1. 目标功能

与3.2（2）类似，将集装箱船装卸作业的时间跨度作为目标函数的值。

1. 速度更新方程

粒子i的位置：(x_n, x_/2, bull; bull;,)

粒子速度/：v_f =（v_zl，v_/2bull;bull;，^）

粒子i的最佳点：= (p_a, p_/2, bull; bull;, p_iD)

该组中所有粒子的最佳点：

P_g=(P_gvP_g2^^P_gD)

用F_最大初始化粒子的速度，F_最大等于20。

粒子速度根据以下等式更新：

^viD ^{= v}iD ^c\^iPiD ^{— x}zX gt;) ^ VipgD ~ ^xi〇) (2)

学习因子c_x 和c_t 均等于2。

1. 位置更新

速度设置为粒子改变的概率，如果速度大，则粒子以更大的概率变为新的置换序列。这里的速度要映射到[0,1]。粒子的位置更新过程描述如下：首先进行粒子速度归一化。假设粒子比特值的范围是n，粒子的速度是vf ¹显然，范围在0和1之间。它确定粒子i的编码是否产生交换。一旦以这种概率产生交换，粒子i的位置d就变成该组最佳解的相应比特值，如图5所示。

50	5	10	40	25
1
1.0	0.1	0.2	0.8	0.5
i
1	11	3	17	6
i i
17	11	3	7	9
^
7	11	3	17	9

图5粒子更新示意图

1. 变异算子

由于粒子以与群体的最优解相同的概率收敛，如果粒子与群体完全相同，则它们将不会改变。为了避免这种情况，引入了变异算子。当粒子和总体最优解相同时，随机选择代码中的两个位置并交换比特值。

3.4模拟退火（SA）算法设计

1. 编码方案

类似地，在顺序编码中将集装箱船区域的操作顺序作为粒子的表达。码头起重机的操作顺序与3.2（1）相同。

1. 目标功能

与3.2（2）类似，将集装箱船装卸作业的时间跨度作为目标函数的值。

1. 邻里定义

根据本章中使用的序列编码的表达式，邻域被定义为船舶区域中操作序列的成对变化的集合。例如：从当前状态[1,2,3,4，...]，交换两个船区的操作顺序（交换1和4），然后得到一个新状态[4,2,3,1， ...]。这完成了邻里移动。

（4）温度参数设定

设定初始温度T_q = 10000，终止温度7y = 0。

退火函数T_{k l} = T_k -AT，AT⁷ = 100。

通过设置内循环迭代n（T_k）来实现热平衡，这里设置n（T_k）= 50。

4、实验分析

4.1实验结果

1. 基于仿真的通用算法（GA）算法考虑到一系列随机因素对仿真模型的影响，通过运行仿真程序得到的同一染色体的评估值将不同，因此，在实验中，每个染色体运行平均五次模拟，五次输出的平均值是染色体的评估值。种群大小为50，最大迭代次数为100，交叉概率为0.9，变异概率为0.1。

通过基于仿真的GA计算，最优船区操作顺序为：

[9，12，15，8，19，4，18，1，6，2，14，20，3， 11， 13， 7， 17， 5， 10， 16]

集装箱船卸载作业的总时间范围为65228s（18.12h），算法计算时间为6762s（1.88h）。

1. 基于仿真的粒子群优化算法（PSO）

同样，考虑到实验中的随机因素，每条染色体平均

资料编号：[3971]