2022年2022年路径优化的算法 .pdf

《2022年2022年路径优化的算法 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年路径优化的算法 .pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、广西工学院2008 届毕业设计论文1 摘 要供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法 Floyd 算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供

2、货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。关键字:路径优化遗传算法 Floyd算法名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 25 页 -广西工学院2008 届毕业设计论文2 Abstract The Path Optimization of Goods Supply Car is the effective way to reduce business costs and enhance economic efficiency.The problem of the Path Optimization of Goo

3、ds Supply Car can be seen as Vehicle routing proble.This paper presents a solution to Vehicle routing proble with Single direction road by Researching the Way of Path Optimization of Goods Supply Car.First,This paper Establish the mathematics model of Vehicle routing proble and introduced the shorte

4、st path algorithm-Floyd algorithm,then taking the Single direction road into account at the same time.Seeking the shortest distance between any two points and landing path by this algorithm,then turn this problem in to TSP.Solving this problem can get the Optimize delivery routes which with Single d

5、irection road by GA,then take some district in the state City of LiuZhou road as an example start experiment.The Imitate the true result showed that this method can be better optimize results.Finally improving the basic GA with a priority strategy,then proceed to imitate the true experiment to the s

6、ame Path diagram.The result expresses the improvement the heredity calculate way ratio the basic heredity calculate way can get quickly give satisfaction of excellent turn the result.Keyword:Path Optimization genetic algorithm Floyd algorithm 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 25 页 -广西工学院2008 届毕业设计论文1 目

7、 录1 绪论.1 1.1 课题研究的意义.1 1.2 国内外供货小车路径优化问题的研究现状.2 1.3 本文的主要研究内容.3 2 供货小车行驶路径优化问题.4 2.1 无约束的供货小车路径优化问题.4 2.2 有单行道路约束的供货小车路径优化问题.4 3 任意两送货点最短路径.5 3.1 用 Floyd 算法求解供货小车的任意两送货点最短距离.5 3.2 用 Floyd 算法求解带单行道的任意两送货点间最短路径.6 3.3 实例仿真结果.7 4 供货小车路径的优化.9 4.1 建立 TSP问题的数学模型.9 4.1.1 概述.9 4.1.2 数学模型.10 4.2 遗传算法的基本理论.10

8、4.2.1 遗传算法的特点.11 4.2.2 标准遗传算法的遗传算法过程描述及步骤.11 4.3 用遗传算法求解供货小车路径的优化问题.12 4.3.1 供货小车路径寻优问题的遗传算法实现.12 4.4 仿真结果.17 4.5 用改进遗传算法求解供货小车路径的优化问题.17 4.5.1 遗传算法改进的思想.17 4.5.2 仿真结果分析.18 5 总 结.19 参考文献.20 致 谢.22 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 25 页 -广西工学院2008 届毕业设计论文1 1 绪论1.1 课题研究的意义随着经济全球化的不断深入，许多跨国公司都已经或计划将制造、采购中

9、心转移到中国，越来越多的国内企业也开始面向全球进行生产和经营，中国作为世界制造中心的地位日益凸显，这种大的国际环境更加刺激了我国物流业的高速发展。与此同时，国家经济建设的深入和商业活动的繁荣刺激了市场对物流服务需求的激增:一方面表现在社会物资流通总量高速增长，呼唤更优化的快递物流解决方案和专业的物流咨询服务;另一方面则是越来越国际化的商业运作要求物流服务水平跟上国际化标准，在速度、可靠性、安全性、个性化、战略远见等方面提出了更高要求。因此，通过降低物流成本，使得物流业的开展更加科学合理并进而通过开展服务创新，提升服务质量己经成了广大物流服务供应商的共识。本文着重从配送环节中的车辆行驶路径选择入

10、手，分析如何优化调整小车送货线路问题，进而达到降低物流成本的目的。那么如何将车辆有效的使用并决定其最经济的行驶路线图，在最短的时间内把商品送到顾客的手中，提高顾客的满意度，将是配送中心作业的重点。显然配送服务的要求将越来越高，为了实现配送成本的降低，必须对配送过程进行合理规划。这就涉及到时间、财务、环境及服务质量四方面的因素，首先从时间上要考虑准时性、快速响应;财务上要考虑运输涉及的各种开支(员工薪酬、消耗等);环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音污染;最后从服务质量上，要求满足顾客要求，达到顾客满意度最大化。这些都可以通过改进运输方式、线路规划等来改善。目前，物流配送活

