多目标遗传算法在船闸调度中的应用

毛 星，胡少英，徐希涛 ，李宁宁

(南瑞集团(国网电力科学研究院)有限公司,江苏 南京 211000)

0 引 言

作为一个河网密度极大，最大值达12.7 km/km2、海岸线达3.2万公里的国家，水运是我国最主要的货运手段之一。当前我国水路运输不断发展，长江水运通道已超过密西西比河和莱茵河，成为世界上最繁忙、运量最大的内河运输通道。但是目前我国的货运周转量承担值只有49.77%，与发达国家的75%相比，相差悬殊。究其原因，船闸通航能力成为制约水路运输效率的最突出问题[1-2]，因此解决船闸调度过程中船舶待闸时间长、闸室利用率低等问题是提高船闸通航能力、增加航运周转量的关键[3]。

目前内河航运主要采用人工编排调度计划的调度方式，人工排船时通常选择减少单次过闸船数、降低闸室利用率的方式来缓解过闸等待时间长的问题，调度过程慢、调度水平低、缺乏科学性，而且人工排档方法太过依赖人为决策，对决策者个人的经验、知识、能力等要求很高，决策的科学性较低。因此，提高船闸通航能力的核心是采用科学有效的调度方法[4-6]。

闸室编排根据船舶报到时间和优先级别，将船舶排入闸室内，可以用二维空间上的装箱模型来描述[7-8]，是一个典型的NP完全问题[9]。目前以二维装箱模型解决船闸排档问题常见的方法有快速编排算法、贪婪算法、二维优化编排启发式算法等[10-14]，这些算法在大多数情况下能取得较高的闸室利用率，但是在编排过程中只注重局部最优选择，不进行回溯处理，很容易错过真正的最优解[15]。本文针对船闸调度过程中的多种决策因素，建立调度问题的数学模型，给出了基于多目标遗传算法的求解过程。

1 船闸调度问题模型

船闸调度问题可以分为单闸调度和多船闸联合调度，本文只考虑船舶通过单个船闸的情况。单闸调度问题是指在有限的船闸空间内，使每条船舶通过的时间最短。包括2个目标函数和3个约束条件。

1.1 目标函数

船闸调度过程中主要考虑2个调度指标，一个是从船主角度出发，要求船舶的等待调度时间最短，另一个是从船闸管理的角度出发，要求每一闸室内所有船舶占用总面积最大。因此具体的实现方法为：

1)构建船舶等待调度时间最短目标函数F1：

(1)

2)构建闸室利用率最大目标函数F2：

(2)

其中：M表示船闸中的待闸船舶数；i表示第i艘船舶；Ti0表示船舶报到时间；Ti1表示船舶过闸时间；flagi表示第i艘船舶能否排进该闸次，能则为1，否则为0；Si表示第i艘船舶的面积；A表示该闸次的闸室面积。

1.2 约束条件

1)所有选中的船舶必须能够排入船闸：

(3)

2)每条船舶的尺寸不能超过闸室的尺寸：

0

(4)

0

(5)

3)同一闸次的船舶相互不重叠：

i1x+i1l

(6)

i2x+i2l

(7)

i1y+i1w

(8)

i2y+i2w

(9)

其中，任意船舶i1,i2∈{1,2,…,M}，x、y为船舶在闸室内的横坐标和纵坐标，l、w为船舶的长度和宽度，L、W为闸室的长度和宽度。

2 多目标船闸调度算法求解

图1 实现算法流程图

普通的多目标遗传算法，针对相互接近而又不具有Pareto支配关系的个体，SPEA很难有效地区分它们的适应度[16-18]，容易产生适应度相同的个体，导致算法计算效率低下。鉴于此种现象，本文提出一种高效、合理的船闸调度方式，具体的实现方法如图1所示。

2.1 染色体编码

借鉴生物进化过程，将船闸排档结果定义为进化对象的个体，进行染色体编码，具体的方法如下：

假设船闸中有M艘待闸船舶，用M艘待闸船舶表示染色体内所包含的M组基因，基因内ji表示第i艘船舶被调度的闸次，xi,fi和yi,fi分别表示第i艘船舶安排于船闸中的X、Y坐标，则染色体编码的编码公式如下：

s=[(j1,x1,f1,y1,f1),(j2,x2,f2,y2,f2),…,(jM,xM,fM,yM,fM)]

其中，s表示船闸中M艘船舶的一种排船方式。

2.2 种群初始化

在初始化种群时，要求生成一组满足目标解的染色体，并且这些解尽量具有较高的指标。本文采用贪婪算法的思想进行种群初始化，具体过程如下：

1)从待闸船舶中随机选择一条船放入闸室。

2)在闸次集合中随机选择一个闸次对该船舶进行排闸。

3)判断该船舶能否排进该闸次，如果能，进入步骤4，如果不能，进入步骤5。

4)更新染色体，更新待闸船舶，进入步骤1，直至待闸船舶列表为空。

5)更新闸次集合，重新进入步骤3，直至闸次集合为空，并将基因更新为(-1,-1,-1)。

6)上述过程反复执行N次，即可得到N组满足目标解的染色体集合，即初始种群，也就是船闸中M艘船舶的N种排船方式。种群规模越大越可能找到全局解，但运行时间也相对较长，一般N在40～100之间取值。

2.3 个体适应度计算

计算个体适应度，具体的实现算法如下：

