基于模拟退火算法的三峡船闸编排

刘瑞杰，秦 放，翟 悦，王立娟

(大连科技学院信息科学系，辽宁 大连 116052)

0 引言

三峡船闸是当今世界上级数最多、规模最大的双线五级连续船闸。三峡船闸的建成及投入运行极大地改善了宜昌至重庆600多公里的航道条件，促进了长江中上游经济和水运的快速发展，截止到2012年，长江沿线从事内河运输的船舶达到9.17万艘，货物通过量突破18亿吨。在如此繁忙的航道上，处于咽喉地位的三峡船闸正面临着巨大压力，三峡船闸的“瓶颈现象”日益突出。数据表明，在目前正常情况下，三峡船闸每天最多能安排过闸船舶150艘次左右，但每天的过闸需求多达160～180艘次，运输繁忙季节超过200艘次［1］，船舶待闸已呈现常态化趋势。这使得大量船舶滞留三峡坝区，给三峡大坝造成极大的安全隐患，同时也使整个航道的水运成本上升、效率下降。因此，在三峡现有船闸的基础上，研究提高三峡船闸通过能力的相关技术问题，对于发挥三峡工程综合效益和保障沿江经济社会可持续发展具有十分重要的意义。

目前，国内外学者对如何提高船闸通过能力的相关问题已经做了许多有益的研究［2-14］。本文在分析影响船闸通过能力因素的基础上，给出一种提高船闸通过能力的船闸编排的模拟退火算法，取得了较好的优化结果。

1 船闸通过能力的影响因素分析

在船闸设计时，衡量船闸通过能力的一个指标在《船闸总体设计规范》(JTJ 305-2001)中按式(1)所示［5］。

P—年过闸船舶总载重吨位(t);

n—日平均过闸次数(次);

N—年通航天数(d);

G—一次过闸平均吨位(t)。

由公式(1)可知，计算船闸通过能力的指标P由3部分构成:日平均过闸次数n、年通航天数N和一次过闸平均吨位G。日平均过闸次数n是根据船舶进出闸、闸门启闭以及灌泄水等时间因素进行计算确定。在目前正常情况下，三峡船闸单线日运行闸次数只有14～16个，本文不研究如何通过提高日平均过闸次数来提高船闸通过能力。因此，在后续的讨论过程中，把日平均过闸次数看作是一个常数值。

年通航天数N是根据特定航道船闸的统计资料确定。而在船闸实际运行时，船闸通航天数具有随机性，也就是说，该参数是不受控制的，当然也就无法通过研究N来提高船闸通过能力。因此，在后续的讨论过程中，把年通航天数看作是一个常数值。

一次过闸平均吨位G主要取决于每艘船的大小和每闸次中能够容纳的船舶数量，即与船舶吨位或尺度以及闸室有效面积利用率等因素有关。本文正是从提高一次过闸平均吨位的角度来研究船闸通过能力提高的问题，即把日平均过闸次数和年通航天数都取一个常数值。这样，提高船闸实际通过能力的问题可以转化为求一次过闸吨位最大值的问题，即:

P实际—实际年过闸船舶总载重吨位(t);

n和N的含义同式(1);

Gi—船闸实际运行时第i次过闸吨位(t)。

由式(2)可知，只要提高每一次的过闸吨位，即求max( Gi)，就可以提高P实际，即提高船闸实际通过能力。

2 参数Gi的确定和船闸编排的问题描述

第i次过闸吨位Gi的确定可采用类似计算一次过闸平均吨位G的计算方法——船队排列法［6-7］来计算。

船队排列法是通过对不同船型、船队加以组合来确定一次过闸平均吨位的，这种思想对确定参数Gi是非常适合的，也就是说，本文提出的一次过闸吨位是针对船闸实际运行时，根据每一次有过闸需求的船舶组合来确定的。然而该方法在计算一次过闸平均吨位时却存在许多问题，这当然一方面是由于我国从事内河航运的船型、船队型式繁多，另一方面是由于各种船舶到闸是随机的，因此设计船型组合及其占全年过闸的比例都是难以合理确定的。但船队排列法对确定参数Gi是不存在上述问题的，因为，在船闸实际运行时，待闸船舶是已知的，对确定参数Gi而言，只需要在所有等待过闸的船舶中按照某种策略和规则找出最优的船舶组合。这实际上就是一个在给定的有限区域内(闸室)尽可能多地安排过闸船舶(小区域)，从而提高船闸实际通过能力的问题。该问题可以用如下数学语言描述:

SL(L，W)表示长为L，宽为W的船闸闸室。对于三峡船闸，其闸室长280米，宽34米。

(1)安排到闸室内的船舶两两互不重叠;

(2)安排到闸室内的船舶不能超出闸室的边界;

(3)安排到闸室内的船舶不能任意旋转，即船头方向必须与过闸方向一致，且船身与闸门侧壁平行。

3 船闸编排问题的模拟退火算法

模拟退火算法［15］是由Kirkpatrick等学者提出的一种能够避免陷入局部最优的随机搜索算法，该算法是对固体物理退火过程的模拟，即给固体充分加热，然后缓慢地让它冷却降温，直到固体内部粒子获得最小晶格能量状态。同时把Metropolis准则引入到算法之中，这样，使得模拟退火算法除了接受改进解以外，还以一定概率接受非改进解(即劣质解)，从而可以跳出局部最优。这一有别于局部搜索算法的特征使模拟退火算法在求解组合优化问题中有着广泛的应用。

