基于改进遗传算法的物流配送路线优化研究.pdfVIP

第26卷 第12期 武 汉 理 工 大 学 学 报 Vol.26 No.12 2004年12月 JOURNALOFWUHANUNIVERSITYOFTECHNOLOGY Dec.2004 基于改进遗传算法的物流配送路线优化研究 李仁安，袁际军 (武汉理工大学管理学院，武汉430070) 摘 要:在分析车辆路径问题(VRP)现有启发式算法的基拙上，建立了考虑路线安排的物流配送方案模型，并提出了 求解该问题的一种改进遗传算法((IGA)。方法的核心在于针对遗传算法的局部有哪些信誉好的足球投注网站能力的不足，在选择、交叉、变异等遗 传操作之后，引入逆转换位算子，根据适应度是否增加，对新产生的染色体进行多次逆转操作。应用C语言编程进行模拟 计算，结果表明该改进遗传算法明显增强了群体演化的质量，提高了算法收敛速度，较好地解决了“早熟收敛”问题。 关键词:改进遗传算法;物流配送;车辆路线问题(VRP);逆转换位算子 中图分类号:U492.3 文献标识码:A 文章编号:1671-4431(2004)12-0099-03 ResearchontheOptimizationofLogisticsDistribution RoutingBasedonImprovedGeneticAlgorithm LIRen-an,YUAN Ji-jun (SchoolofManagement，WuhanUniversityofTechnology，Wuhan430070,China) Abstract: Basedontheanalysisoftheexistingheuristicalgorithmforthevehicleroutingproblem (VRP)，adistribution modelrelevanttoroutearrangementwasestablished.Animprovedgeneticalgorithm (IGA)waspresentedforthesolution tothisproblem.ThecoreofIGAistheconstructionofinversionoperator,whichovercomestheweaknessofgeneticalgo- rithmandlocalsearchalgorithm.ComputationalresultsbasedonClanguageprogrammingdemonstratedthatIGAhasgreat robustnessforVRPandcansolvetheImmatureConvergenceproblemeffectively. Keywords: improvedgeneticalgorithm(IGA);logisticsdistribution;vehicleroutingproblem(VRP);inversion operator 配送车辆路线问题VRP是一个典型的NP难题，其研究方法主要有精确算法和近似算法2大类。精确 算法主要包括分枝定界法 习〔‘、动态规划法等;而近似算法则主要包括禁忌有哪些信誉好的足球投注网站法川、遗传算法3-〔i〕等。精确算 法在求解中小规模的VRP时在精度上优于近似算法，但无法避免指数爆炸，所以在求解大规模的VRP时， 近似算法较占优势，通常可以在有限时间里找到满意的次优解，这是精确算法难以达到的。 1VRP优化问题的数学模型 现有m辆相同的车停在一个配送中心vo，它需要给n个顾客提供货物，顾客为。I}VZI...}v,，并且配送中 心和客户的坐标已知。确定所需要的车辆的数 目N，并指派这些车辆到对应回路中，同时包括回路内的路线 优化，使得运输总距离S最小。每个客户同一时刻只能接受1辆车的服务，1个子回路对应