集装箱装载问题研究

《集装箱装载问题研究》由会员分享，可在线阅读，更多相关《集装箱装载问题研究（51页珍藏版）》请在金锄头文库上搜索。

1、天津大学 硕士学位论文 集装箱装载问题研究 姓名：孟冬梅 申请学位级别：硕士 专业：计算机应用技术 指导教师：张钢 2002.1.1 集装箱装载问题研究 摘要 集装箱装载问题是货物运输过程中普遍存在的一个重要坏节。给出一个合理 的装箱方案以提高集装箱的空间利用率，将会给许参行业带来巨大的经济效益。 然而，到目前为止，我们只能见到有限的几种算法歹本文的主要目的是研究集装 集装箱装载问题属于N P 完全问题，在一个合理时间内无法确定最优解。本 文回顾了集装箱装载问题及其相关的裁剪问题、背包问题等的经典算法，并针对 算法存在的问题提出了一种全新的填充机制一整体装填策略。通过这种策略，可 以有效减少集

2、装箱空间的浪费，同时大大缩小算法的搜索空间，从而使算法的时 间效率明显提高。这种策略，结合剩余空间搜索策略，为弱异类集装箱装载问题 提出了一种新的思路。 空隙向来是集装箱装载问题的难点。本文通过空隙积累策略，在装箱时充分 利用了剩余空间填充过程中浪费掉的许多空隙，进一步提高了算法的有效性。 本文的问题背景来自于广东科龙公司的家电产品的装箱问题。 f 本文对提出的装箱算法进行了测试，测试的数据耿自同类问题的一批标准数 掘。同时，本文给出了本算法与同类问题的四种经典算法的比较。结果表明，本 文给出的算法得到了令人满意的结果。 本文对使用混合遗传算法解决集装箱装载问题进行了尝试。 炳H 埘二何以篡蒙

3、椭鳓示芗指戥僦矽 竹池关键嗯：鑫篓箩装彰徊醪瓴剪与装填问萝空间利用率；弱异类；肩发式 算法；N P 一完全问题 、77 A b s t r a c t l “ h eC o n t a i n e rL o a d i n gP r o b l e m ( C L P ) i sa ni m p o r t a n tp a r te x i s t i n g in t h ec a r g ot r a n s p o r t a t i o n I fo n ec a ng i v ear e a s o n a b l el o a d i n gp a t t e r n s oa

4、st oin c r e a s et h ev o l u m eu t i l i z a t i o no ft h ec o n t a i n e r ，i tw i l lb r i n g g t e a tp r o f i t st om a n yi n d u s t r i e s O n l Ya f e wa l g o r it h m s ，h o w e v e r ，d e a 】 w i t ht h isp r o b l e mu pt on o w T h em a i np u r p o s eo ft h i sp a p e ri s t o

5、s t u d y h o wt op a c kt h et h r e ed i m e n s i o n a lr e c t a n g u l a rb o x e si n t ot h ec o n t a i n e t M e a n w h i l e ，i tp r e s e n t san e wa n de f f i c i e n th e u r i s t i ca l g o r i t h mb a s e do n i n t e g r a t e dp a c k i n gs t r a t e g yt ot h e w e a k l yh

6、 e t e r o g e n e o u s p r o b l e mo l t h e c o n t a i n e rl o a d i n g T h e C L Pi sa N P C o m p l e t ep r o b l e m ，w h i c h c a n n o t g i v e a n o p t i m a l s o l u t i o nw i t h i nar e a s o n a b l et i m e1 i m i t I nt h i sp a p e r ，w er e v i e wt h e c l a s s i ca l g

7、o r i t h m so ft h eC L Pa n dt h er e l a t e dp r o b l e m ss u c ha sc u t t i n g p r o b l e m s ，k n a p s a c kp r o b l e m sa n d s oo n N o t i c i n gt h ep r o b l e m so c c u r r i n g a tt h o s e a l g o r i t h m s ，t h ep a p e rp r o p o s e s an e w p a c k i n gs t r a t e g y

8、 一一 i n t e g r a t e dp a c k i n gs t r a t e g y T h e r e s u l ts h o wt h a t b y m e a n so ft h is s t r a t e g y ，w ec a nr e d u c et h ew a s t a g eo ft h ec o n t a i n e rs p a c e ，s h r i n kt h e s e a r c hs p a c eo ft h ea l g o r it h m ，s ot h a ti m p r o v et h et i m ee f f

