基于改进蚁群算法的物流配送路径优化1童若锋2张维泽许星董金祥（浙江大学人工智能研究所，杭州310027）摘要：本文建立了带约束条件的物流配送问题的数学模型，运用蚁群算法解决物流配送路径优化问题，并将遗传算法的复制、交叉、变异等遗传算子引入蚁群算法，同时改进信息素的更新方式、客户点选择策略，以提高算法的收敛速度和全局搜索能力。经过多次实验和计算，证明了用改进的蚁群算法优化物流配送线路，可以有效而快速地求得问题的最优解或近似最优解。关键词：物流配送；路径优化；蚁群算法；蚁群系统OptimizingLogisticDistributionRoutingProblemBasedonImprovedAntColonyAlgorithmRuoFengTong,WeizeZhang,XingXu,JinxiangDong(InstituteofArtificialIntelligence,ZheJiangUniversity,HangZhou310027)Abstract:Afterconstructingtheexpressionsoftheconstraintsinlogisticdistributionandbuildingthemathematicalmodel,thispaperproposesanimprovedantcolonyalgorithmtosolvedistributionproblem.Severalgeneticoperatorssuchascrossoverandmutationareinductedintotheantcolonyalgorithm,andpheromoneupdatingstrategyisamelioratedtoimprovetheefficiency.Theresultofexperimentsdemonstratesthattheoptimalornearlyoptimalsolutionstothelogisticdistributionroutingcanbequicklyobtainedbyimprovedantcolonyalgorithm.Keywords:logisticdistribution;optimizingrouting;antcolonyalgorithm(ACA);antsystem(AS)1项目基金：本文受国家重点基础研究发展规划（973）项目（2002CB312106）和浙江省重大科技攻关项目（2005C13023）支持2作者简介：童若锋（1969.4-），男（汉族），浙江金华人，教授，博士，主要研究方向为CAD&CG等。E-mail：trf@zju.edu.cn。1引言物流配送路径优化问题[1]是典型的组合优化问题，属于一类NP完全难问题，具有很高的计算复杂性。随着市场经济的繁荣，物流配送业迅猛发展，越来越多的企业看到了物流配送在企业生产销售流程中的重要作用。传统的手工配送路线选择完全是依靠劳动者的经验和智慧，需要耗费很多的时间和精力。随着企业规模的逐渐壮大，业务规模也不断扩大配送网点的数量也逐渐增多，安排配送路线的复杂度越来越高，手工安排配送线路已经很难满足企业的业务需求，采用计算机进行路线安排势在必行。求解配送路径优化问题的方法很多，常用的有旅行商法、动态规划法、节约法、扫描法、分区配送算法、方案评价法等。这些算法虽然能够解决此类问题，但也存在一定的缺陷，节约法的组合点零乱、边缘点难以组合的问题，扫描法非渐进优化等[2]。如何针对物流配送路径优化问题的特点，构造运算简单、寻优性能优良的启发式算法，是一个值得深入研究的课题。近年来遗传算法、禁忌搜索算法[3]等都在此问题上进行了运用，并取得了成功[2,4,5]。但也存在各自的问题，如遗传算法局部搜索能力不强，总体上可行解的质量不是很高[6]，禁忌搜索算法对于初始解具有较强的依赖性[3]等等。目前研究的热点是混合算法[6,7]，通过混合在一定程度上弥补算法的缺陷。蚁群算法是受到人们对自然界中真实蚁群的集体行为的研究成果的启发而在近年来提出的一种基于种群的模拟进化算法，属于随机搜索算法，由意大利学者M.Dorigo[8,9]等人首先提出。M.Dorigo等人首次提出该方法时，充分利用了蚁群搜索食物的过程与著名的旅行商问题（TSP）之间的相似性，通过人工模拟蚂蚁搜索食物的过程（即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP。蚁群算法可用来解决各种不同的组合优化问题，特别适合于在离散优化问题的解空间进行多点非确定性搜索，如旅行商问题（TSP）、二次分配问题（QAP）、作业安排调度问题（JSP）等等；此外在通信网络负载问题和水科学[10]等应用研究中也被广泛应用。它具有通用性和鲁棒性，是基于总体优化的方法。蚁群算法原型本身就是一个寻找最短路径的模型，因此它在路径优化方面有着天然的优势，目前已经有不少蚁群算法在TSP问题中成功运用的例子，如Ant-Q[11]、MMAS[12]等。物流配送路径优化问题和TSP问题相比有共同点—...
