基于贪心-遗传优化算法的中长期船舶进出港调度优化.pdf

第 卷第期 年月武汉理工大学学报(交通科学与工程版)J o u r n a l o fWu h a nU n i v e r s i t yo fT e c h n o l o g y(T r a n s p o r t a t i o nS c i e n c e&E n g i n e e r i n g)V o l N o A u g 基于贪心遗传优化算法的中长期船舶进出港调度优化丁可,)徐言民,)关宏旭,)李诗杰,)李柏苇,)(武汉理工大学航运学院)武汉 )(内河航运技术湖北省重点实验室)武汉 )摘要:文中提出一个目标周期内港口总卸货量最大的目标函数,结合航海实际,建立以靠泊条件、通航模式、船舶窗口期、船舶安全距离等通航限制条件为约束条件的船舶进出港调度优化模型,并选用贪心遗传组合优化算法(G G A)进行实现通过假设港口数据的方式来进行模拟试验验证模型及算法的合理性和有效性,并对港口短期调度模式和中长期调度模式进行对比论证关键词:船舶进出港;全局调度优化;多约束条件;贪心遗传优化算法中图法分类号:U d o i:/j i s s n 收稿日期:第一作者:丁可(),男,硕士生,主要研究领域为交通环境安全保障基金项目:国家自然科学基金()引言水上交通运输与其他各种运输方式相比具有运载量大、成本低等优势,目前国际贸易总运量中,/以上的货物运输是利用海上运输完成的如何提高船舶进出港口调度效率成为了当前研究的热点和难点黄蕴和针对大型船舶在浅水航道的航行问题,根据航道的要求限速、预留间距、进出港航道通航量等要素建立大型船舶进出港安全通航数值模型张新宇等在单通道研究的基础上,建立了以总等待时间最小为目标的模型,并进行了模拟退火多组遗传算法的仿真实验徐国裕等利用某种单向水道船舶进出港设计出最科学排序方式,提出了最合适的方案规划船舶进出港顺序,解决了单向水路船舶进出港的问题王辉运用调和分析法计算潮位,提出了进出港船舶的安全间距和限制航速的确定方法卢璇等提出一种结合网络流模型的两步求解方法 N o r s t a d等在船舶调度优化研究方向上提出了具有速度优化的不定期货轮路线和调度问题,确定货轮每个航行阶段的最佳速度 L i在船舶调度问题中引入了MA S技术,采用综合调度优化策略来解决船舶多项目企业的调度优化问题戴林伟基于N aS c h模型添加船舶追越与对遇规则建造稳定可行的变道双向船舶交通流自动化模型张润等 以船舶进出港口的最小等待时间是目标函数,构造了一个混合整数线性规划模型,设计了一种混合算法(在模拟退火算法中引入了有效的改进措施)张新宇等 以总等待时间最短建立模型并通过多目标遗传算法验证了该方法的有效性 A g a r w a l等 针对船舶调度问题,提出了混合整数线性规划模型,运用贪婪启发式算法(一种基于列生成的算法和一种基于两阶段B e n d e r s分解的算法),提出了一种科学的迭代搜索算法并生成了良好的船舶时刻表蒋思怡 在船舶调度多目标遗传算法交叉算子的设计中将类PMX交叉算子运用到模型中,在满足自然编码方式的同时进一步增强算法全局搜索能力综上,现有的船舶进出港调度研究主要是增加港口泊位分配和船岸协同效率以此减少船舶的到港时间及作业时间,并没有考虑自然环境和通航环境对船舶进出港的影响同时,与单向航道相比,双向航道可以大大缩短船舶在港口的等待时间,提高航道利用率但对于具有可变航道的双向航道的研究不多另一方面,针对整体的调度优化模型问题,多集中在单日船舶进出港调度优化以及给定数量船舶的进出港调度优化,缺少对个港口个月、个季度或年的总体调度情况进行预测分析和进出港调度优化基于此,文中基于通航限 制 条 件 设 计 约 束 条 件,通 过 使 用 贪 心(g r e e d y)策略构建船舶进出港调度适应度函数,对个体解进一步寻优,优化遗传算法(g e n e t i ca l g o r i t h m,GA)的全局寻优能力,提出了贪心遗传算法(G GA)模型该模型适用于大部分港口的中长期船舶进出港全局调度优化模型船舶进出港调度优化建模 模型假设)由于乘潮进出港的窗口期内,水流速度平缓,风速不会对船舶行进造成太大影响,因此简化航道内的水流速、风速等因素,将其折合到模型中的风流压差角和航行时间中)由于一般港口码头内的拖轮调度时间相对固定,拖轮数量足够多,不存在等待情况,因此简化航道内拖船的调度因素,将其折合到模型中的靠泊时间中)进港船舶在航道外锚地等候,出港船舶在港口内泊位等候在实际过程中,风力、流速对船舶航行有重要影响,在模型应用中需结合目标港口实际情况进行设定 模型建立 目标函数的建立设定港口外船舶类型、数量为无限,拟通过优化港口调度的方法达到港口总的卸货量最大对锚地所有船舶按照船型尺度进行分组,选取一个目标周期,设定起始时刻港口内所有泊位空闲,所有船舶在锚地等候进港,一艘船舶进港锚泊作业后出港为一个完整流程,一个完整流程卸货量为该船装载量对应到船舶分组编号即为一个完整流程中目标船初始时编号为m组i船,分配泊位x,进港锚泊作业完成后编号为(m)组i船,出港后流程完成,该流程卸货量为目标船装载量根据船舶进出港调度优化模型的主要原则,设计目标函数m a xZ,即在一个目标周期内,港口总的卸货量Z最大m a xZninm(zmiCmi),其中Cmi(,)()式中:Z为一个目标周期内港口总的卸货量;zmi为m组i船的载货量;Cmi为辅助变量,表示船舶进出港状态,m组i船进港为,反之为 约束条件的设计根据船舶进出港的时间流程构建船舶不同时间节点的时间约束,加上泊位工作时间约束并在时间约束中根据航道条件添加必要的通航模式约束、安全时间约束、乘潮窗口期约束等,以此构成完整的约束条件部分根据实际船舶进出港的流程进行总结简化,绘制了图的船舶进出港逻辑流程图图船舶进出港逻辑流程图约束条件设计如下Qm ni j(,)()式中:Qm ni j为辅助变量,表示调度顺序,例如m组i船在n组j之后进出港为,反之为船舶泊位状态为Kmi xM(Cmi),ttmu i,Kmi X(,)()式中:Kmi x为泊位分配,m组i船分配给x泊位为,若无泊位分配则为船舶开始调度时间为tmu itms iCmilmivmi(Cmi)(smivmitc)()tmd itmu ic lvmi()式中:ts为船舶开始调度时刻;tu为船舶上线时刻;td为船舶下线时刻;c l为进出港航道长;l为船舶所在锚地到进港航道距离;vmi为m组第i条船舶的航行速度船舶下线时间为tmf itmd iCmi(smivmitb)te()式中:tf为船舶完成调度时刻;s为船舶制动段距离tm u itmf itml i,当Cmi()式中:t为船舶结束调度时间,当确定船舶进港时,船舶的上线时刻大于整体完成作业时间第期丁可,等:基于贪心遗传优化算法的中长期船舶进出港调度优化在不同情况下船舶进出港通航模式为若VV,则Hmi;否则Hmi若ww,则Hmi;否则Hmi若BmiY,则Hmi;否则Hmi若BmiY,且载运危险货物,则Hmi;否则Hmi()式中:辅助变量Hmi为通航模式,双向为,单向为;V为能见度;w为风力等级;B为船宽;Y为船宽值船舶进出港航道的通航状态,航行过程中船舶的吃水深度为amu iHs dmiamd iHs dmi()式中:为船舶上线时潮高;ad为船舶下线时潮高;Hs为进出港航道浅点水深;d为船舶吃水深度船舶在港过程中的吃水深度为amm iHs dmi,当t(tmd itmu i)时()式中:am为当t时的潮高横向船舶窗口期约束为Wn(Lmis i nBmi)c,HmiW(n(Lmis i nBmi)cBmi),Hmi()式中:W为航道宽度;L为船长;为风流压差角;n为船舶漂移倍数;c为船舶与航道边线间的富裕宽度进港或出港船舶的最小安全时刻为tg(Qm ni j)LmivnjQm ni jLnjvmi()式中:tg为同向安全时间间隔同向航行两船舶之间的安全间隔约束为(CmiCnj)(tmu itnu j)(Qm ni j)tg)(CmiCnj)(vmivnj)(Qm ni j)()反向航行两船舶之间的安全间隔约束为tg M a xLmi|Lnj/M i nvmi|vnj()(CmiCnj)(tmu itnd j)(Qm ni j)(tmu itnd j)Qm ni jtg)()式中:为一个目标周期的结束时刻;tg为反向安全时间间隔;z为船舶载重量;M为一个大于的极小值算法设计设计贪心遗传优化算法(G GA),以贪心算法为主体,组合遗传算法进行优化求解算法流程图见图图G G A算法流程图模型与算法验证 数据假设假设港口A,布置有危险品船舶锚地个,普通锚地个假设进港航道长 m,规定 万t级以下船舶可双向通航,万t级以上船舶及万t级以上危险品船舶只能单向通航假设港口布置有泊位 个,其中万t级散货船泊位个,万t级散货船泊位个,万t级散货船泊位个,万t级集装箱泊位个,万t级集装箱泊位个,万mL NG船舶泊位个,万t级液体化工船泊位个,万t级液体化工船舶泊位个假设该港口水文情况为规则半日潮,万mL NG船舶和 万t级散货船需乘潮进出港 万mL NG船舶乘潮窗口期为:、:,转化为分钟即为 、m i n;万t级散货船乘潮窗口期为:、:,转化为分钟即为 、m i n 对于液体化工船舶,禁止夜航,只能在:时间段航行,转化为分钟,即为 m i n 并对其他约束条件的值进行假设,建立调度基础数据库 调度试验设置多组不同目标周期的船舶进出港调度试验,对结果进行比较分析分别运用粒子群算法和灰狼算法求解作为对照实验,进行比较来验证模型和算法的合理性和有效性当设置船舶按周d为一个目标周期调度进出港时,运用粒子群算法求解时,求得在d内目标函数最优解为 t,且多次求解均无法避开过早收敛和局部极值现象,结果见图武汉理工大学学报(交通科学与工程版)年第 卷图P S O求解结果当运用灰狼算法求解时,求得在d内目标函数最优解为 t,且多次求解均陷入了局部最优解的快速下降陷阱,结果见图图GWO求解结果当运用贪心遗传优化算法求解时,求得在d内目标函数最优解为 t,结果见图比较可得贪心遗传优化算法更适用于本文模型在d内可以服务万t级散货船艘、万t级散货船艘、万t级集装箱船艘、万t级集装箱船艘、万t级液体化工船艘、万t级液体化工船艘、万t级散货船艘、万mL NG船舶艘图G G A一周调度结果假设港口A一个季度可营运 d,以一个季度为目标周期求得最优解为 t,见图在 d内可以服务万t级散货船 艘、万t级散货船 艘、万t级集装箱船 艘、万t级集装箱船 艘、万t级液体化工船 艘、万t级液体化工船 艘、万t级散货船 艘、万mL NG船舶 艘假设港口A一年可营运 d,以年为目标周期求得最优解为 t,见图在 d内可以服务万t级散货船 艘、万t级散货船 艘、万t级集装箱船 艘、万t级集装箱船 艘、万t级液体化工船 艘、图一季度调度结果 万t级液体化工船 艘、万t级散货船 艘、万mL NG船舶 艘图一年调度结果针对假设港口A分别用周调度、季调度、年调度的方式,其一年总卸货量对比见图图年总卸货量对比图 结果分析根据优化结果,在一个调度周期内可以很直观很明确地调度安排船舶进出港作业,验证了本文模型的合理性同时,本文模型算法不仅仅只限于周船舶进出港的调度优化,通过改变调度结束时刻的约束,本文模型也可用于季度、年甚至更长时间的中长期船舶进出港调度优化与卸货量预测通过图对比分别采用周调度、季调度、年调度三种调度方式对港口A调度年的结果短期调度可以看作是根据当前情况判断出的当前最优解,也即当前时刻的局部最优解,而若干个局部最优解所整合出的近似最优解往往并非全局最优解目前绝大多数港口调度都属于短期调度,优点是灵活方便,可根据每天港口的来船情况对调度计划进行调整但要提高港口的服务能力水平,提升港口吞吐量,通过优化中长期船舶调度从宏观上进行把控更为有效,这也验证了本文模型和算法的有效性可以结合本文模型预测出港口一个中长周期的总卸货量,并根据输出的船舶调度表规划引导这一个周期中各种类型船舶到港作业的数量第期丁可,等:基于贪心遗传优化算法的中长期船舶进出港调度优化与到港时刻,提高港口服务能力结 束 语目前的港口调度多停留于日调度的微观范畴,虽有船舶船期不定的客观条件的影响,但在全局宏观把控上确实会有一定的盲区和疏漏,文中提出此宏观中长期船舶进出港调度优化模型,帮助港口进行全局把控、宏观调度以及长远规划,提高港口服务能力参 考 文 献丁涛,王钰,王帆基于航次串理论的深港珠澳航线客船调度优化J武汉理工大学学报(交通科学与工程版),():黄蕴和大型船舶进出港安全乘潮计算模式的研究J中国航海,():张新宇,林俊,郭子坚,等基于模拟退火多种群遗传算法的港口船舶调度 优化 J中 国航 海,():徐国裕,郭涂城,吴兆麟单向水道船舶进出港最佳排序模式J大连海事大学学报,():王辉船舶乘潮进出港通航组织方案研究D武汉:武汉理工大学,卢璇,郑澜波基于约束规划的煤炭港口进出港协同调度研究J武汉理工大学学报,():NO R S T A DI,F AG E RHO L T K,L A P O R T E GT r a m ps h i pr o u t i n ga n ds c h e d u l i n gw i t hs p e e do p t i m i z a t i o nJ T r a n s p o r t a t i o nR e s e a r c hP a r tC,():L I JHMA S b a s e dn e g o t i a t i o nm e c h a n i s mf o rs h i pm u l t i p r o j e c t s c h e d u l i n gC P r o c e e d i n g so f t h e I n t e r n a t i o n a lC o n f e r e n c eo n M a c h i n e L e a r n i n ga n dC y b e r n e t i c s,L o n d o n,戴林伟双向航道船舶交通流元胞自动机模型及仿真J上海海事大学学报,():郑红星,刘保利,张润,等考虑减载移泊的散货港口船舶调度优化J交通运输工程学报,():张新宇,李瑞杰,张加伟,等多种航道条件下的港口船舶交通组织优化C第十三届中国智能交通年会,天津,A GA RWA LR,E R GUN S h i ps c h e d u l i n ga n dn e t w o r kd e s i g nf o rc a r g or o u t i n gi nl i n e rs h i p p i n gJ T r a n s p o r t a t i o nS c i e n c e,():蒋思怡狭水道船舶乘潮进出港优化调度研究D厦门:集美大学,M e d i u m a n dL o n g t e r mS h i pE n t r ya n dE x i tS c h e d u l i n gO p t i m i z a t i o nB a s e do nG r e e d y g e n e t i cO p t i m i z a t i o nA l g o r i t h mD I N GK e,)X UY a n m i n,)G U A NH o n g x u,)L IS h i j i e,)L IB o w e i,)(S c h o o l o fN a v i g a t i o n,W u h a nU n i v e r s i t yo fT e c h n o l o g y,W u h a n ,C h i n a)(H u b e i I n l a n dS h i p p i n gT e c h n o l o g yK e yL a b o r a t o r y,W u h a n ,C h i n a)A b s t r a c t:T a k i n gt h e t o t a l d i s c h a r g e c a p a c i t yo f t h e l a r g e s t p o r t i na t a r g e t p e r i o da s t h eo b j e c t i v e f u n c t i o n,c o m b i n e dw i t ht h en a v i g a t i o np r a c t i c e,a no p t i m i z a t i o nm o d e lo fs h i ps i n b o u n da n do u t b o u n ds c h e d u l i n gw a se s t a b l i s h e dw i t hn a v i g a t i o nc o n s t r a i n t ss u c ha sb e r t h i n gc o n d i t i o n s,n a v i g a t i o nm o d e,s h i pw i n d o wp e r i o da n ds h i pss a f ed i s t a n c ea sc o n s t r a i n t s,a n dt h eg r e e d y g e n e t i cc o m b i n a t i o no p t i m i z a t i o na l g o r i t h m(G GA)w a ss e l e c t e dt or e a l i z e i t T h er a t i o n a l i t ya n de f f e c t i v e n e s so f t h em o d e la n da l g o r i t h mw e r ev e r i f i e db yt h es i m u l a t i o nt e s tb ya s s u m i n gt h ep o r td a t a,a n dt h es h o r t t e r md i s p a t c h i n gm o d e a n d t h em e d i u m a n d l o n g t e r md i s p a t c h i n gm o d eo f t h ep o r tw e r e c o m p a r e da n dd e m o n s t r a t e d K e yw o r d s:i n b o u n da n do u t b o u n d;g l o b a ls c h e d u l i n go p t i m i z a t i o n;m u l t i c o n s t r a i n t;g r e e d y g e n e t i co p t i m i z a t i o na l g o r i t h m武汉理工大学学报(交通科学与工程版)年第 卷