基于改进蚁群算法的配送路线优化研究

作     者：沈垚 

作者单位：东南大学 

学位级别：硕士

导师姓名：赵林度

授予年度：2006年

学科分类：12[管理学] 02[经济学] 0202[经济学-应用经济学] 1202[管理学-工商管理] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 020205[经济学-产业经济学] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主      题：物流配送 蚁群算法 配送路线优化 车辆路径问题(VRP) 优化仿真 

摘      要：随着信息技术的发展,现代物流作为“第三个利润源泉正受到日益广泛的重视,并面临前所未有的发展机遇。在现代物流中,配送是一个重要的与消费者直接相连的环节,其体现了企业的核心竞争力。而物流配送路线优化研究,是配送系统优化中的重要一环。通过配送路线优化,可以提高企业的运作效率,降低配送成本,实现物流科学化。因此,本文对配送路线的优化研究主要依据蚁群算法从以下几方面展开: 1、对基本蚁群算法进行了改进。基本蚁群算法是20世纪90年代提出的一种新型模拟进化算法,针对该算法易陷入局部最优解、求解速度较慢的缺陷,本文对基本蚁群算法的全局信息素更新公式进行了改进,并在算法的实现过程中动态调整q0值。通过对旅行商问题(Traveling Salesman Problem,TSP)的仿真对比,得到了较为满意的结果,体现了改进蚁群算法的相对优越性。 2、在实际应用中,本文以江苏省科技攻关项目—生鲜加工配送体系食品安全关键技术研究与开发(BE2004311)为应用背景,结合苏果超市有限公司“苏果生鲜加工配送管理信息系统的设计,将改进蚁群算法引入到配送子系统的程序开发中。根据苏果配送的实际需求构建系统模型,对苏果配送路线进行优化,主要解决车辆路径问题(Vehicle Routing Problem,VRP),即确定最佳配送路线,使车辆的总行驶里程最少。参照***的利用基本蚁群算法求解VRP问题的算法实现思想,本文将改进蚁群算法运用到苏果VRP问题的求解中,设计出相应算法(简称算法一),以实现配送路线的优化。 3、由于算法一在实际配送中没有考虑到车辆的满载率,本文在算法一的基础上对其进行了改进。将原有算法一的小循环结束标志――蚂蚁只要一经过配送中心无论其载重已装多少都认为其一次小循环已经结束,改为蚂蚁只有在货物满载的情况下直接返回最初的起始点。根据这一思想,本文重新设计出相应的求解苏果VRP问题的算法(简称算法二)。