改进蚁群算法的物流配送路径优化.docVIP

基于改进蚁群算法的物流配送路径优化 童若锋 张维泽 许星 董金祥 （浙江大学人工智能研究所，杭州 310027） 摘要：本文建立了带约束条件的物流配送问题的数学模型，运用蚁群算法解决物流配送路径优化问题，并将遗传算法的复制、交叉、变异等遗传算子引入蚁群算法，同时改进信息素的更新方式、客户点选择策略，以提高算法的收敛速度和全局有哪些信誉好的足球投注网站能力。经过多次实验和计算，证明了用改进的蚁群算法优化物流配送线路，可以有效而快速地求得问题的最优解或近似最优解。 关键词：物流配送；路径优化；蚁群算法；蚁群系统 Optimizing Logistic Distribution Routing Problem Based on Improved Ant Colony Algorithm RuoFeng Tong, Weize Zhang, Xing Xu, Jinxiang Dong (Institute of Artificial Intelligence, ZheJiang University, HangZhou 310027) Abstract: After constructing the expressions of the constraints in logistic distribution and building the mathematical model, this paper proposes an improved ant colony algorithm to solve distribution problem. Several genetic operators such as crossover and mutation are inducted into the ant colony algorithm, and pheromone updating strategy is ameliorated to improve the efficiency. The result of experiments demonstrates that the optimal or nearly optimal solutions to the logistic distribution routing can be quickly obtained by improved ant colony algorithm. Key words: logistic distribution; optimizing routing; ant colony algorithm (ACA); ant system (AS) 引言 物流配送路径优化问题[1]是典型的组合优化问题，属于一类NP完全难问题，具有很高的计算复杂性。随着市场经济的繁荣，物流配送业迅猛发展，越来越多的企业看到了物流配送在企业生产销售流程中的重要作用。传统的手工配送路线选择完全是依靠劳动者的经验和智慧，需要耗费很多的时间和精力。随着企业规模的逐渐壮大，业务规模也不断扩大，配送网点的数量也逐渐增多，安排配送路线的复杂度越来越高，手工安排配送线路已经很难满足企业的业务需求，采用计算机进行路线安排势在必行。 求解配送路径优化问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法、分区配送算法、方案评价法等。这些算法虽然能够解决此类问题，但也存在一定的缺陷，节约法的组合点零乱、边缘点难以组合的问题，扫描法非渐进优化等[2]。如何针对物流配送路径优化问题的特点，构造运算简单、寻优性能优良的启发式算法，是一个值得深入研究的课题。近年来遗传算法、禁忌有哪些信誉好的足球投注网站算法[3]等都在此问题上进行了运用，并取得了成功[2, 4, 5]。但也存在各自的问题，如遗传算法局部有哪些信誉好的足球投注网站能力不强，总体上可行解的质量不是很高[6]，禁忌有哪些信誉好的足球投注网站算法对于初始解具有较强的依赖性[3]等等。目前研究的热点是混合算法[6, 7]，通过混合在一定程度上弥补算法的缺陷。 蚁群算法是受到人们对自然界中真实蚁群的集体行为的研究成果的启发而在近年来提出的一种基于种群的模拟进化算法，属于随机有哪些信誉好的足球投注网站算法，由意大利学者M. Dorigo[8, 9]等人首先提出。M. Dorigo等人首次提出该方法时，充分利用了蚁群有哪些信誉好的足球投注网站食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁有哪些信誉好的足球投注网站食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP。 蚁群算法可用来解决各种不同的组合优化问题，特别适合于在离散优化问题的解空间进行多点非确定性有哪些信誉好的足球投注网站，如旅行商问题（TSP）、二次分配问题（QAP）、作业安排调度问题（JSP）等等；此外在通信网络负载问题和水科学[10]等应用研究中也被广泛应用。它具有通用性和鲁棒