11、动中的配送运输路径确定问题，成为近二十多年来车辆路径问题的重点研究对象和应用领域。在配送运输中，由于配送用户多，城市交通路线又复杂，如何组成最佳路线，如何使配装和配送路线有效搭配等，是配送运输的特点，也是难度较大的工作。于是采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径，也是配送活动中非常重要的一项工作。路径优化是对车辆行驶路线的优化过程，也是对车辆进行调度的一个问题。由于运输任务的性质和特点不同、道路条件及车辆类型等各种约束标准不同，即使在相同收发货运点间完成同样任务时，所采用的行驶路线方案也可能不同。而车辆按不同运行路线完成同样的运输工作时，其

12、利用效果是不一样的。因此，在满足货运任务要求的前提下，对各种不同的路径问题如何选择最经济的运行路线，是车辆路线安排的一项重要工作。可见VRP 问题实质上就是路径优化问题，因此，规划好车辆路径的优化选择，尤为重要。所谓路径优化(即最经济的运行路线)，就是在保证货物需求的前提下，达到运输时间和运输费用最省的路线。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 25 页 -广西工学院2008 届毕业设计论文2 1.2 国内外供货小车路径优化问题的研究现状对于路径优化这类问题，国内外有不少学者进行了探讨和深入研究，并且提出了许多求解此类问题的有效算法，工具。东北大学信息科学与工程学院系统

13、工程研究所的蒋忠中，汪定伟通过将 B2C 电子商务企业的实际物流配送网络描述为由配送中心和顾客两类节点构成的不完全无向图，建立了0-1整数规划的物流配送路径优化模型首先利用Floyd 算法求得不完全无向图中各节点间的最短路径和最短路径长度，然后设计了捕食搜索算法对模型进行解通过仿真实例计算，取得了满意的结果1。华中科技大学计算机科学与技术学的黄红将其配送路径抽象为TSP 问题，完成现实空间到问题空间的映射，使实际问题转化为平衡运输问题的数学模型，采用单纯形法和贪婪法配合使用，从而求出最优解或满意解2。重庆大学经济与工商管理学院的李志威，张旭梅针对蚂蚁算法在求解大规模物流配送问题中存在的不足，利

14、用动态扫描方法在区域选择方面的实用性和蚂蚁算法在局部优化方面的优点，提出综合两种方法的混合算法，并获得了较满意的效果3。哈尔滨运通汽车销售服务有限公司的尹训波通过对改进的蚁群算法（可见度的改进，信息素浓度更新规则的改进）对物流配送路径的优化，得到了令人满意的结果4。长沙理工大学计算机与通信工程学院的柳林，朱建荣用遗传算法求解物流配送路径优化问题，有效地求解得问题的最优解或近似最优解，但遗传算法存在易陷入局部极小值和收敛速度慢等缺点，在总体上解的质量不是很高5。针对这些问题，北京交通大学交通运输学院的郎茂详、胡思继提出将爬山算法与遗传算法想结合，能有效克服遗传算法在局部搜索能力方面不足6；湖南科

15、技大学的陈湘州，黎志明，刘祖润通过引进一种进化逆转算子，其局部寻优能力很强，收敛性明显好于标准遗传算法7；山东建筑工程学院管理工程学院，东南大学经管学院的亓霞，陈森发对带有约束度为时间窗的小车供货配送路径采用了一种改进小生境遗传算法来优化8，马炫，陈琼还用遗传算法对度约束单源多目的路径优化9。南开大学商学院,天津职业大学的张建勇 ,李军设计了具有同时配送和回收需求的车辆路径问题(VRPSDP),将正向物流和逆向物流同时加以考虑，与现实经济生活联系极为紧密10。沈阳建筑大学的韩中华，吴成东，杨丽英，邓湘宁针对基本遗传算法在计算大型网络的优化问题时表现出的求解效率低等缺点，在基本遗传算法中引入了子

