资源描述：
《遗传算法与蚂蚁算法的融合在带时间窗的车辆路径问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、遗传算法与蚂蚁算法的融合在带时间窗的车辆路径问题中的应用李全亮(河南信阳师院经济管理学院,河南信阳464000)摘要:对带时间窗的车辆路径问题(VRPTW)的求解分为两个过程,先由遗传算法求解出初步的可行解,由此生成信息素初始分布,而后采用蚂蚁算法找出问题的最优解或近似最优解.通过具体算例,从数值计算上探索了遗传算法和蚂蚁算法融合后的优化能力,获得了满意的效果.关键词:车辆路径问题;时间窗;遗传算法;蚂蚁算法;信息素引言0车辆路径问题(VehicleRoutingProblem,VRP)是由Dantzig和Ramser1于1959年首先提出的.该问题一直是运筹学与组合优化领域的前沿与热点问题.
2、在现实生产和生活中,邮政投递问题、飞机、铁路列车、水运船舶及公共汽车的调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为车辆路径问题.研究车辆路径问题具有重要的理论和现实意义.车辆路径问题是一种特殊的旅行商(TravelingSalesmanProblem,TSP)问题,其中运输网络中每个结点都存在货物需求,负责满足这些需求的车辆都有容量限制,每辆车负责运送的货物不能超过自身的容量限制.VRP是许多实际路径规划问题的基本模型,实际的运输路径规划往往根据需要给问题加上一些有意义的约束,形成了各种VRP的变型问题,如多运输中心的VRP问题、带时间窗(即客户对送货时间区间的要
3、求)的VRP问题等等.现实中客户常常会对货物送达的时间有特定的要求,而VRPTW就是研究在满足客户对货物、服务时间等要求的前提下,使车辆行驶总成本(路程或时间)尽可能最优,因此研究VRPTW企业制订具体运输路径具有更为现实的意义.对由于VRPTW是NP2难解(Non2polynomial2hard)的问题,因此对VRPTW的理论研究多集中在求最优解或近似最优解的算法的改进和发现上.Solomon2和Desrosiers等3最早对带时间窗约束的车辆路径问题进行了研究.目前,带时间窗的车辆路径问题的求解主要是基于精确算法和启发式方法两大类方法.Kolen4、Desrochers5、Fisher6、
4、Kohl7等人将各种精确算法如分支定界算法等应用于VRPTW的求解中,成功地解决了理论和现实中的一些规模较小的VRPTW;Solomon最早将用于求解简单VRP的路径构建启发式方法扩展应用于VRPTW的求解中,其研究为以后启发式方法在带约束的车辆路径问题中的应用奠定了理论基础2,其他用于构建生成VRPTW解的启发式方法还有Potvin的并行插入法8、Koskosidis的一般分配法9以及George的贪婪随机自适应搜索法10等.此外,遗传算法、收稿日期:20062122114115期李全亮:遗传算法与蚂蚁算法的融合在带时间窗的车辆路径问题中的应用禁忌搜索等全局优化启发式方法也被应用于VRPTW
5、的求解,如Tan11、Baker12、李大等采用了遗传算法,Taillard15、Brandaυo16卫13、谢秉磊14等采用了禁忌搜索算法.本文拟用遗传算法和蚂蚁算法的融合来求解VRPTW.1遗传算法与蚂蚁算法简介1.1遗传算法简介遗传算法(GeneticAlgorithm,GA)是由美国密执安大学的JohnHolland教授于1975年首先提出的一类仿生型优化算法.它是以达尔文的生物进化论“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗传进化主要在染色体上,子代是父代遗传基因在染色体上的有序排列”为基础,模拟生物界进化过程.其优点是:①具有大范围全局搜索的能力,与问题领域无关;②搜索从
6、群体出发,具有潜在的并行性;可进行多值比较,鲁棒性强;③搜索使用评价函数启发,过程简单;④使用概率机制进行迭代,具有随机性;⑤具有可扩展性,容易与其他算法结合其缺点是:对于系统中的反馈信息利用不够17,当求解到一定范围时往往做大量无为的冗余迭代,求精确解效率低.1.2蚂蚁算法简介蚂蚁算法(antalgorithm,AA)是近年来刚刚诞生的随机优化方法,它是一种源于大自然的新的仿生类算法它是意大利学者M.Dorigo等18219最早提出的,蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的,最初又称蚁群优化方法(antcolonyoptimizationACO).由于模拟仿真中使用了人工蚂
7、蚁的概念,因此亦称蚂蚁系统(antsystem,AS),其优点是:①其原理是一种正反馈机制或称增强型学习系统,它通过信息素的不断更新达到最终收敛于最优路径上;②它是一种通用型随机优化方法,但人工蚂蚁决不是对实际蚂蚁的一种简单模拟,它融进了人类的智能;③它是一种分布式的优化方法,不仅适合目前的串行计算机,而且适合未来的并行计算机;④它是一种全局优化的方法,不仅可用于求解单目标优化问题,而且可用于求解
