遗传算法车辆!!!(Z).doc

系统工程 课程论文（报告、案例分析）院 系 研究生院 专 业 物流工程 班 级 物流工程1班 学生姓名 金骁 学 号 1408524004 任课教师 张方凤 2015 年 1 月 5 日摘 要物流(Logistics)是20世纪发展起来的一门新兴学科,自产生以来就显示出了强大的生命力,成为当代最活跃、最具有影响力的新学科之一。物流作为社会经济活动的基础被誉为“未开发的黑色大陆”,企业的“第三利润源泉”,受到越来越多的关注。尤其是互联网技术的出现和发展,以信息技术为基础的物流服务在全球迅速崛起,物流信息化受到空前重视,使得物流现代化的发展产生了巨大的飞跃。物流本身所具有的开放性、全球性、低成本和高效率等特点,能够更好地满足现代商业发展的要求,推动社会经济的进步。世界各国都越来越重视物流的发展,尤其是在工业发达国家,物流的发展倍受关注,物流管理与物流技术己经得到了广泛的应用。在物流系统中，配送环节是首要的。一个车辆集合和一个顾客集合，车辆和顾客各有自己的属性，每辆车都有容量，所装载货物不能超过它的容量。在车辆的运输过程中，选择最佳的运输路径，降低成本，优化资源配置成为重中之重。本文以遗传算法作为基础，分析解决车辆运输过程中的路径问题。关键词：配送系统; 遗传算法; 车辆路径问题。第一章 配送系统配送是物流系统中运输环节衍生出来的功能，是整个物流业十分重要的一环。配送业务包含了很多方面的内容，如拣选，分货等等。同时，为了获得最大效益，物流企业都在尽可能的降低配送成本，优化配送系统。物流配送的核心部分是配送车辆调度问题。物流配送车辆调度问题是指:在给定运输任务的条件下,如何派车,组织运输,使空驶里程最少,运输成本最低。通过优化车辆调度方案,可以降低物流配送成本。因此,应用现代数学方法及计算机快速求解优化调度方案是国内外专家普遍探讨的重要课题。车辆路径问题(Vehicle Routing Problem ,VRP)是物流配送车辆调度中具有广泛应用的优化联合问题,是物流配送过程中的关键问题,是运筹学与组合优化领域的热点问题,在现代物流中居于中心地位。配送系统要求准确性，及时性兼备，同时也注重科学的优化管理方式。物流配送的核心就是车辆的调度问题，如何派车,组织运输,使空驶里程最少,运输成本最低。通过优化车辆调度方案,可以降低物流配送成本。第二章 车辆路径问题车辆路径问题的一般描述是:已知配送中心和一系列的客户需求点的位置以及客户需求量，配送中心的车辆数量以及车型，要求合理地设计配送车辆行驶路线，在满足一定的约束条件下，使车辆从配送中心出发，每辆车完成若干需求点的配送任务后，最后返回配送中心。通过优化车辆调度，使得在满足客户需求的前提下，达到一定的目标(如行驶总旅程最短，配送成本最低，物流配送服务水平最优，配送车辆数量尽量少等)。用最小化的行驶路程或时间为所有客户提供服务，物流成本达到最小，这是解VPR的目标方向。在简单的VRP中，VRP即 (Vehicle Routing problems)为通常假设所有车辆有相同的容量，每个客户有己知的货物要求，且都在车辆的容量制约范围内的车辆路径问题。是对方开始的开发了就是快乐的房间里等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等等第三章 遗传算法以及其在车辆路径问题上的应用图1 配送关系示意图2.1.遗传算法遗传算法(Genetic Algorithm ,GA)是模拟生物在自然环境中的进化过程而形成的一种自适应、全局优化的概率搜索方法。遗传算法是以适应度函数为依据,通过对种群中的个体进行遗传操作使个体结构重组的迭代处理过程。在这一过程中,逐代演化产生出适应度越来越好的个体,使问题的解一代一代地得以优化并逐渐逼近最优解。现在遗传算法不仅己经发展成为解决复杂全局优化问题的重要方法,而且在很多研究领域的具体科学实践中得到了广泛的应用,在VRP中的应用己经有一定成果。2.2.具体应用由于VRP即问题中需要考虑的因素很多(如配送中心数量、车型等),为研究方便,对车辆路径问题做如下基本假设:1.只有一个配送中心;2.车型为单一车型(即载质量相同);3.配送中心与客户的位置已知;4.客户的需求量已知;5.每个客户仅由一辆车访问;6.每条线路上的需求量总和不得超过车辆的最大载质量;7.所有车辆都是从配送中心出发,在客户处完成任务,最后回到配送中心;8.客户总的需求量不得大于车辆总的载质量。 化目标是满足客户需求的最短车辆行驶路径。模型中变量定义如下:m一配送车辆数n一需要服务的客户数q一车辆的载质量gi一第i个客户的货物需求量cij一表示从客户i到客户j的运输距离xijk=10 (1表示如果车辆k经过客户i向客户j，0表示其他情况yik=10 （1表示如果客户i需求由车辆k满足，0表示其他情况）为便于构造数学模型,将配送中心编号0，为客户依次编号为i(i=1,2,n)，模型中的约束主要为车辆的容量约束。则VRP问题的数学模型如下目标函数：约束条件：模型的优化目标是在满足客户需求的同时，使车辆行驶总里程最短。2.3基本遗传算法求解VRP即的步骤如下:1.使用自然数编码方式,构造可表示行车线路的染色体;2.设置控制参数(交叉概率P。,变异概率Pm,群体规模M,最大迭代次数T);3.随机产生初始种群,种群包含M个染色体,每个染色体表示一条行车线路;4.将种群中的每个染色体译为线路长度,并计算各个染色体的适应度。若满足算法终止条件,则停止,否则继续;5.根据适应度按轮盘赌选择法进行染色体复制;6.从群体中随机选择M*Pc个个体,选用最大保留交叉方式进行交叉操作;7.从群体中随机选择M*Pm个个体,选用反转变异算子对个体的子路径进行变异操作;8.对产生的新一代种群执行（4）,直到算法中止。应用遗传算法求解CVRP就是通过精心设计遗传算法的染色体结构、适应度函数、初始群体、遗传算子和控制参数,使算法能以较大的概率获得全局最优解。由于CV即与TSP存在相似性,在求解CVRP时,也经常采用与求解TSP相同的染色体表示方法,即基于路径表示的单层染色体编码方案。基本遗传算法采用基于路径表示的单层染色体编码方案进行染色体结构设计,引入惩罚函数处理车辆容量约束,选用合适的遗传算子进行遗传操作。为了提高效率,对CVRP采用自然数编码方式,CVRP的一条行车线路n+m+1:(0,i11,i12.i1s,0,.,0,i21,i22.im2,0,. ,0,im1 ,im2 ,.imk,0),其中拓表示第几项任务。这样的染色体结构可通俗地解释为车辆从配送中心0出发,经过任务i11,i12,.,i1s后,回到配送中心0,形成子路径1;然后又从配送中心0出发,经过以前未访问的任务i21,i22 ,. ,i2t后,返回配送中心0,形成子路径2;如此反复,直到所有的n项任务全部被访问为止。如染色体0123045607890表示行车路线:子路径1:配送中心O客户1客户2客户3配送中心O子路径2:配送中心0客户4客户5客户6配送中心0子路径3:配送中心O客户7客户8客户9配送中心O这种染色体结构子路径内部是有序的,若子路径1中客户相互交换位置,会使目标函数值改变;而子路径之间是无序的,若子路径1和子路径2相互交换位置,不会改变目标函数的值。这里m为完成任务所需要的车辆数。为了安排货运路线,首先要对完成配送任务的辆数进行合理的估计。一般来说,问题的约束越多,组织线路就越难,一辆车所完成的满足所有约束的任务越少。实际计算过程中常根据式(4.9)来确定车辆数。这里m为完成任务所需要的车辆数。为了安排货运路线，首先要对完成配送任务的车辆数进行合理的估计。一般来说，问题的约束越多，组织线路就越难，一辆车所完成的满足所有约束的任务越少。实际计算过程中常根据式来确定车辆数。m=gi/q+1其中m是车辆数，表示向下取整，(0l)根据约束条件的多少进行调整。约束条件越多，则越小，反之越大。一般取=0.85。 第三章 总结本文主要介绍了基于遗传算法对于运输过程中的车辆路径问题的优化选择以及配送系统和车辆路径问题的概念。对于整体的介绍以及了解还不全面。另外在物流配送时，有时还需要考虑车辆运输能力不同的一个限制条件，则能更好的适用于多种物流配送的情况，这是以后的一个研究方向。（因知识水平和时间有限，所以关于此算法整体性以及验证还不够完整，会进行后续继续研究补充）参考文献1 赵振华.遗传算法在特种物流配送中的应用研究(D).成都:四川大学，2007