基于遗传算法的三峡-葛洲坝船闸闸室编排算法

第４７卷第２４期　２　０　１　６年１　２月　人　民　长　江　Ｙａｎｇｔｚｅ　Ｒｉｖｅｒ　Ｖｏ１．４７．Ｎｏ．２４　Ｄｅｃ．，　２０１６　

文章编号：１００１—４１７９（２０１６）２４—００５５—０５　

基于遗传算法的三峡一葛洲坝船闸闸室编排算法　

邓　伟，邝祝芳，余绍军，曾非凡　

（中南林业科技大学计算机与信息工程学院，湖南长沙４１０００４）　

摘要：三峡升船机的投入运行以及多线梯级联合调度环境的改变，给三峡升船机与船闸联合调度问题提出了　

新的挑战，其中闸室编排是求解三峡升船机与船闸联合调度问题的重要组成部分。在借鉴目前已有传统算法　

的基础上，提出了基于遗传算法的三峡一葛洲坝船闸闸室编排算法，并介绍了编码表示、选择策略、杂交算子　

和变异操作过程。选取三峡一葛洲坝船闸２０１５年４月船舶流数据进行测试，比较本文提出算法与实际人工　

处理产生的闸室编排以及待闸时间结果，验证了该算法的有效性和实用性。　

关键词：遗传算法；闸室利用率；待闸时间；升船机　

中图法分类号：ＴＶ６６　文献标志码ｉ　Ａ　ＤＯＩ：１０．１６２３２／ｊ．ｃｎｋｉ．１００１—４１７９．２０１６．２４．０１２　

三峡一葛洲坝梯级枢纽对长江交通航运起着重要　

作用。据相关资料统计，２００４—２０１３年通过三峡枢纽　

的货物平均每年增速达到１２．２４％，这给三峡升船机　

与船闸联合调度提出了新的挑战。三峡大坝建有双线　

梯级连续的５级船闸和新投入的升船机，其中５级船　

闸是世界上级数最多、水头最高、线路最长、规模最大　

的梯级船闸，航道由南北两线构成，由于通航条件及航　

道情况不同，船舶通过南线和北线的情况也不尽相同；　

葛洲坝通航系统由葛洲坝１，２，３号船闸组成。三峡两　

线船闸及葛洲坝１，２号船闸的闸室有效尺度为２６６　ｍ　

×３２．８　ｍ（长×宽），三峡两线船闸水深５．５　ｍ，葛洲坝　

１号船闸水深５．５　ｍ，２号船闸水深５　ｍ；三峡升船机有　

效尺度为１１５　ｍ×１７．２　ｍ（长×宽），水深３．５　ｍ，葛洲　

坝３号船闸的闸室有效尺度为１１８　ｍ×１７．２　ｍ（长×　

宽），水深３．５　ｍ。一般条件下，三峡南线走下水路船　

舶，三峡北线通过上水的船舶，葛洲坝的１，２，３号船闸　

根据通航条件和调度计划不同，３个船闸上水和下水　

换向交替运行。　针对三峡船闸闸室的编排问题，国内有学者提出　

了降维快速编排算法、基于拟人策略的算法和基于模　

拟退火算法的三峡船闸编排等¨　。　

三峡升船机的投入使用给梯级枢纽的联合调度带　

来了新的问题。三峡一葛洲坝两坝间联合调度的计划　

编制问题涉及到三峡南北两线梯级船闸和升船机及葛　

洲坝３个船闸不同航向的计划编排　，根据船舶过　

坝权重属性确定船舶过坝优先级　，控制船舶的待闸　

时间及倒闸的闸次数　，综合协调三峡一葛洲坝两坝　

间的通过能力，优化闸室面积利用率，保持两坝水利枢　

纽的畅通性　。　

对梯级船闸的计划编制是ｔｉｍｅｔａｂｌｅ问题　，空间　

上是ｐａｃｋｉｎｇ问题¨　。在一个固定编制计划内，ｔｉｍｅ－　

ｔａｂｌｅ的时间序列可通过模拟退火算法。’　、遗传算法、　

粒子群算法等启发式算法来求解，由于每个船闸的开　

闸时间序列与船舶通过顺序中的每个船舶面积大小相　

关，所以在确立启发式算法时，要嵌入二维Ｐａｃｋｉｎｇ问　

题，所以二维Ｐａｃｋｉｎｇ算法的优劣会直接影响到整体　

收稿日期：２０１６—０６—３０　

基金项目：国务院三峡工程建设委员会办公室科研项目“三峡升船机通航与运行保障关键技术研究”；湖南省科技创新基金项　

目（ＣＸ２０１５Ｂ２９７）；中南林业科技大学研究生科技创新基金项目（ＣＸ２０１５Ｂ１９）　

作者简介：邓　伟，男，硕士研究生，主要从事计算机应用技术、图像处理研究。Ｅ—ｍａｉｌ：ｃｓｕｆｔｄｅｎｇｗｅｉ＠１６３．ｔｏｍ　

