原文传递
基于粒子群蚁群混合算法的物流车辆路径问题研究
| 论文题名： | 基于粒子群蚁群混合算法的物流车辆路径问题研究 |
| 关键词： | 车辆路径;粒子群蚁群混合算法;建模仿真;组合优化 |
| 摘要： | 在经济全球化和信息化的大前提下，物流作为“第三利润源泉”成为拉动我国 GDP增长和第三产业发展的重要因素。配送是从物流系统中衍生出来的重要环节。优化配送路线能够提高配送效率，降低配送成本，同时能够有效减少因物流配送引发的交通拥堵，空气、噪声污染等问题。因此研究如何有效的利用现有资源建立合理的配送方案，提高企业的经济效益，具有重要的现实意义。 车辆路径优化问题(Vehicle Routing Problem，VRP)是物流配送优化中的核心问题。近些年来 VRP问题已经成为运筹学、应用数学、图论以及计算机科学等学科领域关注的重点问题。由于该问题是一个复杂的组合优化问题，所以求解此问题的许多智能型启发式优化算法应运而生。粒子群算法和蚁群优化算法就是人类受自然界真实鸟类和蚂蚁的觅食行为启发而提出的智能优化算法。本文通过研究粒子群算法和蚁群优化算法的优点，提出了一种有效结合两种算法优势的融合算法（PSO-MMA）。通过将 PSO-MMA算法应用于旅行商问题说明其在搜索解的精度上是一种比较优秀的算法，进一步将该算法应用于 VRP问题的求解并验证了其有效性。 本文的研究内容和完成的工作主要有以下几个方面： 1.针对粒子群算法容易陷入局部最优的不足之处，提出了自适应变异和划分多粒子群的策略对该算法进行优化。 2.由于蚁群算法在搜索初期信息素是均匀分布，因此具有搜索盲目性的缺点。本文使用优化后的粒子群算法求得问题的次优解来初始分布最大最小蚁群算法的信息素矩阵。之后利用蚁群算法，以国际库TSPLIB中旅行商问题（旅行商问题是一个经典组合优化问题，由于它的NP完全性，在国际上已经成为衡量算法优劣的标准）的标准算例为实验数据搜索问题的最优解。计算结果显示，PSO-MMA在搜索解的精确性上明显优于基本粒子群算法（PSO）,最大最小蚁群算法（MMAS）和改进后的粒子群算法（IPSO），并且可以搜索到 eil51和 berlin52两个实例的最优解,说明本文提出算法的优越性。 3.对车辆路径问题进行建模，并采用 VRP数据库及其它文献中的实例对融合后的算法进行实验，仿真实验结果验证了粒子群蚁群融合算法求解带容量约束的车辆路径问题的有效性。 |
| 作者： | 高明芳 |
| 专业： | 计算机应用技术 |
| 导师： | 付学良 |
| 授予学位： | 硕士 |
| 授予学位单位： | 内蒙古农业大学 |
| 学位年度： | 2016 |
| 正文语种： | 中文 |
检索历史
应用推荐
