新万博_万博出事了

周一至周五 | 9:00—22:00

作者婚:未知

  摘要坏俺行:   为解决复杂的自动化码头设备协同调度问题醇,考虑码头各作业间的相互作用和制约凹木,以最小化船舶在港时间和主要设备作业成本为目标醋墓,构建新的装卸混合模式下岸桥(quay crane钱桂射, QC)凭裂劝、顶升式自动引导车(lifting automated guided vehicle罐残洗, LAGV)及自动化轨道吊(automated rail mounted gantry crane导, ARMG)协同调度的混合整数非线性规划模型绊蓉。提出一种遗传算法与启发式策略结合的协同调度方法瓷,实现在系统整体性能最优情况下的设备作业序列优化菩。该模型能充分保障QC敖督毯、LAGV漏抱诫、ARMG之间的协同性稼,并引入QC调度的主要约束毫,更利于与QC调度模型进一步集成镁幻纹。数值试验证明了该方法的有效性妮溅拎,可为码头装卸作业调度提供决策支持便。
  关键词捷:
  自动化码头; 自动引导车(AGV); 自动化轨道吊; 协同调度; 遗传算法(GA)
  中图分类号湾超飞: U691.3
  文献标志码谴甜拆: A
  Abstract砍玩:
  In order to solve the complex collaborative scheduling problem of automated terminal equipments呻, considering the interaction and restriction among various operations in terminals徒, a new mixed integer nonlinear programming model is constructed for quay cranes (QCs)瞬, lifting automated guided vehicles (LAGVs) and automated rail mounted gantry cranes (ARMGs) collaborative scheduling under the mixed loading and unloading mode. The model objectives are to minimize the ship turnround time at a port and to minimize the operation cost of key equipments. A collaborative scheduling method based on the genetic algorithm and the heuristic strategy is proposed to obtain an optimized operation sequence of equipments under the condition of the optimal overall performance of the system. The model fully guarantees the cooperativity of QCs吾磊徽, LAGVs and ARMGs缮臣, and the main constraints of QC scheduling are introduced场狮, which is more conducive to the further integration with QC scheduling model. A numerical test is taken to demonstrate the effectiveness of the method. It can provide decision support for loading and unloading operations of automated terminals.
  Key words鼓滤茫:
  automated terminal; automated guided vehicle (AGV); automated rail mounted gantry crane; collaborative scheduling; genetic algorithm (GA)
  0引言
  由于集装箱码头装卸工?读侈捻、作业空间和设备配置等限制矮唯茸,优化各环节调度成为提高码头整体效率的重要途径插磁。目前掂棋,已有学者对包括水平运输设备在内的集装箱码头集成调度问题进行了研究们。CAO等[12]针对出口集装箱分别建立了解决单个岸桥(quay crane潦嫂, QC)与多辆集卡协调分配的混合整数模型和集卡与龙门吊集成调度模型练蕾牧,前者设计了遗传算法和改进约翰逊规则的启发式算法来提高求解速率豌补,后者基于Benders变异对问题进行求解蕉。秦天保等[3]针对集装箱QC与集卡集成调度问题徒成撤,以卸船完工时间最小为目标芭募亢,采用约束规划技术建模求解噶骏。CHEN等[4]研究了集装箱码头QC与集卡集成调度问题篱,建立了带约束的规划模型煌绞,并设计了一个三阶段算法篇。韩晓龙等[5]考虑集卡作业时间不确定和动态性到达的情况林伞,建立了集卡与QC协同调度模型并设计了改进的遗传算法进行求解世。TANG等[6]建立了QC与集卡联合调度模型骆司仟,并用改进的粒子群算法解决进出口箱装卸作业问题赐。HE等[7]建立了传统集装箱码头QC扑律、场桥和集卡的集成调度模型境劲先,提出了基于仿真的遗传算法与粒子群算法结合的优化方法眷郸。
  MEERSMANS等[8]最早研究了自动化码头多类型设备的集成调度问题讳朽,提出了分支定界法及启发式算法兰伶途,但仅考虑了装船作业情形典拍架。LAU等[9]分析了码头核心设备之间的协调关系旦钨,提出了设备集成调度模型沛,设计分层遗传算法并结合启发式策略进行求解里。HOMAYOUNI等[10]提出自动化码头自动引导车(automated guided vehicle谈, AGV)和QC同时调度的混合整数规划模型挫咯,并设计了两阶段启发式遗传算法进行求解换酗弄。DKHIL等[11]考虑码头多种资源之间的相互作用与制约绢对,提出了QCAGVASC(automated stacking crane)集成模型铣零偷。LUO等[1213]分别考虑了装卸同时进行的情形和单卸的情形媳骆莱,研究了自动化码头AGV调度规则和确定集装箱堆放位置的新方法嵌珊,通过数值试验评估算法的有效性瘦撩。   集装箱码头运作由众多环节相互合作完成博辖,且各环节相互影响和制约看猩跑,但当前绝大多数关于调度的研究集中在传统码头领域未仇,缺乏多类型设备的深度集成乖,鲜有考虑边装边卸作业模式及工艺革新造成的调度复杂性萌洗。少数研究集成调度的文献存在的不足有涩:(1)忽略了QC调度中任务约束的影响;(2)假设场桥作业序列完全遵从QC装卸序列萍甫。因此久吨赣,本文将以顶升式自动引导车(lifting automated guided vehicle起嫡,LAGV)为水平运输设备的自动化码头装卸系统作为对象孟,引入QC调度的主要约束盗柿,提出新的QC何仑榷、LAGV和自动化轨道吊(automated rail mounted gantry crane称咐宦,ARMG)协同调度模型和算法卞图,实现系统性能的改善辞贩田。
  1问题描述
  码头设备资源的调度受码头工艺的制约和影响安瓶裁,而码头工艺创新为码头作业效率的提升提供了重要的途径臼。这里研究双车QC朗、LAGV和ARMG组成的新型自动化集装箱码头工艺幻拦舷,其布局见图1沫犁是。LAGV所在的QC作业区位于QC后伸距下方妓犬,各车道为单向行驶堂弓呻,行车方向依据船头朝向和装檀量识、卸箱量的比例设定俩,以减少倒箱门现象对车辆和道路的干扰扣醛婆。堆场采用垂直于岸线的布局韩娜喂,堆场海侧行驶区采用双向车道察及嚷,相邻车道行驶方向相反绷森免,便于车辆在堆场海侧交换区的进出习。缓冲车道位于QC作业区与堆场海侧交换区之间刃崩皋,既作为LAGV的临时等待区反棺晾,又作为岸边与堆场之间的连接通道陌,以缩短水平运输距离狮磋。
  与传统工艺相比匆腹,LAGV负责水平运输慈入,堆场每个箱区海侧布置由一组支架组成的交换区宦,作为集装箱的临时缓冲存放点嚷库,以缓解水平运输能力与堆场装卸能力的矛盾刻确粗,提高系统作业效率莲肥。然而俩,交接方式的灵活性增加了设备调度的复杂性速吼,这对调度方法提出了更高要求剔。
  码头装卸系统是一个复杂的袖舶仆、动态的并行工作系统嫩寒搞,其作业类型包括将进口集装箱运输到堆场侧和将出口集装箱运输到船侧蹦快。以装船作业为例简述运作决策过程钉:首先套防偏,船舶进港后茧寒丹,码头根据船舶配载图荣令捎、堆场分配计划等宏,制定QC分配和调度计划;然后公悸,由ARMG从堆场指定位置提取集装箱败盖,经缓冲支架交给指定LAGV;最后卤怯,由指定LAGV运输集装箱到指定QC路浅。若LAGV晚到则会造成QC等待脆桔你,增加船舶的在港时间茹。卸船过程相反挞俊喷。
  显然陵充凛,QC装卸作业讼鲸、水平运输作业与堆场设备作业相互关联疯,必须制定统筹全局的设备协同调度计划赊嘛。以往大多研究仅考虑单独装箱或卸箱作业瓷荆,即使涉及QC同时装卸扩卵地,也未考虑在堆场箱区混合堆存情况下如何提高调度协同性问题晤娄号。这样的简化会极大地降低全局性能厂皮隶。因此赔桨协,本文研究更一般的情形坎:在装卸混合模式下柿瑞啥,船舶的进出口集装箱混合堆存在不同箱区羌颂,QC边装边卸扯,LAGV灵活服务多台QC且可双循环运输诽挡,同时箱区的ARMG边存边取贬。调度方案的优劣由两方面因素评价怀袜:(1)LAGV自身效率歧侮。为降低空驶率羞靠憋,将LAGV总行驶时间作为评价指标巫按。(2)QC和ARMG的效率授险。集装箱船在港时间越长畏皑慷,其花费成本就越大宋钞蔫,故将船舶在港时间和ARMG移动时间作为评价指标鞍电。
  2自动化设备集成调度模型
  2.1假设条件
 ×宀俾隆(1)集港在装卸船作业之前已经完成胚,疏港在装卸船作业之后才进行;(2)计划期内的船舶配载计划慌、泊位计划帅、堆场箱位计划和QC调度计划已知撑挝,这里QC调度的任务以簇[14]形式定义挪,且簇任务内集装箱装卸顺序和簇之间的约束关系确定;(3)QC跺、LAGV和ARMG数量已知拌焦,且每个设备一次只处理一个集装箱;(4)LAGV百阂拿、ARMG(空/重载)和QC的行驶速度及其装卸效率已知;(5)进匡僻骑、出口集装箱允许堆存在堆场同一箱区局,每个箱区的集装箱仅由海侧ARMG负责装卸锤估悸,已知LAGV与任意两个操作节点之间的距离慰偷诡,忽略LAGV和ARMG在堆场交换区等待支架空闲的时间苟航霓。
  2.2符号变量说明
  常量符号如下理爆量。
  K表示QC的集合挝挫,Q表示ARMG的集合项,V表示LAGV的集合痢板洗。ve和vd分别表示为ARMG提供初始和结束虚拟任务的虚拟QC乱扇甭,vs和vf分别表示为LAGV提供初始和结束虚拟任务的?拟QC添。mk表示第k台QC执行的任务数量贤彭,k∈K冷。(k翻快活,i)为箱任务编号扣,表示第k台QC 的第i个箱任务兰诞,k∈K添蔑,i=1脑侠,2算篮,…谩,mk祈。eki和dki分别为QC在其作业区开始和结束箱任务(k妮,i)的事件碘边,当箱任务(k扳,i)为卸船任务时其分别表示QC开始落箱到LAGV上的事件和结束落箱到LAGV上的事件刑赊蚀,当箱任务(k两,i)为装船任务时其分别表示QC从LAGV上开始提箱的事件和结束落箱到船上的事件炮较,k∈K冻斥氖,i=1默,2付距兄,…皆施急,mk略舒。 Eaki表示LAGV在堆场海侧交换区开始作业箱任务(k链,i)的事件唾,当箱任务(k挂顾污,i)为卸船任务时其表示LAGV开始将箱顶升到支架的事件吭,当箱任务(k颅唇季,i)为装船任务时其表示LAGV开始从支架处接箱的事件甫,k∈K软,i=1韶,2妙弟般,…菊秃,mk讹腑龋。Ebki表示ARMG在堆场海侧交换区开始作业箱任务(k瘦擞酥,i)的事件司,当箱任务(k沫,i)为卸船任务时其表示ARMG开始从支架上抓箱的事件陇,当箱任务(k卧桐,i)为装船任务时其表示ARMG开始放箱到支架上的事件倾岗,k∈K朝井碴,i=1入噶,2棱翘恼,…陈,mk写星。TC表示有先后顺序要求的事件eki的集合杰,TD表示卸船任务对应的事件eki的集合哦购鼻,TL表示装船任务对应的事件eki的集合帽,Nq表示第q台ARMG执行的Ebki的集合钳抢,k∈K写,i=1难椿,2蛾勺,…抢氦,mk富炯苍,q∈Q孩。
  变量符号如下纤清。ski表示第k台QC执行eki的实际准备就绪时刻搞本遂,Hk(i-1)i表示第k台QC完成ek(i-1)后执行eki的全部准备时间闺鲜,yki表示eki的实际发生时刻昆替络,ψki表示dki的实际发生时刻浑勤刮,Δwki表示eki与dki发生时刻的间隔时间蹬匹,Yaki表示Eaki的发生时刻迷挖咖,Ybki表示Ebki的发生时刻乾,Ski表示eki与Eaki之间的间隔时间熄,ΔSki表示Eaki与Ebki之间的间隔时间沧掂厢,k∈K铆复,i=1非,2抒胶,…袭簇,mk店猩艰。Tki党蓉,lj表示   ARMG从
  Ebki发生的位置到Eblj发生的位置的纯移动时间卷湃擅,Rki笺,lj表示ARMG完成Ebki后执行Eblj需要的调整时间捅撼,k∈{ve}∪K犯视瓤,l∈{vd}∪K迹党互,i∈{1轿,2赤咀沉,…船沥杠,mk}邻讳擒,j∈{1馈,2谭儡吝,…龚协,ml}下妈,mve=Q彻喀。tki型珊翟,lj表示LAGV从eki发生的位置到elj发生的位置耗费的时间黄涂世,cki互,lj表示LAGV完成eki后去执行elj需要的调整时间盲,rki慧慕,lj表示eki与Ealj之间LAGV的调整时间汞妹,k∈{vs}∪K努,l∈{vf}∪K耪,i∈{1沟徘徊,2虏和,…磺地逛,mk}炮,j∈{1假,2疲躲,…扣含,ml}信蹋亩,mvs=V促事。
  决策变量如下睦皇呜。ki慨垢辫,lj为01变量蓝坎疯,若同一辆LAGV完成eki后紧接着完成elj则其值为1景,否则为0饯诫涪,k∈{vs}∪K删改,l∈{vf}∪K策湘,i∈{1筹,2镀雇,…涵隘,mk}凄僧鲸,j∈{1卧簇搽,2爸暴,…勃范腔,ml}绕,mvs=mvf=V栋控。φki穿,lj为01变量陈切崎,若同一台ARMG完成Ebki后紧接着完成Eblj则其值为1范,否则为0浑袜,k∈{ve}∪K努,l∈{vd}∪K久赣,i∈{1礁础,2搬慕潍,…锻,mk}率别,j∈{1狈袍,2铃迁巷,…吼泞己,ml}卫全,mve=mvd=Q窃痹涧。
  2.3目标函数及约束
  下式中肉,除有特殊限定外竣:
  k理,l∈K;i=1幕鼎,2尖,…嘶下,mk;j=1盆林诫,2纱酬,…藉霜啊,ml险。
  S1=min(maxk∈K ψkmk)
 ∏懒啤(1)
  S2=min k∈{ve}∪K
  i
  l∈K∪{vd}
  j(Tki泛,ljφki凳,lj)
 ∑侍阜ぁ(2)
  S3=min k∈{vs}∪K i
  l∈K∪{vf}
  j(tki烤,ljφki魔,lj)
 〉ぁ(3)
  l∈{vf}∪K
  jki戚慌律,lj=1邯,k∈{vs}∪K
 『ジ诤隆(4)
  k∈{vs}∪K
  iki驴扭,lj=1喉乱媒,l∈{vf}∪K
 ÷甯忻摇(5)
  l∈{vd}∪K
  jφki擒,lj=1何沥,k∈{ve}∪K
 【男浮(6)
  k∈{ve}∪K
  iφki报帘,lj=1水腊,l∈{vd}∪K
 』薜臁(7)
  ylj-max(yki+cki沸迸,lj蔫割暑,slj)≥M(ki侍苯,lj-1)石辜,
  k∈{vs}∪K
 ∠砍没摺(8)
  Yblj-(Ybki+Rki爬,lj)≥M(φki霓泄偷,lj-1)洽隆,
  k∈{ve}∪K
 〖稹(9)
  Yalj-(yki+rki咐接皋,lj)≥M(ki耐懂结,lj-1)软胚,
  k∈{vs}∪K
 ×迓省(10)
  yki≥ski
 】啤(11)
  ski≥yk(i-1)+Hk(i-1)i贤靶函, i=2眉,3缅强劳,…惜锚,mk
 ∨嗉岣 (12)
  yki≥Yaki+Ski管蝎澄,eki∈TL
 ±蹇啤(13)
  Yaki≥Ybki+ΔSki咖,eki∈TL
 〉倮昀唷(14)
  Yaki≥yki+Ski刹,eki∈TD
 ±艿拧(15)
  Ybki≥Yaki+ΔSki肖替,eki∈TD
 【ⅰ(16)
  Ybki-Yblj≥0痴普泵,Ebki钠,Eblj∈Nq;yki>ylj;
  eki∈TD;elj∈TL; q∈Q;
  若k≠l?teki塑,elj∈TC
 ∧腥荨(17)
  ψki-yki≥Δwki
 〖肽弧(18)
  式(1)~(3)为目标函数联,分别表示最小化所有QC中最大完工时刻倘、最小化ARMG总移动时间献、最小化LAGV的总行驶时间狭。式(4)~(7)表示LAGV或ARMG一次只能执行一个任务貌串,一个任务一旦由某一ARMG或LAGV执行就不能中断踏形,且每个任务都要被执行陪巳。式(8)和(9)表示由同一装卸运输设备执行的相邻任务的时间逻辑关系堡,式(8)表示同一辆LAGV完成
  eki后去执行elj需要有时间cki弹,lj准备相撤芦,以及只有LAGV到达和QC自身准备就绪吠嘉粕,QC才能开始装卸集装箱挪毖嘿。式(9)表示同一台ARMG完成Ebki后去执行Eblj需要有时间Rki拾炉,lj准备揪钡谩。式(10)表示不同作业环节的时间逻辑关系胜,如果任务(k鼓堵牡,i)和(l寞,j)是同一辆LAGV的两个相邻任务藕甲罢,那么LAGV完成eki后需要时间rki棘搐物,lj调整才能执行Ealj刹括苦。式(11)表示eki的实际发生时刻最小为最早可能发生时刻矫儡黄。式(12)表示QC执行ek(i-1)后需时间Hk(i-1)i准备才能执行任务eki青。式(13)和(14)表示某装船任务(k酣,i)的相邻作业环节间的时间逻辑关系戒,此类任务的设备操作顺序是ARMG―LAGV―QC颈,因此LAGV完成Eaki的时刻与Eaki和eki的调整时间之和不会超过QC完成eki的时刻比荤电,ARMG完成Ebki时刻与Eaki和Ebki的调整时间之和不会超过LAGV完成Eaki的时刻处绵惰。同理辩天,式(15)和(16)表示某卸船任务(k酱,i)的相邻作业环节间的时间逻辑关系物须,此类任务的设备操作顺序是QC―LAGV―ARMG吼。式(17)表示每一台ARMG执行QC的任务时其作业顺序在先装后卸情形下需要符合QC作业顺序和其任务约束关系氯。式(18)表示QC装卸每个集装箱需要时间Δwki赎扰别。
  值得注意的是杏呢簇,上述模型与已有文献相比居,主要有3点不同襄酪羞。(1)LAU等[9]的研究将ARMG调度序列归结为QC调度序列的子序列骂,意味着ARMG调度必须遵从QC调度搭挖描,由式(19)约束涉经逝:
  Yki-Ykj≥0陡,Ebki∈Nq;i>j;q∈Q
 ∑住(19)
  而本文模型考虑船舶集装箱装卸混合作业时ARMG与 QC调度的协同性鹿,体现在将式(19)放松为式(17)期湃库,表明ARMG除先装后卸情形外波死,可以按照灵活作业顺序操作焕镀相,无须遵从QC调度序列告剃惶。(2)所有类似文献均研究传统AGV工艺畔仁,在堆场箱区只有AGV与 ARMG刚性衔接凡模,而本文针对缓冲支架系统持,特别定义了Yaki和Ybki两个状态变量光诵,增加LAGV赣轮翟、ARMG和支架三者之间衔接的灵活性考扒。(3)考虑QC调度任务约束关系笛佃,由式(17)体现统痘头,以利于与QC调度模型进一步集成钉乓。   3协同调度方法及算法设计
  3.1协同调度思想
  传统调度方法[9]规定水平运输设备和场桥的作业序列必须遵从QC作业顺序踏归协。该方法一般适用于单装/单卸模式弦,而在装卸混合模式下虽然能够降低集成调度的复杂性鸽腊,缩小问题解空间浓,但会忽略设备作业协同性刚,甚至会将最优解排除怂拘。
  本文提出的协同调度策略的特点在于檀拣,要求水平运输设备必须遵从QC或约束关系的任务顺序蠕,而放松ARMG与QC作业的一致性约束鹤材就,除QC先装后卸作业情形外里校监,允许ARMG自主灵活地确定作业序列钢铃,见图2鳖吴宿。
  3.2结合启发式策略的遗传算法设计
  在QC作业序列的基础上龋慑瞥,基于遗传算法划蚀铃,采用协同调度策略优化ARMG作业序列委脖,并采用启发式LAGV指派策略优化车辆运输任务钒倾舅,见图3玛翰。
  3.2.1染色体编码和解码
  基于QC调度计划对箱任务采用自然数编码记殴两,每个染色体代表所有箱任务的一种随机排列扯抗棵,每个自然数代表箱任务编号惯,染色体长度等于箱任务数量凯。染色体序列需结合LAGV指派和ARMG调度的启发式策略进行解码活,确定各ARMG及LAGV的任务顺序兄零。
  在上述编码基础上淘,设计ARMG调度序列的启发式策略的步骤如下捎牵:(1)从编码序列中抽取每台ARMG的任务序列盾净,获得各台ARMG的随机箱序列;(2)针对ARMG随机任务序列中的任意两个任务弥漆倪,判断两个任务是否属于同一辆QC透摊,若是则转步骤(3)逻耙池,否则继续寻找涝,直到所有的两个任务组合都寻找过一次为止;(3)判断两个任务是否是同一任务类型琅,若是则转步骤(2)挽虫队,否则判断这两个任务在QC作业序列中的作业顺序是否是先装后卸掠铜,若是则将ARMG中这两个任务的顺序调整成QC作业顺序妻,然后转步骤(2)泞持。最终获得符合QC先装后卸作业约束的ARMG箱任务序列详崎。
  若在装卸混合模式下存在同箱区且在同一QC序列中先卸后装两个附近的任务吩椭,则采用上述启发式策略有利于避免各设备的串行完成挪阑,实现并行协同调度猫绵,降低过多等待偶稠,提高码头效率淑仓。
  码头常以船舶在港时间最短为首要目标赶汤搏,因此采用如下3种基于时间型启发式规则的LAGV指派策略长帛绰,逐一为任意箱任务序列中的集装箱指派合适的LAGV乾恳沙。LAGV完成当前运输任务后随即去执行后续任务;LAGV卸船箱任务的起始位置在QC作业区;LAGV装船箱任务的起始位置在堆场海侧交换区苯典。(1)先到先指派策略妇:针对某一运输任务绞抡骂,选择最快完成前项任务抵达该任务起始位置的LAGV宛凶。(2)适合装箱位置就绪策略鸿悲版:针对某一运输任务锭,以起重设备作业该任务的准备就绪时刻(若装船嚏,则是ARMG准备就绪时刻;若卸船甜庙,则是QC准备就绪时刻)为基准释搏备,从所有车辆中选择完成前项任务后最早抵达该任务起始位置的LAGV跋。(3)适合QC就绪策略惟:针对某一运输任务恐梗芍,以QC就绪时刻为基准疾踢,从所有车辆中选择完成前项任务后最早空驶(卸船箱)或提箱(装船箱)至QC作业区的LAGV叛。
  3.2.2不可行和重复序列的修正策略
  随机生成或迭代更新的染色体可能存在不可行或重?透鎏宓那榭觯?故需进行修正乖顽侥。针对不可行序列的修正策略皆构:将箱任务序列满足已知QC作业箱任务顺序及簇任务约束关系盛。针对种群中重复序列的修正策略陛搬:搜寻每代的重复个体媚,并采用部分逆反变异操作生成新的个体替换原染色体忿罚,得到新的种群作为下一代桃。这样不仅降低重复个体存在的概率陡孝烩,而且保持了种群多样性漆黎。
  3.2.3染色体选择伎喜、交叉么涂练、变异操作
  采用轮盘赌的方法对染色体进行选择;采用部分匹配交叉(图4)和部分逆反变异(图5)的方法对染色体进行交叉违釜腹、变异操作接垒。
  3.2.4适应度函数设置
  以最小化箱任务最大结束时刻为首要目标摩,并通过设置加权系数背耗,将适应度函数设计为一种组合函数惊画操,其由箱任务最大结束时刻连某、QC累计等待时间岭烹寞、每台QC的箱任务均衡程度趁邪卑、LAGV的总行驶时间和ARMG总移动时间组成诞苹。鉴于最小化问题搪,将适应度函数设为上述组合函数的倒数茨蹬上,具体计算取决于箱任务的LAGV指派以及各设备之间的交接时刻卞,状态更新流程图见图6摹嗜豆。
  4案例验证与结果分析
  4.1案例说明
  以采用“双车QC+ LAGV+ ARMG”工艺系统的青岛某自动化集装箱码头为例浇迪,码头整体布局和水平运输交通规则见图1厢。LAGV所在的QC作业区共7条行车道唱,每条车道宽4 m蛙,其中4条为装卸车道赤藤衫,3条为穿越车道捂官椿,装卸车道成对布置绊,并与穿越车道相间隔铣梦。堆场海侧行驶区共有6条双向车道此耐潦,且相邻车道行驶方向相反暗略。各装卸运输设备的速度见表1搭罚眷。
  某船需要装卸的进出口集装箱在船上的位置及簇任务划分和约束关系可通过船舶配载计划获得豌邪。假设QC调度计划已知钵,QC抓/放箱操作时间均为10 s妊,QC小车在QC作业区与船之间的水平行驶时间为40 s贝谭,且在QC作业区车道上的行驶方向为逆时针方向;ARMG初始位置在堆场海侧交换区(包含4个缓冲支架和1个空车道)默悉,堆场数量为10个厂垦,每个堆场仅海侧ARMG工作;LAGV初始位置在缓冲车道莎卸朽,各设备完成各自所有任务后必须回到初始位置眠。
  考虑算法运算效率碍统,通过多次组合试验确定算法相关参数聚哇扫。初始种群大小为50唉饰栋,最大遗传代数为100行帅,交叉概率为0.85傻驹腺,变异概率为0.1僳。本文试验均采用MATLAB R2014a编程实现算法晌僵,并在Intel(R) Core(TM) i76700HQ CPU @2.6 GHz处理器线钡散、8 GB内存的电脑上运行得到试验结果鬼吵先。
  4.2协同调度求解结果分析
  4.2.1算法的优化性能分析及鲁棒性分析
  设计7组中等规模仿真算例缉,从计算时间和结果进行比较铂瓷,验证所提算法的优化性能嗡县。采用CPLEX 12.2求解器和遗传算法分别求解算例防哦。在CPLEX求解过程中蔚,将模型的非线性约束式(8)划分成2个线性约束比吞篓,结果见表2兑浪。表2中最后一列显示了采用本文算法得到的加权目标函数值与最优值之间的偏差擂哆。试验发现昧实,计算耗时随着任务数的增加快速上升容坷俗,对30个以上的箱任务问题无法在有效时间内得到结果糕溅反,而用遗传算法尽管不能获得最优解纲锌辆,但其解与最优解的偏差在适当范围内复佰危,且在大规模任务的计算效率上具有优势峭。   不同任务规募旌滩ǎ和LAGV数量下算法的鲁棒性变化如图7所示徊:鲁棒性指标在适当范围(0~4%)内波动身,其最大值为3.90%识,平均值为2.47%吞哄,说明算法有较好的鲁棒性氢。
  4.2.2结果比较分析
  根据设置的案例数据仿,采用结合启发
  式策略的遗传算法对自动化设备协同调度模型进行求解锈。试验选择2个因素作为变量寿砷:LAGV数量钡,设置在8与24之间;每个计划期内的任务规模藤海纽,设置成40母撇、50吾、60委辣、70和80霖沟班。所需其他数据(如LAGV初始位置笔挞、集装箱类型及其在堆场中的位置)均采用随机模拟方式产生酿密县。因此瓮酬风,不同变量因素下有多种组合爸欺花,每种组合随机产生10组数据儒玩吵,每组数据重复试验操作5次极辟惰,取其平均值来减少算法误差喜萝那。
  4.2.2.1协同调度方法的比较分析
  ?榉治鱿低承阅艿牧槊粜裕?将LAGV数量和每个计划期内的任务规模作为变化因素山绊怂,得到不同调度方法的结果持餐山,见图8夹捣。在给定LAGV数量的情况下尝敖袍,2种调度方法的加权目标函数值均随着任务规模的增加而增加胁,但平均每个任务的加权目标函数值在下降吐。这表明任务规模变大时系统将获得更好的性能改揪。但实际上粒光烘,由于码头各种中断事件的发生茬木甲,如起重机或LAGV等设备故障棘,不可避免地需要进行再调度时棺。因此瞪飞,可结合实际情况陈篡钱,选取一个适当的任务规模以权衡计算量和系统性能的损失洪弓摩。在给定任务规慕思暮剑和LAGV数量的情况下复绒,本文提出的协同调度方法的加权目标函数值小于传统调度方法的加权目标函数值杏荤。这表明课,在码头实际管理中歪倦慨,充分优化ARMG作业序列有助于提高其与QC和LAGV之间的协调性忱趣,达到系统整体性能平均8.7%的提升门。
  4.2.2.2不同LAGV指派策略比较分析
  图9为不同LAGV指派策略对整体调度结果的影响悉晨肥。在3种LAGV指派策略下橙轨,随着LAGV数量的增多平均每个任务的加权目标函数值均在下降铆。图9中的数据表明萎莫,不同的LAGV指派策略无绝对的优劣扫,不同的策略适合不同的设备配置比例病岛屠。由此可见播,在码头实际管理中禄,根据设备配置比例合理利用不同LAGV指派策略比利用单一LAGV指派策略效果更好捣,更有助于码头整体效率的提升莫敬。
  图10为不同LAGV指派策略对QC等待时间的影响酗愁。在LAGV和QC配置比例较小时取刑:LAGV本属于瓶颈资源捍乱,采用先到先指派策略更易造成无效等待奈,从而加剧水平运输设备的紧缺性嘘,最终导致其他QC过多等待;采用适合QC就绪策略辛,即始终选择适合的QC辨荷,有助于减少QC等待时间驶。因此苹澜,在此情形下采用适合QC就绪策略的效果优于采用适合装箱位置就绪策略的效果痘。在LAGV和QC配置比例较大时帽,这两种策略对QC等待时间的影响无明显差异拿峨林。
  图11为不同LAGV指派策略对ARMG移动时间的影响轰达。在LAGV和QC配置比例较小时毙疤,LAGV本属于瓶颈资源弗蓟试,采用先到先指派策略和适合装箱位置就绪策略更易导致LAGV等待发生咕,从而加剧水平运输运力的紧张康,导致其他ARMG过多等待入疟力,进而影响到ARMG的调度序列挎,使得重进重出比例下降第衰,因此此时采用适合QC就绪策略效果较好缄汇编。在LAGV与QC配置比例较大时鼻诽撵,QC和ARMG效率成为关键溺,而采用先到先指派策略有助于减少LAGV空驶率荒奉,从而提升运力吝立喷,最终配合ARMG优
  化作业序列祥,降低移动时间舜,因此此时先到先指派策略优于适合装箱位置就绪策略爽蓝。
  图12为不同LAGV指派策略对LAGV行驶时间的影响仍腹欣。采用先到先指派策略冬,即选择最早到达的龚、最近的LAGV有利于减少空驶率龟,从而更有利于降低LAGV行驶成本魏。相对于适合装箱位置就绪策略粉,适合QC就绪策略的目的在于减少无效等待时间诧锤戳,故空驶率不会太高;相对于先到先指派策略碑相趟,适合QC就绪策略用在卸箱任务时容易产生较高空驶率露桥们,且用于装船任务时更倾向于选择无效时间最短的车辆穆歌古,故空驶率较高脯螺宋。总之旅复,从车辆行驶成本看褂,适合QC就绪策略是3种指派策略中的一个折中策略顺殊,其目的在于优化QC等待时间呵淋。因此币起,如图12所示精,该策略下的曲线变化平缓失,且位于其他两种策
  略对应的曲线之间川本。
  5结束语
  码头设备的协同调度有利于减少船舶在港时间盛,提高码头整体作业效率鹃焦。本文在以往研究的基础上构建新的协同调度模型并设计改进的遗传算法进行求解窘,其创新之处在于评:考虑了LAGV结合具有有限堆场缓存空间的自动化集装箱码头装卸新工艺的作业特点;考虑了装卸混合模式下设备调度的协同性;引入了QC调度的主要约束衫澎良。最终通过数值试验与传统调度方法的对比验证了本文模型和算法的有效性腿。
  参考文献峰:
  [1]
  CAO Jinxin俊涟, SHI Qixin估, LEE DerHorng. Integrated quay crane and yard truck schedule problem in container terminals[J]. Tsinghua Science & Technology赴夸翅, 2010播, 15(4)篓豌: 467474.
  [2]CAO Jinxin标癸饺, LEE DerHorng勉枚炭, CHEN Jianghang憾台赌, et al. The integrated yard truck and yard crane scheduling problem纷: Benders’ decompositionbased methods[J]. Transportation Research Part E叭迹: Logistic & Transportation Review顾, 2010譬, 46(3)履: 344353.
  [3]秦天保房滥米, 彭嘉瑶贫汇, 沙梅. 带任务顺序约束的岸桥集卡集成调度约束规划模型[J]. 上汉诤ィ海事大学学报集解拍, 2013撕浇, 34(3)鼎瑟词: 17.
  [4]CHEN Lu第衡庆, LANGEVIN A收列, LU Zhiqiang. Integrated scheduling of crane handling and truck transportation in a maritime container terminal[J]. European Journal of Operational Research尝仑, 2013痛, 225(1)肮觅: 142152.   [5]韩晓龙搭, 牟少莉. 基于CHC算法的集卡与岸桥协调调度优化问题[J]. 武汉理工大学学报(信息与管理工程版)词, 2014奢, 36(2)络葛: 233236.
  [6]TANG Lixin抽托沏, ZHAO Jiao耐斑嫌, LIU Jiyin. Modeling and solution of the joint quay crane and truck scheduling problem[J]. European Journal of Operational Research啡券讲, 2014闻翱, 236(3)篓摆碑: 978990.
  [7]HE Junliang惊, HUANG Youfang愧还, YAN Wei欧疮, et al. Integrated internal truck衅, yard crane and quay crane scheduling in a container terminal considering energy consumption[J]. Expert Systems with Applications逗摄, 2015豌, 42(5)穷簇脐: 24642487.
  [8]MEERSMANS P J M才类瞬, WAGELMANS A P M. Effective algorithms for integrated scheduling of handling equipment at automated container terminals[R]. Rotterdam顾: Erasmus University歼什涕, 2001.
  [9]LAU H Y K赌, ZHAO Ying. Integrated scheduling of handling equipment at automated container terminals[J]. Annals of Operations Research腺谈将, 2008侍, 112(2)肥: 665682.
  [10]HOMAYOUNI S M歌呈, HONG T S须, ISMAIL N签瞬巳, et al. A genetic algorithm for optimization of simultaneous scheduling of AGVs and QCs in container terminals[C/OL]//11th Asia Pacific Industrial Engineering and Management System. Melaka苏录, Malaysia介, December 710乳磕, 2010. http苦蔫巫://www.apiems.org/archive/apiems2010/paper.php.
  [11]DKHIL H禽匡, YASSINE A皖牧颊, CHABCHOUB H. Optimization of container handling systems in automated maritime terminal[J]. Studies in Computational Intelligence倦筏, 2013避, 457排莆: 301312.
  [12]LUO Jiabin撑啡孪, WU Yue. Modelling of dualcycle strategy for container storage and vehicle scheduling problems at automated container terminals[J]. Transportation Research Part E何售咯: Logistics & Transportation Review桐, 2015攘彪, 79哦: 4964.
  [13]LUO Jiabin氰免, WU Yue醚, MENDES A B. Modelling of integrated vehicle scheduling and container storage problems in unloading process at an automated container terminal[J]. Computers & Industrial Engineering实瑟潜, 2016话时, 94嘉日: 3244.
  [14]BIERWIRTH C攘, MEISEL F. A survey of berth allocation and quay crane scheduling problems in container terminals[J]. European Journal of Operational Research薯, 2010逞黔, 202(3)拼秤: 615627.
 ∏闳蕖(?辑赵勉)