文档介绍：时间窗限制下港口泊位优化分配问题模型
第39卷第2期
2010年4月
船海T程
SHIP&OCEANENGINEERlNG
Vol|
时间窗限制下港口泊位优化分配问题模型
秦进,缪立新,陈长彬,陶经辉
(,广东深圳518055;
-程学院,长沙410075)
摘要:提出新的离散型泊位分配模型,对船舶在港口内的服务时间和港口内泊位的可用时间都考虑了
时间窗约束,并在目标函数中考虑了船舶的不同服务时间价值,基于模拟退火算法设计了相应的模拟退火算
,求解大规模问题时,存求解质量和计算时问上要优于CPIEX软件,所
提出的优化方法将有助于帮助繁忙港口提高泊位等资源运营管理的效率.
关键词:港口;泊位分配;优化模型;时间窗;模拟退火算法
中图分类号:U658文献标志码:A文章编号:1671—7953(2010)02—014204
船舶到达港口的时间是已知的,当船舶到达
之后,港口管理人员首先必须为该船舶分配合适
装卸货物的时问在一定程度上取决于其停泊位
置,是一个关于泊位与需要装卸的集装箱堆存位
置之间的距离的函数,泊位的分配会影响整个港
,泊位分配问题(berthallo—
cationproblem,BAP)是港口决策支持系统中的
一
个核心的问题.
泊位分配问题可以分为离散型干¨连续型两
点的集合,那么此类泊位分配问题称之为离散型
泊位分配问题,如果将码头视为一条连续的停泊
空间,那么就是连续型泊位分配问题l】].
提出新的离散型BAP问题的优化模型,与既
有BAP模型不同的是,该模型考虑了不同船舶的
服务时间的不同时间价值,同时还考虑了对船舶
服务时间和泊位可利用时间的时间窗限制,最后
设计了基于模拟退火算法的求解方法对该模型进
行计算和分析.
1模型的建立
定义符号如下:
收稿日期:2009—04一o1
修回日期:2009—05—11
基金项目:广东省自然科学基金(7301729).
作者简介:秦进(1978一),男,博士,副教授.
研究方向:港口系统优化研究.
E-mail:qin.******@.
]42
I--N达港口船舶的集合;
K一港日泊位的集合;
下标i——船舶,i∈;
忌——泊位,是∈K;
——
泊位k上的按照服务顺序排列的船
舶集合,Ok(==;
——
船i在泊位k上的被服务时间,其中包
括必要的连续两艘船进出同一泊位所
需的安全问隔时间;
…一
泊位k可以开始服务的时间;
——
泊位k结束服务的时间;
ai——船舶i到达港口时间,也是船舶i的服
务时间窗的下限值;
6——船舶i的服务时间窗的上限值,也就
是港口所规定的该船舶应该离开泊位
的最晚时间,因此船舶i的服务时间
窗就是,bi];
d——船舶i的吃水深(包括必要的安全值);
D——泊位k的水深;
ZU——船舶i的服务时间的时间价值权重;
——
泊位忌的使用时间的时间价值权重;
——
泊位k上开始工作的时间,规划期内
泊位k停靠第一艘船的时间;
——
泊位k结束所有工作的时问,也就是
规划期内分配于该泊位的最后一只
船离开的时间.
同时,定义决策变量如下:
f1如果船i是在泊位k上第个被服务的
10否则
时间窗限制下港口泊位优化分配问题模型——秦进,缪立新,陈长彬,陶经辉
以表示船i在泊位k的靠泊时间,那么如
果,
zk=0,即船i没有分配到泊位k进行装
卸作业,那么就设置一n.
对于问题的任意解S∈S,实际上都是由船舶
分配集合B(s)构成,且:
A(s)一{,(==,,Vk∈K)
式中:——按服务顺序排列的在泊位k上服务
的船舶,Ok一{1,iz,…,i}.
显然,若尼≠志,则nOk,一,且UKC
一
l.
由此,带时间窗限制的港口泊位分配问题的
优化模型可以表述如下:
minC一∑∑[+∑z一a(1)iEhEKJeOk
∑∑一1,V∈J(2)
hEKjEOk
∑,∈z≤D,V走∈K,Vi∈J(3)
以≤,VkEK,Vi∈I(4)
(+￡)∑∈≤6,V∈K,V∈,
h≤,Vk∈K
≤,Vk∈K
(5)
(6)
(7)
z∈{0,1},Vk∈K,ViE,,V∈Ok(8)
模型的目标函数(1)是要最小化考虑了时间
价值权重的所有船舶在港口的总服务时间,注意
到在目标函数中,如果船舶i没有分