16、群体和迁移策略，提出了基于并行遗传算法的最优路径选择方法，使得在大规模路网中求解效率和求解质量的平衡问题得以解决11。长安大学的弓晋丽,程志敏基于Matlab 进行了物流配送路径优化问题遗传算法的编码,利用Matlab 强大的数值计算能力较好地解决了车辆行驶路径优化问题并进行了实例验证,对物流企业实现科学快捷的配送调度和路径的优化有实际意义12。自20世纪80年代以来，国际上流通业的发展出现了一种大的变化趋势整合(加egrale)即综合、集成、系统化和一体化的意思。早在1962年Balinski等人首先提出 VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP 模型13

17、。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 25 页 -广西工学院2008 届毕业设计论文3 1971年，Eilon 等人提出将动态规划法用于固定车辆数的VRP，通过递归方法求解14。1974年，Wren，Gillett等人提出 Sweep 算法(扫描法)15。1981年，Christofides等人提出了k度中心树和相关算法，对固定车辆数 m 的m 一TSP 进行k度中心树松弛16。后来，M.L.Fishe对这种方法做了进一步改进，可求解有 134个客户的 VRP17。1991年，Gendreau等人将禁忌搜索方法应用于 VRP18。它是针对 VRP 比较好的启发式算法，

18、可以成功地应用于许多经典的VRP。其后 E.Taillard等人通过按角度和路径重心对原问题的空间进行分割，结合禁忌搜索平时模拟退火对子问题求解，实现了对问题求解的并行化19。1.3 本文的主要研究内容随着物流业的发展，物流配送中的路径优化问题已不单单是求取路径最小化的问题，它要考虑的问题是越来越复杂，成为复杂性颇高的问题，传统的精确解法求解此类问题己落后。尤其本文要解决的是经典的、带单行道约束的配送路径优化相结合的问题，从难易程度上讲，以往的优化解法不仅耗时而且要求求得最优解，这是一种理想化的求解方法。因此本文的目的是建立以配送里程最短为目标的配送车辆路径优化模型，通过模型的构建，来解决实际

19、当中可能遇到的问题，进而优化问题;在求解过程中，将遗传算法的逻辑思维应用到 TC 编程中，得到最合理的配送方案，避免了多目标的计算复杂性，同时达到了多目标的效果。本文的主要内容是:简单介绍了论文的研究背景、研究目的及意义，对论文涉及到的相关概念进行界定，为论文的后续工作做好铺垫;通过收集国内外学者专家关于路径优化（即VRP）的研究的相关文献资料并对其进行整理、分类，详细介绍了 VRP 国内外研究现状，尤其对以往解决 VRP 问题的方法的几个大致方向以及对带各种约束的 VPR 问题的解决方法的国内外研究现状分别展开了介绍;总结国内物流配送存在的问题及成因，说明了解决 VRP 的必要性及现实意义;

20、紧接着针对前面涉及到的物流配送路径优化的一般方法作以介绍;在论文的核心部分，针对本文要解决的问题，构建以配送里程最短为目标的配送路径优化模型，其中充分考虑了城市单行道的情况，将单行道路径优化体现在模型当中，作为一个重要的约束条件来约束配送方案的选择，进而对配送路径优化进行制从中选择最佳路径;数学模型的求解作铺垫对模型求解过程中需要用的遗传算法的基本理论进行论述，为将遗传算法的逻辑思维应用到TC 的编程当中，结合算例进行研究，验证该模型算法的合理性及有效性，说明其优越性;通过对全文内容的总结，提出了进一步研究供货小车行驶路径优化问题的方向。名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页

21、，共 25 页 -广西工学院2008 届毕业设计论文4 2 供货小车行驶路径优化问题2.1 无约束的供货小车路径优化问题物流配送车辆调度问题即路径优化问题最早是由DanZitg 和Ramser 于1599年首次提出的，国外将其归结为或称之为VehicleRoutingProblem(简称VRP 问题)。该问题一般定义为:对一系列给定的顾客(取货点或送货点)确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心，并在满足一定的约束条件下(如车辆容量限制、行驶里程限制、时间限制、顾客需求量、交发货时间等)，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少

