最优物流论文范文-试谈基于改善遗传算法的物流配送最优路径搜索论文

1、最优物流论文范文:试谈基于改善遗传算法的物流配送最优路径搜索论文摘要：该文介绍了基于改善遗传算法的最优路径搜索。模拟了物流 配送过程中最优路径规划，避开了传统遗传算法在操作时会产生大量 无效路径和“早熟”现象，并具有准确、高效等优点。实践结果证明 该算法可以为物流配送提供有效服务。关键词：遗传算法；最优路径规划；物流配送1009-3044 (2013) 33-7566-02随着市场经济的发展和物流技术专业化水平的提高，物流配送 业得到了迅猛发展。配送路径的选择是否合理，对加快配送速度、提 高服务质量、降低配送成本及增加经济效益都有较大影响。配送路径 的优化理由是物流配送系统的一个主要理由，物流

2、配送路径的优化就 是以最低的运营成本、最快捷的响应速度、最短的配送运输时间，把 货物运至用户手中。在b2c电了商务物流配送时，物流车装载当日需 要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个 客户进行配送，最后返回仓库。根据此需求，作者设计针对物流配送 的最优路径搜索算法，实现了最优路径选择解决方案。1理由分析最优路径规划，通常是指在一个赋权图的两个指定节点（起始 点和目标节点）之间找出一条具有最小权的路径。在实际复杂地形中 的最优路径规划与正常环境下的最优路径之间存在明显的差异，前者 虽然本质上属于图论中最短路线理由的范畴，但由于多个决策目标的 存在，不能直接运用最短路线模型求

3、解1。遗传算法具有全局寻优和潜在并行的特点，对求解最优路径具 有一定优势2。但传统遗传算法操作时会产生大量无效路径，因此 为了提高求解最优路径理由的效率，采用改善的遗传算法求解，并有 效的避开了传统遗传算法的“早熟”现象。2算法设计2. 1遗传算法介绍遗传算法是一类借鉴生物界的进化规律演化而来的随机化搜索 策略。遗传算法是解决搜索理由的一种通用算法，对于各种通用理由 都可以使用。遗传搜索算法的特征为：首先组成一组候选解；依据某 些适应性条件测算这些候选解的适应度；根据适应度保留某些候选 解，放弃其他候选解；对保留的候选解进行某些操作，牛成新的候选 解。2. 2遗传算法改善基于以上，我们选择遗传

4、算法作为解决此理由的基本算法。但 遗传算法也有它本身固有的缺陷，例如种群早熟、陷入局部最优、多 次进化后种群向纯种发展等。因此我们在传统的遗传算法上又做了如 下的改善：1）初始种群时按照一定的概率选择距离出发点最近的点作为到 达点。基于行走路线不能交叉的原则，出发点与到达点之间大部分都 应该是距离最近的且未走过的点。因此初始化数据时系统自动以定 的概率选择最近的点作为下一个到达点。2）遗传算法求得最优解易陷入局部最优，因此在时间允许的范 围内多次调用遗传算法求得最优解。调用中可以把上次求得的最优解 作为下一次初始种群的一部分参与进化。求解最优解后为了防止个别 点的交叉，对于最优解又进行了优化处

5、理以进一步求得最优解。3）遗传算法中要对种群进行排序，保留最优个体群，删除最差 个体群。但删除最差个体群时，必定会破坏种群多样性，导致种群向 纯种方向进化。因此我们在使用最优个体覆盖最差个体时，将最优个 体反向覆盖最差个体，这样，即保留了个体的多样性，又保证了迭代 进化的方向。2. 3数据结构设计2. 3.1图与基因的描述根据题目描述，采用完全图的方式描述图，采用邻接矩阵的方 式存储图。若是实际中的地图，只要把其中两点间的距离定义为足够 大，程序也能求解（在本文中不讨论）。1）记录距离的图描述public doublet, cost_table；2）记录速度的图描述public doublet

6、, spccd_tablc； /随机生成个点之间的速度值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；/种群的规模privatestaticdoublepn0. 3；/选择后续点时选择最近点的概率pr

7、ivatestaticdoublepc =0.9；/交叉概率privatestaticdoublepm =0. 3；/变异概率privatestaticdoubleps 二0.9；/选择时候保留种群的比privateint genmax 二 100；/迭代进化的基本次数，随着客户数量的增加，应适当增加2.4遗传算法的实现1）初始化种群。完成对种群的初始化，并记录当前的最优基因。 初始化时按一定的概率选择未走的最近点作为下一点。2）基因个体交叉。两两交叉，随机产生交叉点。为防止出现个 别点的重复出现，只复制一半，另外一半程序自动搜索剩余的未被走 到的点。3）基因变异。进化后期，为防止种群早熟，会

8、提高变异率。变 异时，自动生成两个路径点，然后逆置两点间的路径。4）种群进化。种群按照指定的迭代次数进化，进化中记录当前 的最优解，并将最优解作为下一代的优秀基因保存并参与进化。5）最优解优化。对于最优解进行局部最优的判断，若出现个别 局部不优秀的解，给予适当的微调整。3结果分析3.1实际运转结果从大量的结果来分析，在客户数少于等于30时，系统能找到最 优解，当客户数大于30小于等于100时，系统能找到近似最优解。 我们大胆预测，该近似最优解与实际最优解之间的误差小于3%。实 际上我们也可以减少遗传算法的执行次数，这样得到的最优解误差会 大一些，大该在8%左右。但实际运转时间会缩短，我们测试1

9、00个 客户时，大约的运转时间为3分钟（取决于硬件配置）。4结束语遗传算法的执行效果很大程度上取决于变异概率、种群大小、 迭代次数、交叉算子等参数。因此对于某个理由，需要大量的时间去 摸索配置参数，我们经过大量的测试最终选择了现在的参数设置。但 当客户数的数量变大时，这样的参数是否还是最优的有待继续的测 试。我们总结以下几个改善方向：1）交叉可以考虑多个个体参与交 叉。2）优化时不一定按照当前最优优化，而应该在一定概率上接收 当前的非最优结果。3）变异要以更多的方式进行，而不是现在仅有 的一种方式。参考文献：1 汪祖柱，程家兴，方宏兵，等车辆路径理由的混合优化算 法j运筹与管理，2004 （6）： 482-5212