基于改进遗传算法的物流配送最优路径搜索

摘要：该文介绍了基于改进遗传算法的最优路径搜索。模拟了物流配送过程中最优路径规划，避免了传统遗传算法在操作时会产生大量无效路径和“早熟”现象，并具有准确、高效等优点。实践结果证明该算法可以为物流配送提供有效服务。

关键词：遗传算法；最优路径规划；物流配送

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2013）33-7566-02

随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。配送路径的选择是否合理，对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径的优化问题是物流配送系统的一个主要问题，物流配送路径的优化就是以最低的运营成本、最快捷的响应速度、最短的配送运输时间，把货物运至用户手中。在B2C电子商务物流配送时，物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进行配送，最后返回仓库。根据此需求，作者设计针对物流配送的最优路径搜索算法，实现了最优路径选择解决方案。

1 问题分析

最优路径规划，通常是指在一个赋权图的两个指定节点（起始点和目标节点）之间找出一条具有最小权的路径。在实际复杂地形中的最优路径规划与正常环境下的最优路径之间存在明显的差异，前者虽然本质上属于图论中最短路线问题的范畴，但由于多个决策目标的存在，不能直接运用最短路线模型求解[1]。

遗传算法具有全局寻优和潜在并行的特点，对求解最优路径具有一定优势[2]。但传统遗传算法操作时会产生大量无效路径，因此为了提高求解最优路径问题的效率，采用改进的遗传算法求解，并有效的避免了传统遗传算法的“早熟”现象。

2 算法设计

2.1 遗传算法介绍

遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索方法。遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。遗传搜索算法的特征为：首先组成一组候选解；依据某些适应性条件测算这些候选解的适应度；根据适应度保留某些候选解，放弃其他候选解；对保留的候选解进行某些操作，生成新的候选解。

2.2 遗传算法改进

基于以上，我们选择遗传算法作为解决此问题的基本算法。但遗传算法也有它本身固有的缺陷，例如种群早熟、陷入局部最优、多次进化后种群向纯种发展等。因此我们在传统的遗传算法上又做了如下的改进：

1）初始种群时按照一定的概率选择距离出发点最近的点作为到达点。基于行走路线不能交叉的原则，出发点与到达点之间大部分都应该是距离最近的且未走过的点。因此初始化数据时系统自动以一定的概率选择最近的点作为下一个到达点。

2）遗传算法求得最优解易陷入局部最优，因此在时间允许的范围内多次调用遗传算法求得最优解。调用中可以把上次求得的最优解作为下一次初始种群的一部分参与进化。求解最优解后为了防止个别点的交叉，对于最优解又进行了优化处理以进一步求得最优解。

3）遗传算法中要对种群进行排序，保留最优个体群，删除最差个体群。但删除最差个体群时，必然会破坏种群多样性，导致种群向纯种方向进化。因此我们在使用最优个体覆盖最差个体时，将最优个体反向覆盖最差个体，这样，即保留了个体的多样性，又保证了迭代进化的方向。

2.3 数据结构设计

2.3.1 图与基因的描述

根据题目描述，采用完全图的方式描述图，采用邻接矩阵的方式存储图。若是实际中的地图，只要把其中两点间的距离定义为足够大，程序也能求解（在本文中不讨论）。

1）记录距离的图描述

public double[，] Cost_table；

2）记录速度的图描述

public double[，] Speed_table； //随机生成个点之间的速度值

3）基因信息的描述

public struct unit{

public int[] path； //记录基因个体的路径

public double cost； }； //记录当前路径的代价

public unit[] group； //记录种群的信息

public unit opt； //记录最优解的信息

2.3.2 遗传算法的全局参数

根据大量的实际测试，最终确定了遗传算法的参数如下：

private int CityNum； //客户数量

const int N = 500； //种群的规模

private static double pn = 0.3； //选择后续点时选择最近点的概率

private static double pc = 0.9； //交叉概率

private static double pm = 0.3； //变异概率

private static double ps = 0.9； //选择时候保留种群的比例

private int genmax = 100； //迭代进化的基本次数，随着客户数量的增加，应适当增加

2.4 遗传算法的实现

1）初始化种群。完成对种群的初始化，并记录当前的最优基因。初始化时按一定的概率选择未走的最近点作为下一点。

2）基因个体交叉。两两交叉，随机产生交叉点。为防止出现个别点的重复出现，只复制一半，另外一半程序自动搜索剩余的未被走到的点。

3）基因变异。进化后期，为防止种群早熟，会提高变异率。变异时，自动生成两个路径点，然后逆置两点间的路径。

4）种群进化。种群按照指定的迭代次数进化，进化中记录当前的最优解，并将最优解作为下一代的优秀基因保存并参与进化。

5）最优解优化。对于最优解进行局部最优的判断，若出现个别局部不优秀的解，给予适当的微调整。

3 结果分析

3.1 实际运行结果

从大量的结果来分析，在客户数少于等于30时，系统能找到最优解，当客户数大于30小于等于100时，系统能找到近似最优解。我们大胆预测，该近似最优解与实际最优解之间的误差小于3%。实际上我们也可以减少遗传算法的执行次数，这样得到的最优解误差会大一些，大该在8%左右。但实际运行时间会缩短，我们测试100个客户时，大约的运行时间为3分钟（取决于硬件配置）。

4 结束语

遗传算法的执行效果很大程度上取决于变异概率、种群大小、迭代次数、交叉算子等参数。因此对于某个问题，需要大量的时间去摸索配置参数，我们经过大量的测试最终选择了现在的参数设置。但当客户数的数量变大时，这样的参数是否还是最优的有待继续的测试。我们总结以下几个改进方向：1）交叉可以考虑多个个体参与交叉。2）优化时不一定按照当前最优优化，而应该在一定概率上接收当前的非最优结果。3）变异要以更多的方式进行，而不是现在仅有的一种方式。

参考文献：

[1] 汪祖柱，程家兴，方宏兵，等.车辆路径问题的混合优化算法[J].运筹与管理，2004（6）：482-521.

[2] 王小平，曹立明.遗传算法-理论，应用与软件实现[M].西安：西安交通大学出版社，2002.

[3] Michael J de Smith，Michael FGoodchild，PaulA Long-ley，杜培军等译.地理空间分析-原理、技术与软件工具[M].北京：电子工业出版社，2009.