资源描述：
《基于遗传算法的集装箱单箱三维装载优化问题_卜雷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第25卷,第4期中国铁道科学Vol25No42004年8月CHINARAILWAYSCIENCEAugust,2004文章编号:10014632(2004)04010804基于遗传算法的集装箱单箱三维装载优化问题1234卜雷,袁新江,蒲云,常军乾(1西南交通大学交通运输学院,四川成都610031;2乌鲁木齐铁路局运输处,新疆乌鲁木齐830016;3西南交通大学研究生院,四川成都610031;4铁道部科学院运输及经济研究所,北京100081)摘要:研究应用改进遗传算法优化铁路集装箱单箱三维装箱问题,达到充分利用
2、集装箱装载质量或装载容积的目的。改进遗传算法中考虑货物放置方向、装载容积、装载质量及装载重心等约束条件,并结合方向及顺序约束采用巧妙的个体编码方法,结合装载容积、装载质量及重心约束构造合理的适应值函数。以16件货物装入20英尺箱为实例,应用改进遗传算法进行计算,计算结果为集装箱装载容积利用率为6318%,并且可以缩短计算时间一半以上。关键词:集装箱运输;三维装箱;遗传算法;优化中图分类号:U2943文献标识码:A在铁路集装箱运输中,将具有同一到站的货物记符号li,wi,hi,gi分别表示货物i(i=1,2,按照适当方式装载到同一集装箱中的装箱问题属于,n)的长、
3、宽、高、质量;V,G分别表示集装箱[1][2~6]NPhard问题,应用传统的优化算法随着问题的最大装载容积、最大装载质量。则问题的目标函规模的不断增大会产生时间维数灾难问题,不能够数为最大化函数:比较理想地对大规模装箱问题进行优化装载,而遗n传算法[1,2,7~10](简称GA)作为一种基于生物遗传maxz=(liwihii)V+(1-)(gii)Gi=1和进化机制的自适应概率优化技术,具有运算简(1)单、搜索过程灵活、搜索效率高以及隐含并行性等是0-1变量,当追求目标为容积利用率最特点,是一类可用于复杂系统优化计算的鲁棒搜索大时=1,当追求目标为装载质
4、量利用率最大时算法。本文结合铁路集装箱运输实际应用中的约束=0;i是0-1变量,若货物i装载则i=1,否条件,提出应用改进遗传算法优化集装箱单箱货物则i=0。三维装载问题。约束条件包括如下方面。(1)货物放置方向约束。货物只能水平旋转放1单箱装载优化问题描述置。(2)货物装载容积约束。货物装载总容积不得11目标函数及约束条件约定如下条件和要求:(1)货物简化为长方大于集装箱的最大装载容积。体,高度相等且均小于集装箱尺寸;(2)货物去往(3)货物装载质量约束。货物装载总质量不得同一到站;(3)货物以水平方向放置于集装箱中任多于集装箱的最大装载质量。一位置而不受配置位置限制
5、。则集装箱三维装载优(4)货物装载重心约束。货物装载应该使重心化问题描述为:在一定约束条件限制下,将一批货位于允许的范围内而确保整体稳定。物按照适当的装载方法装入同一集装箱中,使得集12货物装载遵循的方向次序原则装箱的容积利用率或装载质量利用率最大,从而增定义集装箱箱门所在端为后端,集装箱在坐标强对集装箱的合理有效使用。系中的位置关系如图1所示。则在集装箱中装载货收稿日期:20030717作者简介:卜雷(1975),女,山东蓬莱人,博士研究生。第4期基于遗传算法的集装箱单箱三维装载优化问题109物遵循以下原则:(1)依次沿左侧至右侧方向(即照
6、编码预处理进行解码;(4)货物在箱中的装载遵y轴方向)、前端至后端方向(即x轴方向)放置循所规定的方向次序原则。每一层;(2)沿下端至上端方向(即z轴方向)逐23适应值计算层放置。通过个体适应值的大小来评价群体中个体所对应装载方案的优劣,对于违反装载质量约束、装载容积约束和装载重心约束的个体,在求解其适应值的过程中要给予相应的惩罚以确保符合条件而较优gen的个体有较大的生存机会。第gen代中个体Sq的适应值fgen(q)计算:fgen(q)=z(q)-pengen(q)7图1集装箱在坐标系中的位置=z(q)-cgenmax[0,h(q)](3)=1nh1(q)=
7、liwihii-V(4)2问题的改进遗传算法i=1nh2(q)=gii-G(5)21集装箱最多装载层数计算及编码预处理i=1nn定义货物水平放置方向为货高与箱高相互平行h3(q)=X-b1=(gixii)gii-b1i=1i=1的放置状态,则集装箱最多装载层数M计算:(6)M=Hhi(2)nn在进行个体编码之前,做如下的编码预处理。h4(q)=a1-X=a1-(gixii)giii=1i=1(1)货物编号:
