路径优化的算法.doc

摘 要 供货小车的路径优化是企业降低成本,提高经济效益的有效手段,供货小车路径优化问题可以看成是一类车辆路径优化问题。 本文对供货小车路径优化问题进行研究，提出了一种解决带单行道约束的车辆路径优化问题的方法。首先，建立了供货小车路径优化问题的数学模型，介绍了图论中最短路径的算法—Floyd算法，并考虑单行道的约束，利用该算法求得任意两点间最短距离以及到达路径，从而将问题转化为TSP问题，利用遗传算法得到带单行道约束下的优化送货路线，并且以柳州市某区域道路为实验，然后仿真，结果表明该方法能得到较好的优化效果。最后对基本遗传算法采用优先策略进行改进，再对同一个供货小车路径网进行实验仿真，分析仿真结果，表明改进遗传算法比基本遗传算法能比较快地得到令人满意的优化效果。 关键字:路径优化 遗传算法 Floyd算法 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 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 algorithm 目 录 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 4.2.1遗传算法的特点 11 4.2.2