李晓玲

（北京交通大学海滨学院 基础教学部，河北 黄骅 061199）

1 引言

煤炭作为我国的主要能源，是我国经济飞速发展的重要支撑[1]。在我国“西煤东运，北煤南下”的战略下，煤炭港口发挥了重要作用。近年来，随着经济的发展，港口的吞吐量不断提升，给港口带来巨大经济效益的同时也带来了很多挑战。毕竟港口资源是有限的，如何合理有效的利用港口资源实现更大的吞吐量，成为了港口所面临的重大问题。泊位资源作为煤炭港口的稀缺资源，其合理分配不仅能够提升装船效率，从而减少船舶在港时间，还能够为后续生产计划环节的实施和优化奠定基础。但是，由于煤炭种类繁多，煤炭港口不同于集装箱港口，目前的调度主要还是人工调度，因此对煤炭港口的智能调度研究对提高港口的资源利用率，缓解疏港压力，增加港口效益有着重要的理论和现实意义。

目前，国内外专家都对港口的资源调度问题做了大量深入的研究。Imai 等[2]以最小化船舶等待时间为目标，模拟了静、动态分配模型，采用拉格朗日松弛法对模型进行求解。Henesey 等[3]采用Agent 技术对集装箱港口的船舶运输策略进行了仿真实验，并对不同的策略进行了比较和评价。Wang 和Lim[4]将NP泊位分配问题转化成了一个多阶段决策程序，利用随机定向搜索算法，提出了改善定向搜索计划、两阶段节点质量评估、随机节点选择标准。韩骏等[5]提出了集装箱码头的泊位与岸桥联合调度问题的协调调度优化模型。王军等[6]采用动态学习方法对在泊时间计算函数进行更新，再基于所得函数对泊位调度方案进行优化，设计了并行算法。刘强等[7]对基于线性规划的煤炭码头泊位调度问题进行研究，建立了以船舶整体缺煤量最少和整体在泊时间最短为目标的逐级线性规划模型。综合国内外对港口泊位调度问题的研究发现，大部分的泊位调度问题研究主要集中在集装箱码头，对于煤炭码头的泊位调度问题研究很少。

本文以某大型输出型煤炭港口系统为背景，充分研究了输出型煤炭港口的服务系统特征，在考虑场存能力的前提下，以船舶在港总时间最短及整体装煤量最大为目标建立数学模型，并利用改进的遗传算法对模型进行求解。

2 问题模型

2.1 问题描述

泊位调度问题就是研究一个计划周期内的到港船舶在什么时候进入到什么位置的泊位问题。在煤炭港口物流系统中，船舶作业流程如图1 所示，当船舶到达锚地时，工作人员根据货量需求信息和堆场存储信息，结合码头正在进行的工作信息，为船舶指定合适的堆场位置及泊位，发送作业指令给各工作单元和装卸设备，进行装货作业。装货完成后，船舶离港。

堆场是用来储存煤炭的场所，由于地理空间及设备的限制，每个垛位堆放的基础原煤只能被运输到可到达的若干泊位上。客户需求的煤种称为合同煤种，合同煤种可以由不同种类的基础原煤按照一定的比例混合而成，这个过程称为配煤，配煤过程中需要的基础原煤种类和比例称为配煤方案，对于一艘船舶的一种合同煤种,可以有多个配煤方案供其选择。

正是因为煤炭港口的这个特性，所以在为船舶指泊时，不仅要考虑船泊匹配约束、时间约束、设备约束等，还要考虑船货匹配约束。由于合同煤种可能有多个配煤方案供其选择，所以待排船中有可能存在某些船舶共享几种原煤的情况，若煤量场存不足，就有可能出现排在前面的船取走煤后，后面的船舶就只能等货的情况，这不仅造成对泊位资源的浪费，也降低了港口的吞吐量。

为此，在煤量场存不足的条件下，本文建立了以港口总输出煤量最大及船舶总在港时间最小为目标的多目标线性规划模型，并给出基于遗传算法的求解方法。

图1 船舶作业流程图

2.2 模型假设

