（计算机应用技术专业论文）集装箱港口堆场资源调度的优化.pdf

摘要 随着经济全球化趋势的发展和我国社会主义市场经济的逐步完善，我国的对外贸易 迅速发展，集装箱吞吐量也在逐年增加，对集装箱码头的管理提出了更高的要求。在集 装箱码头中，码头堆场是对集装箱的中转、管理、存放及修复地，其整体运行效率的高 低会直接影响港口的竞争力，所以对堆场资源的调度优化十分重要。在堆场中，龙门吊 和集卡是非常重要的资源，它们的有效利用能极大地提高集装箱码头的运作效率。 本文综合运用了运筹学、优化理论与方法和计算机仿真等学科理论和方法，对堆场 龙门吊优化调度和集卡路径优化问题进行了研究与分析。具体做了以下两方面的工作： 1 研究了龙门吊资源不足情况下堆场有多个任务的龙门吊优化调度问题，应用蚁 群算法对问题进行了求解。在应用蚁群算法求解问题的过程中，针对集装箱堆场有多个 龙门吊的特点，设计了蚂蚁确定“行走路径的策略。仿真数据表明，在可接受的时间 内，采用蚁群算法所得的结果较遗传算法更好。 2 研究了基于“作业面 运作方式的集卡行走路径优化问题，应用免疫禁忌搜索 算法对问题进行了求解，该算法结合了免疫算法和禁忌搜索的优点，不易陷入局部最优 解，同时避免了禁忌搜索取得的结果受初始解影响较大的缺点。通过数据实例分析了 “作业面 调度模式与“作业线”调度模式对集卡行走路径的影响，结果表明“作业面 运作方式有效降低了集卡的行走距离，节约了作业时间，大大提高了集卡的利用效率。 关键词：龙门吊调度集卡优化调度作业面蚁群算法禁忌搜索免疫算法 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ee c o n o m i cg l o b a l i z a t i o na n dg r a d u a li m p r o v e m e n to f s o c i a l i s mm a r k e te c o n o m yo fo u rc o u n t r y , f l o r e i 朗t r a d ed e v e l o p sv e r yf a s t , a n dt h et h r u p u t i n c r e a s e se v e r yy e 瓯w h i c hp u t sf o r w a r dh i g h e rr e q u i r e m e n tt ot h ec o n t a i n e rt e r m i n a l m a n a g e m e n t t h et e r m i n a ly a r di sar e g i o nf o rt r a n s f e r r i n g , m a n a g i n g , p l a c i n ga n dr e p a i r i n g c o n t a i n e r si nc o n t a i n e rt e r m i n a l ，a n di t se f f i c i e n c yw o u l da f f e c tt h ec o m p e t i t i v e n e s so f c o n t a i n e rt e r m i n a ld i r e c t l y , s oi ti si m p o r t a n tt oo p t i m i z et h er e s o u r o s c h e d u l eo ft h e c o n t a i n e rt e r m i n a l i nt h et e r m i n a ly a r d ，g a n t r yc r a n e sa n dc o n t a i n e rt r u c k s 砌ev e r yi m p o r t a n t r e s o u r c e ，a n dt h ee f f e c t i v eu s eo ft h e mc a ne l e v a t et h eo p e r a t i o n a le f f i c i e n c yo fc o n t a i n e r t e r m i n a lt r e m e n d o u s l y t h i st h e s i su s e s o p e r a t i o nr e s e a r c h , o p t i m i z i n gt h e o r ya n dc o m p u t e rs i m u l a t i o n t o a n a l y z ea n dr e s e a r c ho nt h es c h e d u l eo p t i m i z a t i o no fg a n t r yc r a n e sa n dp a t ho p t i m i z a t i o no f c o n t a i n e rt r u c k s w o r ki nt w oa r e a so fm i st h e s i si ss h o w na sf o l l o w s ： 1 r e s e a r c ho nt h es c h e d u l eo p t i m i z a t i o no fg a n t r yc r a n e sw h e nt h e r ea r es e v e r a lt a s k s a n dt h eg a n t r yc r a n e sa r ei n s u f f i c i e n t a n tc o l o n ya l g o r i t h mi su s e dt os o l v et h i sp r o b l e m i n t h ep r o c e d u r eo fs o l v i n gt h ep r o b l e mu s i n ga n tc o l o n ya l g o r i t h m ，w ed e s i g na n “a n tw a l k i n g p a t h ”s t r a t e g yf o rt h ep r o b l e mw h e r et h e r ea r es e v e r a lg a n t r yc r a n e si nt h ec o n t a i n e ry a r d t h e s i m u l a t i o nd a t ai n d i c a t e st h a tw i t h i na l la c c e p t a b l ep e r i o do ft i m et h er e s u l tg o t t e nb ya n t c o l o n ya l g o r i t h mi sb e t t e rt h a ng e n e t i ca l g o r i t h ma n dt a b us e a r c h 2 r e s e a r c ho nt h ep a t ho p t i m i z a t i o no fc o n t a i n e rt r u c k sb a s e do np o o ls t r a t e g y w eu s e i m t sm e t h o dt os o l v et h i sp r o b l e mw h i c hc o m b i n e st h ea d v a n t a g e so fb o t hi m m u n e a l g o r i t h ma n dt a b us e a r c h i ti sn o te a s yf o ri m t st os i n ki n t ot h el o c a lb e s ts o l u t i o n ，a n di n t h em e a n w h i l e ，i ta v o i d st h ed i s a d v a n t a g eo ft a b us e a r c ht h a ti n i t i a ls o l u t i o nh a sag r e a t i m p a c to nt h er e s u l t w i t hd a t ae x a m p l e s ，w ea n a l y z et h ea f f e c t i o no fo p e r a t i o nq u e u ea n d p o o ls t r a t e g yt ot h er o u t eo fc o n t a i n e rt r u c k s t h er e s u l ti n d i c a t e st h a tp o o ls t r a t e g yd e c r e a s e s t h ec o n t a i n e rt r u c k s l e n g t ho fr o u t e ，s a v e st h et i m eo ft r a n s p o r t a t i o na n di m p r o v e st h e e f f i c i e n c yo ft h ec o n t a i n e rt r u c k s k e yw o r d s ：s c h e d u l eo fg a n t r yc r a n e s ，s c h e d u l eo fc o n t a i n e rt r u c k s ，p o o ls t r a t e g y , a n t c o l o n ya l g o r i t h m ，i m m u n ea l g o r i t h m ，t a b us e a r c h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得天盗理工大学或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均己在论文中作了明确的说明并表示了谢意。 摊舨惜鹳：貔锵日期： 7 月7 目 学位论文版权使用授权书 本学位论文作者完全了解 墨盗墨墨盘堂有关保留、使用学位论文 的规定。特授权墨盗堡墨盘堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 豺日期渺产月7 日 导师鹈扔後咱 街日期沙产月7 日 第一章绪论 1 1 研究背景 第一章绪论 1 1 1 我国集装箱港口的快速发展及问题 随着世界经济格局的变化，全球制造业逐步向我国转移。我国集装箱港口由此得到 了飞速的发展。到2 0 0 7 年，我国完成1 0 0 万t e u 的港口共有1 6 个，都进入了世界前 1 0 0 强的排名。我国的集装箱吞吐量已经超越美国位居世界首位，成为世界海运的一个 重要枢纽。集装箱港口作为国民经济和社会发展的重要基础设施，有力地支撑了经济、 社会和贸易的发展以及人民生活水平的提高。 虽然我国的港口建设己取得了很大的成绩，但是目前我国港口普遍还面临着效率低 下、服务不专业的问题，港口的服务水平与国外的先进水平相比还有很大的差距。究其 原因，一方面由于缺乏资金、技术，先进的操作设备和技术没有普及，限制了整个港口 吞吐量的提高，即便是全负荷工作也无法满足需求。另一方面是在港口的管理系统中， 很多地方还采用经验管理。这样的管理方法落后、运作效率低下，这些都成为制约港口 操作效率提高的瓶颈。 1 1 2 港口堆场的概况和特征 出于海陆运输工具之间在衔接上的需要，以及集装箱码头在管理上的需要等多种原 因，绝大部分集装箱在装船前或卸船后，均需要在码头堆存一段时间，而码头堆场就是 集装箱的中转、管理、存放及修复地。所以在某种程度上讲，堆场的整体业务水平的高 低会影响港口乃至整个物流行业的发展。 具体来说，集装箱码头堆场是供装卸船舶堆放集装箱的场所，同时也是临时保管和 向货主交接集装箱的地方。在堆场上对集装箱进行分区分类堆放，并按照集装箱的规格 尺寸，在堆场上划出“箱位”线，标明号码。尽管业务模式的差异使得各类堆场场站的 服务功能不尽相同，但所有业务功能都是在堆场核心服务功能之上发展而来，因此他们 的关键业务基本一致，堆场的主要业务工作是办理集装箱的装卸、转运、装箱、拆箱、 收发、交接保管、堆存、捆扎、掏载、搬运、以及承揽货源等，此外，还受理集装箱的 修理、冲洗、熏蒸和有关衡量等工作【1 2 1 。图1 1 显示了关于堆场的情景。 第一章绪论 图l - i 堆场示意图 港口集装箱堆场通常分为三个部分：集装箱前方堆场、集装箱后方堆场、空箱堆场。 集装箱前方堆场是指在靠近集装箱码头前沿处，为加速船舶装卸作业，暂时堆放集装箱 船舶直接装卸的集装箱的场地。其作业内容是：当集装箱船到港前，有计划有次序地按 装载要求将出口集装箱整齐地集中堆放，卸船时将进口集装箱暂时堆放在码头前方，以 加速船舶装卸作业。 集装箱后方堆场是集装箱重箱或空箱进行交接、保管和堆存的场所。集装箱后方堆 场是集装箱装卸区的组成部分。 集装箱空箱堆场是专门办理空箱收集、保管、堆存或交接的场地。它是专为集装箱 装卸区或转运站堆场不足时才予设立。这种堆场不办理重箱或货物交接。它可以单独经 营，也可以由集装箱装卸区在区外另设。 有些国家对集装箱堆场并不分前方堆场或后方堆场，而统称为堆场。一般地，堆场 由多个箱区( b l o c k ) 组成，每个箱区由连续的贝位( b a y ) 组成( 一般为4 0 6 0 个贝位) ，每个 贝位通常包括6 - 8 行( 舢h 堆场的堆高为层数( n 劬。堆场上的箱区、贝位、行、层都通 过一定的编码表示，其中箱区通常由字母和自然数( 如：a o ! ，a 0 2 ，b o i ，b 0 2 ) 共同表示， 贝位、行、层通常由自然数( 1 ，2 ，3 ) 表示。在堆场中，通常2 0 尺的集装箱占用1 个贝位， 其所在贝号为奇数，4 0 尺的集装箱占用2 个贝位，其所在贝号为偶数。大多数的堆场都 不允许集装箱混和放置，即把2 0 尺的箱和4 0 尺的箱放在同一贝位上。堆场中每个箱位 都可以通过其所在的箱区、贝位、行、层的编码来唯一确定。如给定一个堆场编码 ( a 4 1 0 0 1 0 3 0 2 ) 表示该箱位的位置是a 0 1 箱区0 0 1 贝0 3 行0 2 层，并且可以判断出这是 2 0 尺的箱；堆场编码( b 0 3 0 0 6 0 5 0 4 ) 表示该箱位的位置是b 0 3 箱区0 0 6 贝0 5 行0 4 层，而 且是4 0 尺的箱。大多数集装箱堆场按功能划分为不同的区域，例如空箱堆存区、拆装 第一章绪论 箱区、制冷区、残箱区、修箱区、重箱堆存区、暂存区等，每个堆场区域有相邻的横向 的箱区组成。这样便于龙门吊移动和减少龙门吊占用集卡的时间h 】。 集装箱码头堆场装卸机械主要用于集装箱装卸和堆高作业。按照码头堆场作业的种 类，其装卸机械可分为重箱作业机械、空箱堆场作业机械两种类型。 ( 1 ) 重箱堆场作业机械 当前国际上普遍采用轮胎式集装箱龙门起重机、轨道式集装箱龙门起重机和集装箱 跨运车。而集装箱叉车和集装箱正面吊运车多用于配合以上主要作业机械，进行倒箱、 拆装箱或装卸车的辅助作业。而轮胎式集装箱龙门起重机具有装卸效率高、操作简单、 作业面大、故障率低、堆场面积利用率高的特点，特别适合于大中型专业化集装箱堆场 及装卸车作业。但是轮胎式集装箱龙门起重机的轮压大导致场地建设费用高，堆层高引 起倒箱量增大，且此设备大多采用柴油发动机驱动，维护及维修能力要求较高。 ( 2 ) 空箱堆场作业机械 一般采用空箱集装箱叉车和空箱正面吊运机。国内港口普遍采用空箱集装箱叉车。 其集装箱堆码高度通常为3 层至6 层，最大可达7 至9 层。但是随着专业化水平的不断 提高，近几年来国内港口对空箱正面吊运机的应用量也明显增大。它对集装箱空箱堆高 能力更强，一般可以堆至7 至8 层，最高至1 0 层，且可跨箱作业，增加堆场利用率， 灵活方便【4 1 。 1 1 3 堆场作业流程 在集装箱进出口货运业务中，码头堆场的主要作业流程如下： ( 1 ) 进场箱作业：首先调度室根据船舶近期计划安排船舶靠泊，并依照卸船堆场计划 等安排卸船机械，组织卸船。卸船结束后，集卡运载进口集装箱进入堆场，当进场的集 装箱通过大门时，由地秤自动测定其重量，根据该重量和运输的目的地，靠计算机确定 后方堆场内该集装箱应该放置的箱位位置，然后由大门交给卡车司机一张带有箱位号码 的门票，卡车司机必须按指示的计划把集装箱放在指定的箱位上。最后，集卡出场。 ( 2 ) 出场箱作业：箱管根据船期及公司的出口预配船图，对在一定期限内预计进港的 船舶登记并进行出口场地预安排。当承运人从堆场提取集装箱时，首先空卡车到达大门， 提交提货单给大门，计算机确定提货单内指定的集装箱的箱位位置，计算最优提箱计划， 然后由大门交给卡车司机一张带有箱位号码的门票，卡车司机必须按指示的计划到指定 的箱位位置提取集装箱。最后集卡运输集装箱出场，运至泊位，由集装箱装卸桥进行装 船4 1 。堆场作业如图1 1 所示。 第一章绪论 集卡在装卸桥下 进行作业 i 一j：尚毛i 一 f 9 5 l 进行作业 一一一一一一一一一一一一一一，一+ 一+ 一一+ 。一一一一。一一一一一一一一一一一一一一一一一一一- i 图l - 2 堆场作业示意图 1 2 研究目的和意义 在港口集装箱物流作业过程中，堆场是码头作业中最复杂的部分，堆场的资源调配 在很大程度上决定了码头的效率，因此，对集装箱码头堆场资源调度进行优化，选择合 适的运行模式是非常必要的。 本课题的研究目的是利用运筹学、智能优化技术和计算机仿真，对集装箱港口物流 进行建模和优化设计，提出针对堆场龙门吊调度问题和堆场集卡路径优化问题的数学模 型，并用智能优化算法进行仿真求解。 在码头堆场中，集装箱装卸操作大都是由堆场龙门吊完成的，所以龙门吊在港口集 吊 1 j j_1 捌 伞团圈目圈妙 桥 一 卸 装 一位俞冒硝 第一章绪论 装箱操作流程中起到至关重要的作用。目前在我国，由于龙门吊没有得到科学合理的使 用，服务能力较低，因此迫切需要进行科学有效的优化调度。在现有设备条件下，提高 龙门吊的效率的主要途径是减少龙门吊不必要的移动，即优化龙门吊的行走路径，达到 节约费用，提高其工作效率的目的。 集卡在集装箱码头的行走路径也是影响堆场运行效率的一个重要因素。根据船舶装 卸过程中集卡是否固定的服务于某装卸桥，集卡的运行模式可以分为“作业线 调度模 式和“作业面 调度模式。“作业线 调度模式管理方便，但是集卡和装卸设备的利用 效率较低。“作业面 调度模式可以在不增加集卡数量的基础上大幅度提高集卡的利用 效率。集装箱堆场集卡的线路优化，对堆场运行效率的提高起着相当重要的作用。 综上所述，对集装箱港口堆场龙门吊的调度优化和集卡线路优化的研究，对于提高 港口的服务水平和竞争能力都具有重要的意义。这将从以下几方面提高堆场的运行效 率：( 1 ) 降低堆场的装卸成本。( 2 ) 减少集装箱在堆场的运输时间，从而降低船舶在港的 停留时间。( 3 ) 有利于港口作业流程的合理布置。 1 3 研究综述以及面临的问题 随着集装箱运输事业和计算机仿真技术的发展，研究者们多利用计算机模拟技术和 优化算法对港口集装箱物流系统进行研究，这些研究主要集中在运营环节及装卸工艺系 统方面，其中运营环节发生在码头前沿、水平搬运、堆场作业等。因此对港口的研究可 以分为泊位的合理分配、装卸设备资源的合理配置及调度、堆场作业和装卸工艺流程优 化等部分。下面对关于港口方面的国内外研究情况进行叙述。 1 3 1 计算机模拟技术在港口码头系统上的应用 我国很早就应用了港口系统计算机模拟技术。国内交通部第一航务工程勘察设计院 开发过码头装卸系统和码头的计算机模拟模型，武汉交通科技大学开发过集装箱码头装 卸系统的模拟模型；天津大学开发过码头的计算机模拟模型；交通部水运科学研究所开 发过用于研究堆场容量的码头计算机模拟模型。 近年来计算机模拟技术在港口码头系统上的应用得到越来越多的重视，应用也越来 越普遍。香港的c h i n al i g h t & p o w e r 公司和s a n d w e l ll n c 公司利用模拟模型研究增加何 种的设备或者设施和如何增加这些设备或设施，才能以最经济的方式适应港口吞吐能力 增长的要求【5 】；荷兰的t e b o d i nb v c o n s u l t a n t s & e n g i n e e r s 利用数值模拟模型研究港e l 的设计和卸船机的选型【6 1 ；计算机模拟器e t o o l ，已用于对跨运车运输、运输机械与有 轨龙门起重机配合、与跨运车类似的新型机械作业的三种作业方案进行比较、评估【7 1 ； 德国l n s t i t u eo f s h i p p i n ge c o n o m i c sa n dl o g i s t i c s 开发的集装箱装卸系统模拟器s c u s y ， 已经成功的应用于研究集装箱的不同堆箱方式对整体布局的影响、比较采用不同设备组 合的堆场作业方式、分析不同设备的适用对码头营运的影响等【8 】。 第一章绪论 1 3 2 泊位分配和装卸桥调度 泊位配置是指在船舶到达之前为其分配靠港泊位。依据特定目标和约束不同，现在 的研究大多把泊位分配归为多种不同的组合优化问题。l a ia n ds h i h l 9 j 研究了离散的泊位 分配问题，并给出了分配问题的几个简单规划；b r o w ne ta l l l 0 】为船舶的泊位分配建立了 整数规划模型。 装卸桥的调度问题是为靠港船舶分配若干装卸桥完成装卸任务，包括把装卸桥分配 给不同船舶或者把装卸桥分配给船舶的不同部分，对此部分的优化没有绝对的目标，一 般目的是减少全部船舶的延迟同时保证装卸桥使用的经济性。h a g h a n ia ，k a i s a re i 】 利用混合整数规划，以最小化船舶在港时间为目标来减少无效移动；d u b r o v s k yo 和 l e v i t i ng t l 2 】应用遗传算法加上安全约束来搜索优化的装卸流程。 1 3 3 堆存空间分布 堆场空间合理分布是堆场优化的重要组成部分。杨淑琴，张运杰等【l3 】根据出口集装 箱尽量轻箱在下重箱在上的原则，采用启发式方法合理安排出口集装箱箱位安排，以达 到装船作业时堆场机械的翻箱率最低。k h k i m 1 4 】考虑了具有权重的出港集装箱的堆放 配位问题以及最小化翻箱作业量问题。k a phk 和j o n gw b 【l 习以码头堆场中最小的倒箱 数及最小的移动距离为目标，来进行码头堆场中箱位的合理设置。k i mkh 【l6 】研究了当 进港集装箱以随机方式到达时对翻箱率的估计问题。徐剑华【l7 】提出用择箱指数方法寻求 集装箱最佳堆存高度和最佳布置，以使堆场的面积利用率和堆场的取箱效率获得综合优 化的结果。 1 3 4 堆场装卸资源设备的调度 我国堆场的装卸设备大多采用龙门吊。l a i 和l 锄【l8 】使用仿真模型比较了不同堆场 分配政策下码头的设备利用率和船舶等待时间。k o z a n 和p r e s t o n 1 9 】通过整数规划模型， 提出了最优的堆存策略，确定了最优龙门吊作业计划，规划模型的日标是使分配给某船 舶的所有龙门吊的工作效率最大。c h u q i a nz h a n g t 2 0 】通过一个混合整数规划模型优化了 集装箱码头龙门吊动态任务安排和堆场之间移动顺序安排。模型以计划期内龙门吊未完 成的任务量最小为目标，通过改进拉格朗r 启发式算法求得了龙门吊的最优任务安排和 最优移动次序。c h u n ge ta 1 1 2 l 】最早提出了龙门吊路径选择问题，目的是减少龙门吊的不 必要移动，提高龙门吊的工作效率。k i ma n dk i m 2 2 j 研究了单个龙门吊的最优路径问题， 建立混合整数规划模型，使龙门吊的箱区间总移动时间最小化来解决配置问题。韩晓龙 【2 3 j 讨论在出口装船过程中龙门吊的最优路径问题，实现作业过程中龙门吊的行走时间最 短。李建忠【2 4 】以各箱区总的未按计划完成的工作箱量所需的龙门起重机时间和龙门起重 机闲置时间的最小化为目标函数，采用基于启发式方法的l a g r a n g i a n 松弛算法，求取轮 胎式龙门起重机的动态配置近似最优解。 第一章绪论 1 3 5 堆场集卡线路规划 集卡的调度优化也可以提高堆场的运行效率。p y u n gh o ik o o 2 5 l 研究了码头静态的 运输问题，即在最初时刻所有需要装卸的集装箱的数量、地点、时间都是预先确定好的。 文中提出一种两阶段启发式禁忌搜索算法，目的是在决定最小集卡配置数量的同时为每 辆集卡确定最优路径。h o o n gcl 和m e l v y ns 1 2 6 】等提出了在满足客户服务需求及车辆数 量有限的情况下，获得最小成本路线计划。在已知船舶装卸作业和堆存需求的情况下， 杨静蕾【27 j 研究了码头物流路径的优化问题。 1 3 6 目前堆场研究所面临的问题 ( 1 ) 集装箱在堆场的装卸作业都是由堆场龙门吊完成的，所以龙门吊的运行效率直接 关系着堆场的运行效率，进而影响整个集装箱码头。目前的研究大多数针对一台龙门吊 的调度优化或者堆场中的龙门吊数量配置，并没有考虑多台龙门吊在堆场内的调度优 化。 ( 2 ) 在集装箱堆场中，集卡的调度是关系堆场的作业效率的一个重要因素。传统的集 卡调度方式是基于“作业线”的。“作业线 调度模式虽然管理方便，但是集卡和装卸 设备的利用效率较低。而集卡的“作业面”模式，即进出口作业同时进行，可以很好解 决这个问题。在这种模式中，集卡服务的岸桥并不固定。集卡同时对应多条作业线，保 证集卡在处于空载状态后可就近投入其他需要的作业线中，大大缩短集卡的空载行驶时 间和距离。目前基于“作业面 调度模式的集卡的研究大多数只考虑集卡，并没有考虑 堆场中龙门吊的因素，未从整体上把握堆场中资源的优化配置。 ( 3 ) 理论研究与实际脱节。有的研究只注重问题的形式化描述和讨论，没有深入对问 题的背景和实际意义进行研究和思考，从而导致理论研究与实际应用脱节。另外，在算 法的一些参数的确定上经验性比较大，无法准确反映问题的实质。 1 4 本文主要的研究工作和创新之处 课题的研究内容是集装箱码头堆场龙门吊调度和集卡路线优化的建模与优化。本文 利用运筹学和智能算法对龙门吊调度和集卡线路规划进行配置优化，并用理论与仿真相 结合的方法对问题进行分析与研究。主要完成了以下工作和创新之处。 l 、研究了龙门吊资源不足情况下堆场有多个任务的龙门吊优化调度问题，应用蚁 群算法对问题进行了求解。在应用蚁群算法求解问题的过程中，针对集装箱堆场有多个 龙门吊的特点，设计了蚂蚁确定“行走路径 的策略。仿真数据表明，在可接受的时间 内，采用蚁群算法所得的结果较遗传算法更好。 2 研究了基于“作业面”运作方式的集卡行走路径优化问题，应用免疫禁忌搜索 算法对问题进行了求解，该算法结合了免疫算法和禁忌搜索的优点，不易陷入局部最优 解，同时避免了禁忌搜索取得的结果受初始解影响较大的缺点。通过数据实例分析了 “作业面 调度模式与“作业线”调度模式对集卡行走路径的影响，结果表明“作业面 第一章绪论 运作方式有效降低了集卡的行走距离，节约了作业时间，大大提高了集卡的利用效率。 1 5 本文架构 本文首先在第一、二章介绍了课题的背景、目的和本文用到的优化算法等内容，在 第三章、四章阐述了本文所研究的主要内容，即关于龙门吊、集卡的优化调度，最后在 第五章总结不足，提出今后研究方向。 具体分为： 第一章，阐述了课题的研究背景、目的、意义以及本文的研究工作。 第二章，阐述了优化算法的含义，并具体介绍了本文所用到的遗传算法、蚁群算法、 禁忌搜索三种智能优化算法。 第三章，讲述了集装箱码头堆场龙门吊调度问题，应用蚁群算法对问题进行求解， 设计了蚂蚁确定“行走路径 的策略，通过具体的算例说明了用蚁群算法解决龙门吊调 度问题优于传统的遗传算法和禁忌搜索。 第四章，讲述了集装箱码头堆场集卡调度问题，首先给出了集卡调度在“作业面 调度模式下的数学模型，根据数学模型设计了免疫禁忌搜索算法，通过算例说明了“作 业面 调度模式相比“作业线”大大提高了集卡的利用效率。 第五章，总结本文的成果以及不足，指出今后的研究方向。 第二章智能优化算法简介 2 1 引言 第二章智能优化算法简介 对集装箱堆场资源的优化需要设计智能优化算法进行求解。什么是智能优化算法? 优化是一种以数学为基础，用于求解各种工程问题最优解的应用技术。作为一个重要的 科学分支，最优化一直受到人们的广泛重视，它对多个学科产生了重大影响，并在诸多 工程领域得到迅速推广和应用，己成为不同领域中很多工作不可或缺的工具【2 引。 优化算法是一种搜索过程或规则，它基于某种思想和机制，通过一定的途径或规则 来得到满足用户的要求。优化问题中的旅行商问题、伽背包问题、图着色问题、设备 布局问题等等，至今没有有效的多项式时间解法，它们已被证明是n p 完全问题。用确 定性的优化算法求n p 完全问题的最优解，需要的计算时间与问题的规模之间成指数关 系。此时对于大规模问题，由于计算时间的限制，往往难以得到问题的最优解，用近似 算法求解得到的近似解质量较差，而且最坏情况下的时间复杂性是未知的。因此，从数 学的角度讲，现有近似算法不可能求出大规模组合优化问题的高质量的近似解。智能优 化算法作为一种新兴的演化计算技术己成为越来越多研究者的关注焦点。智能算法中的 群体指的是“一组相互之间可以进行直接通信或者间接通信( 通过改变局部环境) 的代理 ( a g e n t ) ，这组代理能够合作进行分布式问题求解”，而智能则是指“无智能的代理通过 合作表现出智能行为的特性。智能算法在没有集中控制且不提供全局模型的自i 提下， 为寻找复杂的分布式问题的解决方案提供了基础。智能优化理论同其它优化理论一样， 都是以数学为基础，用于求解各种工程问题优化解的理论。 与大多数基于梯度的应用优化算法不同，智能优化依靠的是概率搜索算法。虽然概 率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比其优点 还是比较显著的【2 9 】： ( 1 ) 没有中心控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具 备更强的鲁棒性。 ( 2 ) 以非直接的信息交流方式实现个体协作，确保了系统的扩充性。 ( 3 ) 并行分布式算法模型，可充分利用多处理器。 ( 4 ) 对问题定义的连续性无特殊要求。 ( 5 ) 算法实现简单。 智能方法易于实现，算法中仅涉及各种基本的数学操作，计算相对简单。另外，其 数据处理过程对c p u 和内存的要求也不高。而且，这种方法只需目标函数的输出值， 而无需其梯度信息。更为重要是，智能算法潜在的并行性和分布式特点为处理大量的以 数据库形式存在的数据提供了技术保证。因此，无论是从理论研究，还是应用研究的角 度考虑，进行智能算法理论及其应用研究都是具有重要学术意义和现实价值的。 就优化机制与行为而分，目前工程中常用的优化算法主要可分为：经典算法、构造 型算法、改进型算法、基于系统动态演化的算法和混合型算法等。 第二章智能优化算法简介 ( 1 ) 经典算法。包括线形规划、动态规划、整数规划和分枝定界等运筹学中的传 统算法，其算法计算复杂性一般很大，只适用于求解小规模问题，在工程中往往不实用。 ( 2 ) 构造型算法。用构造的方法快速建立问题的解，通常算法的优化质量差，难 以满足工程需要。譬如，调度问题中的典型算法有j o h n s o n 法、p a l m e r 法、g u p t a 法、 c d s 法、d a u n c n b r i n g 的快速接近法、n e h 法等。 ( 3 ) 改进型算法，或称邻域搜索算法。从任一解出发，对其邻域的不断搜索和当 前解的替换来实现优化。根据搜索行为，它又可以分为局部搜索法和指导性搜索法。 ( 4 ) 基于系统动态演化的方法。将优化过程转化为系统动态的演化过程，基于系 统动态的演化来实现优化，如神经网络和混沌搜索等。 ( 5 ) 混合型算法。指上述各种算法从结构或操作上相混合而产生的各类算法。 2 2 蚁群算法 人工蚁群算法【3 0 】是人们受到自然界中真实的蚁群集体行为的启发而提出的一种基 于蚁群的模拟进化算法，属于随机搜索算法，由意大利学者m d o r i g o 等人于1 9 9 1 年首 先提出。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称之为外激素 的物质进行信息传递，从而能够相互协作，完成复杂的任务。蚁群之所以表现出复杂有 序的行为，个体之间的信息交流与相互协作起着重要的作用。蚂蚁在运动过程中，能够 在它所经过的路径上留下一种物质，而且蚂蚁在运动过程中能够感知这种物质的存在及 其强度，并以此指导自己的运动方向，蚂蚁倾向于朝着该物质强度高的方向移动。因此， 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息j 下反馈现象，某一路径上走过的蚂 蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达 到搜索食物的目的。蚁群算法正是模拟了这样的优化机制，即通过个体之间的信息交流 与相互协作最终找到最优解。 下面以旅行商问题( t s p ) 为例简单介绍蚁群算法。这里先介绍一下环游的概念。环 游是指从某一个城市出发，将其他每一个城市都访问一次，最后返回到起始城市形成的 路线。以5 个城市为例，1 2 3 4 5 一l 就是一个环游，3 5 2 4 一l 一3 也是一个 环游。显然，环游有很多，每一个环游都有一个长度。t s p 问题：已知n 个城市之问的距 离，寻找一条长度最短的环游。 设是西城市i 到城市j 之l 日j 的路径长度；t i i 表示路径i j 上的信息素；q 甜表示路径i j 的能见度，i 1 = 1 4 ，；第k 只蚂蚁在t 时刻从城市i 到城市j 的转移概率为： p o ( t ) = 一阳n d | 【k ( f ) 】“ t 1 打】p j 0其他 ( 2 - 1 ) 其中a l l o w e d k 表示第k p , 蚂蚁未访问过的城市。 蚁群算法的流程【3 l 】如下： 1 ) 初始化。设置迭代次数c o u n t e r = 0 ，设置最大迭代次数n c m a x ，为信息素赋初始 第二章智能优化算法简介 值1 ：o = 1 ( n k ) ，其中k 表示按照最近邻启发式算法得到的环游长度，n 为城市的数 量。 2 ) 将m 只蚂蚁放在不同的城市上。 3 ) 每一只蚂蚁按照式( 2 1 ) 选择下一个城市。 4 ) 所有的蚂蚁得到各自的环游以后，对得到的环游做局部寻优。 5 ) 按照下面公式更新信息素： t i i = ( 卜p ) t i j + ，其中0 p 1 为挥发系数。 k = y t ：，百：表示第k 只蚂蚁在路径i j 留下的信息素。 ，_ v k = l t 。一j q 厶第七只蚂蚁经过路径驴 叫 10否则 其中q 为常数，厶为第k 只蚂蚁得到的环游长度。 6 ) c o u n t e r + + 。如果c o u n t e r t 2 ，所以蚂蚁分配到龙 门吊2 进行装卸任务调度。由于龙门吊2 此时没有分配任务，所以随机分配任务2 ，这 是t 2 = 1 0 。t 1 t 2 ，所以蚂蚁分配到龙门吊2 进行装卸任务调度。蚂蚁在箱区2 ，按照以上规则决定龙门吊2 移动的下一箱区。循环 执行，直到所有的任务全部分配完成，这时得到一只蚂蚁确定的龙门吊调度方案。整个 流程如下图所示： 第三章堆场龙门吊调度问题 3 3 3 路径选择概率 调度方案：龙门吊l 依次负责箱区1 、3 的装卸任务， 龙门吊2 依次负责箱j x - 2 、5 、4 的装卸任务， 图3 3 单只蚂蚁确定龙门吊调度方案示意图 初始时将蚂蚁k 置于堆场初始位置，蚂蚁是依据一定的选择概率在各箱区间行进的。 当蚂蚁k 所在的第t 台龙门吊在c 时刻行进到箱区i 时，根据蚁群算法思想，在集装箱箱区i 向下一集装箱箱目前进的选择概率为： 咖，= 一 je a l l o w e d k 其他 ( 3 1 0 ) 其中【；表示在第t 台龙门吊在从集装箱箱区i 到下一集装箱箱区j 这条路径上的信息素； 1 ：表示第t 台龙门吊从集装箱箱区i 向下一集装箱箱区j 的能见度，即t 1 ；2 1 ( d u + q ) ； 吒表示龙门吊从集装箱箱区i 向下一集装箱箱区j 的移动时间，此移动时间是由箱区之 间的位置决定的，和龙门吊没有关系。q 表示第t 台龙门吊在箱区j 的作业时间； a l l o w e d k 表示第k 只蚂蚁未访问过的集装箱箱区集合。 3 3 4 信息素更新 每一台龙门吊有自己的信息素表。第t 台龙门吊的信息素更新公式： 巫口团田园可|l|田田回固圈 第三章堆场龙门吊调度问题 t = ( 卜p ) t + t ，其中0 p 1 为挥发系数。 埘 吒= 百，式中，m 是蚂蚁的总数，t 0 表示在第k 只蚂蚁所确定的龙门吊行 捌 走策略中，第t 台龙门吊在从集装箱箱区短0 下一集装箱箱区i 这条路径上留下的信息素。 如果第t 台龙门吊经过集装箱箱区i 到下一集装箱箱区j 这条路径，则t 乞，= q 丘，否则， t 0 = 0 。其中q 为常数，丘是在第k 只蚂蚁所确定的龙门吊行走策略中，第t 台龙门吊完 成所有分配的装卸任务并回到堆场起始位置的时间。 3 4 算法流程 以下给出蚁群算法的步骤，算法流程图如图3 4 所示。 第一步初始化参数。设置迭代次数c o u n t e r = o ，最优解b e s t s o l u ti o n = 极大数，设置 最大迭代次数n c m a x ，为信息素赋初始值，确定蚂蚁的数量m 及其它参数。 第二步将m 只蚂蚁放在不同的箱区上。 第三步每一只蚂蚁按照3 3 2 的方法确定龙门吊调度方案。 第四步所有的蚂蚁得到各自的调度方案以后，对得到的结果做局部寻优。如果局部 解优于最优解，则最优解= 局部解。 第五步按照3 3 4 信息素更新公式更新信息素。 第六步c o u n t e r + + 。如果c o u n t e r n c m a x ，返回第二步；否则结束，输出结果。 第三章堆场龙门吊调度问题 开始 夕 初始化参数 i 土最习一 不同城市 - 糜蚂蚁根据龙门吊完成任j - i 务时间和转移概率选择i i 相应龙fj 吊到下一箱区i l 一一一- j 竺竺奎 j 所有蚂蚁确定完调j j 度方案后，进行局i 更新信息素 ，j n 一j 邑甭到达最犬_ 、 3 5 算法举例及分析 ty 厂一一主 l j 图3 4 蚁群算法示意图 例如，假设有4 台龙门吊，1 3 个箱区装卸任务。1 3 个装卸任务按照其所在箱区进行 编号，从l 至t j l 3 。1 3 个箱区的位置如图3 5 所示。设，d w 表示箱区i 的行数，c o , 表示箱区 i 的列数，为了简单起见，龙门吊从箱区i 到箱区j 所需要的时间为 l o 木i r o w , 一，d j + 2 木jc o l ，哪j ，从堆场起始位置到箱区i 所需要的时间为 1 0 1 厂d wl + 2 水l ，i 。4 台龙门吊完成装卸任务所需要的时间如表3 3 所示。 第三章堆场龙门吊调度问题 行数 l 2 3 7 列数 l23 厂 i 箱区3 i一 厂一一一 l 箱区5 l。一 围 园圃 图3 5 堆场箱区位置示意图 表3 - 3 龙门吊处理的任务数据 任务 l234567891 01 l1 21 3 龙门吊12 01 21 81 01 62 6 7 2 6l l81 31 48 处理时间 龙门吊2 1 571 053 01 41 21 41 35995 处理时问 龙门吊31 691 381 81 6 9 1 8 1 29l l1 56 处理时间 龙门吊4l l1 01 592 21 31 61 51 081 2l l5 处理时间 参数：每两个箱区的初始路径信息素为l ，i f , 是1 5 ，d 是2 ，p 是0 8 ，q 是1 0 0 ， 最大循环次数1 0 0 ，蚂蚁2 5 只。 根据以上数据和参数运用蚁群算法求解的近似最优解为1 5 8 ，结果为12354 01 3 1 00 6798 01 2ll ，即第一台龙门吊依次负责第l 、2 、3 、5 、4 号箱区，第二台龙门吊 依次负责第1 3 、1 0 号箱区，第三台龙门吊依次负责第6 、7 、9 、8 号箱区，第四台龙门 吊依次负责第1 2 、1 1 号箱区。运行结果如图3 - 6 所示，当迭代到第3 8 代时得到近似最 网 囤 囤回国圆 第三章堆场龙门吊调度问题 优解。本文求解了2 0 次，求解的平均值为1 5 9 ，最好的解是1 5 8 ，最差的解是1 6 2 。用 遗传算法求解时，平均值为1 6 5 1 ，最好的解是1 6 1 ，最差的解是1 6 8 。用禁忌搜索进行 求解时，平均值为1 7 2 ，最好的解是1 6 4 ，最差的解是1 7 9 。由以上结果所示，在可接受 的求解时间内，蚁群算法在求解龙门吊调度问题时较遗传算法( g a ) 和禁忌搜索( t s ) 所取 得的结果更加优秀。 3 6 本章小结 图3 6 蚁群算法运行结果图 本章首先描述了集装箱港口堆场的龙门吊调度问题，运