3.1 船闸编排问题的模拟退火算法要素的构建

(1)解空间:解空间可表示为有过闸需求且等待过闸船舶集合S的所有子集的集合。

(2)目标函数:目标函数为编排到闸室内的船舶面积之和占闸室有效面积的比率。即f(s1，s2，…，sb)

(3)邻域结构:从当前解S'cur的集合中去掉一个船舶构成 S″cur，所有不在 S'cur中且能够在 S″cur的基础上编排到闸室内的船舶和S″cur共同组成的集合称为当前解的邻域结构。新解S'new是随机从邻域结构中选一个解作为新解。

(4)目标函数差:Δf=f(S'cur)-f(S'new)。

3.2 船闸编排问题的模拟退火算法描述

Step1 采用贪婪算法产生初始解，初始化退火温度T0;

Step2 在温度Ti时重复如下操作:

(1)随机从当前解S'cur的邻域结构中选一个可行解S'new。

(2)计算 Δf，如果 Δf＜0，接收新解 S'new，转 Step 2;否则，依照概率 exp(-Δf/Ti)＞random［0，1］接收新解 S'new，random［0，1］是［0，1］区间内的随机数。

Step3 令Ti+1=αTi，i=i+1，其中 α 是初始参数(0 ≤α ≤1)，这里取 0.95;若满足收敛条件，给出船闸编排结果，退火过程结束;否则，转Step2。

3.3 实验结果

求解三峡船闸编排问题的模拟退火算法已在Windows XP系统的PC上仿真实现。为了简化计算，在该算法的实现细节上做了简化处理，即把三峡船闸闸室的有效面积在程序实现时看作是一个长280米，宽34米的矩形区域的面积，所有待闸船舶在水平面上的投影区域在程序实现时看作是长为船舶总长，宽为船舶总宽的矩形区域。本文通过2个实例来检验该算法的有效性。第一个实例使用文献［9］中的第一组数据，结果如图1所示(图中的数字代表待闸船舶的编号)。

图1 文献［9］中第一组数据的拍档图

对第一个实例的说明:

(1)在文献［9］中给出的北线闸室的长为280米，宽为32.8米，本计算结果同样也采用此数据。

(2)应用本算法，无论针对文献［9］中的3组数据的哪一组，都能把该组中的所有数据排完，这说明本算法在求解三峡船闸编排问题上是有效的，这里只给出了使用文献［9］中的第一组数据拍档图。

第二个实例是从2013年5月20日长江三峡通航管理局当天发布的三峡—葛洲坝两坝调度计划简表计划中的所有过闸船舶中随机抽取了部分船舶信息(如表1所示)进行船闸编排，共有24艘待闸船舶，应用本算法对这24艘待闸船舶进行编排，闸室有效面积利用率为95.42%，结果如图2所示。

图2 表1中数据的拍档图

表1 船舶信息

4 结束语

本文从船闸实际运行的角度出发，在分析船闸通过能力影响因素的基础上，给出了一种提高船闸实际通过能力的模拟退火方法，通过上述实例试验结果表明，模拟退火算法在提高船闸实际通过能力问题上是有效的，这为提高船闸实际通过能力提供了新的思路和方法。

［1］唐冠军.关于尽快建设长江三峡水利枢纽船舶过坝新通道的建议［EB/OL］.http://www.cjhy.gov.cn/hangyundongtai/dianziqikan/hangyunzazhi/201304/t20130422_233934.html，2013-04-22.

［2］廖鹏.内河船闸通过能力研究进展［J］.水利水运工程学报，2009(3):34-40.

［3］郭涛.三峡船闸通过能力分析［J］.水运工程，2011(12):112-116.

［4］张义军.提高三峡船闸通过能力之措施［J］.水运管理，2012，34(6):13-15.

［5］张玮，廖鹏，昊玲莉，等.船闸通过能力主要影响因素［J］.交通运输工程学报，2004，4(3):108-110.

［6］陶桂兰，张玮，丁坚，等.船闸1次过闸平均吨位的确定［J］.水运工程，2003(4):50-52.

［7］廖鹏，张玮.船闸一次过闸平均吨位计算模型［J］.东南大学学报:自然科学版，2010，40(1):207-212.

［8］刘云峰，齐欢.DFS算法在三峡永久船闸优化编排中的应用［J］.计算机工程，2002，28(8):224-226.

［9］孙波，齐欢，张晓盼，等.三峡-葛洲坝联合调度系统闸室编排快速算法［J］.计算机技术与发展，2006(12):15-17.

［10］肖恒辉，齐欢，王小平.船舶调度闸外编排算法［J］.交通运输工程学报，2007，7(1):26-29.

［11］张晓盼，齐欢，袁晓辉.三峡工程两坝联合通航调度的混合模拟退火算法［J］.控制理论与应用，2008，25(4):708-711.

［12］刘雯丽.贪婪算法在船闸编排问题的应用［J］.电脑知识与技术，2011，7(10):2417-2418.

［13］商剑平，吴澎，唐颖.基于计算机仿真的船闸联合调度方案研究［J］.水运工程，2011(9):199-204.

［14］赵春鹏.船闸调度优化与仿真［D］.大连:大连海事大学，2012.

［15］Kirkpatrick S，Gelatt C D Jr，Vecchi M P.Optimization by simulated annealing［J］.Science，1983，220:671-680.