（计算机软件与理论专业论文）港口集装箱装船作业问题的算法研究.pdf

港口集装箱装船作业问题的算法研究 摘要 论文题目： 专业： 硕士生： 指导教师： 港口集装箱装船作业问题的算法研究 计算机软件与理沦 张惠东 郭嵩山教授 摘要 集装箱运输是现代最重要的运输方式，而集装箱港口是这个运输过程中重要 的一个环节，集装箱港口的工作效率影响着整个运输效率。本文研究的是港口多 种装卸设备的联合调度问题。虽然单个设备的调度已有多人在研究，但联合起来 的研究却很少。而将多种设备联合起来调度才能更有效地优化资源配置、减少运 输成本。 本文研究一个较复杂的港口集装箱装船问题，集装箱被吊机从集装箱堆场取 出来，放到运输车上，运到岸边后让岸边吊机把集装箱吊上船，在这个过程里主 要考虑了两个问题：( 1 ) 取集装箱时当被别的箱子压着，应该要把上面的箱子移 到哪；( 2 ) 集装箱在运输车上的运输顺序。本文采用禁忌搜索加分支定界的方法 求解此问题，用禁忌搜索求优先顺序，同时用分支定界确定集装箱的取出方法。 文章最后实验部分，通过随机化生成了实验数据，实验结果显示对用贪心算 得的初始解有较大的改进。由于本问题是由本文作者根据实际情况提出的，目前 尚没有可作比较的其它文献，但是本文使用到的两个算法( 禁忌搜索和分支定界) 稍加修改后可以应用到两个已有的问题的求解，因此对这两个问题分别进行了横 向对比，实验表明本文算得的结果比较理想。 关键词：集装箱港口物流，禁忌搜索，倒箱，分支定界，联合调度 港口集装箱装船作业问题的算法研究 a b s t r a c t t i t l e ： m a j o r ： n a m e ： a l g o r i t h mr e s e a r c ho i lc o n t a i n e r s h i pl o a d i n gp r o b l e m a tc o n t a i n e rt e r m i n a l c o m p u t e rs o f t w a r ea n dt h e o r y z h a n gh u i d o n g s u p e r v i s o r ：p r o f e s s o rg u os o n g s h a n a b s t r a c t c o n t a i n e rt r a n s p o r ti st h em o s ti m p o r t a n tw a yf o rm o d e mt r a n s p o r t a t i o n ，a n dt h e e f f i c i e n c yo fc o n t a i n e rt e r m i n a ls i g n i f i c a n t l ya f f e c t st h ec o n t a i n e rt r a n s p o r t t h i s p a p e rf o c u s e s o ns c h e d u l i n gd i f f e r e n tk i n d so ft e r m i n a lc o n t a i n e rh a n d l i n g e q u i p m e n t s t h e s ee q u i p m e n t sa r eu s u a l l ys t u d i e da l o n ea n dt h ei n t e g r a t e ds c h e d u l i n g o ft h e s ee q u i p m e n t si ss t u d i e df e w i nt h i sp a p e r , t h ea u t h o rp r o p o s e sac o m p l i c a t e dt e r m i n a lc o n t a i n e r s h i pl o a d i n g p r o b l e m t h ec o n t a i n e r i st a k e no u tb yay a r dc r a n e ，p u to nav e h i c l e ，t r a n s p o r t e dt o t h es h o r e ，a n dl o a du pt ot h ec o n t a i n e r s h i pb yaq u a yc r a n e i nt h i sp r o c e d u r e ，t w o p r o b l e mn e e dt ob es o l v e d ：( i ) i f c o n t a i n e ra i sl o c a t e du p o nc o n t a i n e rb ，w h e r e c o n t a i n e ra s h o u l db er c l o c a t 酣i no r d e rt or e t r i e v ec o n t a i n e rb ( 2 ) t h eo r d e rt h a ta l i c o n t a i n e ra r ep r o c e s s e db yv e h i c l e t h i sp a p e ru s e st a b us e a r c ht og e tt h eo r d e ra n d u s e sb r a n c h a n d b o u n da l g o r i t h mt os c h e d u l ey a r dc r a n e i nt h el a s tp a r to ft h i sp a p e r , t h ea u t h o rf i s tg e n e r a t e sa l lt h ee x p e r i m e n td a t a , a n d t h ee x p e r i m e n ts h o w st h a to u rr e s u l ti sm u c hb e t t e rt h a l lt h ei n i t i a ls o l u t i o nc a l c u l a t e d b yg r e e d ya l g o r i t h m b e c a u s et h i sp r o b l e mi sp r o p o s e db yt h ea u t h o r , t h e r ea r en o p u b l i s h e dr e s e a r c h e so rr e s u l t so nt h i sp r o b l e m b u tt h et w oa l g o r i t h m ( t a b us e a r c h a n db r a n c h a n d - b o u n d ) u s e di nt h i sp a p e rc a nb eu s e di nt w oo t h e re x i s t i n gp r o b l e m s s oi nt h e s et w op r o b l e m s e o m p a r i s i o ni sm a d e t h ee x p e r i m e n ts h o w st h a to u r r e s u l t sa r e q u i t ew e l l k e yw o r d s ：c o n t a i n e rt e r m i n a l ，t a b us e a r c h ，r e l o c a t i o n ，b r a n c h a n db o u n d ， i n t e g r a t e ds c h e d u l i n g 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：目锺、东 日期：2 0 晰j 月斗日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：蜀壕走 日期：2 归，年月2 垆u 导师签名：荠易一导师签名：芳p 夕夕一 日期：掣年厂月彤日 港u 集装箱装船作业问题的算法研究第1 章绪论 1 1 研究背景及意义 第1 章绪论 全球贸易的发展大大促进了航运的发展，其运输量逐年稳步递增，而其中集 装箱运输的增长最为迅速。集装箱船在海上航行时，一般都维持一定的最适宜航 行速度，因而在整个运输过程中，集装箱船在港口装卸货物时所停留的时问长短 将大大影响集装箱船的运输效率。另一方面，由于计划不周或某些不可控的随机 冈素等原冈，集装箱经常要在装船前或卸船后在港口集装箱堆场停留一段时间， 随着港口吞吐量的增大，集装箱在港口暂存的空问需求也小断增大。这些都增加 了港口管理的难度。 为了提高装卸效率，必须对港口集装箱装卸设备的调度计划进行优化。对大 多数集装箱港口，主要的装卸设备有三种不同类型：岸边吊机，用于把集装箱吊 上船或者从船上吊下来；场内拖车，用于把从船上吊下来的集装箱运到集装箱堆 场，或者把集装箱从堆场运到岸边供岸边吊机吊上船；堆场吊机，用于在堆场内 移动集装箱，或把集装箱从堆场搬到场内拖车上，或者反过来。 本文研究的是这三种设备间的联合调度问题，尽量使到所有集装箱的装船时 间缩短，从而减少集装箱船的停留时间，提高港口效率及利润。 1 2 国内外研究现状 在2 0 0 0 年之前，港口集装箱物流的研究主要集中在对某种港口设备单独调 度进行研究，分析其要在达到一定效率的前提下使需要的设备数量最少，或者是 给定设备数量求其最优的调度方法使到效率最高。这样的研究一般不考虑其他设 备的数量限制或时问限制等，文献【l 】【2 】在这方面给出了详细的分类和文献综述。 而对2 种以t 的设备进行联合调度研究的论文并不多，主要有如下几篇： 2 0 0 1 年，m e e r s m a n s 和w a l g m a n s 在文献【3 】中首次提出多种设备联合调度问 题，以荷兰鹿特丹港为研究对象进行建模，探讨了集装箱装船的问题，主要考虑 的是集装箱装船的先后顺序。作者提出采用分支定界及启发式的束搜索两种方法 l 港【j 集装箱装船作业问题的算法研究第1 章绪论 求解。 2 0 0 6 年和2 0 0 7 年，我校0 4 级硕士生黎俊瑜和0 5 级硕士生林祺颖在他们的 毕业论文【4 1 嗍中，针对上面的鹿特丹港集装箱装船问题，分别用遗传算法和束搜 索算法进行了一定的探讨，得出与m e e r s m a n s 和w a l g m a n s 的方法相当的效果。 2 0 0 6 年，k a n gh u i g u i 和z h o up e i f e i 在文献 6 e o 提出了另一个装箱问题， 这个问题的特点是只考虑单个岸边吊机，而且此吊机的操作任务已经制定好，但 集装箱分多种类型，每种类型有多个，可能分布在不l j 的堆场区域，昂机每次操 作的集装箱类型已知，具体取哪个来装，就要在其中选择。然后再要安排车辆来 运输集装箱。作者提 用遗传算法来求解此问题。 2 0 0 7 年，曾庆成和杨忠振在集装箱卸船问题上提出了两个不同的具体闯题 p i g l 。文献【7 】讨论的是集装箱的卸货顺序和车辆安排问题，而文献【8 】讨论的是集 装箱卸货顺序和集装箱在堆场内的摆放位置问题。作者在这两个问题上都采用两 阶段的禁忌搜索算法求解。 2 0 0 6 年，l uc h e n ，n a t h a l i eb o s t e l 等人在文献 9 】提出先卸货后装货的问题， 问题特点有( 1 ) 集装箱在三种设备上的处理时间已知，( 2 ) 同一设备处理两个集装箱 的过程巾间需要有准备时间，而且这个时闻跟这两个集装箱有关， _ 叫l i 一1f + 1 j i ，+ 1 卜啼o ( ) l 叫o 卅_ o 一+ 口 图5 2 移动任务 这样解的邻域大小是约n 2 ，在n 较大的时候，邻域过大将导致程序运行很 长的时闻，力此，在禁忌搜索达到第一个局部最优解之居，该邻域将改变为：把 一个任务移动到序列的另一个位置，而且新位置与老位置问的距离不超过2 0 。 这样邻域规模将下降到n x 4 0 。 5 2 5 禁忌表 本文的禁忌对象是解变化的过程。假设当前在邻域里选择的解是通过把任务 i 移动到位置j 这一变换得到的，而 目此解比当前最优解差，则把_ 元组( i ，j ) 作为禁忌对象。 本算法采用的禁忌表是一个二维数组t a b u 】，当某禁忌对象( i ，j ) 要加入 禁总表时，将t a b u i j 的值设为一个固定的禁忌长度值。判断某对象( i ，j ) 是 否被禁忌时，只需要看t a b u i j 的值是否大于0 。 5 2 5 藐视规则 在邻域里，如果某个被禁忌的合法解，比邻域里其他的解的估价函数优，丽 且优于当前已知的最优解的评价函数，就解禁这个解。 5 2 6 终止条件 港口集装箱装船作业问题的算法研究 第5 章求解装船问题 当迭代次数达到某一个预设值t ，或者迭代过程中有连续k 代没有更新最优 解，则终止。 港口集装箱装船作业问题的算法研究第6 章实验分析 6 1 生成实验数据 第6 章实验分析 本文研究的问题相对较新颖，目前没有现成的权威数据，而港口运营商出于 商业理由也不会把其港口实际数据公布于众，因此本文没有现存港口的历史数据， 所以本文只能根据实际情况选定某些控制参数，并按照一定仿真规则随机产生一 些比较符合实际情况的实验数据。只要选择合适的参数和仿真规则，那么计算机 产生的数据也能较好地反映实际问题的特点。 本问题与2 0 0 6 年黎俊瑜在文献【4 】里研究的问题有类似之处，文献【4 】在生成 实验数据的时候，采用了文献【2 2 】提出的仿真模型，在确定具体仿真规则和控制 参数的时候参考了文献【2 3 】【2 4 】【2 5 】。该仿真模型是由3 个基本部分所组成，包括 船上集装箱布局的生成，码头仓库中集装箱布局的生成，和装卸设备相关参数的 确定【4 】。文献【4 】的数据生成方法较科学，而且文献【5 】也曾使用过，所以局限性 较小。因此本文在文献【4 】的数据生成方法的基础上，根据本文问题的特点增加 部分数据，从而重构出本文的实验数据。 本文实验所需要的数据有n a s c ，n y c ，n q c ，s i z e i ，t m o v 。，1 k n d l e ，n ， t a g v ( j ) ，t q c ( j ) ，p o s i ，q ( i ) ，p r e o c ( i , j ) ，其中n a s c ，n y c ，n q c ，n ，t a g v o ) ， t q c ( j ) ，q ( i ) ，p r e q c ( i , j ) 在文献【4 】的数据里已经有了，本文需要添加的是s i z e i ，t m o 。e ， t h a n d l e ，p o s i 的数据。 一般集装箱堆场的布局都是均匀对称的，所以我们假设所有b l o c k 的s i z e 都 是一样的。因为生产难度高，y c 设备的体积有一定限制，y c 的体积直接影响 到b l o c k 里一个b a y 的大小，根据文献【1 3 】的说法，b a y 的宽度为6 到1 0 个标准 集装箱，高度为4 到7 个标准集装箱。如果集装箱摆放过高，在风的影响下有倒 塌的危险，所以一般b a y 的高度比宽度小。 在文献【4 】，在堆场取出一个集装箱的平均处理时间是1 8 0 秒，因此我们设 1 - m 一为6 0 秒，t h a n d l e 为2 0 秒。 每个集装箱的位置p o s i ，将通过以下方法生成： 港口集装箱装船作业问题的算法研究第6 章实验分析 的。 ( 1 ) 对同一个b l o c k 的所有集装箱随机生成一个顺序排列； ( 2 ) 根据上面得到的顺序，逐一对每个集装箱随机分配b a y 和r o w 值，然后 把集装箱放到那r o w 的项部，如果此r o w 已满或此b a y 里集装箱数日达 到了n r o w 卡n t i e r - ( n t i e r - 1 ) ，就再次随机b a y 值和r o w 值。 上面说到的随机都是均匀的，即取值范围内取到每个取值的可能性都是一样 下面是各组测试数据的规模，每组有l o 个测试点： 表6 1 测试数据的规模 数据编号( 组) j o b q c y c s i z e ( b a y ，r o w ，t i e r )a g v g ll o2l ( 1 ，4 ，3 ) 2 g 22 032 ( 2 ，4 ，3 ) 2 g 34 0 32 ( 3 ，4 ，3 ) 3 g 44 0 3 3 ( 1 ，6 ，4 ) 3 g 58 043 ( 2 ，6 ，4 ) 4 g 6 8 043 ( 2 ，6 ，4 ) 6 g 71 2 044 ( 3 ，6 ，4 ) 8 g 81 2 04l ( 6 ，6 ，4 ) 4 g 9 1 6 042 ( 6 ，6 ，4 ) 6 g 1 0 1 6 0 44 ( 3 ，6 ，4 ) 8 表6 - 1 的第5 列给出了y c 的规格，通过三元组( b a y ，r o w ，t i e r ) 表示。 6 2 实验结果 程序运行环境是：i n t e lc o r e 2t 5 4 7 01 6 g h z ，2 gr a m ，w i n d o w sx ps p 3 操作系 统。 禁忌搜索算法的参数是：最大迭代2 0 0 代，连续5 0 代没改进则结束程序， 下面的表格列出了程序运行的初始解、最终解以及运行时间，取各组1 0 个 测试点的平均值： 3 l 港口集装箱装船作业问题的算法研究 第6 章实验分析 表6 - 2 实验结果 编号初始解最终解时间比较 g l7 8 3 77 4 9 70 0 1 4 3 4 g 21 4 6 51 3 7 4 70 0 5 36 1 6 g 32 7 4 82 2 2 50 7 9 31 9 0 3 g 42 3 7 8 52 1 8 3 5o 9 3 48 2 0 g 53 8 8 6 53 4 5 2 71 3 3 9 。1 1 1 6 g 62 9 3 7 82 4 7 0 61 2 5 6 4 1 5 9 0 g 74 2 6 4 13 5 0 0 23 7 5 2 5 1 7 9 1 g 81 7 4 1 2 99 2 0 9 21 4 8 9 5 94 7 1 1 g 91 3 9 0 0 77 8 6 8 52 3 4 0 54 3 3 9 g l o 5 3 9 5 74 2 7 6 71 4 1 7 6 4- 2 0 7 4 本章所有实验的程序运行时间以秒为单位，当a 与b 进行比较时用百分数 ( a b ) b 1 0 0 的形式给出。从上面的比较可以看到，禁忌搜索对贪心算得的 初始解有较大的改进。 6 3 实验比较 由于本问题由本文作者自行提出，目前没有可作比较的其它文献，但是本文 的禁忌搜索算法稍加修改后可以应用到文献 4 1 1 5 的港口集装箱装卸设备联合调 度问题的求解，而本文的分支定界算法町以直接应用到求解文献 1 3 1 的集装箱倒 箱位置问题。因此下面对这两个问题分别进行横向比较。 6 3 1 与文献1 4 11 5 1 比较 文献 4 1 1 5 1 的问题里堆场的结构比较简单，集装箱在堆场被取出的操作较简单， 每个集装箱被取出的处理时间是一个固定值。下表给出文献【4 】的测试数据规模， 港口集装篇装船作业问题的算法研究第6 章实验分析 每一组有1 0 个测试数据。 表6 - 3 文献【4 】的测试数据的规模 数据编号( 组)规模 j o b q c a s ca g v s l小8222 s 2 小8224 s 3 小 2 0 3 44 s 4 小 2 0346 s 5 小 2 0348 s 6中等9 0 4 1 21 8 s 7 中等9 0 41 2 2 0 s 8 中等 1 2 041 22 2 s 9 中等 1 6 041 22 4 s l o 中等 1 6 041 22 6 s l l大3 0 042 73 0 s 1 2 大 4 5 042 74 0 s 1 3 大 6 0 042 74 0 s 1 4 大 7 5 042 7 5 0 s 1 5 大 9 0 042 76 0 文献【4 】【5 】的实验环境都是：i n t e lp e n t i u mm1 6 g h z ，d d rr a m512 m b ， w i n d o w sx p s p 2 ，v i s u a lc + + 。 下面与文献 4 】的遗传算法进行枕较： 表6 - 4 与文献【4 】的比较 编 g a _ g r e e d y l 4 1 禁忌搜索( 本论文) 号 解时间解时间差别 s l1 2 5 7 1 0 0 7 3 1 2 5 7 1 0 0 3o 0 0 s 21 1 4 2 90 0 5 91 1 3 6 90 0 3 4 o 5 2 s 3 1 5 8 9 60 0 9 61 5 8 5 30 3 6 10 2 7 港u 集装箱装船作业问题的锋法研究第6 章实验分析 s 41 7 1 1 8o 0 9 31 7 1 1 8 0 3 9 1o o o s 51 9 6 9 20 0 9 31 9 6 8 60 4 0 80 0 3 s 63 1 1 2o 3 83 1 1 22 0 9 20 o o s 73 5 4 4 90 3 8 63 5 3 8 41 6 5 3- 0 1 8 s 84 0 9 5 9 0 5 4 8 14 0 8 5 43 5 1 9o 2 6 s 95 2 2 40 8 2 0 95 2 2 41 0 9 0 9 o o o s 1 05 0 7 6 50 7 4 9 85 0 7 2 27 1 8 9 一o 0 8 s l l7 0 1 0 91 6 37 0 0 9 23 9 5 2 0 0 2 s 1 29 8 2 02 7 6 6 49 7 9 6 38 5 8 5 80 2 4 s 1 31 2 8 9 8 83 7 4 4 9 1 2 8 1 1 51 9 8 7 0 9o 6 8 s 1 41 7 2 3 9 94 5 9 0 l 1 7 2 2 1 95 2 5 1 5 6一o 1 0 s 1 51 9 1 6 7 95 9 5 9 l1 9 0 9 4 33 2 2 4 2 5 o 3 8 1 5 纽数据里，有4 组的解一样，其他l l 组本论文的解比文献【4 】的好一点。 平均计算1 5 组解的平均值，文献【4 】的足6 3 2 4 0 9 3 ，本论文的是6 3 0 8 3 2 7 ，提高了 0 2 5 ，但本文的计算时间长很多。这个禁忌搜索算法的参数是：迭代2 0 0 次， 禁忌长度3 0 。 文献【5 】直接采用了文献【4 】的测试数据，也可以直接比较，下嘶是比较结果： 表6 - 5 与文献【5 】的比较 b e a ms e a r e h1 5 j 参 编 禁忌搜索( 本论文) 数：b w = 4 0 ，f w = 1 0 ，m p = 5 号 解时间解时间差别 s l1 2 5 7 1 o 0 01 2 5 7 1o 0 3o o o s 21 1 3 6 9o o l1 1 3 6 90 0 3 4 o 0 0 s 31 5 8 8 4o 0 61 5 8 5 3o 3 6 1o 2 0 s 41 7 1 1 8 0 0 61 7 1 1 8o 3 9 lo o o s 51 9 6 8 60 0 71 9 6 8 6 0 4 0 80 0 0 s 63 1 2 0 93 7 03 1 1 22 0 9 20 2 9 港口集装箱装船作业问题的算法研究 第6 章实验分析 s 73 5 4 4 24 ，9 93 5 3 8 41 6 5 3- 0 1 6 s 84 0 9 3 48 4 24 0 8 5 43 5 1 90 2 0 s 95 2 5 6 7 1 2 8 95 2 2 41 0 9 0 9d 6 2 s i o5 0 8 7 ，91 2 ，1 7 5 0 7 2 2 7 1 8 9 趣3 1 s ll7 0 2 65 0 1 27 0 0 9 23 9 5 2o 2 4 s 1 29 9 0 2 89 6 4 l9 7 9 6 38 5 8 5 8一1 0 8 s 1 3 1 2 9 i 2 ，51 3 4 ，1 61 2 8 1 1 51 9 8 7 0 9筑7 8 s 1 41 7 2 4 0 22 5 1 0 4 1 7 2 2 1 95 2 5 1 5 6一o 1 1 s 1 51 9 1 2 9 83 7 5 2 71 9 0 9 4 3 3 2 2 4 2 5 o 1 9 有4 组的结果相同，其他l l 组的结果本文结果更好，1 5 组解的平均值分别 是6 3 3 1 8 1 3 和6 3 0 8 3 2 7 ，整体来看本文的解比文献 5 】好0 3 7 。 6 3 2 与文献1 1 3 11 老较 本文5 1 节介绍的分支定界算法用于求解单个b a y 取箱的最少倒箱次数问题， 这个问题跟文献【1 3 】研究的其中一个问题一样，因此为了单独测试和比较这个算 法的效果，先随机生成一些测试数据。生成方法： ( 1 ) 设定b a y 的宽度n r o w 和高度n t i e r 的大小，让集装箱个数n = n r o w n t i e r 一( n t i e r 一1 ) ： ( 2 ) 随机生成数字1 ，2 ，n 的一个排列( a 1 ，a 2 ，a n ) ； ( 3 ) 按照a 1 ，a 2 ，a n 的顺序逐一为每个集装箱分配随机的一个r o w ，把集装箱 放到那l o w 的顶部，如果此r o w 已满，就再随机选出另一个r o w 。 n 越大，合法解也越多，搜索量就越大，因此让n = n r o w n t i e r 一( n t i e r 一 1 ) ，这样能更好地测试程序的性能。 对每种不同的规模( n r o w 取值范围是【6 ，1 0 】，n t i e r 取值范围为【4 ，7 1 ) ，都生 成1 0 0 0 组测试数据，进行测试。 下面是本论文算法的运行结果： 港【集装箱装船作业问题的算法研究 第6 章实验分析 表6 - 6 各组的平均结果和最坏结果 n t i e r xl o w e rl b 最最大扩展最长运 最优解扩展结点数时间 n r o wb o u n d优解节点数行时闻 4 x 61 2 1 7 1l1 0 6 39 0 9 0 1 3 4 10 0 0 0 35 0 2 30 ，0 1 5 4 x 7 1 4 1 5 7 1 2 9 8 2 9 1 7 0 3 0 0 20 0 0 0 51 7 7 2 70 0 1 5 4 x 81 6 1 7 21 4 9 2 59 2 2 9 1 2 5 9 50 0 0 2 05 2 1 2 8 4o 7 1 8 4 x 91 8 3 1 31 6 9 1 29 2 3 5 4 7 4 0 50 0 0 8 4 9 9 9 6 0 61 6 2 5 4 xl o2 0 5 0 81 9 0 5 79 2 9 2 1 1 9 3 6 1 0 0 2 0 08 3 5 4 7 0 91 2 5 7 8 5 x 61 8 1 5 l1 5 8 98 7 ，5 4 6 3 1 8 3 0 0 0 9 56 9 7 6 4 01 0 7 8 5 x 7 2 1 2 4 6 1 8 7 1 9 8 8 1 1 5 6 2 1 4 00 0 8 6 4l3 4 3 4 2 6 61 8 5 1 5 5 x 82 4 3 7 52 1 6 0 28 8 6 2 1 7 9 6 2 1 00 3 2 8 53 6 8 7 5 0 2 86 1 5 x 92 7 5 2 12 4 4 7 48 8 9 3 4 5 1 5 9 6 7 09 0 4 9 41 6 e + 0 9 3 3 1 8 5 x 1 03 0 2 4 32 7 0 4 08 9 4 1 8 6 51 0 5 7 83 9 3 1 1 51 7 e + 0 91 1 0 1 2 6 x 62 5 0 1 52 1 2 7 98 5 0 6 3 9 8 8 5 8 ，l0 6 0 l l4 8 2 8 7 2 6 2 7 3 6 x 72 9 1 5 52 4 9 6 58 5 6 3 4 0 5 3 5 3 7 4 4 4 4 6 1 0 63 6 e + l o3 5 6 5 6 第三列给出的是对初始状态的下界估测值( 1 0 0 0 个测试点的平均值) ，第四 列给出这个下界与最优解的比例，平均来说l o w e rb o u n d 是最优解的9 0 左右， 表明l o w e rb o u n d 函数的效果很好，因此本算法有很强的减枝能力，从上表第五 列的数据也可以看出，由于减枝能力强，只需要搜索较少的结点就可以求得最优 解。 第五列给出每组测试点的平均运行时间，而第七列给出的是所有测试点里运 行时间最长的测试点所需要的运行时间。可以看到，对n t i e r x n r o w 小于等于4 0 的所有测试点，平均只需要不到1 秒的时间就可以求得最优解，而最坏情况下也 只需要搜索约5 千万个结点，运行时间少于7 3 秒。 而文献【1 3 】的分支定界算法只能求解n t i e r x n r o w 小于等于3 0 的测试数据， 而且当n t i e r = 5 ，n r o w = 6 的时候，平均运行时问是4 4 分钟，远大于本文的最长运 行时间。下图是文献【1 3 】的实验结果，实验环境是p e n t i u m8 0 0 m h z ，1 2 8 m b ： 3 6 港口集装箱装船作业问题的算法研究第6 章实验分析 表6 7 文献【1 3 】分支定界算法的实验结果 n t i e r x n最优解平均运 r o w 平均值行时间 3 x 33 4 57 3 3 x 45 1 08 0 3 x 5 7 2 31 3 2 3 x 68 3 5 1 4 5 3 x 79 8 84 5 5 3 x 8l1 3 31 4 2 3 4 x 49 5 31 4 8 4 x 51 1 8 53 3 4 4 x 6 1 3 7 5 1 5 2 4 4 x 71 6 7 02 2 6 8 5 x 41 2 6 34 9 5 5 x 51 5 7 82 2 3 3 5 x 62 1 0 02 6 5 7 5 可见，本文的分支定界算法比文献【1 3 】的分支定界算法好很多。 港u 集装箱装船作业问题的算法研究 第7 章结束语 7 1 总结 第7 章结束语 集装箱运输是现代最重要的运输方式，而集装箱港口在其中是重要的一个环 节。目前，各种设备被单独研究得很多，但联合起来的研究还很少。而将多种设 备联合起来考虑才能更有效地优化资源配置、减少运输成本。 本文研究了一个较复杂的港口集装箱装船问题，首先奉文先回顾了已有的一 些港口设备调度问题的研究，再自行提出一个港口集装箱装船问题的模型，给出 问题的特点，限制条件，以及相应的数学模型。然后，本文采用禁忌搜索加分支 定界的方法求解此问题，用禁忌搜索求优先顺序，同时用分支定界确定集装箱的 取出方法。在集装箱取出调度问题里提出了一个非常有效的下界计算方法，得到 了明显的效果。 文章最后实验部分，通过随机化生成了实验数据，实验结果显示对用贪心算 得的初始解有较大的改进。由于本问题由本文作者自行提出，目前没有可作比较 的其它文献，但是本文的禁忌搜索算法稍加修改后可以应用到文献【4 】的港口集 装箱装卸设备联合调度问题的求解，而本文的分支定界算法可以直接应用到求解 文献【1 3 】的集装箱倒箱位置问题。因此对这两个问题分别进行了横向对比，实验 表明，禁忌搜索得到的结果比文献 4 1 1 5 】的结果都要好，而分支定界的效果比文 献【1 3 】的分支定界算法要好很多，因为本文提出的l o w e rb o u n d 比文献【1 3 】好很多。 7 2 进一步研究方向 在集装箱堆场中取出所有集装箱的方法只能处理较小规模的情况，在堆场 y c 设备和运输设备a g v 间的合作做得还不够好。可以尝试其他的启发式方法 代替分支定界法，虽然求得的是近似解，但可以处理更大规模堆场的取箱问题。 还可以尝试y c 调度和a g v 调度同时进行搜索( 本文的做法是先a g v 调度再 y c 调度) 。 本文研究的只是一种港口的布局，而且为了简化问题做了很多假设，因此本 港口集装箱装船作业问题的算法研究 第7 章结束语 论文提出的算法对这些因素有依赖性。以后的研究可以尝试针对不同的假设和港 口布局，也可以考虑多个港口问的调度问题。 港口集装箱装船作业问题的算法研究参考文献 参考文献 【11s t e e n k e nd ，v o bs a n ds t a h l b o c kr c o n t a i n e rt e r m i n a lo p e r a t i o na n d o p e r a t i o n sr e s e a r c h ac l a s s i f i c a t i o na n dli t e r a t u r er e v i e w o rs p e c t m m ，2 0 0 4 ， 2 6 ：3 4 9 【2 】s t a h l b o c kra n dv o bs o p e r a t i o n sr e s e a r c ha tc o n t a i n e rt e r m i n a l ：al i t e r a t u r e u p d a t e o rs p e c t r u m ，2 0 0 8 ，3 0 ：1 5 2 【3 】m e e r s m a n sp j m ，w a g e i m a n sa p m e f f e c t i v ea l g o r i t h m sf o ri n t e g r a t e d s c h e d u l i n go fh a n d l i n ge q u i p m e n ta ta u t o m a t e dc o n t a i n e rt e r m i n a l s e c o n o m e t r i c i n s t i t u t er e p o r te l ，2 0 01 ，l9 【4 】黎俊瑜港1 3 集装箱装卸设备联合调度问题的算法研究硕士论文中山大 学2 0 0 6 【5 1 林祺颖使用束搜索解决港口集装箱装卸设备联合调度问题硕上论文中 山大学2 0 0 7 【6 】k a n gh u i - g u i ，z h o up e n g f e i r e s e a r c h o np r o g r a m m i n go fc r a n e v e h i c l e s c h e d u l i n gf o rl o a d i n gc o n t a i n e r s h i p j o u r n a lo fd a l i a nu n i v e r s i t yo f t e c h n o l o g y , 2 0 0 6 ，4 6 ( 3 ) ：3 7 2 3 7 9 【7 】z e n gq i n g - c h e n g ，y a n gz h o n g z h e n at w o p h a s et a b us e a r c ha p p r o a c ht o s c h e d u l i n go p t i m i z a t i o ni nc o n t a i n e rt e r m i n a l s j o u r n a lo fm a r i n es c i e n c ea n d a p p l i c a t i o n ，2 0 0 7 ，6 ( 2 ) ：4 4 5 0 8 】曾庆成，杨忠振集装箱码头卸船作、i k 调度方案的两阶段禁忌搜索算法交 通运输工程学报，2 0 0 7 ，7 ( 2 ) ：1 0 9 1 2 2 【9 】l uc h e n ，n a t h a l i eb o s t e l ，p i e r r ed e j a x ，j i a n g u oc a i ，l i f e n gx i at a b us e a r c h a l g o r i t h mf o rt h ei n t e g r a t e ds c h e d u l i n gp r o b l e mo fc o n t a i n e rh a n d l i n gs y s t e m si n am a r i t i m et e r m i n a l e u r o p e a nj o u r n a lo fo p e r a t i o n a lr e a s e a r c h ，2 0 0 7 ， 1 8 1 ：4 0 5 8 【10 】h e n r yy k l a u ，y i n gz h a o i n t e g r a t e ds c h e d u l i n go fh a n d l i n ge q u i p m e n ta t a u t o m a t e dc o n t a i n e rt e r m i n a l s a n n a l so f o p e r a t i o n sr e s e a r c h ，2 0 0 8 ， 4 n 港口集装箱装船作业问题的算法研究参考文献 l5 9 ：3 7 3 3 9 4 e b r uk b i s h am u l t i p l e - c r a n e c o n s t r a i n e ds c h e d u l i n gp r o b l e mi nac o n t a i n e r t e r m i n a l e u r o p e a nj o u r n a lo f o p e r a t i o n a lr e s e a r c h ，2 0 0 3 ，1 4 4 ：8 3 - 1 0 7 k a ph w a nk i m ，y o u n gm a np a r k ，k w a n g r y u lr y u d e r i v i n gd e c i s i o nr u l e st o l o c a t ee x p o r tc o n t a i n e r si nc o n t a i n e ry a r d s e u r o p e a nj o u r n a lo fo p e r a t i o n a l r e s e a r c h ，2 0 0 0 ，1 2 4 ：8 9 1 0 1 k a ph w a nk i m ，g y u - p y oh o n g ah e u r i s t i cr u l ef o rr e l o c a t i n g b l o c k s c o m p u t e r s & o p e r a t i o n sr e s e a r c h ，2 0 0 6 ，3 3 ：9 4 0 9 5 4 c e n ka y d i n i m p r o v e dr e h a n d l i n gs t r a t e g i e sf o rc o n t a i n e rr e t r i e v a lp r o c e s s m a s t e rt h e s i s s a b a n c iu n i v e r s i t y 2 0 0 6 w a t a n a b e1 c h a r a c t e r i s t i c sa n da n a l y s i sm e t h o do fe f f i c i e n c i e so fc o n t a i n e r t e r m i n a l - - a na p p r o a c ht ot h eo p t i m a ll o a d i n g u n l o a d i n gm e t h o d c o n t a i n e ra g e ， m a r c h1 9 9 1 ，3 6 - 4 7 c a s t i l