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

开篇：润墨网以专业的文秘视角，为您筛选了一篇模拟退火算法在装箱问题中的应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

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

关键词:模拟退火;收敛性

中图分类号:U169文献标识码:A文章编号:1009-3044(2010)05-1179-01

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

1 装箱问题的数学模型[3-4]

设有n批待装配的货物Bi(i=1,2,3…n),其重为pi,体积为vi,需要将其配装的集装箱内,集装箱的静载重为P,容积为V,则如何装配货物使集装箱载重最大。

以静载重量最大为优化目标建立模型

其中变量含意如下

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

2 算法的实现

2.1 关键技术与参数

目标函数:f(x)=p1x1 + p2x2 + p3x3 + p4x4 + p5x5 + p6x6

降温方法:t=t*0.999。

新解产生方法:随机选一个货物,若此货物已装车则将其去除,若没装车则将其装车。

内循环终止准则:在指定温度下当循环次数达到k=1000次时终止。

算法终止规则:

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

2.2 算法流程[5]

STEP1 初始解x=(0,0,0,0,0,0)没有任何货物装车,t=100(初始温度)

STEP2 内循环是否执行了1000次,若执行了1000次则转STEP 3;否则从临域N(x)随机生成一个解x0,计算df=f(x0)-f(x);若df>=0,则x=x0,否则若exp(df/t)>random(0,1)时,则x=x0;重复STEP 2。

STEP 3t=t*0.999;若t

3 算例分析

3.1 算例[3]

有6件货物,质量分别为8t,11t,7t,13t,15t,8t体积分别为10m3,12m3,8m3,15m3,16m3,9m3集装箱的标记体积为52 m3,静载重为45t,应怎样进行拼箱配装才能使集装箱的静载重得到最大利用。

算例模型:

经计算x1=x4=x5=x6=1,x2=x3=0,Z=44结果令人满意。

3.2 算法收敛性

从图1可以看出随着跌倒次数的增加货车载货总重迅速向最大值收敛,最后停留在44t处不再波动。因此算法收敛迅速,令人满意。

4 结论

实例数据结果表明,此算法收敛速度快,用时少。充分体现了模拟退火算法的优点,以一定的概率接受质量差的解,即可以跳出局部最优解。因此,此模拟退火算法能有效的解决装箱问题。

参考文献:

[1] 卜雷,蒲云,刘海旭,等.集装箱中零担货物合理混载的遗传退火进化算法[J].世界科技研究与发展,2002,24(6):88-91.

[2] 冯玉蓉, 模拟退火算法的研究及其应用[D].昆明:昆明理工大学,2005.

[3] 付永军,安晨.改进有序组合树法在铁路普通零担货物拼箱配装中的应用[J].铁道货运,2007(9):12-14,52.

[4] 张天伟.基于登山法的铁路零担货物轻重配装的研究[J].哈尔滨铁道科技,2006(03):02.

[5] 邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,2009.

[6] 周颖,零担货物配装模与算法研究[J].铁道运输与经济,2006,28(7):32.