摘要供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。
本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。
首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法—Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。
最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。
关键字:路径优化遗传算法 Floyd算法AbstractThe 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 Goods 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 shortest 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 direction 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 same 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 algorithm1绪论 (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)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)1.1 课题研究的意义随着经济全球化的不断深入，许多跨国公司都已经或计划将制造、采购中心转移到中国，越来越多的国内企业也开始面向全球进行生产和经营，中国作为世界制造中心的地位日益凸显，这种大的国际环境更加刺激了我国物流业的高速发展。
与此同时，国家经济建设的深入和商业活动的繁荣刺激了市场对物流服务需求的激增:一方面表现在社会物资流通总量高速增长，呼唤更优化的快递物流解决方案和专业的物流咨询服务;另一方面则是越来越国际化的商业运作要求物流服务水平跟上国际化标准，在速度、可靠性、安全性、个性化、战略远见等方面提出了更高要求。
因此，通过降低物流成本，使得物流业的开展更加科学合理并进而通过开展服务创新，提升服务质量己经成了广大物流服务供应商的共识。
本文着重从配送环节中的车辆行驶路径选择入手，分析如何优化调整小车送货线路问题，进而达到降低物流成本的目的。
那么如何将车辆有效的使用并决定其最经济的行驶路线图，在最短的时间内把商品送到顾客的手中，提高顾客的满意度，将是配送中心作业的重点。
显然配送服务的要求将越来越高，为了实现配送成本的降低，必须对配送过程进行合理规划。
这就涉及到时间、财务、环境及服务质量四方面的因素，首先从时间上要考虑准时性、快速响应;财务上要考虑运输涉及的各种开支(员工薪酬、消耗等);环境上要尽可能减少不必要的行驶，避免交通拥挤、空气以及噪音污染;最后从服务质量上，要求满足顾客要求，达到顾客满意度最大化。
这些都可以通过改进运输方式、线路规划等来改善。
目前，物流配送活动中的配送运输路径确定问题，成为近二十多年来车辆路径问题的重点研究对象和应用领域。
在配送运输中，由于配送用户多，城市交通路线又复杂，如何组成最佳路线，如何使配装和配送路线有效搭配等，是配送运输的特点，也是难度较大的工作。
于是采用科学的、合理的方法来确定配送线路，成为提高物流配送车辆效益、实现物流配送科学化的重要途径，也是配送活动中非常重要的一项工作。
路径优化是对车辆行驶路线的优化过程，也是对车辆进行调度的一个问题。
由于运输任务的性质和特点不同、道路条件及车辆类型等各种约束标准不同，即使在相同收发货运点间完成同样任务时，所采用的行驶路线方案也可能不同。
而车辆按不同运行路线完成同样的运输工作时，其利用效果是不一样的。
因此，在满足货运任务要求的前提下，对各种不同的路径问题如何选择最经济的运行路线，是车辆路线安排的一项重要工作。
可见VRP问题实质上就是路径优化问题，因此，规划好车辆路径的优化选择，尤为重要。
所谓路径优化(即最经济的运行路线)，就是在保证货物需求的前提下，达到运输时间和运输费用最省的路线。
1.2国内外供货小车路径优化问题的研究现状对于路径优化这类问题，国内外有不少学者进行了探讨和深入研究，并且提出了许多求解此类问题的有效算法，工具。
东北大学信息科学与工程学院系统工程研究所的蒋忠中，汪定伟通过将B2C电子商务企业的实际物流配送网络描述为由配送中心和顾客两类节点构成的不完全无向图，建立了0-1整数规划的物流配送路径优化模型．首先利用Floyd算法求得不完全无向图中各节点间的最短路径和最短路径长度，然后设计了捕食搜索算法对模型进行解．通过仿真实例计算，取得了满意的结果[1]。
华中科技大学计算机科学与技术学的黄红将其配送路径抽象为TSP问题，完成现实空间到问题空间的映射，使实际问题转化为平衡运输问题的数学模型，采用单纯形法和贪婪法配合使用，从而求出最优解或满意解[2]。
重庆大学经济与工商管理学院的李志威，张旭梅针对蚂蚁算法在求解大规模物流配送问题中存在的不足，利用动态扫描方法在区域选择方面的实用性和蚂蚁算法在局部优化方面的优点，提出综合两种方法的混合算法，并获得了较满意的效果[3]。
哈尔滨运通汽车销售服务有限公司的尹训波通过对改进的蚁群算法（可见度的改进，信息素浓度更新规则的改进）对物流配送路径的优化，得到了令人满意的结果[4]。
长沙理工大学计算机与通信工程学院的柳林，朱建荣用遗传算法求解物流配送路径优化问题，有效地求解得问题的最优解或近似最优解，但遗传算法存在易陷入局部极小值和收敛速度慢等缺点，在总体上解的质量不是很高[5]。
针对这些问题，北京交通大学交通运输学院的郎茂详、胡思继提出将爬山算法与遗传算法想结合，能有效克服遗传算法在局部搜索能力方面不足[6]；湖南科技大学的陈湘州，黎志明，刘祖润通过引进一种进化逆转算子，其局部寻优能力很强，收敛性明显好于标准遗传算法[7]；山东建筑工程学院管理工程学院，东南大学经管学院的亓霞，陈森发对带有约束度为时间窗的小车供货配送路径采用了一种改进小生境遗传算法来优化[8]，马炫，陈琼还用遗传算法对度约束单源多目的路径优化[9]。
南开大学商学院,天津职业大学的张建勇 ,李军设计了具有同时配送和回收需求的车辆路径问题(VRPSDP),将正向物流和逆向物流同时加以考虑，与现实经济生活联系极为紧密[10]。
沈阳建筑大学的韩中华，吴成东，杨丽英，邓湘宁针对基本遗传算法在计算大型网络的优化问题时表现出的求解效率低等缺点，在基本遗传算法中引入了子群体和迁移策略，提出了基于并行遗传算法的最优路径选择方法，使得在大规模路网中求解效率和求解质量的平衡问题得以解决[11]。
长安大学的弓晋丽,程志敏基于Matlab进行了物流配送路径优化问题遗传算法的编码,利用Matlab强大的数值计算能力较好地解决了车辆行驶路径优化问题并进行了实例验证,对物流企业实现科学快捷的配送调度和路径的优化有实际意义[12]。