改进遗传算法在船只调度路径优化中的应用*

（海军工程大学舰船综合试验训练基地 武汉 430033）

1 引言

自我国2001年加入WTO以后，国内港口吞吐量不断提升，国际化市场进一步开拓，各个港口的市场竞争也越来越激烈。随着大吨位船舶数量的不断增多，对港口相关的能力标准也有了更高的要求[1～2]。所以优化港口船只人员调配，有助于提升港口竞争力，实现货物优质运输[3]。常规港口运输均以VTS为依托，其是由雷达、数据处理等软件构成。随着航运水平和规模的扩大，当前CTS系统功能以不能满足实际需求，故需及时改进遗传算法，优化VTS系统，实现船只合理调配[4]。

2 船舶调度数学模型

在实际港口泊位调度中，有相当多变化因素，故不能单纯将时间加减，还有吨位因素，船舶因素等。故在实际船舶调度中，需依船舶属性区分。建立数学模型时需依照船舶到岗时间最远为标准。但实际中，到港时间计算有误差，吨位数也会改变。故遇这种情况时先调度大型船舶，公式如下[5～6]：

为目标函数添加时间前，可以确保大吨位航运船只具有优先权，通过对目标函数进行加权处理，可以确保在不同吨位的航运船只同时具备航运条件时，大吨位航运船只优先被调度使用[7]。综上，即可建立航运船只调度参考模型的目标函数：

因考虑到作业港口上岸桥实际作业效率gj与作业岸桥实际数量Mi以及港口船舶j的货物载重量Wj都将影响到航运船舶在港口的作业时间Cij，所以能够更加真实的反映港口的实际作业情况[8]。

根据船舶类型和吨位规模，以及需求单位对大吨位船舶和小吨位船舶的等待时间需求，综合考量进行加权处理，考虑船舶吨位大小，故设置权值和船舶实际载货吨数成正比关系，采用约束IT条件，设泊位参考时间Ti=0，则上面目标函数可改为

其中，hj表示船舶j的权值，Wmin表示载货和重量最小吨数。Wmax表示载货吨数最大的船舶载货量，Wj表示船舶j载货吨数。q因港口的变化而变化，是可以根据具体情况而进行优化的。

3 改进遗传算法设计在船只调度路径优化中的应用

传统遗传算法无法全面利用反馈信息，容易导致搜索陷入盲目性，并且当算法收敛到一定范围时容易陷入大量冗余迭代，导致算法效率降低。故基于传统遗传算法基础上进行改进，有助于提升算法效率，合理配置资源[9～10]。

本文采用基于贪婪构造法的路径译码算子的改进算法。译码时按序尽最大可能地将基因位表示的客户点插入到线路中，当一个点违背时间窗或载重约束时，就开辟一条新路径并将这个点插入该路径。例如：染色体串：7 3 5 1 9 6 4 2 8。经过路经一码为路线 1：0→7→3→5→0；路线 2：0→1→9→6→4→0；路线3：0→2→8→0。

3.1 种群的初始化

假设一个港口有BerthNum个泊位，一个时间段内的靠泊船只用ShipNum表示，每一条染色体为C，其取值范围小于靠泊船只数ShipNum。随机产生的一组染色体｛C1、C2、C3…CN｝（N 为种群大小），种群代码如图1所示。

初始化种群用initGroup的矩阵保存，其中种群的每一行，代表一个染色体。例如：设ShipNum=10，Num=3，这样每次运算后的结果都会有五个可行解。输入vts-initGroup（5，10，3）后，输出结果为

上表中的每行为一条染色体编码，这样运算产生的5条染色体，即输出的五条染色体数据即可构成初始种群矩阵。当对该船舶进行调度时，将上面的每条染色体都解码为可行的船舶调度方案，以0为分隔，设定BerthNum=3，因而每条染色体都会被0分割成三段字串，如第1行所示：

由左至右，以0为分隔，可以得到（3，2，9），（7，5，6，1），（10，8，4）三个自然数字串，这其中，每一个子串则代表着停靠在泊位上等待调度的船舶队列。所以数组（3，2，9），它表示在泊位1上，首先调度船舶3进行作业，船舶3完成后，再调船舶2进行作业，船舶2作业完毕后在调船舶9进行作业；数组（7，5，6，1）则表示在2号泊位上，首先调度船舶7进行作业，然后再依次调船舶5、船舶6、船舶1进行作业；数组（10，8，4）则表示在3号泊位上首先调度船舶10进行作业，然后调度船舶8进行作业，最后调度船舶4进行作业。那么，通过对得到的结果中每条染色体进行解码后，我们即可得到船舶调度方案。

