【智能车辆路径规划分析现状文献综述3800字】

中国农业大学硕士学位论文STYLEREF"标题1"错误！文档中没有指定样式的文字。智能车辆路径规划研究现状文献综述1研究现状路径规划的目的是降低交通参与者出行的时间成本和经济成本，在最短的时间内到达目的地。这一领域内已经积攒了相当的研究成果，应用的范围也早已不局限于手机导航、车载导航，在移动机器人、无人机的使用中，路径规划也有着举足轻重的地位，因此如何短时间内选出最优路径具备重要的研究价值。路径规划的常见解决方法有：Dijkstra算法、启发式搜索算法A*、模拟退火算法、遗传算法以及蚁群算法等。【2】1993年，杨建刚【3】博士用人工神经网络方法来建立自主运动系统AMS的动态路径规划集成系统。2000年，谢秉磊[9]等人将目标约束确定为货运量的约束与时间窗的约束，设计了一类可以将带软、硬时间窗的货运问题一起同步处理的遗传算法，提高了算法的效率和实际应用性。2001年，李嘉[10]等人将禁忌搜索算法与遗传算法相结合，两种算法各司其职，对混合车队规划车辆路径的问题进行了求解。2003年，崔雪丽[11]等人通过对蚁群优化算法加以改进，结合实际背景，在经典VRP的基础上对有缺货情况下的车辆路径问题进行了求解，并获得较好的结果。2004年，阎庆和鲍远律[12]将模拟退火算法与遗传算法相结合，并加入了记忆装置，设计了一种拥有记忆功能的遗传模拟退火算法。实验结果表明，该方法在一定程度上可以解决物流配送的问题，获得高质量的解。2008年，殷志锋[13]等人提出一种基于进化规划与MMAS算法相融合的混合算法，并通过对车辆路径问题的求解体现出算法的优良性能。2009年，叶伟[14]将模拟退火算法所具有的局部寻优能力以及量子粒子群算法所具有的全局寻优能力相结合，提出了一种新型混合算法并应用于求解车辆路径问题，实验结果体现了改进后算法收敛速度快、解的质量高的优点。2011年，刘晓勇[15]等人针对蚁群算法在求解车辆路径问题时所体现出来的求解速度慢，解的质量差的缺点，提出了一类基于启发式信息的蚁群算法并应用于求解有限制的车辆路径问题。实验结果表明，在收敛速度以及解的质量方面，该算法要优于基本蚁群算法。2021年，李文振，李富康等人通过改进转移概率来优化蚂蚁转移规则，从而让蚂蚁对最佳栅格信息进行精准定位，还采用新启发式信息来扩展视野和加快搜索，仿真结果表明，该改进方法在路径搜索效率和收敛速度方面有着优秀的表现。2路径问题的研究方法车辆路径规划问题是一类经典的NP问题，VRP同时也属于组合优化问题，并且拥有广泛的应用背景。从提出问题到现在，就受到了各个领域专业人士的广泛关注，如运筹学、物流科学、计算机科学。因此许多针对性的算法也被提出，算法分类如图1-1所示，图1-1算法分类Fig1-1Algorithmclassificationdiagram主要的求解算法有下列几种：1.精确算法能够求出最优解的方法就是精确算法。在面对路径规划问题时，主要有分支定界法、割平面法、动态规划法、网络流算法等，其中分支定界法和动态规划法在运筹学中都有所涉及，解决一些相对较简单的问题。显而易见，当用精确算法解决规模扩大后的问题时，求解用时将大幅增长，局限性明显。分支定界法在求解整数规划和混合整数规划问题喜欢常用分支定界法，它通过选择不同的分支变量和子问题来搜索迭代。它的基本思想在于每次分支后，先判断解时候可行，若为不可行解则不再进行分支，到此为止，缩小搜索范围。在保证可行解的情况下，继续分支，反复进行这一过程直到无法继续分支并得到最优解。动态规划法二十世纪五十年代初，美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，创立了动态规划法。利用了递归思想，把多阶段问题转换为多个单一阶段问题，从而求解。2.启发式算法启发式算法（heuristicalgorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计【】。启发式算法的分类一般为两种：传统式启发式算法和现代智能启发算法。传统启发式算法相较于现代智能启发算法来说比较简单，易于实现。解决规模较大的路径规划问题时，通常可以求得局部最优解或是满意解。而现代启发式算法可以全面搜索解空间，超越了局部最优解。下面对常见的启发式算法进行简单介绍。(1)传统启发式算法①构造法构造法的基本思想是:按照一定的准则，将不在线路上的点逐个增加进线路中，直到所有的点都被加入到路线中为止。目前的构造法主要有Gendreau提出的GENI插入法、Solomon插入法、Gavish等人提出的并行节约法等。该类方法最早用于求解旅行商问题，后来被运用于求解车辆路径问题。其使用起来简单方便，但是获得的解的质量有时候可能会比较差。②两阶段法大M法与两阶段法是在LP原问题缺少初始可行基的情况下添加人工变量，获得单位矩阵和初始可行基，从而继续求解。用大M法在手工计算时不会碰到麻烦，但是用计算机求解时，M的取值被计算机的最高位数限制。并且M通常要和线性规划问题中的参数差距大，若两者数值相近则有可能计算结果并非时原问题的真正最优解。为了避免以上的麻烦，就将需要进入人工变量的问题采用两个阶段进行解决，避免使用M。两阶段法的基本思想是:在第一阶段求解目标函数的只包含人工变量的辅助问题，获得一个可行解;第二阶段在保持解可行的基础上，在原问题上去除人工变量，继续寻找最优解，直到无法改进。目前的两阶段法主要有Miller和Gillett提出的Sweep算法、Fisher和Jaikumar提出的算法以及Renaud提出的Petal算法等。（2）现代启发式算法①遗传算法(GA)遗传算法是由JOHNHolland于1975年提出的一类优化算法。该算法主要以孟德尔的遗传变异理论以及达尔文生物进化论中“适者生存、优胜劣汰”的思想为基础，通过对最初的解(“先代”)不断进行交叉、变异、选择等操作以产生新的解(“后代”)。这类算法具有快速的全局搜索能力，通常得到的解的质量也比较好。遗传算法的运算过程如下:步骤1:参数初始化。需要设置的参数有：种群数量M、最大迭代次数、交叉概率、变异概率。令时间t=0，并随机生成M个初始群体。步骤2:个体评价。计算每个个体的适应度值。步骤3:选择。根据适应度值的大小进行选择能够进入下一代的个体。步骤4:交叉。按交叉概率对个体进行交叉操作。步骤5:变异。按变异概率对交叉过后的个体进行变异，从而得到下一代群体。步骤6:若没有达到算法的停止条件，则转步骤2继续进行以上步骤，若达到停止条件，则转步骤7。步骤7:输出具有最大适应度的个体。得解。遗传算法的运算对象一般为决策变量的编码，可以直接对结构对象进行操作，一般用于模拟生物的遗传和进化，当然在生产调度、自动控制、数据挖掘等领域也有广泛应用。遗传算法和本文研究的蚁群算法一样具有群体搜索的特性，大量个体同时搜索可以在开始时试错，避免后期的浪费。遗传算法具有很强的可扩展性和融合性，常与其他技术混合使用。但它同时也有明显缺点：效率通常低于其他的优化方法，不如蚁群算法有先天优势，因此在选择单纯算法改进时，并没有选择遗传算法。图1-2GA流程图Fig1-2theflowchartoftheGA②粒子群算法(PSO)粒子群算法是由Kenney和Eberhart于1995年共同提出的，与遗传算法类似，粒子群算法也是一类需要通过不断迭代才能进行优化的算法。算法的思想来源于鸟类的捕食行为，目前己广泛用于数据挖掘、模糊神经网络、函数优化等各个领域。粒子群算法的运算过程如下：步骤1:初始化所有粒子，设置粒子数量M，随机生成M个初始解及M个初始速度。步骤2:根据粒子当前所在位置和速度产生新的位置。步骤3:判断所有粒子的适应值。更新个体极值pbest，找出全局极值gbest。步骤4:更新粒子的速度及位置。步骤5:判断是否达到了之前设定的最大迭代次数，若是则转步骤6，否则转步骤2。步骤6:输出全局极值。粒子群算法和遗传算法都是通过初始化种群，使用适应值来评价体系，不同点在于，遗传算法的染色体之间是共享信息的，而PSO中是由全局最值单向向其他粒子发出信号，比遗传算法更快收敛于最优值。但粒子群算法在网络权重的编码和遗传算子的选择有些麻烦，因此也没有选择粒子群算法。③蚁群算法（ACA）蚁群算法是从蚂蚁觅食的过程中获得灵感，属于仿生学算法，最早应用于求解TSP问题并取得成功。在其他方面的应用也获得不错的效果，例如日常生产调度问题、指派问题等。蚁群算法广泛应用于车辆路径规划问题，而本文也正是需要改进蚁群算法在智能车路径规划问题上应用，因此在下文继续讨论蚁群算法的发展现状。图1-3ACA流程图Fig1-3theflowchartoftheACA参考文献[1]杨建刚.自主运动系统——人工神经网络方法在ANN-AMS信息感知与规划集成系统中的运用[D].浙江大学.1993.[9]谢秉磊.李军.郭敦煌.有时间窗的非满载车辆调度问题的遗传算法[J].系统工程学报,2000,15(3):290-294.[10]李嘉,宋建海一类特殊车辆路径问题(VRP)[J].东北大学学报:自然科学版,2001,22(3):245-248.[11]崔雪丽,马良.有缺货限制的VRP蚂蚁算法研究[J].上海理工大学学报,2003,25(1):39-44.[12]阎庆.鲍远律.新型遗传模拟退火算法求解物流配送路径问题[J].计算机应用,2004(S1):261-263.[13]殷志锋,张岩松等.带时间窗车辆路径问题的混合蚁群算法[J].许昌学报,2008(02):88-90.[14]叶伟.带时间窗车辆路径问题的混合量子粒子群算法[J].物流科技,2009(6):35-37.[15]刘晓勇,付辉.基于启发式蚁群算法的VRP问题研究[J].计算机工程与应用,2011,47(32):246-248.[16]李文振.李富康等.基于改进蚁群算法的移动机器人路径规划[J].组合机床与自动化加工技术.2021(04):49-52.[17]王晓燕等.基于改进势场蚁群