英语原文共 9 页

改进的三峡工程两坝通航调度混合模拟退火算法

张小潘a，元小惠b，元彦斌c

华中科技大学系统工程学院，武汉430074

华中科技大学水电与信息工程学院，武汉430074

武汉工业大学资源与环境工程学院，武汉430070

2006年6月30日收到;

2007年10月16日收到的修订表格;

2007年11月17日接受申请

摘要

本文研究了三峡工程两个大坝的最优通航调度问题。，三峡大坝和葛洲坝。协同调度包括两个大坝全部五座船闸的运行调度，以及申请通过大坝的船舶调度调度。与柔性制造系统(FMS)相比，针对NCS设计了一种混合整数非线性规划模型，并提出了一种改进的模拟退火和局部搜索混合算法，以获得最优调度。基于实际历史执行数据的实验表明，该方法是可行的。

关键词:模拟退火;局部搜索;混合整数非线性规划;最优导航；合作规划;三峡工程

1. 介绍

著名的三峡工程包括三峡大坝上游和葛洲坝下游。葛洲坝大坝有三个单级闸门，三峡大坝有两个五级闸门，如图1所示。

图1三峡工程导航系统的总体结构。

导航协同调度(NCS)包括锁操作调度(决定每个锁的操作时间表)和船舶调度(决定每个船的通过时间表)。实际上，航海部门需要在某些目标下为国家导航系统制定一个一段时期的最佳计划。提高黄金水道的通航能力具有十分重要的意义。为了表示NCS的细节，需要解释一些概念。船闸服务的定义是:船闸打开后，船舶进入船闸室，通过大坝转运。在这个过程中有四个重要的考虑。第一个是过程开始的时间，即。，锁定门打开，称为服务点。第二是船闸所传送的船只的方向。显然，所有通过同一船闸服务转移的船舶都具有相同的航行方向。此属性称为服务方向。第三个是船闸将一间船室通过水坝所花的时间。在NCS中，这叫做传输时间。最后一点是两个连续锁服务的服务点之间的最小时间间隔，称为服务间隔。这比五步锁的传输时间短，因为它们就像通过管道一样运行，比单步锁的传输时间长，因为它们像电梯一样运行。如果两个连续的锁服务在五步锁中具有相同的方向，或者在单步锁中具有不同的方向，那么它们之间还有一个额外的转换过程，称为锁转换。

船舶的航行路线可以根据其上的坝分为不同的阶段。图2给出了一艘分四个阶段的船的例子。椭圆区域的概念表示各阶段关键点的时间

图2所示。有四个阶段的船。

最优的NCS计划有三个目标，即:

(a)尽量减少船舶的总加权延误。船舶的晚点是其等待时间的一个递增函数。目标等于每艘船的拖拖拉拉程度按其重要性和所占面积加权的总和。

(b)尽量减少闸转换的数量。船闸转换过程中的空闸操作不仅浪费水，而且对船闸设备造成危害。

(c)在调度期内最大限度地平衡葛洲坝三大船闸的工作量。工作负载由所有锁服务的总和来度量。葛洲坝大坝的每一个船闸在三个船闸的总负荷范围内都有一个预先确定的最优工作负荷率。锁的工作负载更平衡意味着它的实际速率更接近于最优值。

NCS与柔性制造系统(FMS)有许多相似之处，如表1所示。

表1

NCS和FMS之间的相似性

NCS的概念 FMS中的类似概念

闸 机器

船 工作

阶段 操作

锁服务的服务间隔 处理时间

船闸转换时间 设置时间

船舶等待时间 迟到

但由于船闸同时传送一批船舶，因此其结构复杂，船舶在船闸舱内的布置也是一个np难题。关于该问题已有相关研究，如船闸室布置问题[1-3]、船舶多属性决策等。

葛洲坝[4]调度与[5]大坝调度问题，但对五座船闸的协同调度问题缺乏研究。由于FMS和NCS之间的相似性，对FMS的现有知识是有帮助的。在[6]中提出了FMS的全局混合整数线性规划模型。由于FMS具有np完全复杂度，模拟退火[7,8]、遗传算法[9,10]等启发式算法非常适合大规模问题。

2. 数学模型

2.1。符号和参数I:船舶索引集。

i:船舶iisin;i的索引。j:舞台的索引。

j (i):船舶总级i。

U = {(i, j) | iisin;i, 0le;j lt; j (i)}: (i, j)表示调度单元，表示阶段j船舶i。vi j:船舶iat阶段j航行方向，上游0，下游1。

tau;i j:导航时期船的长度我在舞台j。li j, wi j: i船在j阶段的长度和宽度。

alpha;i j:船我在舞台上的重要性的程度。k:锁的索引。

K ={0,1,2,3,4}:船闸索引集，其中0,1,2,3,4分别表示三峡大坝南闸、北闸，葛洲坝1号、2号、3号船闸。

K (i, j):船舶i在第j阶段通过K (i, j)isin;K时可用的船闸集合。m:锁的锁服务序列号。

m(k):锁k的最大锁服务。(k,m):锁k的第m个锁服务。