22、等)。VRP 问题实质上就是路径优化问题，因此，规划好车辆路径的优化选择，尤为重要。所谓路径优化(即最经济的运行路线)，就是在保证货物需求的前提下，达到运输时间和运输费用(通常为吨公里)最省的路线。路径优化问题是对车辆行驶路线的优化过程，也是对车辆进行调度的一个问题。由于运输任务的性质和特点不同、道路条件及车辆类型等各种约束标准不同，即使在相同收发货运点间完成同样任务时，所采用的行驶路线方案也可能不同。而车辆按不同运行路线完成同样的运输工作时，其利用效果是不一样的。因此，在满足货运任务要求的前提下，对各种不同的路径问题如何选择最经济的运行路线，是车辆路线安排的一项重要工作。选取恰当的配送行驶路

23、径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本，因此设计合理、有效的车辆路线方案，尽量减少车辆数量和配送里程数就成为非常实际的问题。2.2 有单行道路约束的供货小车路径优化问题随着城市建设的发展，市区道路出现交通秩序较乱、高峰期拥堵的情况，为了解决这一问题，越来越多城市在市区的一些地方采用单行交通组织方式，这样才能对城区内车流进行重新组织，缓解交通拥堵程度。通过前人的文献来看，在研究供货小车行驶路径优化问题的时候没有把这个问题考虑进去，把城市单行道这个约束度加进去是很有必要的，这样才能满足现在的大多数城市的情况。单行道直观来理解就是线路的走向是单

24、方向的，比如在某条特定的线路上车辆(行人)只能从一点走向另一点，而无法返回(特定规则限制)，反过来亦如此带有单行道路约束的供货小车路径优化问题和上面提到的无约束的供货小车路径优化问题差别不大,小车在送货过程中遇到的单行道都是正向时其实与没有单行道的路径规划是一样的,只有当在小车供货过程中遇到逆向单行道时,这时小车必须改道去寻另外一条路径到达送货点，为了能得到一条比较优的路径，要重新规划路径网络图。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 25 页 -广西工学院2008 届毕业设计论文5 3 任意两送货点最短路径3.1 用 Floyd 算法求解供货小车的任意两送货点最短距离供

25、货小车行驶路径网可以看做是带权的图，图3.1 就是一个加权图 G=（V，E,W)来表示。其中V为顶点集，V=vii=1，2，n；E为边集VvvvveEjiji,，W 为权集，VuvvvwWjiji,。本文不仅要把交叉路口看成图G 的顶点，还要把各个送货点也看成图G 中的顶点，边是指供货小车行驶的路径，权是指任意两顶点间路径的长度。而供货小车行驶路径网其实就是一个无向图，它要求每一个顶点经过一遍且仅经过一遍。图3.1 就是一个无向图 G=（V，E,W)。图3.1 无向图如图3.1 无向图所示的看成是一个供货小车行驶路径示意图。其中顶点1是发货点，顶点2,4,6 看成是送货点,3，5看成是交叉路口

26、。本文用 Floyd 算法求解供货点间的最短路径。Floyd 算法其实就是全部顶点间最短路径算法，是 1962年由福劳德(Floyd)提出的算法.它的主要思想是从代表任意两个顶点vi到vj的距离的带权邻接矩阵开始，每次插入一个顶点 vk，然后将 vi到vj间的已知最短路径与插入顶点 vk作为中间顶点(一条路径中除始点和终点外的其他顶点)时可能产生的 vi到vj路径距离比较，取较小值以得到新的距离矩阵.如此循环迭代下去，依次构造出n个矩阵D(1)，D(2)，D(n)，当所有的顶点均作为任意两个顶点vi到vj中间顶点时得到的最后的带权邻接矩阵 D(n)就反映了所有顶点对之间的最短距离信息，成为图G

