CVRP物流配送路径优化及应用研究.docVIP

CVRP物流配送路径优化及应用研究 　　摘 要：车辆行驶路径优化问题是智能安全交通网络的重要组成部分。针对传统车辆路径求解有哪些信誉好的足球投注网站时间过长、得不到最优解、求解质量不高的现况，在研究一般物流配送路径问题处理方法和数学模型的基础上，提出了一种改进的蚁群算法求解问题以提高构建路径的速度和质量，在限量车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）中用改进的蚁群算法来优化求解车物流的配送路径。通过MATLAB仿真结果表明，蚁群算法有哪些信誉好的足球投注网站速度相对较快，具有良好的全局求优能力，收敛结果表明可以准确求出最优路径，相比传统方案，优化后解的质量得到了提高，速度提高了80%左右，是一种可行性较高的求解物流配送路径优化问题的有效算法。 　　关键词：蚁群算法；物流配送；路径优化；数学模型 　　DOIDOI：10.11907/rjdk.161974 　　中图分类号：TP319 　　文献标识码：A 文章编号文章编号2016）011014004 　　基金项目基金项目： 　　作者简介作者简介：袁文涛（1993-）男，安徽马鞍山人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为模式识别与智能系统；孙红（1964-）女，上海人，上海理工大学光电信息与计算机工程学院副教授、硕士生导师，研究方向为模式识别与智能系统、 控制理论与控制工程、企业信息化系统与工程。 　　0 引言 　　解决组合优化问题的最优化求解算法有多种现代人工智能算法方案，优化算法用来处理问题最优解的求解，该问题通常由多个变量共同决定。当前，求解最短路径问题是图论研究中的一个典型求解组合优化算法问题，旨在寻找图表（由节点和路径构成）中两节点或多节点之间的最短路径。常用的最优化路径求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蚁群算法。这些算法都有自身的优点和不足。在对不同算法作出比较后，可以得出蚁群算法在解决网络路由和城市交通系统的问题中是相对有利的。 　　就目前研究来看，随着实际组合问题的变化，基本的智能算法已经不能满足解决这类组合优化问题，同时其优势也在减弱[1]。本文采取改进后的组合优化蚁群算法以弥补传统蚁群算法易陷入局部最优解的不足，加快了求全局最优解的构造速率。 　　蚁群算法（Ant Colony Optimization， ACO），是一种模拟蚂蚁群体智能行为的进化仿生类优化算法，在求解性能上具有强鲁棒性、优良的分布式计算能力、便于与其它算法相结合等优点[2-3]。通常作为一种用来在多变量组合优化问题的多候选解中寻找最优化路径的机率型算法。它由Marco Dorigo于1992年在其博士论文《Ant system： optimization by a colony of cooperating agents》中首先提出，其灵感来源于通过对蚁群社会的长期跟踪观察后发现，虽然单个蚂蚁没有视力、智慧程度低、工作方式简单，但它们却有强大的执行能力和协同工作能力，依靠复杂群体的自组织协同能力发挥出超出单个个体累加的智能，是一种超个体（superorganism，又称超有机体）存在现象。蚁群是在这样的超个体案例中最有名的例子。虽然蚁群算法的严格理论基础和实际应用尚未成熟，国内外相关研究暂处于实验阶段，但这并不妨碍人们对蚁群算法的研究已经由当初单一的解决商旅问题（TSP）发展到解决调度问题、网络通信等多个方向的最优化求解应用。 　　目前，蚁群优化算法已广泛应用于多种求组合最优化问题，在面临路例如作业安排调度问题和路由车辆的二次分派问题上表现出了良好的性能，也经常被用来求旅行推销员问题的拟最优解。它在图表动态变化情况问题的求解上相比萤火虫算法和遗传算法具有绝对优势：蚁群算法的最大优点在于可以连续运行并适应实时变化；缺陷是在处理较大规模和复杂数据问题时，容易存在运算耗时长、收敛速度慢、得不到全局最优解等问题。 　　在求最优解的历次迭代中，单个蚂蚁会根据给定的规则和限定条件选择从一个城市（节点）转移到另一个城市（节点）：它必须对所有城市访问一次，而相对距离越远的城市被选中为下一个访问点的机会越少（能见度低）；相反，在两个城市（节点）边际的一边形成的信息素越浓烈，则该边际作为路径被选择的概率越大；在较短路程情况下，短时间内更多蚂蚁会在所有走过的路径上留下更多信息素，在每次迭代更新后，信息素轨迹浓度会按百分比挥发从而反馈给下一只途经的蚂蚁并影响它作出路径选择。 　　1 车辆路径问题 　　传统的车辆路径问题也叫VRP（Vehicle Routing Problem）问题，是关系到现代物联网发展过程中物流配送系统的一个关键问题，属于NP难题。一直以来，该问题也是管理科学和物流运输方