遗传算法在vrp中的应用与研究.doc

分类号单位代码 10618
密级学号 10819002
硕士学位论文
论文题目: 遗传算法在VRP中的应用与研究
ic Algorithm Research and Application in the VRP
研究生姓名: 王刚

导师姓名、职称: 池洁教授
申请学位门类: 工学
专业名称: 系统工程
论文答辩日期: 2011年月日
学位授予单位: 重庆交通大学
答辩委员会主席:
评阅人:

2011年 04 月
重庆交通大学学位论文原创性声明
本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。
学位论文作者签名: 日期: 年月日
重庆交通大学学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被查阅和借阅。本人授权重庆交通大学可以将本学位论文的全部内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本人学位论文收录到《中国学位论文全文数据库》,并进行信息服务(包括但不限于汇编、复制、发行、信息网络传播等),同时本人保留在其他媒体发表论文的权利。

学位论文作者签名: 指导教师签名:
日期: 年月日日期: 年月日
……………………………………………………………………………………………………
本人同意将本学位论文提交至中国学术期刊(光盘版)KI系列数据库中全文发布,并按《中国优秀博硕士学位论文全文数据库出版章程》规定享受相关权益。
学位论文作者签名: 指导教师签名:
日期: 年月日日期: 年月日
摘要
在科学技术飞速发展的今天,物流业面临着更多的挑战,要想在挑战中获胜,就要进行变革,而在创新变革的过程中,由于运输成本占物流总成本的50%以上,因此,如何优化配送路径也就成为了物流企业最关心的课题。车辆路径问题(Vehicle Routing Problem,简称VRP)是一个复杂的组合优化问题,针对这一问题的研究已经越来越广泛,运输路径的好坏将严重影响配送的速度、成本和用户满意度等,因此,本文应用遗传算法来优化车辆路径的问题,这对企业实现降低运营成本、增强顾客满意度、提高服务质量等都有很高的参考价值。
目前对于车辆路径问题的研究还处于探索阶段,还没有一种万能的方法适合所有的问题模型。在考虑车辆路径问题的约束方面也不够全面,很多研究都仅仅局限于满足车载量约束等初级阶段,没有考虑到时间窗约束、客户满意度约束等。针对问题的最终目标,很多研究仅仅考虑路径最短,而不注重配送车辆数目、客户配送等级等问题,导致总配送成本的提高,本文针对这些问题做了进一步的研究,考虑了时间成本、客户满意度等问题,使总物流成本得到了降低,提高了企业的经济效益。
本文主要的研究内容为:
首先,系统地介绍了车辆路径问题以及各类算法的相关理论知识,并在此基础上深入分析此问题模型,通过对现有的解决车辆路径问题的方法进行研究,采用局部改进的遗传算法解决车辆路径问题。
其次,考虑了车辆路径问题中的车载量约束、时间窗约束、客户满意度约束等,完善了问题模型,并对模型进行了优化,使模型在满足所有条件的前提下更加简化,更容易算法的实现。
对遗传算法采用自然数编码策略,使其更容易满足不同模型的需求;通过扫描法生成算法的初始种群,一定程度上避免了纯随机策略导致的初始种群适应值过低的现象,加快了算法的收敛速度;采用排序法进行遗传算子的选择,使适应值高的个体遗传到下一代的概率得到了提高;将逆转算子与变异算子结合,使变异的过程更具规则性,同时降低了优良基因缺失的概率。对于算法的设计,每一个步骤都降低随机性选取的概率,加快算法的收敛速度,降低局部收敛概率,使其更容易寻找到最优解。
通过案例验证了算法的优越性,并通过matlab对算法进行模拟仿真,使算法的应用更加直观和清晰。
关键词:遗传算法;VRP;配送成本;遗传算子;仿真
ABSTRACT
With the rapid development of the science and technology, the logistics industry is faced with more challenges. Thus the reformation is highly demanded if you want to eed. Since the delive