免疫算法在带时间窗的车辆路径问题中的应用.pdf

2006年10月 系统工程理论与实践 第10期 文章编号：1000—6788(2006)10．0119．06 免疫算法在带时间窗的车辆路径问题中的应用 李全亮 (西安交通大学管理学院，西安710049) 摘要：根据带时间窗的车辆路径问题的实际情况，提出了一种基于分组匹配的亲和力的计算方法．实 验结果表明，免疫算法能有效地解决带时间窗的车辆路径问题．计算结果优于节约算法、分派算法、遗传 算法． 关键词：车辆路径问题；时间窗；免疫算法；分组匹配；亲和力 中图分类号：F506 文献标志码：A Immune forVehicle Problem Algorithm Routing withTimeWindows LIQuan—hang SchoolofXi’an (Management University，Xi’Ⅱ710049，China) Jiaotong aHovel basedon match to Abstract：This to immune vehicle paperproposes affinity group apply algorithm routing withtimewindows．Itis thatimmune Callfindthe or solution problem proved algorithm optimalnearlyoptimal the resultisbetterthan andsenetic effectivelyby experiment．The algorithm，assignmentalgorithm algorithm． saving words：vehicle windows；immune Key routingproblem；time algorithm；groupmatch；alfinity l 问题描述 在许多物流配送系统中，管理者们需要采取有效的配送策略以提高服务水平、降低货运费用．其中车 辆路径问题(Vehicle Routing 一系列装货点或卸货点，达到诸如路程最短、费用最小，耗费时间尽量少等目的．此问题可描述如下：有一 个货物需求点(或称顾客)，已知每个需求点的需求量及位置，至多用K辆汽车从中心仓库(或配送中心) 到达这批需求点，每辆汽车载重量一定，安排汽车路线使运距最短且满足每条路线不超过汽车载重量和每 个需求点的需求量必须且只能由一辆汽车来满足的约束条件．车辆路径问题是一个NP完全问题，只有在 Problemwith 需求点数和路段数较少时才有可能寻求其精确解．带时间窗的车辆路径问题(VehicleRouting Time 都可以归结为VR阑r来处理，但处理的好坏将直接影响到一个企业的效益和对顾客的服务质量，所以对 它的研究越来越受到人们的重视，目前对它的求解主要集中在启发式算法上． 进入20世纪90年代以后，遗传算法、禁忌有哪些信誉好的足球投注网站算法、模拟退火算法和人工神经网络算法等启发式算 和C—w算法求解了VRPlw；李大卫、王莉、王梦光№’用一种修正的最近距离有哪些信誉好的足球投注网站启发式算法求解了 VRPTW．但是，遗传算法存在