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

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