通讯作者：邝祝芳，男，副教授，博士，主要从事计算机网络、算法应用研究。Ｅ—ｍａｉｌ：ｅｓｕｆｔｋｕｎｇｚｈｕｆａｎｇ＠１６３．ｅｏ

ｍ　５６　人　民　长　江　

计划编制算法的性能，因此需要确立闸室编排算法。　

闸室的编排问题可用二维Ｐａｃｋｉｎｇ模型描述，是ＮＰ完　

全问题　，由于通过两坝的船舶类型不同，且约束条　

件多，建立数学模型困难，因此，在对梯级枢纽联合调　

度进行计划编制时，需建立新的优化算法来解决闸室　

编排问题。　

１船闸闸室编排的数学模型　

将船闸简化为大矩形，其中三峡南北线船闸、葛洲　

坝１，２号船闸为２６６　ｍ×３２．８　ｍ的矩形，三峡升船机、　

葛洲坝３号船闸为１１８　ｍ×１７．２　ｍ的矩形。船舶简化　

为小矩形，因此船舶编排的过程可以简化为小矩形填　

充大矩形的过程，即在编制计划内填船（排挡）¨　，如　

图１所示。计划编制船舶时，船舶是否被选中以及选　

中后所处位置都会影响编排结果。　

图１船闸编排示意　

为了保证船舶先到先过原则，同时兼顾船舶优先　

级，通过对船舶综合权重的计算，船舶过闸按综合权重　

大小进行排序，并生成有序的船舶流。本文中符号定义　

如下：ｉ，＿『表示船舶编号，　表示第ｉ艘船舶以Ｏ为原点　

在船闸的停靠横坐标，Ｙ　表示第ｉ艘船舶以Ｏ为原点在　

船闸的停靠纵坐标，ｏ　表示第ｉ艘船舶的面积，ｒ／Ｚ表示　

已选船舶总数，ｎ表示待选船舶总数，Ａ表示船闸闸室　

面积，　表示船闸闸室有效长度，　表示船闸闸室有效　

宽度，ｚ　表示第ｉ艘船的长度，Ｗ　表示第ｉ艘船的宽度。　

闸室编排的过程中，由于不同船舶的进闸组合方　

案对于平均待闸时间影响不大，因此主要优化闸室面　

积利用率，闸室编排的目标即最大化闸室面积利用率：　

ｍａｘ　＝　ｍ　（７／＇ｉ）　

选择进入某一闸次的船舶必须满足以下约束条　

件。　

（１）所有选中的船舶能全部排下。　

∑。　≤Ａ　（２）　

（２）每条选中船舶的尺寸必须小于船闸的尺寸。　

０＜Ｚ　≤Ｌ　（３）　

０＜　≤Ｍ　（４）　

（３）所有选中的船舶放置位置不可与其他船重　叠。设船舶　是已选船舶中除ｉ以外的任意一艘，则必　

须满足：　

＋Ｚｆ≤　，　‘≥　，＋Ｚｆ≤司　

Ｙｌ＋　ｆ≤，，，或Ｙ　≥），　＋Ｗ　（５）　

由以上模型的建立可知，这是一个复杂的ＮＰ问　

题，时间的复杂度与空间复杂度计算困难。常用的优　

化算法分为精确算法和近似算法¨　，本文结合新的问　

题提出了基于遗传算法的三峡一葛洲坝船闸闸室编排　

算法。　

２船闸闸室编排的算法求解　

三峡一葛洲坝通航联合调度系统中的闸内编排算　

法要解决的问题是：在通航能力不足的情况下，在保证　

权重优先和先到先过的原则同时，尽可能地把待排船　

舶安排到闸室中，以达到最大的船闸面积利用率¨　。　

分析以往编排方案，发现对同一船舶集排人闸室问题　

有多个可行解，每组可行解对某些关键船舶位置固定，　

剩余其它船舶可按约束条件随机排列，因此，该问题转　

化为从宽度上搜索和优化船舶的关键位置。　

遗传算法是通过模拟生物的遗传进化机制来进行　

搜索寻优的方法，遗传算法的设计包含了编码表示、选　

择策略、杂交算子、变异操作等方面。　

（１）编码表示。使用长度为ｎ（ｎ为待选船舶数）　

的二进制串表示一个染色体，代表一个闸室编排方案，　

在染色体中，如果第ｉ位为“１”，则表示／＇ｔ条船中第ｉ条　

船被选进闸室。　

（２）初始化种群。种群中的个体染色体可表示为　

Ｉｋ＝ｂ　（ｋ）ｂ：（ｋ）…ｂ　（ｋ），其中／１，为待选船舶数，ｂ　（　）　

∈｛０，１｝，ｉ∈｛１，２，…，／＂ｔ｝，ｋ∈｛１，２，…，Ⅳ｝，Ⅳ为种群　

中的个体（染色体）的总数。当ｂ　（ｋ）为…１’，表示ｎ条　