27、的最短距离矩阵。下面描述该方法的构造矩阵的原理。对一个有 n个顶点的图 G，将顶点用 n个整数(从1到n)进行编号。把G 的带权邻接矩阵W 作为距离矩阵的初值，即 D(0)=(dij(0)nn=W。第一步:构造D(1)=(dij(1)nn，其中dij(1)=mindij(0)，dil(0)，dik(0)是从vi到vj的只允许以v1作为中间路径中的最短长度。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 25 页 -广西工学院2008 届毕业设计论文6 第二步:构造D(2)=(dij(2)nn，其中121212,minjiijijdddd从vi到vj的只允许以 vi，v2作为中间点

28、的路径中最短路的长度。第n步:构造D(N)=dij(n-1)，din(n-1).dnj(n-1)从vi到vj的只允许以 v1，v2，vn作为中间点的所有路径中最短路的长度，即是从从vi到vj中间可插入任何顶点的路径中最短路的长度，因此nD即是距离矩阵。本文只用考虑送各个货点之间的最短路径，通过Floyd 算法求出各个顶点之间的最短距离并得到最短路径走法。3.2 用 Floyd 算法求解带单行道的任意两送货点间最短路径带单行道约束的路径优化问题实际上可以看做是带权混合图的最短距离问题。混合图中既包括有向边，也包括无向边。图3.2 就是一个带权混合图，它与图3.1 区别在于其中的几条边是有向边。图

29、3.2 混合图上图3.2混合图所示的看成是一个单行线交通示意图。已知一个各边权值均大于 0的带权有向图，对每一对顶点jivv，要求求出jivv 到之间的最短路径和最短路径长度。其实用Floyd 算法求解有单行道约束的最短路径问题与无约束最短路径问题是差不多的，不同的在于要考虑有向边的权值问题。本文的思想是把那些无向边看作是有往返两重边的有向边，两无向边的顶点顶为jivv 和，无向边jivv,可以看成是在这两个送货点之间存在权值相同的两条有向边jivv,和ijvv,。有向边正向时权值不变，有向边反向时权值赋为所有两点间距离的总和。其他的求解步骤和上面的不带约束条件的供货小车的最优行驶路径的步骤是

30、一样的。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 25 页 -广西工学院2008 届毕业设计论文7 对图3.2进行分析：顶点 1是发货点，顶点 2，4，6看成是送货点，3，5都看成是交叉路口。这时就要通过 Floyd 算法求解出任意两点间最短距离。看从1到2的线路，先随机走一条为 1-2，得到一条路经，再在 1-2之间插入 3，就得一条新的路径 1-3-2，这时候1-3是反向单行道，它的值是所有顶点间距离的总和，可以看出比较优的走法是前面一种，再拿第一种走法和另外一种走法1-6-5-3-2 相比，再通过比较两条路径的长度，再选择那条比较短的路线。3.3 实例仿真结果本文采集

31、了柳州市市中心某区域地图如图3.3 所示为例进行送货，采用C 语言程序对供货小车行驶路径进行仿真，得到优化的供货小车行驶路径。这个地图中包含有一个发货点,十个送货点，十四个交叉路口，把这些点都看成是混合图G=（V，E,W)的顶点，其中1是发货点，2到11这十个点是送货点，其他的为交叉路口，供货小车行驶的路径满足的要求是：要求每个送货点都有一辆小车送货且只有一辆且只送一次，使得每条行驶路线尽可能短即尽可能优。求解方案都是按上面提到的思想来解决供货小车最优行驶路径的问题。图3.3 柳州市某区域地图对这个图进行仿真得到以下结果1 2 3 4 5 6 7 8 9 10 11 1 0 301 540 2

32、70 823 520 655 365 894 235 900 2 301 0 807 571 1124 821 956 566 1095 436 1101 3 540 807 0 398 951 648 783 905 1434 775 1079 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 25 页 -广西工学院2008 届毕业设计论文8 4 270 571 398 0 553 250 385 635 1164 505 681 5 883 866 543 803 0 278 413 778 1030 1018 446 6 605 806 1056 702 637 0 267

33、 500 1029 740 563 7 582 783 941 679 522 267 0 477 1006 717 448 8 365 566 860 462 895 592 727 0 529 500 939 9 894 1095 1389 991 1424 1121 1256 529 0 863 1128 10 235 436 775 505 1058 755 890 500 863 0 665 11 721 420 759 991 1544 1241 1376 939 1128 665 0 以上是通过 Floyd 算法得到的把各个供货点提取出来的矩阵，这个矩阵给出了任意两个送货点之间的

34、最短路径值，对这个路径图仿真同时还得出任意两点(包括交叉路口)最优路径的走法。通过上面的矩阵可以看出，当tsvvd,这条线路中所有点边全部是无向边时,tsvvd,=stvvd,当tsvvd,中包含有有向边时,tsvvd,stvvd,例如1,22,1dd，这是因为2,1d所走的最优路径是 1-24-2，1,2d所走的最优路径是2-24-2，这里面不包含有向边，即单行道，所以所走的路径都是一样；7,99,7dd，这就是因为9,7d所走的最优路径是 7-18-17-8-23-9，而7,9d的所走的路径是 9-23-8-17-15-19-20-7，这是因为所走的路线有单行道，两点间来回所走路径不是同一

35、条，所以路径距离也是不相等的。名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 25 页 -广西工学院2008 届毕业设计论文9 4 供货小车路径的优化4.1 建立 TSP问题的数学模型4.1.1 概述由于现代配送具有多频次、小批量、多品种、高效率的特点，配送要准确做到7R(right product，right quality，right tillle，right place，right codiniton，irght customer，right cost)，如何合理、有效的对配送路线进行优化，就成为非常现实的问题。进行配送路线优化时，必须有明确的目标，遵循基本的原则。配送路

36、线方案目标的选择可以从以下几个方面来考虑:(1)配送效益最高或配送成本最低。效益是企业追求的主要目标，可以简化为用利润来表示，或以利润最大化作为目标;成本对企业效益有直接的影响，选择成本最低化作为目标值与前者有着直接的联系。当有关数据容易得到和容易计算时，就可以用利润最大化或成本最低作为目标值。(2)配送里程最短。如果配送成本与配送里程相关性较强，而和其他因素相关性较弱时，配送里程最短的实质就是配送成本最低。则可考虑用配送里程最短作为目标值，这样就可以大大简化线路选择和车辆调度方法。(3)配送服务水准最优。如准时配送要求成为第一位时，或需要牺牲成本来确保服务水准时，则应该在成本最大容忍的限度下

37、，以服务水准为首选目标。这种成本的损失可能从其它方面弥补回来，如优质服务可以采取较高的价格策略。(4)配送劳动的消耗最小。即以物化劳动和活劳动消耗最小为目标，在许多情况下，如劳动力紧张、燃料紧张、车辆及设备较为紧张的情况下，限制了配送作业的选择范围，就可以考虑以配送所需的劳动力、车辆或其它有关资源作为目标值。TSP 一般描述为：旅行商从驻地出发经所要去的城市经过且只经过一次后返回原地应如何安排其旅行线路才能使总的旅行距离(或时间费用等)最少,对于现实问题由于限制条件的增加 TSP 可衍生出许许多多相关的问题,本文最主要是的优化目的是上面提到的第(2)个,即配送里程最短。TSP 模型数学描述为有

38、一个配送中心（编号为0）现在有 n个点需要配送，以 1，n表示，求满足货运需求的费用最小的车辆行驶线路。其主要假设还有：1）供货小车以配送中心为起点和终点；2）车辆行驶相同的路段，其成本相同；3）每一节点只允许车配送一次；4）弧上没有容量限制。名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 25 页 -广西工学院2008 届毕业设计论文10 4.1.2 数学模型根据上述目标和假设，一般TSP 的数学模型如下minijijnjniXCZ1010 (4.1)1,1,0110njXijni (4.2)101,1,01njijniX (4.3)1SXij (4.4)1,1,001nio

39、rXij1,1,0nj (4.5)说明1）决策变量：;10jiijx行驶到点车辆从点若行驶不存在2）参数变量：ijC：点i 到点j 的行驶距离；N：配送点数；3）方程说明式（4.1）为目标函数；为极小化车辆行驶距离式（4.2）（4.4）为约束方程式(4.2)表示对于任何一个送货点除配送中心只有一辆车到达送货点式(4.3)为消去支路约束即消去不构成完整线路的解式(4.4)为变量的取值约束4.2 遗传算法的基本理论遗传算法是一种从生物进化的规律中得到灵感和启迪的自适应全局随机搜索方法。由于遗传算法的整体搜索策略和优化计算时不依赖于梯度信息的特点，所以它的应用范围非常广泛，尤其适合于处理传统搜索方法

40、难以解决的高度复杂的非线性问题。有专家断言，遗传算法是用来解决NP难题的趋势。Berthold,Malmborg,Ochi 和 Luiz 都曾利用遗传算法对物流配送的车辆路径问题进行求解，但仍处于尝试阶段，还有待于进一步的研究。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 25 页 -广西工学院2008 届毕业设计论文11 4.2.1 遗传算法的特点同传统的算法相比较，遗传算法具有以下特点:遗传算法对问题参数的代码集起作用，而不是对参数本身起作用。遗传算法处理的对象是染色体，因而要求把所要优化问题的基本参数转化成定长的优先符号的染色体。遗传算法是从初始群体开始搜索的，而不是从

41、单点开始搜索的。许多传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这种点到点的搜索方法在多峰值优化问题中，首先找到的可能不是最优峰值;而遗传算法是以点集开始的寻优过程，初始群体是随机地在搜索空间中选取的，这样在搜索过程中达到最优峰值的概率远大于点到点方法的概率。遗传算法在搜索过程中只使用适应度函数信息，而不用导数及其他辅助信息。对于不同类型的优化问题，传统方法需要不同形式的辅助信息，没有一种优化方法能适应各类问题的要求。遗传算法在优化过程中，放弃使用这些辅助信息，具有广泛适应性。遗传算法使用概率转换规则而不用确定性规则。遗传算法使用概率转换来调整其搜索方向，各代群体间没有统

42、一的联系规律。但使用概率转换规则并不意味着这种方法属于随机算法范畴，它只是使用随机转换作为工具来调整搜索过程趋向于目标函数不断改进的区域。与传统方法相比，遗传算法的优越性主要表现在:首先，在遗传算子的作用下，遗传算法具有很强的搜索能力，能以很大概率找到问题的全局最优解:其次，由于它固有的并行性，能有效地处理大规模的优化问题。4.2.2 标准遗传算法的遗传算法过程描述及步骤遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适应环境的个体，使群体进化到搜索空间中越来越好的区城，这样一代一代地不断繁衍进化，最后收敛到一群最适应环境

43、的个体，求得问题的最优解。遗传算法步骤如下:(1)构造满足约束条件的染色体。由于遗传算法不能直接处理空间的解，所以必须通过编码将解表示成适当的染色体。实际问题的染色体有多种编码方式，染色休编码方式的选取应尽可能地符合问题约束，否则将影响计算效率。(2)随机产生初始群体。初始群体是搜索开始时的一组染色体，其数量应适当选择。(3)计算每个染色体的适应度.适应度是反映染色体优劣的唯一指标，遗传算法就是要寻得适应度最大的染色体。(4)使用选择、交叉和变异算子产生子群体。这三个算子是遗传算法的基本算子，其中复制体现了优胜劣汰的自然规律，交叉体现了有性繁殖的思想，变异体现了进化过程中的基因突变。名师资料总

44、结-精品资料欢迎下载-名师精心整理-第 14 页，共 25 页 -广西工学院2008 届毕业设计论文12(5)重复步骤(3),(4)直到满足终止条件为止。遗传算法的运算流程可以如下表示;图 4.1 遗传算法运算流程4.3 用遗传算法求解供货小车路径的优化问题4.3.1 供货小车路径寻优问题的遗传算法实现(1)编码个体或当前近似解被编码为由字母组成的串，即染色体，使基因(染色体值)能在域决策变量上被唯一描述。在遗传算法中，染色体的表现形式通过编码机制来实现的。算法的编码机制直接影响着算法的整体性能，并且也决定了种群初始化和各种遗传算子的设计等各种过程，因此说，编码机制是遗传算法的关键步骤。编码随

45、机产生初始种群计算染色体的适应轮盘赌法复制子代交叉算子变异算子满足终止条件Y 算法结束N 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 25 页 -广西工学院2008 届毕业设计论文13 由于遗传算法应用的广泛性,迄今为止人们已经提出了许多种不同的编码方法.总的来说,这些编码方法可以分为三大类:二进制编码方法、浮点数编码方法、符号编码方法。人们常用的编码方案有二进制编码、格雷码编码、浮点数编码、符号编码方法、多参数级联编码方法、多参数交叉编码方法、实数编码、Gary 编码、自然数编码等。本文采用的 Grefenstette等提出的一种新的巡回路线编码方法,该方法能够使得任意的

46、基因型个体都能够对应于一条具有实际意义的巡回路线。下面介绍这种新的编码方法。对于一个供货小车路径优化问题的送货点列表W，假定对每个送货点的一个送货顺序为 T：T=（t1 t2 t3 tn）规定每送完一个送货点，就从送货点列表W中将该送货点去掉，则用第nii,3,2,1个所送的送货点it在所有未访问送货点列表W-t1 t2 t3 ti 中的对应位置序号11inggii就可表示具体访问哪个送货点，如此这样知道处理W中所有的送货点。将全部ig顺序在一起所得到的一个列表：1gG2g3g ng就可表示一条巡回路线，它即为遗传算法中一个个体的基因型。假如有这样一个简单的参考点:T=(1 2 3 4 5 6

47、 7 8 9 10 11)一个送货路线如下:1-3-4-8-11-7-10-5-2-6-9 则被表示为参考表G如下:G=(1 2 2 5 7 4 5 2 1 1 1)（2）初始群体生成种群的初始化操作是指随机产生N个初始串结构数据，每个串结构数据称为一个个体，N个个体构成了一个群体。遗传算法以这N个串结构作为初始点开始迭代。一般情况下，种群的初始化操作都是随机的，因为通过随机的方式生成初始种群，能够有效地避免种群的单调性，防止种群陷入局部最优。当然，为了避免初始的种群中出现很多不合格的解，也可以采用简单的局部搜索算法获取初始解，不过这会消耗一定的问题求解时间。（3）确定适应值函数xg在遗传算法

48、中使用适应度(Fitness)这个概念来度量群体中各个个体在优化计算中能达到或接近于或自助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 25 页 -广西工学院2008 届毕业设计论文14 率就较大;而适应度较低的个体遗传到下一代的概率就相对小一些。度量个体适应度的函数称为适应度函数(FitnessFunction)。适应度函数也称为评价函数，是根据目标函数确定的用于区分群体中个体好坏的标准，算法演化过程的驱动力，也是进行自然选择的唯一依据。适应度函数通常要求是非负的，任何情况下都希望其值越大越好。而目标函数可能有正有负，

49、既有时求最大值，有时求最小值，因此需要在目标函数与适应度函数之问进行变换。目标函数是提供一测量手段，测量个体在问题域的完成情况。在一个最小化问题中，最适合的个体对应最小的目标必数值。未经加工的函数值通常只用在遗传算法的中期来判断一个个体的相对性能。另一函数-适应度函数通常用于转换目标许多情况下，适应度函数值对应大量子代-预计在下一代中能存在的个体。通常使用如下转换进行适应度概率分配。个体的适应度-每一个个体的 F(ix)通过个体的未加工的适应度ixf相对整个种群的适应度被计算出来，即NindiiiixfxfxF1式中，Nind是是种群大小，ix是个体 i 的表现值，与此同时适应度分配确保每个个

50、体均存按其相对适应度再生的机会，但它不能处理负的目标函数值。本文的适应度函数是由下面的公式得到的:xfitness=5001.1.1xxvaluexpopulationzvaluexpopulationz式中xfitness就是适应度函数,z 是供货小车行驶路径最长的路径长度,valuexpopulation.就是第x条供货小车行驶路线的长度,则适应值越大方案越优。（4）选择选择(Selection)又称复制(Reproduction)，它模拟了生物进化过程中自然选择的规律，按照某种特定的方法从群体中选取N个个体放入交配池。选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代