9、 i c i e n c yo l t h e a l g o r i t h m T h i ss t r a t e g y ，c o m b i n e dw i t h t h es t r a t e g yo fs e a r c h i n gt h e r e s i d u a l s p a c e s ，p r e s e n t s an e wi d e at ot h e w e a k l yh e t e r o g e n e o u s s i t u a t i o no ft h eC L P T h eg a p sa r et h ed i f f

10、i c u l t i e si nt h eC L P T h i sp a p e ra l s op r e s e n t s a n o t h e rs t r a t e g y - - g a p a c c u m u l a t i n gs t r a t e g y B yu s i n gi t ，w ec a nr e c y c i e t h eg a p sp r o d u c e db yt h ep a c k i n gp r o c e d u r es oa st om a k et h ea l g o r it h m m o r ee l f

11、 i c i e n t T h eb a c k g r o u n do ft h isp a p e ri st h ep a c k i n gp r o b l e mo ft h eG u a n g D o n g K E L O Nc o m p a n y T h ep a p e rg i y e st h et e s tr e s u l to ft h en e wa l g o r i t h mb yc o m p a r i n gw i t h o t h e rf o u rc l a s s i ca l g o r i t h m su n d e rt

12、 h es a m ed a t as o u r c e I ts h o w st h a t t h en e wa l g o r i t h mism o r ee f f i c i e n tt h a no t h e r s T h ep a p e ra l s oc a r r i e sO U ta n e x p e r i m e n t i ns o l v i n gt h eC o n t a in o r L o a d i n gP r o b l e mb yG e n e t i cA l g o r it h m s M e a n w hi1e ，

13、t h ep a p e rgiy e sac o m p u t e r b a s e dC L Pp r o g r a m T h isp r o g r a m p r e s e n t sa ni n p u ti n t e r f a c ea n da no u t p u tp a r to fat h r e e d i m e n s i o n a l g r a p hr e p r e s e n t a t i o no ft h el o a d i n gp a t t e r n K e yw o r d s ：t h eC o n t a i n e

14、rL o a d i n gP r o b l e m ；C u t t i n g P a c k i n gP r o b l e m s s p a c e u t i1iz a t i o n ： w e a k l yh e t e r o g e n e o u s ：h e u r i s t i ca l g o r it h m N PC o m p l e t ep r o b l e m 第一章绪论 第一章绪论 1 1 问题背景 广东科龙电器股份有限公司是一家以生产电冰箱、空调等家用电器产品为主 的大型企业。公司生产出来的冰箱、空调等产品被放入某种规格的长方体盒子， 然后

15、通过集装箱运送到各销售地区。集装箱内通常要放入几种不同规格的盒子， 如空调的室内机、室外机、配管，或者几种容量不同的冰箱等。出于家用电器本 身的特性，存放电器的盒子在集装箱内的摆放要求正面向上。在这个前提下，盒 子要尽量紧密地放入集装箱内，以提高集装箱的空间利用率，降低运输成本。同 时，由于人力、物力及家电本身的要求，盒子只能一次性地装入，而不能反复装 卸。 到目前为止，将盒子装入集装箱的工作完全依靠人工调度来进行。调度员在 现场凭借经验估计被装入的几种盒子的数量及所需集装箱数，并开出装箱单据。 然后，装箱工人按照单据将盒子放入集装箱。这种操作程序存在两方面的问题： 一方面，虽然调度员经验丰富

16、，可是，单凭直观经验估计出来的数字却很难保证 集装箱的高利用率，因而经常出现集装箱未被装满的情形：另一方面，装箱工人 在装箱时没有任何装箱方案的依据，完全是随意地或经验式地将盒子装入集装箱 内。这种装载的随意性同样造成由于盒子摆放不合理而导致的集装箱低利用率的 问题，甚至经常出现装箱单上的盒子不能装入集装箱而重新改写单据的现象。科 龙公司致力于生产、销售的科学化管理，然而，在货物运输环节中的这种人工装 箱的方式无形中增加了产品的成本，降低了企业的效益。 天津海运公司和天滓正元食品有限公司在货物装运过程中存在着同样的情 况。事实上，集装箱装载问题是货物运输中的重要环节，是一类具有广泛行业背 景的问题。如何摆脱人工操作的落后局面，同时给出一个合理的布局及装载方案， 以提高集装箱的空间利用率和装箱的效率，是我们的主要目标。实现这些目标， 将会给许多行业带来巨大的经济效益。 为此，本文将就上述环节中存在的两个问题着力进行如下的工作：寻求种 有效的集装箱装载算法，将几种不同规格的长方体盒子合理有效地放入集装箱，