图1 种群代码

3.2 适应度函数

种群初始化完成以后，通过种群适应度函数，得到每条染色体对应的适应度函数值。在船舶调度模型中，可得目标函数，将其简化可得：

C表述每条染色体的应对应适应度函数值，具体代码详见图2。

图2 染色体的应对应适应度函数

3.3 交叉算子

交叉操作结束后，并不能保证产生的结果满足约束条件，如果航运船舶应该有且仅有一艘会得到被服务的机会，那么经历交叉后，可能会导致有的船舶被调度了两次，有的船舶没被调度。出现这样的结果是不能够避免的，但是这样的结果是不符合条件的，所以我们要对这种结果进行调整，所采用的单点交叉算法如图3所示[11～12]。

图3 单点交叉算法

3.4 变异算子

本文所用换位变异，可将其代码设计如图4所示。

3.5 遗传算法的步骤

在求解最佳方案时，我们需要判断迭代的代数是否为符合要求的代数maxt，如果是符合要求的代数，就可以停止进化，进而选择性能最好的染色体Gh所对应的路径集合，作为原Vrptw问题的有化解输出，具体步骤如下：

Step1：t=0，采取自然数编码方式，通过插入启发式算法和随机方式产生的初始化种群，同时输入控制参数（启发式初始化概率，较差概率Pc，变异概率Pm，规模N和最大运行代数maxt）；

Step2：求解个体适应度；

Step3：t＜maxt，t=t+1，则转Step4；否则停止计算，输出结果；

Step4：数量一定时调配船只；

Step5：数量随时变化时施行船舶交叉重组；

Step6：逆转算子配置船舶及人员调动；

Step7：重复步骤2～6

图4 变异算子

4 实验仿真

4.1 算法背景

改进遗传算法需要在优质的环境中运行，方可保证船只调配效果。现将VTS系统下改进遗传算法实现背景总结如表1所示。

表1 算法背景

4.2 船舶调度VTS系统设计

在VTS系统船舶调度方法中，船舶的本身属性、泊位属性及气象等其他相关因素具有密切影响，故需针对具体情况实施有效的船舶调度。

首先，设计船舶调度时，应充分考虑将所需的船舶基本信息、船舶调度顺序、天气以及任务量等因素。调度的实现采用JAVA语言，编译工具My-Eclipse的后台可以看到遗传算法执行和迭代情况。

第二，VTS系统数据交换时，将实时停泊计划的信息上传至服务器，再通过xF*传递所需信息。VTS系统以转讯的方式读取FTP上的xml数据，经过后台解析，将所需信息插入数据库，并能够以动态的形式，将信息显示在操控页面上。

4.3 仿真试验

下面以某公司港口运输配送为例，通过改进遗传算法实现现代化配送。

现有400t货物以及一个配送转运中心，每个客户的货物量、装货时间等要素整理如下，详见表2。依照客户要求以大、小船只交叉配货，各个船只与配送中心距离详见表3。

表2 配送任务

表3 船只配送距离

经测试，CPU4-3.0G，内存为1G，开发软件为VC++6.0，C语言为编程语言，设定初始种群规模数为50，启发式初始化概率为0.5，交叉率PC=0.8，变异率Pm=0.03，遗传算法迭代次数为120。以笔者构造的选择算子和引入的遗传操作算子进行群体重组，最后得到优化解，优化解是经过优化后所得到的最小路径里程（km）。将本文得到优化解与预算法，分派算法与改进遗传算法相对比，观察其效果。改进算法与其他算法相比，不仅速度有提高，迭代次数明显减少，结果更接近最优解。故以改进遗传算法应用于船只调度路径优化中，效果更为理想。具体详见表4。

表4 各项算法效果对比

5 结语

本文基于VTS系统基础上，对遗传算法进行改进，提升船舶及人员的合理调配。经船舶调度建模、改进遗传算法设计及应用可观其良好的调配效果，实用价值较高。且当前我国各大港口均存在船舶、人员调配不均等问题，改良遗传算法的应用前景较为广阔。