其中：xm表示船闸中M艘船舶的第m种排船方式，即个体m；Fitness(xm)是个体m的适应度，SumMation(xm)是Pareto支配xm的个体的强度和，S(xm)是xm的强度，SET(xm)是所有xm与具有相同个体的强度和的集合；xn表示船闸中M艘船舶的第n种排船方式，即个体n；S(xn)是xn的强度。

遗传算法中个体适应度用于计算被选择的概率，遗传结束后，适应度最高的个体将作为最优解。

2.4 遗传操作

遗传算法的操作算子主要有选择、交叉和变异3种，分别模拟了自然界的生物繁衍、交配和基因突变。

选择算子的作用就是从群体中选出比较适应环境的个体繁殖到下一代，选择算子计算的基础是个体的适应度评价值。本文采用比例选择的思路设计选择算子，个体被选择的概率如下：

其中：Pm表示个体被选中的概率，即该种排船方式能被选中遗传给下一代的概率；Fitness(xm)是个体m的适应度值；N表示初始种群的数量，即N种排船方式。

交叉算子是将2个个体的基因的一部分片段互相交换，从而产生2个新的个体，其过程：按照选择算子随机从初始化的种群中选择2个父代个体，在随机产生的交叉点处，进行2个个体的交叉操作，产生2个新的个体。

变异算子是随机选择个体和个体的某一位进行变异操作。

遗传操作需要对选择出的个体组成的种群反复按序进行选择操作、交叉操作和变异操作，从全局的角度进行评估决策，输出满足调度需求的最优排档方案。当遗传操作GEN次之后，即进化GEN代之后，则将进化过程中所得到的具有最大适应度个体作为最优解输出，得到最优排船方法，终止计算。

3 实验结果

本次试验以长洲船闸三号闸室2017年6月每天船舶过闸数据资料为例，长洲船闸是世界上通过能力最大的内河船闸群。利用优化多目标遗传算法进行闸室编排，并与目前采用的人工编排方式进行闸室利用率和平均待闸时间的比较，结果如表1和表2所示。

表1 长洲船闸三号闸室6月份平均闸室利用率 单位：%

表2 长洲船闸三号闸室6月份平均待闸时间 单位：min

由表1和表2可见，优化多目标遗传算法的船闸智能调度方法与传统人工编排的方法相比，闸室利用率从75.23%提高到78.00%，船舶平均待闸时间缩短28 min，体现了算法的科学性，提高了船闸通航能力。

4 结束语

本文针对内河航道船闸调度存在的问题，考虑多种调度指标和约束条件，借鉴生物进化过程的启发式搜索算法，建立多个目标函数，提出了基于多目标遗传算法的调度模型，并对适应度计算方法进行优化改进，通过实例验证了该方法科学性和有效性，为船舶调度和船闸运行提供了决策辅助功能。

参考文献：

[1] 孙波. 三峡-葛洲坝联合调度系统闸室编排研究[D]. 武汉:华中科技大学, 2006.

[2] 刘瑞杰,秦放,翟悦,等. 基于模拟退火算法的三峡船闸编排[J]. 计算机与现代化, 2013(11):65-67.

[3] 张玮,廖鹏,吴玲莉,等. 船闸通过能力主要影响因素[J]. 交通运输工程学报, 2004(3):108-110.

[4] Wang Hongfeng, Yang Shengxiang, Ip W H, et al. Adaptive primal-dual genetic algorithms in dynamic environments[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009,39(6):1348-1361.

[5] 陈明辉,盛黎. 苏北运河船闸智能排档调度研究及应用[J]. 中国水运(下半月), 2016,16(4):75-77.

[6] 高蕾,吴婷. 隔代遗传算法在船舶调度系统中的应用[J]. 舰船科学技术, 2017(4):61-63.

[7] Kirkpatrick S, Jr G C, Vecchi M P. Optimization by simulated annealing[M]// Readings in Computer Vision: Issues, Problems, Principles, and Paradigms. 1983,220(4598):606-615.

[8] 蒋金山,林正春. 用自适应遗传算法解二维装箱问题[J]. 计算机应用与软件, 2008,25(7):244-246.

[9] 汤岩,胡俊敏,武立丰. 一种改进的二维装箱问题的混合遗传算法[J]. 集美大学学报(自然科学版), 2006,11(3):258-262.

[10] 刘云峰，齐欢. 二维优化编排启发式算法及其在三峡永久船闸调度决策系统中的应用[J]. 计算机与现代化, 2002(1):1-3.

[11] 王晓华. 算法的乐趣[M]. 北京:人民邮电出版社, 2015.

[12] 王小平,阮茜. 基于蚁群算法的船舶过闸计划优化模型[J]. 华中科技大学学报(自然科学版), 2011,39(8):100-103.

[13] 吴小涛,袁晓辉，Muhammad Adnan Ikram. 基于拟人策略的三峡永久闸室编排新算法[J]. 水电能源科学, 2015(5):148-151.

[14] Neto R F T, Filho M G. An ant colony optimization approach to a permutational flowshop scheduling problem with outsourcing allowed[J]. Computers & Operations Research, 2011,38(9):1286-1293.

[15] 李楠,李桂华,尹剑平. 湘江船闸的过闸调度算法研究[J]. 水运工程, 2013(3):171-175.

[16] 冯明波. 基于改进多目标遗传算法的船闸调度方法[J]. 江苏船舶, 2016(4):30-33.

[17] 李凯. 一种基于改进遗传算法的图着色算法[J]. 计算机与现代化, 2017(2):6-11.

[18] 公茂果,焦李成,杨咚咚,等. 进化多目标优化算法研究[J]. 软件学报, 2009,20(2):271-289.