G = {(k,m) | kisin;k, 0le;m lt; m(k)}:锁服务集。lk, wk:锁k的可用长度和宽度。

pk:闸k的传输时间。

tsk:闸k的使用间隔。

tc凯西:锁k .beta;k的转换时间:锁的优化工作负载平衡率k .beta;0 =beta;1 = 0,beta;2 beta;3 beta;4 = 1。tb, te:调度周期的开始和结束。

micro;(x):阶跃函数,即:如果x gt; 0,micro;(x) = 1,否则micro;(x) = 0。2.2。变量和工具功能的调度

rkmisin;{0,1}:1，如果锁服务(k,m)是可操作的;0,否则。tkmisin;R :锁服务的服务点(k,m)。

dkmisin;{0,1}:船闸(k,m)的服务方向，上游为0，下游为1。zi jkmisin;{0,1}:1，如果船舶i在其阶段j通过船级锁服务(k,m)转移。

习jisin;R :船舶x坐标i放置在船闸室其阶段j。yi jisin;R :船舶在其阶段j处船闸室的y坐标。

2.3。约束条件与成本函数

锁定服务顺序约束。这五个限制确保同一锁中的所有锁服务都按时间升序排列，并以适当的间隔列出:

rkmminus;1ge;rkm, 1le;m lt; m(k) (1)

tkm - 1zi jkmle;tkm zi jkm, 1le;m lt; m(k) (2)

jkm lt; tezi jkm, 0le;m lt; m(k) (3)

rkm(t s k tc k |dkmminus;dkmminus;1|)le;rkm(tkmminus;tkmminus;1)，0le;m lt; m(k)， kisin;{0,1} (4)

rkm [t s k tc k (1minus;| dkmminus;dkmminus;1 |)]le;rkm (tkmminus;tkmminus;1), 0le;m lt; m (k), kisin;{2、3、4}。(5)

导航的约束。这六个约束条件保证船舶调度结果的合理性:

zi jkmrkm = zi jkm (6)

X

kisin;K (i, j)

m(k)minus;1 X m=0

zi jkm le; 1 (7)

X

kisin;(Kminus;K (i, j))

m(k)minus;1 X m=0

zi jkm = 0 (8)

X

(k,m)isin;G

zi jkm le;

X

(k,m)isin;G

zi( jminus;1)km, j ge; 1 (9)

dkm zi jkm = vi j zi jkm (10)

X

(k,m)isin;G

zi jkm times;

X

(k,m)isin;G

zi( jminus;1)km(tkm pk tau;i j ) le;

X

(k,m)isin;G

zi jkm tkm . (11)

包装的约束。这三个约束条件保证了同一船闸舱内的船舶没有发生重叠，如图3所示。

图3船闸舱内的船舶布置。例如两艘船。，单位(i, j)和(p, q)

0 le; zi jkm xi j le; zi jkm(lk minus; li j ) (12)

0 le; zi jkm yi j le; zi jkm(wk minus; wi j ) (13)

zi jkm z pqkmmicro;(x pq lpq minus; xi j )micro;(ypq wpq minus; yi j )micro;(xi j li j minus; x pq)micro;(yi j wi j minus; ypq) = 0. (14) Obj. 1. Tardiness cost of ship

Z(i, j) = li jwi jalpha;i j (1ti j 1t2 i j ). (15)

The waiting time 1ti j should be calculated as follows:

1ti j =

                            

' X

(k,m)isin;G

zi jkm tkm minus;

X

(k,m)isin;G

zi( jminus;1)km(tkm pk tau;i j )

#

(te minus; tb)

if

P

(k,m)isin;G

zi jkm times;

P

(k,m)isin;G

zi( jminus;1)km = 1, '

te minus;

X

(k,m)isin;G

zi( jminus;1)km(tkm pk tau;i j )

#

(te minus; tb)

if

P

(k,m)isin;G

zi jkm

P

(k,m)isin;G

zi( jminus;1)km = 1,

0, else.

(16)

2闸服务的转换成本

C(k,m) = 3rkmlkwk |dkm minus; dkmminus;1| k isin; {0, 1}

rkmlkwk(1 minus; |dkm minus; dkmminus;1|) k isin; {2, 3, 4}. (17)

3锁的不平衡工作负载成本

NCS定义为三个成本加权和的单一目标程序:

min J (U, K ) = alpha;1

X

(i, j)isin;U

Z(i, j) alpha;2

X

kisin;K

'

ck

m(k)minus;1 X m=0

C(k,m)

#

alpha;3

X

kisin;K

ek E(k). (19)

3.混合算法

在本节中，我们提出了一种模拟退火和局部搜索的混合算法。解空间被rkm和dkm分割为局部域，即，同一域中所有解的rkm和dkm值相同。在各区域采用模拟退火算法搜索tkm的局部最优值。船舶调度调度采用3.1中表示的过程，按照rkm、tkm、dkm进行调度。

U:船舶调度调度，包括zi jkm、习j和yi j, K:锁操作调度，包括rkm、tkm和dkm, U:局部最佳船舶调度调度，

K显示出局部最优锁操作调度

资料编号：[4175]