基于SP的模拟退火算法在装箱问题中的应用.doc

doi:10.3969/j.issn.1005-152X.2011.10.032基于S P 的模拟退火算法在装箱问题中的应用余蕾（福州大学阳光学院,福建福州350015）[摘要]在传统模拟退火算法的基础上，对装箱问题的优化算法进行 doi:10.3969/j.issn.1005-152X.2011.10.032 基于 S P 的模拟退火算法在装箱问题中的应用 余 蕾 （福州大学 阳光学院,福建 福州 350015） [摘 要]在传统模拟退火算法的基础上，对装箱问题的优化算法进行了研究。结合装箱问题的具体特点，采用 SP 序列对来 描述模块间的拓扑关系，并通过精细的模拟退火策略（精细的降温策略，提前退出策略），以及增量式的新解评估策略对算法进行 优化。试验结果表明，相比传统的模拟退火框架，改进的算法能够取得较好的运行时间与面积利用率。 [关键词]装箱问题；模拟退火算法；序列对；精细退火策略；增量式新解评估 [中图分类号]O223 [文献标识码]A [文章编号]1005- 152X（2011）10- 0106- 05 Application of SP-Based Simulated Annealing Alogrithm in Bin Packing Problem YU Lei (Sunshine College, Fuzhou University, Fuzhou 350015, China) Abstract: A new algorithm to solve the bin packing problem is formulated within the simulated annealing framework. Sequence pair is adopted to represent the topological relationship among the modules. In view of the characteristics of the bin packing problem, the paper improves the algorithm by incorporating the elaborate annealing strategy and a novel incremental solution evaluating algorithm. The experiment that follows shows that, compared with the traditional framework, the algorithm can arrive an a better area utility rate in shorter time. Keywords: bin packing problem; simulated annealing algorithm; sequence pair; elaborate annealing strategy; incremental solution evaluation 空间分解的启发式算法来求解二维的空间装箱问题。文献[2] 以及文献[4]都采用了定序规则、摆放规则、定位规则和空间合 并的策略，提出了一种基于空间分解的启发式算法。文献[15] 研究并总结了货物配送过程中提高容积利用率的三个规律。 文献[9]利用了遗传算法求解装箱问题。在将编码转化为装箱 问题时利用三叉树的结构，但存在着在每次产生新解时，都要 进行译码即重新布局，导致效率不高的缺陷。 模拟退火算法提出于 20 世纪 80 年代初，其思想源于固 体退火过程，根据一定的概率接受目标函数值不太好的状态， 使得结果跳出局部最优解，达到全局最优解。文献[13]将 SP 应 用到模拟退火算法中，将 SP 转化为布局时的时间复杂度为 O (n2)，存在着较高的时间复杂度问题。文献[11]采用了启发式的 布局结果作为模拟退火算法的初始布局方案。但是在模拟退 火中没有利用有效的布局表示，致使解的有哪些信誉好的足球投注网站空间太大。 本文在传统模拟退火算法基础上，通过对序列对(SP)的理 论分析与实验，说明利用 SP 与 SA 相结合解决装箱问题的适 应性与优越性，同时提出了精细的模拟退火策略及增量式的 新解评估方法，有效地缩短了求解的运行时间。 1 引言 在经济日益全球化的今天，物流活动越来越显示出它的 重要性，物流相关技术的应用和发展受到越来越多的重视。如 何提高物流效率、降低物流成本就成为一个很重要的实际问 题。物流装箱作为物流配送过程中的一个关键性环节，对降低 配送成本，提高流通配送效率，提升经济效益都有重要意义。 装箱问题(Bin Packing problem，简称 BP)广泛的应用于物 流配送中的铁路货车车