基于多Agent的偏好泊位约束下泊位-岸桥分配

朱硕博，金永贺（上海海事大学信息工程学院，上海　201306）

基于多Agent的偏好泊位约束下泊位-岸桥分配

朱硕博，金永贺
（上海海事大学信息工程学院，上海201306）

泊位和岸桥是码头前沿最宝贵的资源，为其设计合理调度机制能够获得更高的效能。考虑连续泊位的岸线，加入偏好泊位约束条件，以最小化偏离偏好泊位成本为目标函数，结合多Agent的智能化特点，提出基于多Agent的联合调度模型，在模型基础上设计分步的遗传算法，实现高效的泊位岸桥联合调度。并用实验证明模型和算法的有效性，实验结果验证引入偏好泊位约束条件确实能提高码头作业效率，降低因偏离偏好泊位带来的成本。

连续泊位；偏好泊位；多Agent；遗传算法；智能化

0　引言

随着经济全球化以及世界贸易的高速发展，集装箱水路运输逐渐呈现船舶的大型化、高速化态势，这也对码头装卸设备的合理配置提出了更高的要求。泊位和岸桥的分配是码头前沿作业的首要环节，因而设计合理的靠泊计划和岸桥分配策略是提高集装箱码头作业效率的关键。

Imai等［1］针对离散的泊位-岸桥调度建立了优化模型，根据船舶总在港时间最小化为原则安排服务顺序。Liang等［2］以船舶总在港时间最小化为目标建立模型，采用遗传算法与启发式算法相结合求解。高超锋［3］针对多个岸桥并行作业时相互干扰的问题，研究了岸桥并行作业效率约束下泊位分配与岸桥调度问题。杜卫华等［4］在泊位岸桥集成调度中加入岸桥移动约束条件，设计算法模型，解决了岸桥频繁移动导致的岸桥作业相互干扰及资源利用率低的问题。

在以上的文献中都没有提及偏好泊位的概念，实际船舶在靠泊作业时是存在偏好泊位约束的，因为船舶在靠泊作业过程所需要的岸桥、集卡、堆场及工作人员已经做好准备，这个泊位就是该船舶的偏好泊位。P. Legato等［5］考虑船舶偏好泊位和时间，以船舶作业时间和岸桥使用数量最少为目标建立泊位分配和岸桥调度模型。乐美龙等［6］针对泊位和岸桥联合分配问题，考虑偏好泊位等7个影响因素的泊位-岸桥集成分配问题。但也只是简单地介绍了偏好泊位作为约束条件之一的分配问题，没有给出具体的偏好泊位对调度的模型优化。郑子龙等［7］针对离散泊位提出了偏好泊位约束下的泊位分配问题，对离散泊位分配建模优化，但是现在泊位发展的趋势是连续泊位，连续泊位越来越符合实际船舶靠泊与码头作业需要。

随着多Agent的智能系统建模的发展，基于多Agent的泊位岸桥调度集成优化成为可能。周鹏飞［8］针对码头堆场管理问题，设计了堆场收发箱多Agent管理系统，实现堆场收发箱分布式动态优化管理。李尤丰［9］通过对集装箱码头装卸作业环节的设备设施的分配调度特点及各子系统间的关系，建立基于多Agent系统的生产调度模型。王祥雪等［10］提出的基于多Agent系统的协同作业模型，设计了系统的Agent层次模型和实线层类图，优化集装箱装卸最短路径搜索方案。李斌［11］针对集装箱码头物流系统的协同生产问题，建立基于Agent的计算的集装箱码头物流系统优化，得出一种高鲁棒的协同生产体系。邹金松［12］通过分析集装箱码头智能操作系统框架，对系统的功能进行设计，实现集装箱码头智能操作系统。

当前已有一些文献是针对动态连续型泊位和岸桥联合调度进行优化的研究，但是考虑偏好泊位这一约束，并结合多Agent智能特点进行研究的文献很少。本文提出的基于多Agent的偏好泊位约束下连续泊位分配和岸桥联合调度问题，建立了联合调度的多Agent模型，并通过算法设计以及仿真模拟实验，分析加入偏好泊位约束条件对船舶的靠泊影响，以及对泊位和岸桥的分配的影响，这对于进一步优化泊位-岸桥调度具有实际意义。

1　问题描述

1.1泊位-岸桥联合调度问题