为便于模型建立，首先做如下假设：

（1）不考虑机械故障、天气因素等干扰。

（2）假设堆场在该规划期内不会补充库存。

（3）假设船舶一旦停泊不允许移泊。

（4）假设船舶进港后先在锚地等候，一旦被安排进泊便开始作业。

（5）假设每条船舶符合其船型约束的可停靠泊位提前已知。

（6）假设机械的作业效率是一个固定值d。

（7）假设船舶在航道上行驶的时间忽略不计，船舶在每个泊位上的工作时间，即在泊时间窗可以提前计算得出。

2.3 符号说明

b：泊位编号，b ∈B。

v：一个计划周期内的在港船舶编号,v ∈V。

Vb：符合泊位b船型约束的船舶集合，Vb⊂V。

Av：船舶v的计划到港时间。

Gvbk：船舶v停靠在泊位b上作为第k条船被服务时泊位b可到达的堆场可以为其提供的煤量。

Lv：船舶v所要求的配载煤量。

η:船舶要求的最小匹配度。

xvbk=1 表示船舶v停靠在泊位b上作为第k条船被服务，否则，取0。

Cvbk：船舶v停靠在泊位b上作为第k条船被服务时对应的装载量。

2.4 模型建立

港口企业的利润取决于港口的整体输出量，由于存在争煤现象，整体输出量一方面取决于港口的效率，主要表现在船舶的总在港时间，一方面取决于船舶的整体装载量，故本文以整体装载量最大和总在港时间最小为目标函数，考虑船舶与泊位的一次性服务约束、船舶的装载量约束以及时间窗约束，建立如下模型。

目标函数：

式（1）表示所有船舶的整体装载量最大，式（2）表示所有船舶的总在港时间最小。

约束条件：

一次性服务约束：

式（3）表示一艘船只能停靠在一个泊位上，b表示泊位编号，B表示所有泊位的集合；式（4）表示一个泊位一次性最多只能服务于一条船，Vb表示符合泊位b船型约束的船舶集合；式（5）表示在整个计划周期内一条船最多被服务一次。

装载量约束：

式（6）、（7）限制了船舶v停靠在泊位b上作为第k条船被服务时对应的装载量不得小于船舶要求的最小匹配量，也不可能大于相应堆场可以为其提供的煤量。

时间约束：

式（8）-（10）表示第k条船必须在前一条船离泊之后进泊，且计划进泊时间必须大于计划到港时间，小于计划离泊时间。

3 基于改进遗传算法的模型求解方案

该问题是一个具有复杂的多约束条件、多目标函数的优化问题，很难找到精确的算法。遗传算法是模拟自然界生物进化机制的一种算法，具有很好的自组织性、自适应性和自学习性，但传统的遗传算法在实际应用中容易陷入局部最优，或者求解结果与实际情况不一致，为本文在求解模型时加入人工干预的启发式规则，以提高求解的高效性和有效性。

3.1 染色体编码

遗传算法最常用的编码方式是二进制编码，但是泊位调度问题的特性决定了使用二进制编码计算机不易处理，因此本文采用泊位-次序的二维编码方式。例如，一个周期内的到港船舶有9 只，可用泊位有3个，则我们将横轴划分为9个区间，竖轴划分为3个区间，得到一个3×9 的矩阵，矩阵中第i行第j列的值为船舶序号，记做vij，表示第vij号船在第i个泊位作为第j条船被服务。图2则表示一个染色体，第2 行第4 列的元素3 表示3 号船舶停靠在2 号泊位上被第4 个服务，在它前面接受服务的船舶依次是7号、9号、2号船。

图2 染色体举例

这里的0表示不再排船，要求每一行的第一个零元素后不再出现非零元素。

3.2 适应度函数

本文所建立的模型为双目标函数模型，由于两个目标的量纲不同，根据问题本身特性，选择排序方式[8]来计算个体的适应度。

