遗传算法的改进算法在物流配送当中的应用

2014-05-30富文军王文发王诗瑶李晓英

延安大学学报（自然科学版） 2014年1期

富文军，王文发，王诗瑶，李晓英

(延安大学数学与计算机科学学院，陕西延安 716000)

随着社会的进步，运输行业的发展，城市物流这种活动频繁、运输节点多、运输批量小、频率高的配送方式应运而生。在物流配送过程中，存在很多优化策略问题，本文讨论的物流配送过程中的路径优化问题就是其中之一。目前对这类的解决方法主要有:Floyd算法、模拟退火算法、节约法、蚁群算法、禁忌搜索算法等。其中，廉晚祥、徐国平、柳林、蔡良伟、郎茂祥、刘敏等人就曾利用遗传算法的相关思想解决过路径优化类的问题［1－7］。但由于该方法计算量大、效率低，在实际中难于维护，特别是对一些规模较大的物流配送更是如此。作者尝试将遗传算法进行改进，把模拟退火的思想融入到遗传算法当中，以求达到更好的效果。经过反复测试，该方法比单纯使用遗传算法有较大的改进。

1 数学模型

物流配送的路径优化问题可以描述为:从配送中心用多辆车向各客户所在的物流点进行配货，各个物流点和货物的需求量是固定的，每辆汽车的载重量一定，要求合理安排汽车行驶路线，使得总运距最小。

基于上述要求，作如下的约定:

该城市一共有L个配送点，需要通过k辆汽车来进行配送，每辆车载重限制为b，每个配送点的需求量为gi，任意两个配送点i到j的距离为dij，nk为车辆k所满足的配送点数目，rki表示在车辆k所行驶的路径中配送点的顺序i，rk0=0表示物流中心，用集合Rk表示第k辆车所行驶的路径。

车辆路径问题的数学模型为:配送中所需车辆数进行确定

上述模型中，式(1)为目标函数;式(2)到式(7)为约束条件，其中式(2)为每辆汽车所行驶路线上所有客户的载重量之和不超过汽车本身的载重量;式(3)为每条路径配送点的组成;式(4)为每个配送点只能由一辆汽车进行配送;式(5)表示一辆车的配送点数目不超过总配送点数;式(6)表示所有车辆所行驶配送点数目总和即为总配送点数;式(7)为标志变量，用来查看当前所选车辆是否用于配送。

2 遗传算法的改进算法

针对一般遗传算法收敛速度方面的不足，作者在变异过程中将模拟退火算法与之结合，从而构造出如下的路径优化问题中遗传算法的改进算法:

1)构造染色体，产生初始种群

首先确定染色体的编码方式，由于遗传算法不能直接处理解空间的数据，所以必须通过编码使他们形成基因数串的结构。此问题中我们采用的是自然数编码。随机产生一组种群大小为N，染色体中基因个数为L(L为互不重复的自然数)的初始群体。

2)适应度计算

3)选择操作

本文采用如下最佳个体保留与赌轮选择相结合的选择策略［7］:将每代群体中的N个个体按适应度由大到小排列，排在第一位的个体性能最优，将它复制一个直接进入下一代，并排在第一位;下一代群体的另N－1个个体需要根据前代群体的N个个体的适应度，采用赌轮选择法产生，具体地说，就是首先计算上代群体中所有个体适应度的总和∑fj，再计算每个个体的适应度所占的比例fi/∑fi(j=1，2，…，N)，以此作为其被选择的概率。上述选择方法既可保证最优个体生存至下一代，又能保证适应度较大的个体以较大的机会进入下一代。

4)交叉操作

交叉规则采用部分匹配交叉。选择操作产生的新种群，除第一条染色体外，另N－1条染色体要根据交叉概率Pc进行交叉配对。本文采用了一种改进的两点交叉法，例如:随机在染色体G1、G2中选择一个交配区域，交换G1、G2的交配区域，且G1交配区域前面的数与G2交配区域后面的数交换，G1交配区域后面的数与G2交配区域前面的数交换。相对于别的交叉法，这种方法既能产生一定程度的变异效果，又能保持种群内个体的多样性。

5)变异操作

我们在染色体的变异中对遗传算法进行了改进，加入了模拟退火算法的思想。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。染色体上的某一段基因会以一定的概率来决定是否接受变异。

初始化各变量，Pm为变异概率，T0是退火初始温度，α是温度冷却参数。

对于一个已产生的初始化种群，对它实行变异交叉操作，产生新的群体:计算出群体中每个个体的适应函数值fh。随机选取两个个体进行交叉操作，产生两个新个体，计算它们的适应度函数值fi，fj，若exp(－|fi－fj|/Tk)＞random(0，1)，则接收新解。通过该方法决定是否接收变异后的解，直到满足收敛条件则进化过程结束;若不满足，则Tk+1=α*Tk，对交叉后的个体继续实行变异操作。