文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 交通运输 > 模拟退火算法在装箱问题中的应用
侵权投诉

模拟退火算法在装箱问题中的应用

装箱问题是个NPC问题^[1],该文采用了模拟退火算法解决这一问题。文中给出了数学模型,模拟退火算法的步骤并结合实例进行了收敛性分析.算法理想能迅速得出配装方案。

l SN 1 0 - 0 4 S 9 3 4 0

E-ma h e u C C . t n i d C Cne. c

Co u o ld ea dT c n lg电脑知识与技术 mp ̄r Kn we g n e h oo y Vo . No 5 F b u r 01, P. 1 9 1 81 1 6, ., e r a y 2 0 P 1 7, 1

h t: w w. n sn t a t/ w d z .e . p/ c Te: 6—— 9O 3 5 09 4 1+8 551 56 96 69 6

模拟退火算法在装箱问题中的应用 贾权向 (州交通大学交通运输学院,肃兰州 7 0 7 )兰甘 30 0

摘要:箱问题是个 NP问题【该文采用了模拟退火算法解决这一问题。文中给出了数学模型,拟退火算法的步骤并结合实例装 C ,模 进行了收敛性分析 .法理想能迅速得出配装方案。算 关键词:拟退火;模收敛性中图分类号: 6 U1 9文献标识码: A文章编号: 0 9 3 4 (0 0 0—1 7 - 1 1 0— 0 4 2 1 )5 1 9 0

在货物的运输中配装是关键㈣货物的装配问题是个 N C问题 _当大规模地进行货物选择装箱就会使得搜索空间以 2的指数, P l 1, 倍规模扩大,算时间也不断增加,拟退火算法是局部搜索算法的扩展,不同于局部搜索之处是以一定的概率选择邻域中费用计模它值大的状态。理论上来说,是一个全局最优算法利用模拟退火算法来解决装箱问题是个有效办法,法收敛迅速,时少,从它。算用解的质量高,满足现实要求。能

1装箱问题的数学模型【 设有 n批待装配的货物 Bf 1,…n,重为 P,积为 v,要将其配装的集装箱内,装箱的静载重为 P容积为 V,如何 .,3 ) i 2 _其。体 .需集,则 装配货物使集装箱载重最大以静载重量最大为优化目标建模型 其中变量含意如下 『 1件货物被选中,装车当第z 一

f第,物未被 件货 0当选中,装车不

P表示第 i货物的重量;,示第 i货物的体积; 件 v表件 P表示允许装货的总重量; V表示允许装货的总体积。

mx= aZ∑∑P p j j -丑

∑ =

V

口 1=口…或, ,

1

2算法的实现 21关键技术与参数 .

目标函数:x px+ 2+ 3+p 4 s+ 66 f ) 1 px px 4+p 5 px (= l 2 3 x x 降温方法: tO9 9 t *.。= 9新解产生方法:随机选一个货物,此货物已装车则将其去除,没装车则将其装车。若若 内循环终止准则:指定温度下当循环次数达到 k 0 0次时终止。在=1 0

算法终止规则:

零度法[模拟退火算法的最终温度为零,而最为简单的原则是:出一个较小的正数 (算例取 O 0 )当温度小于这个数 2 1:因给本 . 1, 0 时,法停止,算表示已经达到最低温度。 22算法流程 i . s 1

S E 1初始解 x (,,, 00没有任何货物装车, l 0初始温度 ) TP=0 0,, 0 0 ) t O(=

S E 2内循环是否执行了 10 TP 0 0次,执行了 10若 0 0次则转 S E ;则从临域 Nx随机生成一个解 x,算 d=( )f ) T P3否 () 0计 ff 0一(; x x若 d> O则 x x,则若 epd/>a dm(,时, x x;复 S E。 f=,= O否 x ( t rn o 01则= O重 f) ) T P2 S E =* . 9 tO0 1终止计算; T P 3 tt09;< .0, 9若否则,回到 S E 。 T P2

3算例分析 31算例[ . 3 1

有 6件货物,量分别为 8,I,t1t1t8体积分别为 lm,2 8 1 m,6 9 装箱的标记体积为 5 静载重质 t1t7,3,5,t O 1m,m,5 1m,m集 2m,为 4 t怎样进行拼箱配装才能使集装箱的静载重得到最大利用。 5,应 (下转第 18 11页 )

收稿日期: 0 9 1 3 2 0—1—2

本栏目责任编辑:唐一东

人工留镌及识别技术

17 19

模拟退火算法在装箱问题中的应用

第1页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email