对每一个个体xi，分别计算其两个目标函数值，根据计算的值对所有个体进行排序，得到排序序列S1={R1(xi)}；S2={R2(xi)}，其中，Rj(xi)(j=1,2)表示个体xi在目标j中的优劣排列序号，取值越小说明该个体对于该目标越优。设种群规模为N，定义以下公式作为个体的适应度。

式（11）定义了个体对每个目标的适应度值，分段的意义在于使得最优解的适应度值足够大。式（12）则表示个体的总适应度值。

3.3 初始种群

种群初始化过程结合随机生成和启发式规则的混合方式。启发式规则包括先到先服务（FCFS）原则、紧急船优先、自有船优先等原则，对产生的随机个体验证是否满足约束条件，进行初步筛选，这里涉及到的主要问题为泊位指定和顺序指定（即时间指定）。具体操作过程为：

第一步：根据船货匹配、船泊匹配条件及设备可达性等，确定可用泊位集，随机选择泊位；

第二步：计算可靠泊时间约束，如果该泊位已经有船，随机选择排列顺序，否则根据最早可靠泊时间窗，随机选择时间点，作为该泊位第一艘被服务船舶；若可靠泊时间约束无解，重新制定泊位，若所有泊位无解，则计入未排船集合。

第三步：更新数据。将启发式规则和随机生成原则结合在一起，既保证了初始种群中基因的多样性，又保证初始种群的优良性和有效性。

3.4 遗传操作

遗传操作主要包括选择、交叉和变异操作。

（1）选择操作。选择操作的目的是为了从群体中选择优良的个体，使他们有机会作为父代来繁殖子孙。根据适应度函数的特性，这里选用轮盘赌方法。

第一步，根据适应度函数的定义方式，计算出每一个个体的适应度值；

第四步：若r ＜q1，则选择个体1，否则选择个体k，使得qk-1＜r ≤qk成立；

第五步：重复第三、四步N次。

（2）交叉操作与变异操作。由适应度函数的特性，交叉概率和变异概率都由以下公式自适应产生。

其中fmax为群体中所有个体的最大适应度值，为平均适应度值为要进行交叉的个体的最大适应度值（要进行变异的个体的适应度值），c,d为[ ]0,1之间的常数。由于采用二维编码方式，这里举例说明具体的交叉方式和变异方式。

①选择一对个体作为父代个体1 和父代个体2，如图3所示。

②生成随机数P与交叉概率pc比较，如果P ＞pc，则不进行交叉，直接将父代复制到子代中，否则转③。

③随机选择一个位置，写出对应元素对。如果没有零元素，如第2 行第3 列，对应元素对为（2，4），找到个体2中该位置船号（4）在个体1中的位置（第3行第1列），交换这两个位置上的船号；同时找到个体1 中该位置船号（2）在个体2 中的位置（第1 行第1列），交换这两个位置上的船号，得到新一代个体（如图4所示新个体1、新个体2），否则，转④。

图3 父个体举例

④若有两个零则不进行交叉操作，否则若有一个零如第2行第4列（3,0），则从该非零数字所在的个体中任选一行的第一个零与之互换（若该非零数字为所在行最后一个非零数字，则与除了本行外的其他行的非零数字互换），从零元素所在的个体中找到该非零数字，二者交换。剔除非零行非零数字前面的零，产生新一代个体（如图4所示新个体3、新个体4）。

图4 新个体举例

⑤对于通过选择复制及交叉产生的新个体进行变异操作，由于变异概率pm比较小，变异操作一般不发生，变异操作采取单点变异方式。对个体中的每一个基因，产生一个随机数p，如果p ＞pm则不发生变异，否则随机产生一个位置，将该位置的基因与此基因进行交换，如果随机产生的位置与该基因位置相同，则不交换。

4 试验与仿真

算例以某港口实际数据库为依据，计划周期为48小时，计划周期内的到港船舶为26艘，最小匹配度设置为0.8。通过MatlabR2012a 实现，得到结果。与其人工调动数据做对比，见表1。

表1 人工调度与模型调度数据表

与人工调度相比，虽然本文所建模型调度使未排船量增加了，但是船舶的平均等待时间减少了34%，总装载量提高了2.5%，达到了优化的目的。