基于退火算法的物流配送网的求优研究

段敬民，常跃军，李赞祥，崔建明

(1.三门峡职业技术学院建筑工程系，河南三门峡472000;2.西南交通大学桥梁及结构工程系，成都610031;3.河南工程技术学校建筑工程系，河南焦作454000;4.长安大学信息工程学院，西安710064)

1 前言

模拟退火算法［1］(simulated annealing，SA)原理就是模拟在某个温度下，金属分子停留在能量小的状态时刻的概率要比停留在能量大的状态的概率要大。

模拟退火算法与爬山算法对比，爬山算法是一种简单的贪婪搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法的主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示:假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向哪个方向小幅度移动都不能得到更优的解。

爬山算法是完完全全的贪心算法，每次都以较小的步长选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火算法其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到D的移动。也许经过几次这样的不是局部最优的移动后会到达E点，于是就跳出了局部最大值A的范围。

图1 最优解搜索最优示意图Fig.1 Schematic diagram of search for the optimal solution

在物流的配送网络中［2］，存在寻优的网络方案，如果采用这种优选方案，对物流配送企业来说会节省资金，增加配送速度;对货物接收方来说能够在较为合理的时间内接收物品，从而节省生产成本或消费成本。

2 模拟退火算法数学描述

若

即移动后得到更优解，则总是接受该移动;若

即移动后的解比当前解要差，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)。这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。根据热力学的原理，在温度为T时，出现能量差为dE的降温的概率为P(dE)，可表示为

其中，k是一个常数，e表示自然指数，且dE＜0。

公式是指:温度越高，出现一次能量差为dE的降温的概率就越大;温度越低，则出现降温的概率就越小。又由于dE总是小于0(这是模拟退火的本质决定的)，因此dE/kT＜0，所以P(dE)的函数取值范围是(0，1)，随着温度T的降低，P(dE)会逐渐降低。

将一次向较差解的移动看做一次温度跳变过程，以概率P(dE)来接受这样的移动。

终止条件:设置一个接近于0的较小的值，例如 0.3。

3 模拟退火算法的程序语言描述

3.1 模拟退火算法流程

模拟退火算法流程如图2所示。

图2 模拟退火算法流程Fig.2 Process of simulated annealing

3.2 参数与函数定义

在计算程序中的各个参数与函数的定义说明如下:

J(y):在状态y时的评价函数值;Y(i):表示当前状态;Y(i+1):表示新的状态;r:用于控制降温的快慢;T:系统的温度，系统初始应该要处于一个高温的状态;T_min:温度的下限，若温度 T达到T_min，则停止搜索。

3.3 模拟退火算法伪代码

//函数exp(dE/T)的取值范围是(0，1)，dE/T越大，则exp(dE/T)也变大。

}

T=r* T; //降温退火 ，0＜r＜1。r越大，降温越慢;r越小，降温越快

/*

＊若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值

*/

i++;}

4 模拟退火算法在区域交通流预测示例

4.1 区域物流配送示例

图3为一简单配送网络图，该网络表示在一个区域中进行配送分配问题，等同于最优化问题，表述模型表达式见式(4)。

图3 配送网络图Fig.3 Network diagram of distribution and delivery

式(4)中，q为OD(origin-destination)量;xa为路线a上的流量;Ca为路线a的路阻函数。

用退火算法解决此类问题，假设道路损耗的时间和经济价值如(2，3，5，1，4)和(2，5，8，3，6)。

可行解采用0和1的序列表示，如i=(10101)表示选择1，3，5线路，不选择2和4。

4.2 计算进行步骤

第一步，初始化，假设初始解i=(11001)，初始温度为10℃，计算开始。

第二步，在温度T下局部搜索，直到“平衡”;降温时机用在同一温度下反复进行Metropolis［3］演算，假设次数为3，搜寻法则，随机改变某一位的0，1或交换某两位0，1的值。假设产生新解j=(11100)，f(j)=2+5+8=15＞13，所以接受新解。假设产生的新解j=(11010)，f(j)=2+5+3=10 ＜13，计算接受概率 P(T)=exp((10－13)/10)≈0.741，在(0，1)范围内产生一个随机数，如果随机数小于接受概率，则接受j为新解，否则不接受。

第三步，降温，假设温度降为T=T－1，如果没有达到结束标准，则返回第二步继续执行。

4.3 计算结果

通过以上步骤的计算，i=(10010)，即选择线路1和4作为最优解。存在2个最优的原因是结束过早，如果把成本计算进行的终止条件设置为0.03，则结果将是i=(00010)，即结果4为最优解。

5 结语

模拟退火算法同其他各类人工智能算法相似，是一种随机算法，该算法并不一定能找到全局的最优精确解，但是可以比较快地找到问题的近似最优解，这是由算法本身决定的。但是作为一种在物流配送路径中的最优预测模型，可以认为是比较好的工具。模拟退火算法缺点在于如果参数设置不当，很容易造成得到结果耗费大量的时间，这无疑近似于穷举算法，这是科研工作者不希望看到的，故此参数设置将是模拟退火算法需要注重的一步。

［1］Kathleen M Carley，David M Svoboda.Modeling organizational adaptation as a simulated annealing process［J］.Sociological Methods Research ，1996，25(1):138 －168.

［2］池 洁，李 莉.物流中配送区域与配送路线的网络优化法［J］.运筹与管理，2003，12(2):124－126.

［3］Beichl I，Sullivan F.The metropolis algorithm［J］.Computer in Science ＆ Engineering，2000，2(1):65 －69.