泊位-岸桥联合调度是指在某段时间内，码头调度人员根据各类资源的状态和调度策略，为每艘即将到港作业的船舶分配最佳靠泊位置和靠泊顺序，并根据船舶作业要求调配相应数量的岸桥，以期望得到最优的服务和最高的作业效率。在实际的操作中，泊位分配和岸桥调度是两个紧密相关的过程，岸桥不是固定在一个位置不动的，而是根据任务需要沿着作业线移动，本文是将泊位和岸桥两者的调度联合起来考虑的。

在码头实际靠泊作业中，每艘船舶都有其偏好的泊位，船舶在靠泊后，参与作业的岸桥数以及堆场运输的协调性等都是码头作业效率的影响因素，船舶停靠在其偏好泊位上能够大幅提高作业效率。对于偏好泊位的描述，可以用图1-1来表示，其中横轴代表泊位岸线，纵轴代表时间；Δbi表示船舶i偏离偏好泊位的距离；Tpr表示船舶i延迟到港时间；Tqs表示船舶i延迟离港时间。

图1　船舶靠泊时空图

1.2Agent的结构设计

根据调度框架结构的需要，设计了混合型的Agent结构，其中，动态管理Agent、岸桥调度Agent和泊位分配Agent作为管理者，侧重的是思考型；船舶Agent、岸桥Agent和泊位Agent作为任务的执行者，侧重的是反应型。Agent内部是由感知器、缓冲区、推理机、知识库、响应器和注册机组成，即Agent=＜P，B，D，K，R，I＞。图2给出了岸桥调度Agent作为管理者的内部结构，其他Agent内部结构与其类似，区别在于推理机的不同。

P：感知器。实时监听发送给Agent的信息，实现对外部环境的主动感知。

B：缓冲区。存放发送给Agent的消息队列。

D：推理机。是Agent的核心组成，包括推理、决策分析、优化及评估等功能，不同类型的Agent的推理机功能不同。

K：知识库。存放Agent相关知识、规则的数据库。

R：响应器。负责向其他Agent发送消息。

I：注册机。Agent中变量的声明、定义和初始化。

图2　岸桥调度Agent的内部结构

1.3泊位岸桥调度多Agent系统框架模型

码头泊位岸桥联合调度是一个复杂、动态的过程，本文在对泊位、岸桥业务流程深入分析的基础上，提出了基于多Agent的泊位-岸桥联合调度系统框架。系统由以下几类Agent组成：船舶Agent、动态管理Agent、泊位Agent、岸桥Agent、泊位分配Agent、岸桥调度A-gent。图3给出了集装箱码头多Agent系统结构框架模型。

图3　集装箱码头多Agent系统结构框架模型

该模型中，动态管理Agent的功能是负责控制和监督整个任务的具体执行；岸线上每个泊位对应一个泊位Agent，实时更新泊位的状态信息，将结果及时反馈给泊位分配Agent，并接受泊位分配Agent的靠泊分配任务；岸线上每个岸桥对应一个岸桥Agent，实时将岸桥状态信息反馈给岸桥调度Agent，接受岸桥调度A-gent的调度；泊位分配Agent负责给各个泊位Agent发送指令，查询泊位Agent的实时信息，接收动态管理A-gent的实时调度请求，根据泊位Agent的实时状态做出回应；岸桥调度Agent接收动态管理Agent的实时调度请求，根据岸桥Agent的状态信息对岸桥进行调度，并进行实时反馈。

2　数学模型

船舶在靠泊过程中偏离偏好泊位，将会降低码头装卸作业效率，导致延迟离港以及延迟到港的问题，从而增加码头作业成本。这些问题是不可避免的，如何将偏离带来的损失控制在最小范围，这是一个复杂的调度问题。本文在连续泊位条件下，加入偏离偏好泊位因素与因偏离偏好泊位对岸桥调度造成的影响的混合整数规划模型。

模型基于以下的假设条件：

（1）岸线有满足船舶靠泊的一切条件；

（2）每艘船舶都有一个偏好的停泊位置；

（3）每艘船舶都有最小岸桥需求数和最大岸桥需求数，本文忽略岸桥移动时间；

船舶作业时间连续，不会中断，相邻岸桥之间存在干扰。为了便于模型的建立，引入以下符号：

2.1参数

A：到港船舶集合，A=｛1，2，…，K｝；

B：港口的可用岸桥总数量；

L：港口岸线的总长度；

li：船舶i的长度；

Ci：能够同时分配给船舶i的岸桥数变化范围，Ci=

