目前，物流业正处在快速发展的时期，集装箱运输将会有大幅度的增长。集装箱装载作为物流配送过程中的一个关键性环节，可提高配送业务的自动化水平、提高货物装载的优化程度、提高配送业务的工作效率和规范业务流程等。
　　从二十世纪70年代初开始，集装箱装载问题就引起了广泛的研究和探讨^[1]。装箱问题就是将不同尺寸的物品摆放入有一定容量的容器中，以获得某种最佳的效益。从计算复杂性理论来讲，装箱问题属于NP完全问题^[2]，求解极为困难。
　　遗传算法采用了生物进化论的思想，通过自然选择和适者生存的竞争策略来求解优化问题^[3]；模拟退火起源于统计物理学方法，并首先被Kirkpatrick等引入组合优化领域^[4]。遗传算法的全局搜索性能较强，但是其容易过早收敛，而且在进化后期搜索效率较低，种群的进化缓慢；而模拟退火算法" title="模拟退火算法">模拟退火算法具有较强的局部搜索能力，并且能使搜索过程避免陷入局部最优解，但是把握搜索过程的能力不强，运行效率不高。本文通过将模拟退火的思想引入遗传算法，使两者有效地结合，缓解了遗传算法的选择压力，增强了遗传算法的全局收敛性，避免在搜索过程中陷入局部最优。
1 遗传算法
　　遗传算法最早由美国Michigan大学的J. Holland教授提出，起源于上世纪60年代人们对自然和人工自适应系统的研究^[5]，是基于Darwin进化论和Mendel的遗传学说的一种全局优化概率搜索算法，它模拟了生物界中的生命进化机制，在人工系统中实现特定目标的优化。对于复杂的优化问题，遗传算法无需建模和进行复杂的运算。与传统的搜索算法不同，遗传算法把优化问题的解的搜索空间转化为遗传空间，从代表问题可能潜在解集的一个种群开始，其中种群中的每一个体对应问题的一个解，称为染色体。初代种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，按预先根据目标函数确定的适应度函数计算各个体对问题环境的适应值，再根据个体的适应值对个体对应的染色体进行选择，使适应性好的染色体比适应性差的染色体有更多的繁殖机会；然后进行交叉、变异等遗传操作产生新一代群体。如此循环，逐步向优化的种群进化。
　　遗传算法的主要特点是：遗传算法的处理对象不是参数本身，而是对参数集进行编码的个体；遗传算法采用同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估；遗传算法仅使用问题的目标函数进行工作，不需要其他的先决条件或辅助信息；遗传算法不是采用确定性规则进行工作，而是采用概率的变迁规则来指导其搜索方向；遗传算法具有隐形并行性，可以在较大的解空间迅速寻优。
　　标准的遗传算法求解过程如下：
　　(1) 初始化遗传算法的控制参数，如群体规模N、变异概率p_m、交叉概率p_c；
　　(2) 随机产生初始解群p(t)={p₀ p₁ p₂…p_n}，个体的数目一定，每个个体表示为染色体的基因编码；
　　(3) 计算群体中每个个体的适应函数" title="适应函数">适应函数值；
　　遗传算法在搜索过程中基本不利用外部信息，仅以适应度函数为依据，利用种群中每个个体的适应度值进行搜索。因此适应度函数的选取至关重要，将直接影响遗传算法的收敛速度以及能否找到最优解。解的好坏用适宜度函数值的大小评价，适应度函数值越大，解的质量越好。
　　(4) 根据个体的适应度选择复制再生个体，适应函数值大的个体的复制概率大；
　　选择是指以一定的概率从种群中选择优胜个体，淘汰劣质个体的操作。选择的过程是一种基于适应度的优胜劣汰的过程，是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。
　　(5) 按照一定的交叉概率和交叉方法,对现有解群中的个体实施交叉操作,生成新个体；
　　交叉是指对两个相互配对的染色体以某种方式相互交换部分基因，从而形成两个新的个体，交叉是遗传算法的核心。
　　(6) 按照一定的变异概率和变异方法,对交叉后的个体进行变异操作；
　　变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因替换，从而形成一个新的个体。
　　(7) 由交叉和变异产生了新一代种群，若满足收敛条件，遗传进化过程结束；否则转(3)。
2 模拟退火算法
　　模拟退火算法是基于Monte Carlo迭代求解法的一种启发式随机搜索算法，它模拟固体物质退火过程的热平衡问题与随机搜索寻优问题的相似性来达到寻找全局最优或近似全局最优的目的。在搜索最优解的过程中，模拟退火法除了可以接受优化解外，还用一个随机接受准则(Metropolis准则)有限度地接受恶化解，并且接受恶化解的概率慢慢趋向于0，这使得算法有可能从局部极值区域中跳出，即可能找到全局最优解，并保证了算法的收敛性。
　　模拟退火算法的求解过程如下：
　　(1) 随机产生初始解x₀；
　　(2) 初始化退火温度T₀；
　　(3) 在温度TK下执行如下操作:
　　·产生新的可行解x′,x′为x的邻解；
　　·计算评价函数f(x′)和f(x)的差值△f=f(x′)-f(x)；
　　·以min{1,exp(-△f/T_k)}＞random[0,1]的概率接收新解，其中random[0,1]是[0,1]之间的随机数。若达到温度Tk的平衡状态转(4)，否则转(3)；
　　(4) 按一定方式降低温度,可定义下降函数为T_k+1=αT_K,k+1→k，其中α∈[0,1]；
　　(5) 若满足收敛判据,退火过程结束；否则转(3)。
　　通过以上分析可知,在模拟退火过程中,其退火温度控制着求解过程向最小值的优化方向进行,同时它又以概率exp(-△f/T_k)接收劣质解,因此算法可以跳出局部极值点。只要初始温度足够高,退火过程足够慢,算法能够收敛到全局最优解。
3 模拟退火遗传算法
　　虽然遗传算法使用简单、鲁棒性强、应用范围甚广，但是它本身也存在着许多不足，尤其是容易过早收敛，使搜索陷入局部最优解，因此本文把模拟退火引入到遗传算法中。本文的模拟退火遗传算法如下：
　　(1) 初始化控制参数：
　　N为群体规模；p_m为变异概率；T₀为退火初始温度；α为温度冷却参数；
　　(2) 随机产生初始解群；
　　(3) 对现有解群实施如下操作,直至产生出下一代新的群体：
　　· 评价群体中每个个体的适应函数值f(x_i)，i=1,2,…,N,本文中以空间利用率作为适应度函数；
　　· 采用轮盘赌选择法对个体进行选择；
　　轮盘赌选择法的基本思想是：生成一个随机数γ∈[0,1]，并且计算个体的相对适应度值pi=fi/∑fi，如果p₀+p₁+…+pi-1＜γ≤p₀+p₁+…+pi，则第i个个体被选择到下一代。可见，个体的适应度值越大被选择到下一代的机会也越多。
　　·对选择复制后的个体实施交叉操作，随机选择两个个体x_i和x_j进行交叉操作，并且计算两个新个体x′_i和x′_j的适应函数值f(x′_i)和f(x′_j)；生成一个[0,1]之间的随机数random,以min1,exp(-△f/T_k)＞random[0,1]的概率接受新的解，即接受新个体。
　　·对交叉后的个体进行变异操作,按第三步中的方法决定是否接收变异后的解；
　　(4) 若满足收敛条件,进化过程结束；否则T_k+1=αTK,转(3)。
　　模拟退火遗传算法首先利用轮盘赌选择方法，淘汰了适应度较低的个体。而交叉操作是遗传算法中的核心，寻优过程主要通过它实现，模拟退火遗传算法吸取了这一思想,对选择后的个体均实施交叉操作,并且把交叉和变异后的子代与父代竞争，通过Boltzmann机制来接收子代，不但有利于优良个体的保留，同时防止了早熟收敛的问题。随着进化过程的进行，温度逐渐下降，接收劣质解的概率也逐渐减小，有效地利用了模拟退火算法的爬山特性，提高了算法的收敛速度。
4 集装箱装载实例与算法分析
　　在实际应用中，为了求解的快速性和实用性，人们通常采用一些启发式算法" title="启发式算法">启发式算法^[6]来求解装箱问题。为了评价模拟退火遗传算法的性能，将模拟退火算法和启发式算法进行比较，分别用来求解装箱问题。
　　本文使用DELPHI程序进行模拟装箱，所使用的模拟退火遗传算法的控制参数选取如下：群体规模N=100，变异概率p_m=0.01，初始温度T₀=1000，冷却参数α=0.9；待装物品为洗衣机散件，单位为毫米，其体积以及数量如表1所示；布局空间采用规格为11.96×2.35×2.69的集装箱，单位为米。物品装箱过程中，充分考虑到物品的摆放方式，以及是否可以置底，分别利用启发式算法以及本文的模拟退火遗传算法进行装箱，得到的结果如表2、表3所示，装载效果如图1、图2所示。其中X₀，Y₀,Z₀表示物品在集装箱中的位置。
　　本例中的待装物品共有712件，其中需要装载500台主机，7台30#，1台17#，45台11#，6台9#，10台3#，139台2#，4台8#。
　　启发式算法使用知识规则，搜索速度快，搜索方向相对明确，但是知识规则的使用使得搜索空间的范围急剧缩小，因此求解结果通常会有很大的局限。利用文献^[7]中的启发式算法装载物品，共布入645件物品，空间利用率为88.3%。装箱结果如表 2、图1所示。

　　模拟退火遗传算法把模拟退火和遗传算法有效地结合起来，既加速了算法的收敛速度又避免陷入局部最优解。利用模拟退火遗传算法装载物品，物品全部布入，空间利用率为92.6%。装箱结果如表 3、图2所示。