（系统工程专业论文）两种不确定情况下的鲁棒泊位分配问题研究.pdf

摘要 摘要 集装箱运输大大地推动了世界经济的一体化，集装箱正在使世界变小。集装 箱码头是国际物流体系中的一个重要节点，它的生产效率直接影响着世界经济 的效率。但由于恶劣天气、机械故障、管理不善等原因，集装箱码头一直面临 着各种各样的不确定因素，这些不确定因素给码头生产效率的提高带来了极大 的挑战，也大大增加了码头生产作业的成本。泊位是集装箱码头最核心的资源， 泊位分配计划是岸桥计划、集卡调度、堆场分配、场桥调度和人员排班的基本 依据，在充满不确定因素的作业环境中，如何制定鲁棒的泊位分配方案，一直 是工业界和理论界关注的话题。 本文首先回顾了国内外有关鲁棒泊位分配问题的研究成果，对研究的发展和 现状进行了系统、详细的介绍，并指出了目前研究中存在的问题。针对这些问 题，本文做了以下几方面的工作： 针对船舶抵港时间随机延误的不确定情况，研究了鲁棒泊位分配问题。给出 了鲁棒泊位分配的数学模型，设计了一个反馈调整的求解算法。该算法抓住了 计划阶段和实时阶段之间的联系，主要由三个部件组成：求解确定性模型的模 拟退火算法，延误发生时的实时调整规则，调节船舶缓冲时间的启发式方法。 模拟退火算法的多次执行保证了算法的寻优能力，而鲁棒性则来源于两个方面： 模拟退火算法解码过程中插入了岸线缓冲；通过算法的不断迭代，每条船舶都 拥有了合理长度的缓冲时间。实验表明，文中提出的反馈调整技术框架能够产 生非常鲁棒的泊位分配方案，且在不同的波动模式下都有优秀的表现；同时， 根据算法结果得到的缓冲时间频率分布图，能给码头计划人员提供极大的帮助； 此外，算法求解效率很高，也不存在过度拟合现象。 针对计划外船舶临时靠泊的不确定情况，设计了对预定方案的实时调整策 略。此调整策略分为两步：首先，根据战略重要度系数、直接利润系数和调度 压力系数确定局部调度时间区间；然后，在局部调度时间区间上，利用本文设 计的实时调整规则把计划外船舶插入泊位分配方案。数值实验表明，该实时调 整策略对预定方案的干扰小，能够保证预定方案的平滑实施，而且在不同波动 模式下都性能良好；实验还分析了计划外船舶的数目对泊位分配方案的影响。 在当前经济危机持续蔓延、成本控制决定生存的时期，希望本文的研究工作 摘要 能给集装箱码头的生产调度和成本控制提供一些运作层面的参考。 关键词：泊位分配问题鲁棒优化不确定反馈实时调整 i i a b s t r a c t a b s t r a c t c o n t a i n e r sa r em a k i n gt h ew o r l ds m a l l e r , a n dc o n t a i n e rs h i p m e n ts i g n i f i c a n t l y a c c e l e r a t e st h ei n t e g r a t i o np r o c e s so fw o r l de c o n o m y p r o d u c t i v i t yo ft h ec o n t a i n e r t e r m i n a l ，w h i c hi sac r i t i c a ln o d ei ni n t e r n a t i o n a lt r a n s p o r t a t i o nn e t w o r k ，d e v o t e s m u c ht ot h ee f f i c i e n c yo fw o r l de c o n o m y o w i n gt ob a dw e a t h e r , m a c h i n e m a l f u n c t i o na n dp o o rm a n a g e m e n t ，v a r i e t i e so fu n c e r t a i n t i e sc o n f r o n t i n gt h e c o n t a i n e rt e r m i n a ld r a gd o w nt h ep r o d u c t i v i t yal o ta n dp u s hu pt h ec o s tt oah i g h l e v e l b e r t hi st h ec o r er e s o u r c ei nt h et e r m i n a l ，a n db e r t hp l a ni st h eb a s i so fw h o l e s c h e d u l ew o r kt o w a r d sq u a yc r a n e s ，c o n t a i n e rt r u c k ，c o n t a i n e ry a r d ，y a r dc r a n e sa n d t h e c r e w c o n s e q u e n t l y , r o b u s t b e r t ha l l o c a t i o n p r o b l e m u n d e ru n c e r t a i n c i r c u m s t a n c e si sa l w a y sah o tt o p i ci nt e r m i n a li n d u s t r ya n da c a d e m i cc o m m u n i t y f i r s t l y , i nt h i st h e s i st h ed o m e s t i ca n df o r e i g nr e s e a r c ho nr o b u s tb e r t ha l l o c a t i o n p r o b l e mi sr e v i e w e d ，a n ds t a t e - o f - a r tf o rt h i sp r o b l e mi si n t r o d u c e di nd e t a i l s o m e s h o r t c o m i n g so ft h ee x i s t i n gw o r ka r ea n a l y z e d t ot h e s ep r o b l e m s ，t h ef o l l o w i n g r e s e a r c hw o r k sh a v eb e e nc o n d u c t e d t h er o b u s tb e r t ha l l o c a t i o np r o b l e mw i t hs t o c h a s t i cv e s s e ld e l a y si sc o n s i d e r e d f i r s t l y , t h er o b u s tb e r t ha l l o c a t i o np r o b l e mi sf o r m u l a t e da sas t o c h a s t i cm o d e l t o s o l v et h ep r o b l e m ，af e e d b a c kp r o c e d u r e ，w h i c hg r a s p st h ei n t e r r e l a t i o n s h i pb e t w e e n p l a n n i n gs t a g ea n dr e a l t i m es t a g e ，i si n t r o d u c e d t h ef e e d b a c kp r o c e d u r em a i n l y c o n s i s t so ft h r e ec o m p o n e n t s ：as i m u l a t e da n n e a l i n ga l g o r i t h mw h i c hf i g u r e so u tt h e d e t e r m i n i s t i cm o d e l ，r e a l - t i m er e a s s i g n m e n tr u l e sf o rs t o c h a s t i cd e l a y s ，a n da h e u r i s t i ct oa d j u s tt h et i m eb u f f e rf o re a c hv e s s e l i t e r a t i v er e e x e c u t i o n so ft h e s i m u l a t e da n n e a l i n ga l g o r i t h mg u a r a n t e et h eo p t i m i z a t i o n t h er o b u s t n e s so r i # n a t e s f r o mt h eb u f f e rs c h e m e m a r fb u f f e r sa r ei n s e r t e di nt h ed e c o d i n gp r o c e s st o e n h a n c et h er o b u s t n e s s t i m eb u f f e r sp l a ya ni m p o r t a n tr o l ei np r e v e n t i n gd e l a y p r o p a g a t i o nt h r o u g ht h ew h o l es c h e d u l e b ya d j u s t i n gt h et i m eb u f f e rf o re a c hv e s s e l i t e r a t i v e l y ，r o b u s t n e s so ft h es c h e d u l ei si m p r o v e ds t e pb ys t e p n u m e r i c a l e x p e r i m e n t sr e v e a lt h a tt h ep r o p o s e df e e d b a c kp r o c e d u r ei sc o m p e t e n tt oc o n s t r u c t i i i 垒旦! 堕垒垡一 一一一 h i 碰r o b u s tb e r t h s c h e d u l e su n d e ra l ld e l a yv a r i a b i l i t yp a t t e r n s m e 觚、h i l e ， 丘e q u e n c yd i s t r i b u t i o nd i a g r a m s o b t a i n e df r o mt h i sp r o c e d u r ec a l ls u p p o r t t 1 1 e t e r m i n a ld l a n n e r si nd e v e l o p i n g r o b u s th o m eb e r t hs c h e d u l e s m o r e o v e r , t h e f e e d b a c kp r o c e d u r ei so fl o wc p u t i m ec o s ta n dn oo v e r f i t t i n gp h e n o m e n o n a n o t h e rk i n do fu n c e r t a i n t y v e s s e l s o u to fw e e k l ys c h e d u l et e r n p o r a r i l y m o o r i n gi i l m e 包e r 而n a l i st a k e ni n t oa c c o u n t i no r d e rt od os u i t a b l e r e a s s i 罂皿m e r l t sf o rt h eg i v e np l a n ，t w os t e p sa r ec a r r i e do u t a sf o l l o w s f i r s t l y , t h e l o c a l s c h e d u l et i m eh o r i z o ni sd e t e r m i n e da c c o r d i n gt ot h r e ei m p o r t a n tc o e f f i c i e l l t s ： s t r a t e 西c a li i n p o t r a n c ec o e f f i c i e n t ，s h o r t t e r mp r o f i tc o e f f i c i e n ta n ds c h e d u l ep r e s s e f f i c i e n t s e c o n d l y ，t h ed e s i g n e dr e a s s i g n m e n tr u l e sa r ei m p l e m e n t e d t o w a r d st h e 2 i v e l lb e n l lp l a ni nt h el o c a l s c h e d u l et i m eh o r i z o n i ne x p e r i m e n t s ，i t l s1 n d i c a t e d t h a t 也er e a s s i 昏皿e n ts c h e m ed o e sl i t t l ea b o u tt h eg i v e np l a na n d m a k e si tp o s s i b l e f o rt 1 1 ep l a nt ob ec a r r i e d o ns m o o t h l yu n d e ra l ld e l a yv a d a b i l i 够p 蝴s f 砷e 衄o r e ，a n o t h e re x p e r i m e n ti sc o n d u c e dt oi l l u m i n a t et h ei n f l u e n c eo f v e s s e l n u n l b e ro u to fs c h e d u l eo nt h er o b u s tb e r t hp l a n f o rt h et i m eb e i n g ，a i le c o n o m i cc r i s i si ss p r e a d i n gt h r o u g ht h ew o r l da n dc o s t n 锄1i sp u t0 nt h ea g e n d af o ra l lc o m p a n i e s i ti sh o p e d t h a tr e s e a r c hw o r k s1 nt l l i s t h e s i sc 趾d 打e r s i 母t e r m i n a lc h o i c e so fp r o d u c t i o ns c h e d u l ea n d c o s tc o n 仃o li nt h e o p e r a t i o n a l l e v e l k e v w o r d s ：b e r t ha l l o c a t i o np r o b l e m ；r o b u s to p t i m i z a t i o n ；u n c e r t a i n t y ；f e e d b a c k ； r e a s s i g n m e n t w 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进 行研究工作所取得的成果。除文中已经注明引用的内容外，本学位 论文的研究成果不包含任何他人创作的、已公开发表或者没有公开 发表的作品的内容。对本论文所涉及的研究工作做出贡献的其他个 人和集体，均已在文中以明确方式标明。本学位论文原创性声明的 法律责任由本人承担。 学位论文作者签名：和嘭 2 0 0 9 年5 月2 8 日 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位 获得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文 ( 包括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论 文，并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将 公开的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检 索、文摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向 教育部指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和 中国学术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文 数据库，通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答 辩；提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 和嘭 2 0 0 9年5月2 8 日 南开大学研究生学位论文作者信息 论文题目 两种不确定情况下的鲁棒泊位分配问题研究 姓名杜玉泉学号 2 1 2 0 0 6 0 3 6 3 答辩日期2 0 0 9 年5 月2 4 日 论文类别博士口学历硕士团硕士专业学位口高校教师口同等学力硕士口 院系所信息技术科学学院自动化系 专业 系统工程 联系电话 0 2 2 2 3 5 0 7 7 8 0e m a i l d u y u q u a n 2 0 0 6 y a h o o t o m c i l 通信地址( 邮编) ：天津市卫津路9 4 号南开大学信息技术科学学院伯苓楼6 0 4 邮编：3 0 0 0 7 1 备注：是否批准为非公开论文 否 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文电子版授权使用协议 ( 请将此协议书装订于论文首页) 论文两巾嘱角龟促况下睹碑触桫i 蚴知系本人在 南开大学工作和学习期间创作完成的作品，并己通过论文答辩。 本人系本作品的唯一作者( 第一作者) ，即著作权人。现本人同意将本作品收 录于“南开大学博硕士学位论文全文数据库 。本人承诺：已提交的学位论文电子 版与印刷版论文的内容一致，如因不同而引起学术声誉上的损失由本人自负。 本人完全了解g 直五态堂图盘绾羞王堡左! 焦厦堂焦途塞的筻堡查洼滏! 同意 南开大学图书馆在下述范围内免费使用本人作品的电子版： 本作品呈交当年，在校园网上提供论文目录检索、文摘浏览以及论文全文部分 浏览服务( 论文前1 6 页) 。公开级学位论文全文电子版于提交1 年后，在校园网上允 许读者浏览并下载全文。 注：本协议书对于“非公开学位论文在保密期限过后同样适用。 院系所名称：隹詹攫懈和它钟亿小 作者签名：撕 学号：f 细口石o ；钐 日期：矽p c 7 年f 月万日 第一章绪论 1 1 1 研究背景 第一章绪论 第一节问题的提出 港口是国家和经济发展中的重要基础设施，它承载着一个国家对外贸易和 区域经济协调发展的重要使命，能够直接拉动城市和腹地区域经济快速增长。 在现代物流体系中，港口是远洋、内河航运以及内陆运输( 公路、铁路、管道) 的重要枢纽，尤其在石油、铁矿石、煤炭等大宗物资和国际工业品运输链上具 有举足轻重的地位。现代集装箱运输具有运输速度快、装卸方便、机械化程度 高、作业效率高、便于水陆联运等优点，自2 0 世纪5 0 年代出现以来即得到蓬 勃发展。随着世界经济一体化的加深以及跨国公司的快速成长，集装箱运输业 务必将在世界经济发展中扮演着日益重要的角色集装箱正使世界变小。 进入新世纪，我国对外开放政策坚定不移地推进，在区域经济乃至世界经 济发展中逐渐体现出“龙头 拉动作用。与之伴随，我国的港口集装箱运输强 劲发展。2 0 0 2 年，我国大陆港口集装箱吞吐量实现3 7 2 1 万标准箱( t e u ) ，位 居世界第一。2 0 0 6 年实现9 3 6 1 万t e u ，2 0 0 7 年跨越1 亿t e u ，仍高居世界第 一，平均每年增长超过11 0 0 万t e u ，举得了举世瞩目的成绩。 天津港位于渤海湾的西端，是首都北京的海上门户，是华北和西北地区省 市通往国际最近的综合性枢纽港。其独特的地理位置和发达的铁路、公路、海 运和航空等运输基础设施，使其成为北京、天津、河北、山西、陕西、内蒙、 河南、甘肃、青海和宁夏等省市出口货物的首选港口，是欧亚大陆桥的起点之 一和蒙古国的出海口，经济腹地十分广阔。“十五 期间，天津港吞吐量年均增 幅超过2 0 ，高出全国平均水平8 个百分点，跻身世界港口十强；相继完成了 1 0 万吨和1 5 万吨级航道改造，跨入世界深水港之列；2 0 0 8 年，天津港货物吞 吐量达到3 5 4 亿吨，集装箱吞吐量突破8 5 0 万t e u ，增长1 9 7 。 与港口发展伴随的是日益增长的压力。一方面，港口间对腹地货源和客户 的争夺日益激烈；另一方面，船舶的大型化、快速化对港口的基础设施和服务 第一章绪论 水平提出了新的挑战。如何利用码头有效的资源提升自己的服务水平一直是业 界和研究界关注的焦点。集装箱码头是一个复杂的系统，在作业调度中面临着 种种不确定性，如，船舶到达时间的不确定性，岸桥、场桥装卸效率的变动性， 各种机械设备的故障等，而且源自一个子系统的不确定性可能会传播到其它子 系统，这增加了提升作业效率和管理水平的难度。雪上加霜的是，蔓延至全球 的经济危机已经使世界各主要港口把“降低成本提上日程。在集装箱码头中， 泊位是一种“瓶颈 资源，面对各种系统内和系统外的不确定性，如何有效地 为抵港的船舶分配泊位，对降低成本和提升服务水平有着至关重要的意义。 1 1 2 研究问题的描述 泊位分配问题指的是，在一条连续的岸线上，为每一条到港的船舶分配一 个合适的停靠位置和停靠时间，以便进一步为其提供装卸服务。泊位是港口的 稀缺资源，因而高效、合理的泊位分配关系着港口服务水平的提高和经营成本 的控制。制约泊位分配的因素主要利l j ： 1 船舶相关信息。如，船期计划、船长、吨位、装卸箱量等。 2 岸边资源情况。如，岸桥分配计划和装卸效率、集卡调度等。 3 其它物理条件。如，岸线和泊位长度、水深等。 泊位分配的目标一般可以归结为以下几个及其混合形式： 1 最小化计划期内所有船舶的等待时间。 2 最小化计划期内所有船舶的延误时间或成本。一条船舶通常都有一 个要求离港的最晚离开时间，当由于码头作业调度的原因致使该船 舶不能在“要求的最晚离港时间 之前离港，就会对码头索取一定 的费用。 3 最小化停靠泊位与货物堆存位置之间的距离。在堆场上，一条船舶 待装卸的货物堆放在一个已知的堆存空间中，把船舶停靠在离这个 堆存位置较近的泊位上，有利于减少从岸线到堆场的运输距离和费 用。 4 最大化泊位和岸桥的利用率。 在泊位分配问题中，常常要面对各种不确定性因素，这些不确定因素往往 会给现存的泊位计划带来诸多扰动，有时甚至使泊位计划变得作用甚微。由于 2 第一章绪论 天气、浪高等原因，船舶抵港常常发生迟到( 在计划靠泊时刻尚未抵港) ，一条 迟到的船舶，不仅要求重新为其分配泊位，而且可能造成其它船舶停靠作业的 推后，发生严重的延误传播；岸桥、集卡等岸边作业设备的工作效率常常产生 波动，这将导致轮船的装卸作业时间发生变动，极端的情况是，若干岸桥发生 了故障而中止工作；当一条计划外的船舶临时抵港，申请靠泊时，码头经常不 得不改变原有的泊位计划，为其分配一个合适的泊位和作业时间区间。本文只 考虑船舶抵港时间具有随机延误和有计划外船舶临时靠泊两种不确定性。本文 试图建立鲁棒的泊位分配方案，能够吸收各种不确定性对泊位计划带来的扰动， 同时给出不确定情况发生时的实时调整策略。 第二节研究的现实意义和理论意义 集装箱运输在世界经济和区域经济发展中扮演着越来越重要的角色，集装 箱是经济全球化的助推器，集装箱正在使世界变小、变平，也成就了中国以制 造业出口为主导的经济体的腾飞，集装箱运输业的效率将决定世界经济的效率 2 】。集装箱码头间的竞争也随之激烈，提高服务水平和降低成本成为竞争的焦 点。集装箱码头是资本密集型的经济实体，提高资源的使用效率对提高服务水 平和降低成本至关重要。在诸多资源中，泊位资源又扼集装箱码头之咽喉，因 为一个港口的岸线长度在一个较长的时期内是不会变化的，岸线的建设是受地 区乃至国家经济发展政策的驱动。因此，合理分配泊位，提高泊位资源的使用 效率，对降低成本、提高服务水平起着重要作用。 从本章1 1 2 部分的分析可以看出，由于天气和机械故障等原因，泊位分配 问题中充斥着种种不确定性。本文正是抓住主要的几种不确定性，分析其对泊 位分配计划的影响，试图建立一个鲁棒的泊位分配方案；此外，本文也专注于 不确定情况发生时的实时调整策略研究。面向不确定的作业环境，如何构造鲁 棒的泊位分配计划和高效经济的实时泊位调整策略，对提高集装箱码头的竞争 力和降低成本有着特殊的意义。在当前经济危机的背景下，各集装箱码头对控 制成本有着非同一般的需求，本文的工作完全从集装箱码头企业降低成本的角 度出发，因而具有重要的现实意义。当前，世界上主要的集装箱码头在泊位分 配时，大都采用半手工化的决策支持系统，本文的研究工作对丰富其模型库有 重要价值。 第一章绪论 同时，鲁棒的泊位分配研究属于鲁棒优化和鲁棒调度的范畴，而且是其中 比较艰深的问题。鲁棒泊位分配方案的研究进展，能够从实际应用上丰富和深 化鲁棒优化和鲁棒调度理论。此外，不确定情况发生时，泊位分配调整策略的 研究，也能丰富干扰管理( d i s r u p t i o nm a n a g e m e n t ) 理论的内容。 第三节国内外对此问题的研究进展及评述 本文先从泊位分配问题、鲁棒优化和鲁棒调度问题、干扰管理问题、不确 定环境下的鲁棒泊位分配问题四方面介绍国内外的研究进展，然后对其进行评 述。 1 3 1 泊位分配问题的研究进展 泊位分配问题( b e r t h a l l o c a t i o np r o b l e m ，b a p ) 大致上可以归为两类：离散 的泊位分配问题( b a p d ) 和连续的泊位分配问题( b a p c ) 。离散的泊位分配问 题中，岸线由若干独立的泊位组成，泊位分配问题可以看作并行机的调度问题。 连续的泊位分配问题把码头岸线看作一条连续的直线，理论上，只要不越过岸 线的边缘，一条抵港的船舶可以停靠在岸线的任何一个位置：b a p c 一般可以 看作在岸线一时间平面( w h a r f - t i m ep l a n e ) 上的矩形( 代表船舶) 排列问题。 b a p 从另外一个角度可以分为静态的( s t a t i c ) b a p 和动态的( d y n a m i c ) b a p 。 静态b a p 假定，在泊位分配计划制定前，所有的船舶均抵港【3 1 ；而动态b a p 则更符合实际，认为在泊位计划执行过程中，船舶动态地依次抵港。b a p 的研 究工作多集中在动态b a p 问题上。 就离散的泊位分配问题而言，l a i 和s h i h 基于先到先服务( f c f s ) 的规则 提出了一个高效的启发式算法【4 】；b r o w n 等以海军军港为背景，试图最大化船 舶在港的总利益【5 】，但军港中频繁进行的移泊操作往往不同于商业性的港口； i m a i 等人基于所有泊位水深相同的假设，以泊位性能为目标，采用l a g r a n g i a n 松弛的方法，提出了一种次梯度求解算法【6 】；针对大型的集装箱船舶和可在船 舶两边同时装卸的高效泊位，i m a i 等提出的b a p 中允许多条船舶同时停靠在 一个泊位上，这在现代化大型码头中具有广阔的应用前景【_ 7 1 。就连续的泊位分 配问题而言，研究者也取得了丰硕的成果。文献 8 基于船舶抵港即可停靠的假 4 第一章绪论 设，仅对停靠位置进行决策，对b a p c 提出了一种启发式算法。文献 9 】视b a p c 为最小化m a k e s p a n 的j o bs h o p 调度问题，提出了一种启发式算法并对其做了 最坏情况分析。文献 1 0 】一 1 2 】均假设存在一个给定的泊位计划模板，把最小化 靠泊位置与计划模板的偏离作为决策目标之一。i m a i 等人在他们的问题中证明， 一个b a p c 问题的近似最优解，和泊位长度等于其中最大船长的b a p d 问题的 最优解是一样的，基于此，他们先解b a p d ，然后对解进行调整，得到b a p c 的近似最优解【l3 1 。上述的b a p 问题都是确定性的问题，而m o o r t h y 和t e o 基于 序列对( s e q u e n c ep a i r ) 编码的方法，采用项目评审技术( p r o j e c te v a l u a t i o na n d r e v i e wt e c h n i q u e ) 对随机的b a p c 问题进行了求解【l 训。 考虑到岸边资源对泊位分配问题的限制，研究者在泊位一岸桥的联合调度 上取得了一些进展，主要的思路是把问题分解为岸桥调度和泊位调度两个子问 题 1 2 , 1 5 - 1 9 】。但这方面的成果并不多见。 1 3 2 鲁棒调度问题研究简述 鲁棒调度是研究不确定环境下生产调度的一个重要分支，其基本思想是在 制定计划时，以一种较为保守的态度对可能的变化进行预测，进而采取一定的 预防措施，使调度方案具有一定的抗干扰能力( 即鲁棒性) 。不确定环境下的调 度问题已不再是一个单纯的优化问题，在很多情况下保证调度方案的鲁棒性比 单纯追求最优性更为重要。目前对鲁棒调度的研究主要围绕调度的可行性和最 优性展开，h o n k o m 认为不确定环境下生产调度的目标在于生产的可行、鲁棒 及尽可能的最优。其中“可行 是前提条件，“最优 是要追求的目标，但由于 不确定因素的存在，二者往往不可兼得。鲁棒成为一种折衷，也是一种必然的 选择，鲁棒调度则是实现这一目标的手段【2 0 1 。 由于不确定性在建模和求解上的困难，在生产调度中，我们追求的不再是 单纯的方案选择，而是着眼于整体的一套鲁棒策略的制定。总的来看，不确定 环境下的生产调度大致上分为两类：完全反应式调度和预测反应式调度。完全 反应式调度在预调度阶段并不制定任何调度方案，所有的努力都集中于实时调 度阶段( 执行阶段) ；预测反应式调度则在预调度阶段( 计划阶段) 制定出一个 预调度方案，作为调度工作参考的基准，在执行阶段，当不确定情况发生时， 采用各种重调度( 反应式调度) 方法修复调度方案，具体地，可能是完全重调 5 第一章绪论 度、局部重调度，也可能是简单修复。在预测反应式调度的预调度阶段，如果 决策者追求的是一个最优方案，可把其称为确定的预测反应式调度；反之，如 果追求的是一个鲁棒的方案，称其为鲁棒的预测反应式调度。后者成为研究者 最为关注的热点。 从上世纪9 0 年代开始，研究鲁棒调度的文献开始多起来【2 4 1 。具体地， v e l a g a p u d i ( 19 9 2 ) 2 1 】，l e o ne ta l ( 19 9 4 ) 2 2 】，d a n i e l sa n dk o u v e l i s ( 19 9 5 ) 2 3 】，k o u v e l i s a n dgy u ( 19 9 7 ) 【2 4 1 ，d a n i e l se ta 1 ( 19 9 7 ) 2 5 】，h o n k o m p ( 19 9 7 ) 2 0 】，j a m e sa n d b u c h a n a n ( 1 9 9 8 ) 2 6 1 ，sd w ue ta 1 ( 1 9 9 9 ) 2 7 l ，t 然, , ( 2 0 0 6 ) 2 s l ，。就应用领域而言，研 究多集中在机器调度( m a c h i n es c h e d u l i n g ) 和项目调度( p r o j e c ts c h e d u l i n g ) 两个 方面。值得关注的是，近5 年来，由o l a m b r e c h t s ，e d e m e u l e m e e s t e r , w h e r r o e l e n ，r l e u s 等人组成的研究团队在鲁棒项目调度方面取得了可喜的进展 2 9 - 3 3 】，另外，a 1 一f a w z a na n dh a o u a r i ( 2 0 0 5 ) t ：幌代表性的成剁3 4 1 。 1 3 3 干扰管理问题研究简述 当干扰事件发生后，如何以最小的扰动使系统恢复正常运行，是干扰管理 ( d i s r u p t i o nm a n a g e m e n t ) 研究的主要任务。这里值得注意的是：g a n gy u 是 d i s r u p t i o nm a n a g e m e n t 的集大成者，他在用中文表达时，习惯于把d i s r u p t i o n m a n a g e m e n t 称为“应急管理”，本文为了避免和国内e m e r g e n c ym a n a g e m e n t 的中文翻译混淆，把d i s r u p t i o nm a n a g e m e n t 译为“干扰管理。按照g a n gy u 的观点，干扰管理分为四类：预案管理、鲁棒优化、随机模型、实时应急管理 【3 5 】( 下文用“实时干扰管理一词代替) 。鲁棒调度以鲁棒的预测调度和高效的 反应式调度为特点，也属于干扰管理的范畴。值得注意的是，在实时干扰管理 中，虽然也考虑预定方案中的目标，但更强调对预定方案的扰动要小，尽可能 平滑地执行预定方案。 干扰管理在多个应用领域取得了成功，尤以航空领域为代表。在航空邻域， 2 0 世纪9 0 年代以来即取得了丰富的理论成果和实践成果，以t e o d o r o v i c ( 1 9 8 4 ) 【3 6 1 ，删a n dy u ( 1 9 9 7 ) 【3 7 1 ，y ue ta 1 ( 2 0 0 3 ) 3 8 1 ，l e t t o v s k y ( 1 9 9 7 ) 3 9 1 ，l a r s e ne ta 1 ( 2 0 0 2 ) 【4 0 j ，s m i t he ta 1 ( 2 0 0 4 ) 4 1 1 ，马辉和林晨( 2 0 0 5 ) 4 2 】为代表，同时，g a n gy u 为美国大 陆航空公司开发的c r e w s o l v e r 系统【3 5 j 把干扰管理成功地推向产业界。在物流 配送领域，g i a g l i sa n dm i n i s ( 2 0 0 4 ) m 3 1 ，h u i s m a ne ta 1 ( 2 0 0 4 ) 4 4 j ，z e i m p e k i se t 6 第一章绪论 a 1 ( 2 0 0 5 ) t 4 5 1 ，p o t v i nc ta 1 ( 2 0 0 6 ) t 4 6 ，l ie ta 1 ( 2 0 0 7 ) 1 4 7 1 是代表性的研究成果，国内的 研究也有一些进展 4 8 - 5 0 】。在供应链研究领域，比较重要的研究成果有h a n e v e l de t a 1 ( 1 9 9 8 ) 5 1 】，c o r b e t t ( 2 0 0 1 ) 5 2 】，c a c h o n ( 2 0 0 1 ) 5 3 】，q ie ta 1 ( 2 0 0 4 ) 【州，l e w i se t a 1 ( 2 0 0 5 ) 【5 5 】，以及国内的于辉等( 2 0 0 5 ) 1 5 6 , 5 7 ，宁钟和戴俊俊( 2 0 0 5 ) 5 引，张存禄等 ( 2 0 0 5 ) t 5 9 1 。在机器调度和项目调度领域，除了本文1 3 2 中提到的文献外，b e a n e ta 1 ( 1 9 9 1 ) 【6 0 】，a b u m a i z a ra n ds v e s t k a ( 1 9 9 7 ) 6 q ，h u re ta 1 ( 2 0 0 4 ) 6 2 】，z h ue ta 1 ( 2 0 0 5 ) 【6 3 】，l e ee ta 1 ( 2 0 0 6 ) 6 4 1 ，q ie ta 1 ( 2 0 0 6 ) 6 5 】也是代表之作。干扰管理在其它领域的应 用不一而举。 1 3 4 不确定环境下的鲁棒泊位分配问题研究进展 如前所述，集装箱码头生产作业中面临着天气、机器故障、管理水平带来 的诸多不确定性，跟泊位分配问题相关的主要有：船舶常常不能按照预报的时 间抵港，呈现出随机性的延迟；在计划执行中，偶尔会碰到计划外的船舶i 晦时 要求靠泊：船舶装卸箱量的不确定性；岸桥工作效率有一定的波动性，甚至会 出现故障。m o o r t h ya n dt e o ( 2 0 0 6 ) u 4 j 对鲁棒泊位分配问题进行了研究，根据建 立的时间约束图( t i m e c o n s t r a i n e dg r a p h ) 模型，他们采用p e r t 技术，对船舶 在锚地上的等待时间进行了估计，实验表明，依靠这种方法得到的预调度方案 具有很强的鲁棒性。针对岸桥工作效率的波动性，周鹏飞【1 和于蒙【1 7 】对岸桥泊 位联合分配问题进行了研究，研究的方法大致上分为岸桥分配和泊位分配两个 阶段，但对于岸桥分配子问题采用的估计策略过于简单。 1 3 5 国内外研究进展评述 从前面的描述可以看出，鲁棒调度和干扰管理理论成果丰富，工具和技术 繁多，但在集装箱码头的泊位分配问题上，如何应对纷繁复杂的不确定性，并 没有取得太多成果。具体表现在一下几个方面： 1 面向船舶到达时间不确定性的鲁棒泊位分配问题的文献很少。 2 据本文作者所知，对于计划外船舶临时申请靠泊的情形，尚没有 文献研究如何制定干扰调整策略。 3 现有的b a p 文献大都基于一种假设：已经存在一个原始预调度 方案( h o m eb e r t hp l a n ) ，船舶待装卸的集装箱在堆场中的位置 7 第一章绪论 已知，因而待靠泊的船舶有自己的偏好泊位( 离目标堆场最近) 。 但这个原始预调度方案是如何制定的? 研究的文献很少，而这一 问题也是码头计划人员最为关注的话题之一。 出现这种情况的原因大致如下。第一、确定的b a p c 问题本身就是n p h a r d 问题，难度较大。第二、不确定性问题本身的建模和计算困难。不确定性信息 的度量、对预定方案的影响、不确定情况下的决策等问题本身十分复杂，不仅 与可用的决策资源、问题规模有关，还与决策者对待不确定性的态度、决策的 实时性要求等紧密相关。 第四节研究的目的、框架和内容安排 1 4 1 研究的目的 从本文1 3 5 部分可以看出，在b a p c 问题上，针对船舶到达时间不确定( 有 随机延迟) 和有计划外船舶临时靠泊两种不确定性，研究的文献很鲜见。本文 正是针对这两种不确定性，研究在连续的岸线上如何为到港的船舶分配泊位， 制定出的原始预调度方案能够尽可能地吸收未来可能发生的不确定性；同时， 在不确定情况实际发生时，有一套干扰管理策略能够高效地对预定计划作出局 部调整，从而保证预定计划的平滑执行。本着“鲁棒的预调度方案+ 高效的实时 调整策略 的基本思想，本文的研究目的具体叙述如下： 1 在船舶到达时间具有随机延误的情况下，如何制定原始的鲁棒泊位分配方案 本文试图抛弃“已经存在一个原始的预调度方案 的假设，弄清影响b a p 方案鲁棒性的关键性因素，抓住“预调度 和“实时调度两个阶段之间的联 系，努力构建一个原始的鲁棒泊位分配方案。结果方案不仅仅是一个泊位计划， 还可以作为岸桥调度、堆场资源分配等的参考。 2 在计划外船舶临时靠泊的情况下，如何制定一套实时调整策略 由于“计划外船舶临时插入”不会频繁发生，在制定预调度方案时，没必 要考虑此种不确定性( 否则，鲁棒的方案将会更加保守，资源浪费将更加严重) 。 也即，此种不确定性主要依赖于实时的干扰调整策略来处理。如何设计一个实 时调整策略，能够对预定计划产生尽可能小的扰动，是本文的另外一个研究目 8 第一章绪论 的。 1 4 2 研究的框架和内容安排 本文在介绍了集装箱码头基本业务知识后，对不确定环境下的相关理论问题 鲁棒调度和干扰管理理论进行了总结；之后在论文的核心部分，先对“船 舶抵港时间随机延误下的鲁棒泊位分配问题进行了研究，进而把“计划外船 舶临时靠泊 这种不确定性考虑进去，精心设计了实时干扰调整策略；最后， 对论文作了总结，并对未来研究进行展望。 图1 1 论文的研究框架 论文的具体内容安排如下： 第二章，集装箱码头基本知识。首先对集装箱码