一种求解集装箱装载问题的启发式算法.pdfVIP

计算机科学 2008Vol35 №8 　 一种求解集装箱装载问题的启发式算法 ) 1 2 1 1 陈端兵 　黄文奇 　尚明生 　傅 　彦 ( ) 1 ( ) 2 电子科技大学计算机学院　成都 6 10054 　 华中科技大学计算机学院　武汉 430074 　 摘 　要 　所谓集装箱装载问题 ,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器 ,其 目标是最大化 容器的积载率 。对这一问题 , 国内外学者利用不同的哲学思想 ,提出了诸如遗传算法 、模拟退火算法等求解算法 。本 文提出一种求解此问题的基于最大穴度优先原则的启发式算法 。算法中使用了两个重要的策略 :最大穴度原则和最 小边度原则 。用一些公开的算例对算法性能进行了实算测试 ,测试结果表明:算法所得结果的容器积载率高 ,是求解 集装箱装载问题的有效算法 。 关键词 　Packing 问题 ,集装箱装载 ,启发式算法 ,穴度 ,边度 　 Heuristic Algorithm f or Solving the Container Loading Problem C H EN Duanbing1 　HU AN G Wenqi2 　SHAN G Mingsheng1 　FU Yan1 ( School of Comp ut er Science ,U niver sit y of Elect ronic Science and Technology of China ,Chengdu 6 10054 ,China) 1 ( School of Comp ut er Science , Huazhong U niver sit y of Science and Technology ,Wuhan 430074 ,China) 2 　 Abstract 　The cont ainer loading p roblem i s t he p roblem of loading a series of boxes wit h different sizes into a fixed cu boid cont ainer . The obj ective i s to maximize t he volume utilization of t he cont ainer . Researcher s p ropo se many algo rit hm s such a s genetic algorit hm and simulat ed annealing to solve it based on different idea . Thi s p ap er p resent s a heu ri stic algorit hm ba sed on maximum caving degree fir st p rincip le for solving t hi s p roblem . Two import ant st rat egies are con sidered in t he algorit hm p ropo sed . One i s t he maximum caving degree p rinciple ,t he ot her i s t he minimum edge de gree p rincip le . The p erform