pi：船舶i的预期到港时间；

qi：船舶i的预期离港时间；

wi：船舶i的最迟离港时间；

α：偏离偏好泊位系数；

2.2决策变量

bi：船舶i实际靠泊位置；

Δbi：船舶i实际靠泊位置偏离偏好位置的距离，Δbi=|Δbi-bi|；

ri：船舶i实际到港作业时间；

si：船舶i完成作业实际离港时间；

2.3目标函数与约束条件

该模型主要考虑的是船舶在靠泊过程中偏离偏好泊位靠泊，系统重新分配岸桥产生的成本，船舶Δbi'个泊位偏差距离共需要（1+·Δbi）·mi个岸桥服务时间；同时，在目标函数中还应该体现出两个时间差的成本，一是延迟离港时间成本，二是延迟到港的时间成本。该模型的目标函数为：

此模型给出了船舶的靠泊位置、靠泊时间和在每个时间点服务于该船舶的岸桥数量。目标函数式（1）表示船舶在港停泊的最小总成本；式（2）-（4）分别给出目标函数式中三个成本的表达式，（2）式表示因偏离偏好泊位所引起的岸桥变动成本，（3）式表示迟于预期离港时间产生的成本，（4）式表示迟于到港时间产生的成本；（5）式限制了船舶的停泊位置；（6）式表示船舶离港时间与靠泊时间关系；（7）式限制了同一时刻作业的岸桥总数小于总可用岸桥数；（8）式是各船舶的实际作业时间；（9）、（10）式限制了该模型必须保证船舶离港时间不迟于最迟离港时间，到港时间不早于预期到港时间；（11）、（12）式限制了两艘船舶在空间和时间二维图中不会重叠。

3　分步的遗传算法

本文提出的基于多Agent的泊位岸桥联合调度的算法主要思想即：首先根据遗传算法确定船舶的靠泊位置和靠泊顺序；在泊位确定的基础上，再确定每个泊位上的岸桥数量。

算法步骤如下：

①染色体编码：编码方式如表1所示。子染色体1是服务优先级顺序，与泊位偏好成正比；子染色体2是停靠泊位位置。为了保证实验结果的多样性，初始种群随机生成。

表1　染色体编码示例

②适应度值函数：本文模型考虑的是最小化目标函数，故采用目标函数值倒数来表示适应度值函数，即f=1/z。进化过程中适应度值函数越大的染色体，越有可能被保留继续进行遗传操作以生成子代染色体；

③选择策略：采用比例算子，根据上一步个体的适应度函数采用轮盘赌法确定个体被选择出来的概率；

④交叉映射：包括双切点交叉和修复程序，用这种修复程序修复因简单双切点交叉而引起的不合法性。包含四个步骤：（1）确定染色体矩阵切点列X，Y；（2）交换中间部分；（3）选取合理的映射关系（1-2，6-7，5-3；10-30，110-90，125-105）；（4）按映射关系恢复未交换部分的合法性。过程如图4所示。

⑤换位变异：随机在染色体矩阵上选取两列位置，将相应基因的位置交换，过程如图5所示。

⑥终止条件：达到迭代次数或达到最优解情况。

4　算例求解

假设某集装箱码头的连续岸线长度为1200m，岸桥总数为10个，随机选取一段时间内的船舶到港信息如表2。

表2　船舶到港信息

图4　染色体交叉映射过程

图5　染色体换位变异过程

已知设置不同的偏好泊位惩罚成本会对泊位分配结果产生影响，船舶在靠泊泊位时，都希望能够靠泊在偏好泊位，但是泊位分配过程中总存在各种意外。本文通过实验，借助C++软件求解，假设α=0，遗传参数：种群规模为10，遗传迭代次数为200，交叉概率为0.5，变异概率为0.4。通过改变的值，得到不同额外成本下的泊位分配结果如表3所示。

通过表3的结果可以发现，随着偏离偏好泊位惩罚成本的不断上升，对该模型结果的约束效果越明显。当=10时，此时相当于不考虑偏离成本的因素，总的偏离量达到了13，当实验的数值不断增大，总的偏离量也在随之减少。通过实验结果的对比，发现引入惩罚成本概念，可以大大降低船舶偏离偏好泊位的现象，从而提高码头作业效率，降低作业成本。

表3　不同偏好泊位惩罚成本下的泊位分配

