【作者】 朱建荣；

【导师】 柳林；

【作者基本信息】 长沙理工大学 ， 计算机应用技术， 2006， 硕士

【摘要】 随着计算机技术的日新月异,一些新的仿生优化算法像蚁群算法得到了迅速发展和广泛应用。论文首先介绍了物流配送车辆优化调度问题等相关概念,接着详细介绍蚁群算法的产生、发展和研究现状,以及该算法在经典VRP问题上的应用。论文的主要工作是对蚁群算法的改进。蚁群算法的改进策略主要有以下几个方面:首先,针对基本蚁群算法选路计算开销太大,引入了一种新的优化选路方法,通过三种改进策略,减少了蚁群的选路次数,减小了选路时间,提高了运行效率。其次,引入了蚂蚁个体差异策略,通过调整菲尔蒙因子以及期望启发式因子在选路概率中的作用,使蚂蚁的行为方式具有多样性。仿真实验表明这可以使蚁群算法避免过早陷入局部最优。最后,在此基础上融合近似解可行化算法,构造了求解经典VRP问题的自适应蚁群算法。实验结果表明,自适应蚁群算法性能优良,能够有效解决VRP问题。论文提出的自适应蚁群算法,不仅改善了算法性能,还在VRP问题上的应用取得了较好的效果。一系列仿真实验表明,改进蚁群算法在执行效率上有明显的优势,主要体现在选路次数比基本蚁群算法有明显减少,而且随着客户规模的扩大,改进蚁群算法选路次数的减少尤为明显。论文还分析了蚁群算法中参数的选取方法及其对算法性能的影响,提出了一些有益的建议。更多还原

【Abstract】 With the development of computer technology, some new biomimetic optimizing algorithms like the Ant Colony Optimization are developed quickly and applied broadly.In this thesis, we begin with the introduction of Vehicle Routing Problem related topics. Then we introduce the background and the details of Ant Colony Optimization. Among the applications of ACO, we emphasize some existing methods solving sutra VRP problem.The new improvements and results of ACO solving sutra VRP problem are presented, which are the main contributions of the thesis. And we proposed three improvements on ant colony optimization algorithm to solve VRP problem. First, a novel optimized implementing approach is designed to reduce the processing costs involved with routing of ants in the conventional ACO. Secondly, the improvement of ACO is put forward to ant Individual Variation. The experiments show it can avoid stagnation behavior. At last, this paper proposes an adaptive ant colony algorithm for solving the physical distribution Vehicle routing problem which is improved from basic ACO by means of integrating C-W algorithm and introducing the adaptive ant attraction of arc in order to decrease computing time and avoid stagnation behavior. The computational experiments show that this algorithm is feasible and valid for VRP.The improved algorithm greatly improves the performance of ACO, and it gets good effect on applying for large-scale VRP problems. The results of the simulated experiments show that the improved algorithm not only reduces the number of routing in the ACO but also surpasses existing algorithms in performance for solving large-scale VRP problems. And it is obvious to reduce the number of routing with expands of client server’scale. This paper is that we put forward some beneficial suggestion on the solution through analyzed the every parameter in the function of solution.更多还原