遗传算法在物流配送线路选择方面研究

1 概述

物流配送路径最短问题是典型的旅行商（Traveling Salesman Problem，TSP）问题。车辆从配送中心出发，将车上货物分别送到本辖区内的其它分发点（简称节点）1,2,3,…,n，车辆在一次配送任务中，只经过各节点一次。由于交通管制和道路方面的原因，可能存在各节点间并不完全互通，个别节点间可能还存在单向性通行，如图1物流配送路线示意图。

对于这样一个典型的TSP问题，随着节点数目的增加，其可能的配送路线数目与节点数目n是成指数型增长的，是一个NP难题，所以很难精确的求出其最优解，因此寻找有效的近似求解算法就具有重要的现实意义。遗传算法是一种仿生算法，核心思想起源于对生物进化过程的认识。通过模仿生物的进化，利用达尔文的进化论和孟德尔遗传变异思想对研究问题进行数学抽象和建模。

遗传算法是通过模仿生物的繁殖、基因变异、物种间竞争和自然选择对研究问题采取适当的计算策略，最终得到研究问题的满意解。遗传算法只利用研究问题的目标满意度评价信息，是一种多条并行的随机搜索优化方法，适用于大规模、高度非线性以及无解析表达式的问题，有很强的通用性[1]。物流配送的路线最短选择问题采用该方法非常合适。

图1 物流配送路线示意图

2 数学建模及求解方法

（1）路线信息。对于从物流配送中心出发，将货物分别投送至各分发点的配送路线之间的关系，可以用表1物流配送节点信息表进行表达（假定11个节点）。对于路线的单向性或节点彼此不通的路线，设值一个比正常路径大几个数量级的值，如表1中设定1 000。对各分发点进行节点编号。表1中列表示出发，行表示到达，如：第2列第3行取值为3，表示从节点2出发，到达3节点路程为3个单位。

（2）创建初始种群。对于物流配送车辆所经过的各节点编号所构成的一条路线为一个个体（称染色体），节点编号在个体中称基因。基因在个体中的位置不同，个体的表现（路程大小）不同。为了增加个体进化效率和多样性，初始个体数量一般选择得都比较多，这些初始个体所构成的集合称为初始种群。对于本问题，选择初始种群的规模为100个。初始种群可借由MATLAB的randperm函数产生。由randperm函数按照分发点的节点编号所产生的一个个体形如：5 11 4 8 10 9 2 6 1 7 3。个体中节点编号是随机排列的，每次调用randperm函数所生产的个体都可能互不相同。

表1 物流配送节点信息表

（3）个体评价和选择。对于创建的初始种群需要对每个个体进行评价，好的个体和差的个体应当通过适当规则进行保留和淘汰。依据节点信息（表1）对创建的初始种群中每个个体按节点编号顺序所构成的路线的路程值大小作为个体的适应度评估函数，越小表明个体的适应度越好，反之越差。在个体保留和淘汰方法上有多种策略，最常见的有轮盘赌法、随机联赛法、无回放余数比例随机法等，本文选择随机联赛法。随机联赛法是随机抽取种群中两个个体，比较其路程值，路程小的个体被保留，路程大的个体被淘汰。选择后的种群规模和选择前的种群规模保持相同。

（4）染色体编码。遗传算法运行过程不对所求解问题的实际决策变量直接操作，而是对表示可行解的个体的编码进行交叉和变异操作。编码就是把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法[1]。对物料配送路线的编码方法比较多，本文选取Grefenstette等提出的编码方法。对上述个体5 11 4 8 10 9 2 6 1 7 3采用Grefenstette编码方法得到的染色体为：5 10 4 6 7 6 2 3 1 2 1。

（5）染色体交叉。染色体交叉是将种群中的染色体（种群中的个体）按照交叉概率，随机选取染色体，随机对染色体基因位置之前或之后的基因进行互换操作。本文采用随机交叉点之前的基因对随机选取的两条染色体进行交叉操作。

（6）基因变异。基因变异是将对构成染色体的基因，按照变异概率，随机选择染色体上的基因进行随机改变的操作。由于染色体的编码方法决定了不同位置基因的可能取值，因此基因变异后，在该位置上的基因值应保证是有效的基因改变。

（7）解码和新个体评价。在染色体交叉、变异完成后，得到下一代新的种群。为了评价新种群中个体（染色体）的优劣，需要首先将编码的染色体按编码的逆过程进行解码。对解码后的染色体按照适应度进行评估，并按上述所确定的个体选择规则保留或淘汰。

（8）计算进化代数和差异。计算种群中适应度最好的个体，即路程最短的个体，并将该个体与上一代表现最好的个体进行对比，计算他们之间的差异值；同时计算种群进化的代数，当两条件都达到程序结束运行条件时程序就停止计算，并将优化结果输出。

3 求解及结果分析

按照遗传算法的计算策略，采用MATLAB编制的求解程序框图如图2所示。

经过几次运行其计算结果如下：

进化第116代，当前最小值61.000，共有1个最小值解；

群体中第64个个体，最小值61.000，2→3→4→5→11→10→9→8→6→7→1；

进化第385代，当前最小值61.000，共有51个最小值解；

群体中第2个个体，最小值61.000，11→10→9→8→6→7→1→2→3→4→5。

从优化计算的结果看，虽然得到最优解的进化代数各不相同，但都能得到相同的结果。上述求解得到的路线2→3→4→5→11→10→9→8→6→7→1与路线 11→10→9→8→6→7→1→2→3→4→5在形式上不完全相同，但所确定的路线是完全一致的。结果表明，从配送中心出发，遍历各分发点的最优路线为：1→2→3→4→5→11→10→9→8→6→7，总路程为61个单位。

4 结论

采用遗传算法求解物流配送路线最优选择是可行有效的方法。遗传算法只与求解问题的目标函数取值信息有关，而与实际所研究问题的类型和数学特性无关，因此具有广泛的普适性。对于多节点遍历问题或多孔加工路线最优选择等实际问题都可以利用遗传算法进行求解。

图2 遗传算法求解物流配送路径最短流程图

参考文献：

[1]周明，孙树栋.遗传算法原理与应用[M].北京：国防工业出版社，1999:143-157.