为了更直观地观察加入偏好泊位惩罚成本对泊位岸桥联合分配的影响，在其他条件不变的情况下，对比不同偏离系数α下的分配状态，图6、图7分别给出了α=0和α=8泊位岸桥联合调度的结果图。从图中可以看到，当α增大时，船舶靠泊在偏好泊位上的概率更大，进而岸桥的调度也得到了优化。

5　结语

本文在对连续岸线上泊位岸桥联合调度研究基础上，引入偏好泊位约束条件，以偏离偏好泊位成本为约束条件，并结合多Agent智能化的特点，建立基于多A-gent的泊位岸桥联合分配模型。设计了分步的遗传算法，结合数学模型进行泊位分配，降低船舶偏离偏好泊位的概率，再根据泊位状态安排相应数量的岸桥。最后通过对比实验的结果证明了模型和算法是有效的，设置较高的偏离惩罚成本能够使船舶优先考虑偏好泊位。但在文中只是说明了根据泊位分配岸桥数量，而没有具体的分配策略，缺少对Agent间通信的研究，这是接下来需要继续深入研究的。

［1］Imai A，Chen H C，Nishimura E，et al.The Simultaneous Berth and Quay Crane Allocation Problem［J］.Transportation Research Part E Logistics&Transportation Review，2008，44（5）：900–920.

［2］Liang C，Huang Y，Yang Y.A Quay Crane Dynamic Scheduling Problem by Hybrid Evolutionary Algorithm for Berth Allocation Planning［J］.Computers&Industrial Engineering，2009，56（3）：1021-1028.

［3］高超锋，胡志华.岸桥并行作业效率约束下泊位与岸桥集成分派［J］.重庆交通大学学报：自然科学版，2014（3）.

［4］杜卫华，黄有方，杨斌.岸桥移动约束的连续泊位和岸桥集成调度［J］.上海海事大学学报，2013，34（4）：43-48.

［5］Legato P，Gulli R，Trunfio R.The Quay Crane Deployment Problem at a Maritime Container Terminal［C］.Proceedings of the 22nd Eu-ropean Conference on Modeling and Simulation.Campora San Giovanni，Amantea Italy，2008：53-59.

图6　α=0时泊位岸桥联合调度

图7　α=8时泊位岸桥联合调度

［6］乐美龙，刘秀玲.基于泊位偏好与服务优先级的泊位和岸桥分配［J］.辽宁工程技术大学学报（自然科学版），2013（5）：709-712.

［7］郑子龙，杨斌，胡志华.偏好泊位约束下的集装箱港口离散泊位分配问题［J］.水运工程，2013（12）：64-68.

［8］周鹏飞，方金灿.集装箱堆场收发箱管理Multi-Agent系统研究［J］.大连理工大学学报，2013（3）：382-389.

［9］李尤丰.基于MAS的码头物流系统的调度体系研究［J］.计算机技术与发展，2013（5）：246-249.

［10］王祥雪，朱瑾.基于MAS的集装箱自动化码头协同作业系统模型［J］.计算机应用研究，2013，30（04）：1072-1075.

［11］李斌，李文锋.基于MAS的集装箱码头物流系统协同生产调度体系［J］.计算机集成制造系统，2011，17（11）：2502-2513.

［12］邹金松.集装箱码头智能操作系统设计与实现［J］.工程建设与设计，2015（9）：117-120.

Continuous Berth；Preference Berth；Multi-Agent；Genetic Algorithm；Intelligent

Berth-Crane Allocation Problem Based on Multi-Agent with the Preferences of Berthing Position

ZHU Shuo-bo，JIN Yong-he
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

Berth and crane are the most precious resources，making reasonable design for the scheduling mechanism can make full use of resources. Considers the continuous berth with preference berthing constraints，to minimize the deviation from the berth preference cost as objective function，combined with the Multi-Agent's intelligent characteristics，proposes a scheduling model based on Multi-Agent.Designs a new genetic algorithm bases on the model to achieve efficient berth crane scheduling.And makes example to prove the validity of the model and algorithm.The experimental results verify the introduction of preference constraints can efficiency improve the berth handling，and also can reduce the cost caused by the deviation from the berth preference.

1007-1423（2016）20-0039-06

10.3969/j.issn.1007-1423.2016.20.008

朱硕博（1990-），男，江苏徐州人，硕士研究生，研究方向为港口物流优化

金永贺（1988-），男，山东菏泽人，硕士研究生，研究方向为港口物流信息化

2016-04-19

2016-06-10