船中第ｉ条船被选进闸室。　

（３）适应度函数的确立。通过适应度函数值的大　

小，来决定种群中的个体是繁殖还是消亡。将个体，＾的　

适应度函数定义为　

ｆ（１　）：∑ｍ　（６）　

＃　Ａ　

（４）基于适应值比例选择策略。首先根据适应度　

函数　Ｉｋ）来计算个体的适应值，再采用择优策略的方　

法，并将计算出的适应值中最高值作为个体直接保留　

到子代种群中。然后根据各个体的适应值，按公式（７）　

计算对应的相对适应值，并作为该个体的选择概率。　

ｆ（１　、　Ｐ（，　）＝　二　一　（７）　

∑ｆ（Ｉｉ）　

式中，Ⅳ表示群体规模，　，　）为第ｉ个个体的适应值。

　第２４期　邓　伟，等：基于遗传算法的三峡一葛洲坝船闸闸室编排算法　５７　

最后，采用转盘式选择策略对个体进行选择。即将　

一个圆按选择概率的大小按比例将圆盘分成Ⅳ份，其　

中第ｉ个扇形的圆心角为２，ｒｒｐ（，　），如图２所示。转动圆　

盘，停止后，当某参照点落到第ｉ个扇形内，则选择个　

体，　。具体方法为：先生成一个随机数ｋ，ｋ∈［０，１］；当　

Ｐ（，。）＋Ｐ（／２）＋…＋ｐ（，ｊ—１）＜ｋ≤Ｐ（，１）十ｐ（／２）＋　

…＋Ｐ（　时，选择个体，　。因此个体的适应值越大，个　

体所占的扇形区域面积就越大，被选择的机会就越多。　

图２　转盘式选择策略　

（５）杂交操作。由杂交过程设计一种新的杂交算　

子，其过程为：按转盘式选择算法随机地从种群中选择　

两个父代个体，。和，２，随机产生交叉点ｐｏｓｌ，在ｐｏｓｌ　

处，两个父代个体，。和，２进行交叉，产生两个新的个　

体。　

（６）变异操作。随机选择个体，。进行变异操作，同　

时随机选择个体，。的某一位进行变异操作。基于遗传　

算法的闸室编排算法流程图如图３所示。　

图３算法流程　

３　闸室面积利用率与待闸时问的优化　

考虑船舶先到先过、重点优先的原则最大化闸室　

面积利用率，随后确定闸室面积利用率与待闸时间的　

关系，现定义如下符号：（ｉ，．『）表示处在第．『个航行阶　

段的船舶ｉ，也即“调度单元”；［ｋ，ｚ］表示大坝ｋ的第ｚ　

个船闸；　表示所有调度单元的集合；力表示所有船闸　

的集合；ｒ（　，　）表示调度单元（ｉ，　）的到锚时间　ｔ，表　示调度单元（ｉ，＿『）的进闸时刻，ｅ川表示调度单元（ｉ，＿『）　

是否通过船闸［ｋ，ｚ］，其中１表示通过，０表示不通过，　

ｓ　表示调度单元（ｉ，　）的面积，　表示船闸［ｋ，ｚ］的总　

开闸次数，Ａ　表示船闸［ｋ，ｚ］的闸室面积。　

３．１　平均闸室面积利用率　

平均闸室面积利用率指计划期内过闸船舶的面积　

之和与所有闸次面积之和的比值，简称闸室利用率　

表示船闸［ｋ，ｚ］在一个调度计划期（２４　ｈ）内的平均闸　

室面积利用率。　

∑ｅ　，ｓ　厶　Ｖ　ｒ　ｕ　

＝业　（８）　ＵｋｌＺ＇￣肼　

Ｆ　表示三峡南、北线、葛洲坝１，２号船闸在一个　

调度计划期（２４　ｈ）内的平均闸室面积利用率。　

∑　

Ｆｔ＝　（９）　

最大化平均闸室面积利用率并非指闸室面积利用　

率越大越好，根据当前的船型情况和运行经验，一般闸　

室面积利用率超过８０％以后，面积利用率和船舶过闸　

效率（日均闸次数）反而呈负相关关系，即面积利用率　

越高，船闸日均闸次数越小，相应日均过坝总艘次数越　

小，一般来说，面积利用率７０％左右，南北线船闸可以　

运行１６～１７个闸次；面积利用率平均达８０％（没有日　

均闸次面积利用率均达到如此高水准的典型实例）　

后，南北线船闸约需少运行１个闸次左右，估计平均利　

用率达９０％以后，闸次数可能更少。　

因此，在计算平均闸室面积利用率时，我们给面积　

利用率界定一个合理的取值范围，根据运行实际情况，　

取经验数据７０％～８０％为优化的平均闸室面积利用　

率取值范围。　

３．２最小化平均船舶待闸时间　

船舶待闸时间是指船舶进入船闸时刻与船舶抵达　

指定水域时刻的差值。本文中定义Ｆ　表示所有船舶过