详情

原文传递车辆路径问题的蚁群算法研究

论文题名：	车辆路径问题的蚁群算法研究
关键词：	车辆路径问题;蚁群算法;容量约束;物流配送效率
摘要：	蚁群算法(Ant Colony Algorithm，ACA)是一种新生的仿生优化算法,其基本原理是对真实蚁群觅食行为的协作过程的模拟，该算法算法主要由信息素更新、局部搜索算法和轮盘赌策略等构成。自从90年代初意大利学者M.Dorigo等人提出该算法以来，很多的专家、学者对其进行了研究和改进，尤其是针对不同问题的研究改进，提出了大量的各种各样的蚁群算法的改进算法，改进后的算法搜索最优解能力、算法的收敛性等性能和原算法相比，都得到了一定的改进和提高。现在蚁群算法已经在很多领域得以广泛应用，如TSP、网络路由、排课问题、指派问题、车辆路径问题、智能机器人、大规模集成电路设计、交通运输规划问题等等，都取得了很好的效果。　　车辆路径问题(Vehicle Routing Problem，VRP)是近几十年来运筹学、应用数学、网络分析、图论、计算机应用及交通运输等学科研究的一个热点问题，其产生于现实的公路交通运输领域，并在通讯、生产、国防、生物、计算机应用等领域得到了广泛的应用。可是VRP发展至今，当问题规模较大时仍然很难得到问题的精确解。因此，探讨如何经过少量的计算，得到一个相对满意的解，已成为现阶段相关学者研究的重点。　　本文研究的主题，就是针对有容量约束的车辆路径问题(Capacity Vehicle Routing Problem,CVRP)以及蚁群算法的本身，对蚁群算法在现有基础上进行了改进，提出一种新的改进蚁群算法，实例仿真证明该算法能够较好地解决规模不大的有容量约束的车辆路径问题。　　主要研究工作如下: 　　①通过对有容量约束的车辆路径问题和蚁群算法的学习，对国内外同类问题的研究进行了简单的综述。　　②通过对目前蚁群算法的分析，针对有容量约束的车辆路径问题，提出蚁群算法的改进算法，为快速、有效地求解有容量约束的车辆路径问题开辟了途径，这是本文的核心部分。　　③根据改进蚁群算法的思路，利用Matlab语言实现了该算法，采用一些算列对算法进行了测试，实验结果表明改进后的蚁群算法在求解有容量约束的车辆路径问题上是有效的。　　本文提出的改进蚁群算法，为求解有容量约束的车辆路径问题提供了一种有效的工具，能有效地提高物流配送的效率，对电子商务和物流配送发展有一定的理论意义与应用价值。
作者：	王书勤
专业：	运筹学与控制论
导师：	叶仲泉
授予学位：	硕士
授予学位单位：	重庆大学
学位年度：	2008
正文语种：	中文