路径规划典型算法范文1
关键词：多目标路径规划 贪心算法 压缩映像 早熟收敛
中图分类号：TP301 文献标识码：A 文章编号：1672-3791（2014）01（c）-0238-03
随着需求的增长，市民出行时除路程外还将其他要素纳入考虑，比如驾驶过程中的舒适度体验，行程的安全性，路段的拥挤程度等等。所以把市民出行时的路径规划问题抽象成多目标优化模型更加符合实际[1]。在实际应用中，用户需要在可忍受的时间内获得一组高质量的解。因为用户最满意的不一定是算法定义的最优解，而是最符合现实情境要求的解，所以合理的做法是提供多个选择，让用户根据实际情况进行决策。上述背景对算法提出了两个基本要求，即高效性和解的多样性。在一个城市内进行最优路径搜索时，所涉及到的节点数高达几千多个，而路径规划问题是典型的NP难问题，一些精确算法，如动态规划，分枝定界，其计算量呈指数增长[2]。而经典Dijkstra算法在节点数比较多时，消耗的时间和存储空间都十分巨大，所以应用也十分有限。近几年来，遗传算法在解决复杂的多目标优化问题中有成功应用，将其应用于大规模的多目标路径规划问题开始成为学者们研究的热点。相较于前面提到的几种算法，遗产算法在处理大规模路径规划问题时更具优势，更加容易实现解的多样性[3]。本文在遗传算法的传统框架上进行优化，用贪心算法设计初始种群，将压缩映像引入适应度标定中并且改进了更新策略，从而将算法更好地植入模型中，提高了计算效率。
1 模型建立
本文设定三个目标，，，分别代表最小路径长度，最小事故发生率和最小路径拥挤度，建立多目标路径规划问题的数学模型：
（1）
（2）
（3）
（4）
其中，为全体有效路径；为路径的路段总数。为路径中第个路段的长度；为路段的事故发生率；为路段的拥挤程度，且。求解该模型的目的在于找到一个非劣解集，协调各个目标之间的矛盾，达到目标间的平衡[3]。
2 算法设计
在60年代中期，Holland提出遗传算法，模仿达尔文的生物进化论，将适者生存的概念引入算法设计中，其主要组成部分包括初始种群的产生，个体适应度标定，选择算子，交叉算子和变异算子[4]。本文对传统遗传算法进行了三处改动：（1）用贪心算法设计初始种群；（2）将压缩映像法引入适应度标定中；（3）改进更新策略。
2.1 初始种群的生成
初始种群最常用的是逐次递进法，节点从起始点开始深入，逐层递进，不满足条件时，逐步退回上一个节点，再次逐层深入直至到达终点。还有随机节点生成法，由计算机随机生成一列节点，检验是否构成有效路径。与上述两种方法的盲目式搜索相反，利用贪心算法能够在起点和终点唯一确定一条路径。
算法步骤是这样的：决定起点的下一个节点时，考察其邻节点到终点的距离，两点间的距离由坐标计算可得，选择离终点最近的节点，依此类推直至到达终点。所以建立每个节点的二维坐标信息是算法实现的重要前提，节点的坐标能简化算法设计，提高搜索效率，并且通过现有的科技手段很容易获得，既不占用过大的存储空间，也不增加数据结构的设计的难度。所以路径搜索时引入节点的坐标有很大的价值。
为生成大量初始路径，将贪心算法与随机节点生成法结合，由计算机随机生成个节点，，1，2，…，。是给定常量，表示起点，表示终点。在和间运用贪心算法生成连通道路，最后整合成从起点到终点的通路。需要注意的是，该路径可能存在回路，必须使用紧缩算子消除回路[5]。
2.2 压缩映像在适应度评价中的应用
权重法是将多目标优化转化成单目标最简单和直接的手段，其算法实现相当容易，只需为每个目标赋予权重系数，但存在这样一个缺点：不同性质的目标之间单位不一致，单位小的目标函数值对结果影响微弱，比如本文提到的事故发生率。为改善这一不足，作者引入模糊数学领域中的压缩映像法[6]，将三个目标的度量纳入一个体系中。
以第一个目标为例，假设有一列染色体，，，则第一个目标函数值的压缩值为：
（5）
同理可计算和。经过压缩后，，，都落在中，完成了单位的统一。设给三个目标赋予的权重分别为，，，适应度的计算公式为：
（6）
2.3 更新策略
设为第代父代种群，为经交叉生成的子代种群，种群规模均为。传统的遗传算法通过选择算子从选出一组染色体进入池，交叉生成子代，经变异后直接作为新种群继续进化[7]。这种做法会流失父代中的优秀基因，从而降低收敛效率。结合精英保留策略和NSGA-Ⅱ算法中的更新策略[8～9]，本文采用如下方法：合并父代和子代组成规模为的，剔除中重复的染色体，根据适应度从大到小排列，选取前条染色体进入新种群，若不足，剩余个体从中随机产生。在更新过程中，子代个体并不比父代更具被选入的先天优势，两者根据适应度大小公平竞争，获得继续进化的机会。相较经典的“精英保留”策略，它扩大了父代染色体参与竞争的数量，使更多优良个体被保留，相较NSGA-Ⅱ，它的计算量要小得多。其中删除重复个体的操作维持了种群在进化过程中的多样性，避免算法陷入早熟收敛。
2.4 几个关键算子
选择算子使用普通的赌方式，在文献[10]中有详细介绍。交叉算子采用常用的一点交叉，但如果随机选出的染色体，没有共同节点时，则搜索二者中距离最近的节点，（距离由坐标计算可得），使用前文提到的贪心算法构造连通路径，接着仿照一点交叉法完成染色体交叉，得到两条新的染色体。
设计变异算子时，首先由计算机随机生成两个节点，通过贪心算法构造这两个节点间的连通路径替代原染色体中的路段。
无论是交叉算子还是变异算子，生成的新染色体都有可能产生回路，和初始种群的产生一样，也需要消除路径中的回路。强调一点，在本文的交叉算子和变异算子中，节点的坐标信息发挥了很大的作用，笔者认为在解决多目标路径规划问题时，有必要将节点的坐标进行充分利用。
2.5 算法流程
step1：产生初始种群。
step2：计算个体适应度并判断是否满足终止条件；若满足，输出一组最优解，否则转入step3。
step3：用选择算子从中选出条染色体进入池。
step4：对池中的染色体通过交叉算子进行随机，产生种群。
step5：合并，组成，用本文设计的更新策略获得条染色体。
step6：对更新后的种群应用变异算子，结果作为新种群，返回第二步。
3 试验结果及分析
3.1 前5条最优解
利用几何画板5.0绘制出33个节点75条边的无向图，节点坐标和路段长度由几何画板获得，事故发生率和拥挤度由计算机随机产生，构造出验证遗传算法效果的算例，如图1所示。
算法在MATLAB7.0环境下编译。种群规模取40，迭代次数取200，交叉率取0.8，变异率取0.08，路程，事故发生率，拥挤程度的权重系数分别为0.4，0.3，0.3，求得从节点1到节点33的在多目标规划下的前5条最优解，结果见表1。从表1中可以看出目标之间的相互制约关系。由于本文选取的算例规模比较小，所以可以用Dijkstra算法获得算例在仅考虑一个目标下的精确的最优值，见表1中最后一行。从表中可以发现没有一条路径能同时取得单目标下最小值，这证明求解多目标优化模型的关键在于协调和平衡几个目标。值得一提的是，为考察本文使用的更新策略的作用，将传统方法即把交叉变异后的种群直接作为进化的新种群的方式和改进后的方法对比，经试验发现，用传统方法得到的最后一代几乎全是路径1，而后者却得到了超过30条互不相同的路径。实验结果表明，该遗传算法在解决解的多样性问题上效果很好，扩大了用户决策的空间。（如表1）
3.2 解的收敛性
图2是迭代200次中种群的路程平均值变化曲线。从图中可以看出，最初种群的路程平均值比较大，经过50代后开始逐渐趋向平稳，在100代时因变异算子产生小的波动，最后稳定在18.7左右。曲线表明算法是快速收敛的。
3.3 解的有效性
我们知道在多目标路径规划问题中，绝大多数情况下无法找到一条路径同时取得三个目标的最优值。现在假定这条路径存在，那么非劣性解越接近它，表明解的质量越好[11]。基于这种思想，定义任意一条有效路径到虚拟的最优路径的距离，记这条虚拟路径的三个目标函数值为，，，任意有效路径函数值为，，。计算两者距离的公式如下：
（7）
公式（7）给出了比较两条路径优劣的指标。那么用产生初始种群的算法随机生成一条有效路径，挑战表中的5条最优解，如果最优路径到虚拟路径的距离小于随机路径到虚拟路径的距离，则称这个最优解是成功的，否则失败。试验200次，5条最优路径的成功率分别为100%，98%，99.5%，99%，91%。为避免算法的偶然性，对算例求解10次，其最优解的成功率均在90%以上，说明这5条最优解的性质都不错，证明遗传算法是有效的。
4 结语
本文采用遗传算法解决大规模的多目标路径规划，并对传统的遗传算法进行改进，使之具备更好的计算性能。在具体试验中，该算法体现了良好的收敛性和解的多样性，同时保证了最优解的有效性。为缓解种群陷入早熟收敛的压力，本文改进了传统的更新策略，但尚不明确它是否会带来意想不到的副作用。遗传算法的研究仍将集中在两方面：一是改进交叉和变异算子，防止种群早熟或陷入局部最优解[12]；二是提高算法的搜索能力，减少求解时间。
参考文献
[1] 潘斌斌.多目标路径规划问题的算法综述[J].重庆工商大学学报：自然科学版，2012，29（5）：78-84.
[2] 郎茂祥.基于遗传算法的物流配送路径优化问题研究[J].中国公路学报，2002，15（7）：77-79.
[3] 梁晓辉，吴威，赵沁平.大规模真实地形数据中的全局路径规划方法―― 基于遗传算法的研究[J].计算机研究与发展，2002，39（3）：301-306.
[4] 阮宏博.基于遗传算法的工程多目标优化研究[D].山东：大连理工大学土木工程系，2007.
[5] 刘旭红，张国英，刘玉树，等.基于多目标遗传算法的路径规划[J].北京理工大学学报，2005，25（7）：613-616.
[6] 宋晓秋.模糊数学原理与方法[M].徐州：中国矿业大学出版社，2004.
[7] 肖晓伟，肖迪，林锦国.多目标优化问题的研究概述[J].计算机应用研究，2011，28（3）：805-808，827.
[8] 刘旭红，刘玉树，张国英，等.多目标优化算法NSGA-II的改进[J].计算机工程与应用，2005（15）：76-78.
[9] 关志华.非支配排序遗传算法（NSGA）算子分析[J].管理工程学报，2004（1）：56-60.
[10] 井祥鹤，魏冬峰，周献中.运输方式选择多目标优化问题的混合遗传算法[J].计算机工程与应用，2008，44（6）：210-212，224.
路径规划典型算法范文2
关键词：车辆路径问题；启发式算法；多配送中心；带时间窗；集送货一体化
中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2016）26-0079-02
Development and Application of Vehicle Routing Problem
BIAN Chen， ZHAO Jian-dong
（School of Computer Science and Engineering， Anhui University of Science & Technology， Huainan 232001， China）
Abstract： As a hotspot in the field of operational research and combinatorial optimization， vehicle routing problem is closely related to real life.As long as the deepening study of vehicle routing problem， various kinds of new types of heuristic algorithm is applied to solve such problems.The vehicle routing problem with various constraint were investigated， analysis and summary in this paper， and the related domestic and foreign research results were reviewed and refined， on this basis， this paper summarizes the research of vehicle routing problem. Based on the current various standard of classification， this paper discusses and analyzes the classical vehicle routing problem firstly， and summarized the basic methods and modern heuristic algorithm on this basis.
Key words： vehicle routing problem； heuristic algorithm； hybrid；multi-depots； time window； pickup and delivery
1 背景
车辆路径问题（Vehicle Routing Problem，VRP ）是由 Dantzig等人在1959 年提出的一个经典的NP-hard问题[1]。是指对于一系列的装货点及卸货点，规划合理的配送路径，在满足了约束条件之下，载货车辆按照规划的路线依次访问，能够满足一定的需求或达到某些目标。其研究成果已广泛地应用于各个学科之中。VRP已经不止是单纯的理论研究，现实世界中，国内外学者的研究经历了其从最早期无车辆约束的TSP问题发展为对车辆运载能力、车辆行驶里程、客户服务数量进行限制的经典VRP，而后依据客户需求的改变和客户对配送要求的提高，从服务无时限向有时限（也称为时间窗问题）以及从纯送货问题或者纯取货问题向混合取送问题（也称为集货送货一体化）的变化的VRP问题。为了不断满足现实要求，当前针对VRP的大部分研究，集中在对其动态性的讨论上，即从配送过程中信息的确定性向动态接受客户需求（也称为不确定性）的变化。
随着现代物流行业的崛起，企业为了降低运输成本，越来越重视对VRP问题的探究，新型的VRP不断地涌现，使得其更有研究价值和现实意义。
2车辆路径问题研究现状及评述
本文根据现有对VRP问题研究的成果，从综合的角度分析车辆路径路径问题，目前国内外针对车辆路径问题的研究主要集中在其扩展问题上。
2.1 多配送中心的车辆路径问题
根据配送中心数目的多少，配送车辆调度问题可以分为单配送中心车辆调度问题和多中心车辆调度问题，在整个物流管理的体系中，配送地一般都存在多个中心，因此对多配送中心车辆调度问题的研究更加具有现实意义。目前国内对于多配送中心车辆调度问题的研究还是处于一个有限的阶段。
在多配中心车辆路径问题中，车辆路径的安排需要满足以下四点条件：
1）每一辆车都从一个配送中心驶出，并在服务了一定数量的客户后返回初始的配送中心；
2）每一个客户每次只能被一辆车服务；
3）车辆不能够在两个配送中心之间进行运输，并且行驶路径不能够出现回路；
4）车辆的运载量不能够超出容量限制，并且每一个配送中心提供的客户服务数量是有限的。
对配送中心的车辆路径问题一般可以如下的描述：在整个物流配送系统中，存在着多个服务中心为多个客户进行服务，需要制定一条配送行车路径使得所有客户的需求被满足的前提之下，配送成本降至最低。多配送中心的VRP是一个NP难度组合优化问题，因此一般求解是很难得到最优解的。当前，国内外学者普遍采用多阶段的办法来解决此类问题，一般先将多配送中心问题转化为单配送中心问题，再利用启发式算法进行求解。崔文[2]通过多阶段的启发式算法，将此类问题通过聚合―求解―优化的步骤逐步求解出最优路径，提出了通过启发式算法在短时间生成最初的有效路径来代替Lin-Kemighan算法中采用的随机路径作为初始路径。
2.2 开放式车辆路径问题
开放式车辆路径问题（OVRP）是现代运输运筹学中的一个新型研究课题，与经典VRP问题相比较，他的一个显著特点是车辆在完成运输服务后可以将其他的配送中心点选为终点。OVRP一般可以简化为忽视了回程约束的带容量约束车辆路径问题（CVRP），其求解目标是构建一个哈密顿通路以满足所有顾客的需求。在现实中，物流公司可能通过雇佣车辆来完成配送任务，那么车辆是否回到出发点并不受到关注，这段路程的费用也将不计。
OVRP是配送运输管理中广泛存在的问题，在现实生活中有很多应用，特别是在具有外包业务特点的配送服务中具有较大的应用价值，例如校园班车问题、牛奶配送、报纸配送等，在这类问题中，由于企业没有自己的车辆，所以将其配送业务外包给其他的车辆或车队，而且企业并不要求车辆在服务完客户后回到车场点。OVRP问题的首要优化目标一般都是最少车辆数，在此基础上优化行驶距离。在过去的十几年里，尽管学者们通过禁忌搜索，确定性退火技术，大规模领域搜索方法，分枝切面法等多种方法为OVRP问题提供了基本的解决办法，但面对大规模的数据处理，OVRP问题仍然存在着一定的求解难度。Sariklis[6]等人通过两阶段启发式算法来进行求解，第一阶段是先生成客户群，然后在每一个客户群中安排路线，进行局部优化，第二阶段将OVRP问题转化为最小生成树问题并求解。Brandao[7]在求解时，通过最近邻居法和最小K度生成树来划分客户群，并最终用禁忌搜索法优化路径。
2.3 时间窗口约束的车辆路径问题
带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows，VRPTW）作为物流管理问题中一个重要的分支，他基于以下假设：1.需要必不可少的通信设备，使得顾客和服务中心之间，服务中心和货运车辆之间的信息能够快速便捷的传递；2.配送的计划中，存在预约服务的客户。服务车辆必须在客户规定的时间窗[[Ai，Bi]]对其进行服务，其中[Ai]是客户[i]的允许最早开始时间，[Bi]是其所允许的最迟开始时间。如果车辆到达客户的时间早于[Ai]，那么车辆只得等待直至到达服务的最早时间点，其系统优化目标是最小化客户的平均等待时间。
近年来，对于求解带时间窗车辆路径问题取得较好效果的是启发式算法。Gold等人最早综述了VRPTW的研究状况。上世纪80-90年代，对VRPTW的研究开展综述的是Solomon等人[10]。随后Braysy等人[11]综述了经典启发式、智能启发式算法并提出了展望。最近，Raúl Ba?os[12]等人提出了一种针对多目标VRPTW问题的混合现代启发式算法，得到优化解决方案。
2.4 带集货送货需求的车辆路径问题
车辆调度领域之内的问题一般可以按如下区分为两大类：一种是纯装货或者纯卸货问题，另一种是带装货卸货一体化的车辆调度问题（VRPSPD），而后者更是包括了先送货后取货的车辆路径问题，同时集货送货的车辆路径问题以及混合集货送货的车辆路径问题。
VRPSPD的提出最早可以追溯到1989年，由Min提出的在解决了车辆数量一定并且车辆运载能力有限的情况下，一个中心配送点和22个地方图书馆之间的书籍配送问题。VRPSPD问题可描述为：某一个仓库为其用户群体进行货运服务，任意用户可能同时需要送货和集货服务，并且某一客户的送取货的需求之和不能大于车辆总运载能力Q。
VRPSDP的难点在于服务车辆的装载量难以控制易发生溢出。当每一个客户的送货需求是已知的时候，依据车辆的剩余装载能力来定义插入准则，。
2.5 动态车辆路径问题
依据物流信息在配送之前是否完全可知，VRP按新的分类方式分为静态VRP和动态VRP。动态车辆路径问题的首次完全提出要归功于Wilson和Colvin[13]，当时他们研究的单一车辆问题描述了客户旅程的需求，从始发地到目的地的旅程是动态变化，并通过启发式算法来提升计算效率。车辆路径问题中动态信息最常见的来源就是客户需求的在线到达。具体来说，需求可以是针对货物的调整也可以是是服务需求的变化。
一般认为动态车辆路径问题和静态车辆路径问题的区别在于信息的确定性与未知性，而前者在配送服务过程中，会出现不同类型的动态信息。
动态车辆路径问题一般具有的特征如下：
1）安排配送路径和车辆执行计划的过程中新客户信息能够实时的传达。
2）任何新传达的信息都允许是不精确的。
3）新信息需要被快速的响应。
4）与静态VRP问题相比求解的目标函数更为繁杂。
任何动态车辆路径问题仍是基于静态车辆路径问题提出的，目前针对动态车辆路径问题的求解办法，仍然需要借鉴处理静态车辆路径问题的各类算法，其中大部分算法为元启发算法。
动态车辆路径问题首先要明确需要响应哪些动态信息，并以客户需求变化为依据，选择需要优化的目标函数，例如将配送车辆的总行程作为目标函数进行优化，然后再设置额外的约束条件，例如设定单车最大行程为约束条件。借助各类启发式算法如蚁群优化算法等进行优化，在整个配送过程中，不再是单一直接地插入顾客需求，通过最大熵法分布估计算法计算出具有发展潜力的客户群体和区域。在=当需求发生冲突时衡量各个客户需求的利益，通过惩罚措施来降低费用。
3 结束语
车辆路径问题因其不可预估的经济效益和其在现代物流中的所占据的重要地位已经引起了国内外学者的高度关注，并依据实际需求不断引入新的约束。在理论与应用上，各类精确算法、启发式算法被广泛地应用于解决车辆路径问题，并已经取得了长足的进步。然而，同样被关注的是，从现有的各类研究成果看来，虽然新型约束条件下的VRP模型更加完善也更符合现代物流实际需求，但实际求解算法却很难在精度和效率上做到两全，简化算法测率需要得到更多的重视，特别是，各类启发式算法在求解时的弊端也愈加明显，需要取长补短发挥其他算法的优势。
参考文献：
[1] Dantzing G，Ramser J. The truck dispatching problem[J]. Management Science， 1959， 10（6）： 80-91.
[2]崔西.大规模多配送中心车辆路径问题研究[D]. 济南： 山东大学， 2009.
[3]Sariklis D， Powell S.A heuristic method for the open vehicle routing problem[J].Journal of the Operational ResearchSociety，2000，51： 564-573.
[4] Branda～o J.A tabu search algorithm for the open vehicle routing problem[J].European Journal of Operational Research， 2004，157：552-564.
[5] Desrochers M， Lenstra J K， Savelsbergh M W，et al. Vehicle Routing With Time Windows： Optimization and Approximation[M]. Amsterdam， The Netherlands： Elsevier Science Publishers， 1988.
[6] Braysy， Gendreau. Vehicle Routing Problem With Time Windows，Part I：Route Construction and Local Search Algorithms[J]. Transportation Science， 2005（39）： 104-118.
路径规划典型算法范文3
【关键词】智能交通系统 蚁群算法 信息素 最优路径 组合优化
交通运输的现代化使人们享受便利的同时，也面临道路拥堵、事故频发等问}。近年来，智能交通系统越来越受到人们的重视，它涉及到交通领域诸多方面，如最优路径选择、车辆路径规划、动态车辆调度、交通流量控制等。其中一个重要的应用是一类典型的以数学理论为基础的组合优化问题，而蚁群算法具有内在的搜索机制及正反馈性，适合求解一系列的组合优化问题。
1 蚁群算法描述
蚁群算法源于20世纪90年代初意大利学者M.Dorigo首次提出的蚂蚁系统。它是基于种群的启发式放生进化系统，是通过对蚁群觅食过程中其行为的研究而得出的一种算法。主要思路是蚂蚁借助自己路径寻优的能力可以找到巢穴与食物之间最短的途径。在寻找过程中主要依靠的是每个蚂蚁在行进过程中留下的挥发性分泌物――信息素，依靠信息素，蚁群的蚂蚁之间可以相互合作，相互配合，因此形成的正反馈可以使每只蚂蚁找到所有路径中最短的路径。
蚂蚁a从节点j移动至k的转移概率可以从式（1）中获取：
（1）
（2）
（3）
2 蚁群算法的应用优势
蚁群算法，又名蚂蚁算法，蚂蚁可以利用信息素的浓度大小从而寻找到觅食的最优路径。该算法的优点可以总结为：
2.1 并行分布式计算
每个蚂蚁都是独立的个体，在觅食过程中属于多起点同时启动，互不影响，从根本上分析该过程属于分布式的多Agent系统，整体蚁群最终任务的顺利完成不会由于某些个体的缺陷而受到影响。该算法具有真实可用性，并且可用于解决对单目标的优化或者对多目标的优化等重要问题。此外，蚂蚁算法还可进行并行计算。
2.2 鲁棒性
蚁群算法的最终结果与蚂蚁最初选择的路径无太大关系，在利用人工仿真蚂蚁进行问题求解过程中，不需要对其进行人工的修整。把问题简单化，可以和其他算法相互结合求解最优问题。
2.3 自组织性
蚁群算法组织指令的来源为系统内部，它不受外界环境的干扰，因此该算法具有自组织性。
2.4 正反馈性
蚂蚁对于最优路径的选择主要依靠路径上信息素浓度的多少，信息素的堆积是正反馈的过程，路径上信息素的含量越多则该路径被选择的几率就会越大，正反馈的作用是使整体能够更快的寻找到最优途径，正反馈在蚁群算法中处于重要地位。
2.5 易于实现
它是一种启发示算法，其计算复杂性为，整个算法的空间复杂度是：。
3 蚁群算法在智能交通领域的应用空间
蚁群算法在解决组合优化问题方面有着明显的优势，从而在智能交通领域也有着广泛的应用空间。
3.1 车辆路径导航
根据行车人员的需要，根据对实时路况信息的统计，系统可以智能的为其推荐最优路径，节省时间，节省资源。
3.2 动态车辆调度
当客户需要调度中心为其进行车辆服务时，调度中心要考虑到客户的情况，要考虑到效率的问题，要考虑到行车路线、行驶时间等问题。蚁群算法便可迅速得到合理的解决方案，使客户和调度中心均可受益。
3.3 车辆路径规划
面对多个客户不同的要求时，配送中心要根据实际情况进行车辆的配送，通过蚁群算法系统获取整体的最优路线，根据路线规划，及时进行车辆出发以满足客户要求，同时充分利用了道路资源和车辆资源。
3.4 公共交通智能化调度
利用先进的技术手段、大型数据库技术等动态地获取实时交通信息，实现对车辆的实时监控和调度，最终建立集运营指挥调度、综合业务通信及信息服务等为一体的智能化管理系统。
3.5 交通流量控制
通过蚁群算法简化复杂的道路交通网络，尽量使交通流量在各个道路上分布均匀，避免因流量过大而造成车辆的阻塞。及时了解交通流量情况，缓解了交通拥挤，降低了交通事故的发生率。
参考文献
[1]M.Dorigo，V.Maniezzo，A.Colom.Ant System：Optimization by a colony of cooperating agents.IEEE trans on SMC，1996，26（01）：28-41
[2]Eric BONABEAUB， Marco DORIGO，Guy THERAULAZ.AWARM intelligence： from natural to artificial systems[M].New York：Oxford University Press，1999
[3]杨海.蚁群算法及其在智能交通中的应用[D].济南：山东师范大学，2008：14-18
作者简介
白晓（1979-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为软件工程、智能算法。
王娅（1983-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为网络工程，软件设计。
路径规划典型算法范文4
[关键词]VR技术；虚拟现实技术；加工仿真
[DOI]1013939/jcnkizgsc201650244
1虚拟现实技术简介
VR技术就是虚拟现实技术，它是在拟的环境下体验现实状况的事和物。虚拟现实技术的显著特征有沉浸性和交互性等。沉浸性是指人以第一人称存在在虚拟世界中的真实体验。当然，以目前技术还没有达到最理想的程度。交互性是指人在虚拟世界中，能够像在现实当中一样，可以通过对一些物体的抓取、使用等动作，感觉到所触碰的物体的重量、形状、色泽等一些人与物体之间的互动信息。
本文将虚拟技术应用于数控加工课程的教学中，使学生在课堂上就能体会到零件在车间生产一线设备加工的工况，熟悉加工流程，处理加工故障，保证合格产品的安全、文明生产。
文中运用CAXA软件的仿真功能进行典型铣削零件的加工，同时介绍宇龙仿真系统的数控车削零件加工仿真。
2典型铣削仿真加工
CAXA制造工程师是由北航海尔软件有限公司研制开发的面向数控铣床和加工中心的计算机辅助设计与辅助制造（CAD/CAM）软件。
CAXA软件具有CAM辅助加工功能：加工中心可以进行2-5轴的数控加工，生成刀具轨迹、仿真加工、生成加工程序、生成工艺单。数控加工方法可根据加工实际，灵活选用。加工方法有粗、半精、精、补加工等多种加工方式。
数控代码的正确性可以通过系统仿真手段检验，如果仿真加工发生干涉或刀具路径不是很合理，可以进行编辑修改，即进行刀具路径的优化。数控系统可根据用户的要求进行后置处理格式的选择和处理，直接输出用户需要的数控加工代码。
下面运用CAXA制造工程师对典型零件进行了三维建模和计算机辅助加工虚拟仿真，以体会VR技术在数控加工中的应用。首先依据图纸要求对零件进行实体造型，转接盘实体造型过程依次如下图：图1为零件底座实体图，图2为孔特征实体图形，图3为零件最终实体造型图。
图1底座实体图2孔特征实体图3转接盘实体造型
实体造型后根据零件加工实际需求，制定合理加工工艺进行零件的加工。其中主要包括毛坯的定义、刀具的选择、加工方法的选择、各种加工工艺参数的合理设置等。根据零件图纸要求，零件的加工方法可以选用区域粗加工、轮廓线精加工、啄式钻孔、区域式粗加工、等高线精加工等加工方法。图4为仿真加工零件图，图5为仿真加工刀具路径规划图，图形如果不合理，可以进行修改，然后依据最终合理的刀具路径生成数控加工代码。
3典型车削零件仿真加工
典型的车削零件介绍利用宇龙仿真软件来进行了虚拟仿真加工。依据图纸要求对零件进行工艺分析和数控加工程序的编制，然后打开数控加工仿真系统如图6所示。该数控仿真系统与实际加工的步骤完全相同，依次进行数控系统和机床设备选择见图7，刀具选择及工件装夹见图8，加工零件加工并监控加工过程如图9所示，加工零件成品图如图10所示。如果出现撞刀和加工中的问题，都可以进行修改。
4结论
在数控加工的课程教学中，充分运用CAXA软件的CAM功能或宇龙仿真软件的加工仿真，进行零件的数控虚拟加工，验证加工代码的正确性；同时进行了刀具路径的规划和优化，仿真加工对学生学习加工类课程具有很好的效果。
虚拟现实技术是一个极具潜力的研究项目，是未来的重要技术之一。它不论在理论，软件或者硬件的领域上都依赖着很多技术，不过可以预见，在未来虚拟现实技术绝对会被广泛应用。
参考文献：
[1]杨伟群数控工艺员培训教程（数控铣部分）[M].北京：清华大学出版社，2002
路径规划典型算法范文5
关键字 群智能算法； ACO； PSO； AFSA； SFLA；ABC；FA
中图分类号 Q5-3 文献标识码A 文章编号 1674-6708（2014）114-0160-02
1 群智能算法概述
群智能算法是近几十年发展起来的一类基于生物群体行为规律的全局概率搜索算法。这些算法将搜索空间中的每一个可行解视为生物个体，解的搜索和优化过程视为个体的进化或觅食过程。生物个体适应环境的能力用来度量待求解问题的目标函数，生物个体的进化或觅食过程用来模拟优化中较差的可行解被具有优势的可行解替代的迭代过程。下文将对几种典型的群智能算法进行简要的介绍。
2 典型群智能优化算法
2.1 蚁群算法
1991年意大利学者Dorigo M等受到自然界中蚁群觅食行为启发而提出了蚁群算法 （Ant Colony Optimization， ACO）。
蚁群算法的思想是：在最短路径的找寻过程中，每只蚂蚁只可以根据局部信息调整路径上的信息素，一轮循环结束后，采取全局信息对路径上的信息量再进行一次调整，且只对寻优过程中发现的最好路径上的信息素进行加强。在蚁群算法中，蚂蚁逐步地构造问题的可行解，在解的构造期间，每只蚂蚁使用概率方式向下一个节点跳转，这个节点是具有较强信息素和较高启发式因子的方向，直至无法进一步移动。此时，蚂蚁所走路径对应于待求解问题的一个可行解。
蚁群算法目前已成功地用于解决旅行商TSP问题、数据挖掘、二次指派问题、网络路由优化、机器人路径规划、图着色、物流配送车辆调度、PID控制参数优化及无线传感器网络等问题。
2.2 粒子群算法
1995年美国的Kennedy等受鸟群捕食行为的启发而提出了粒子群算法（Particle Swarm Optimization， PSO）。
粒子群算法的思想是：将群体中的任一个个体，即每个可行解，视为D维搜索空间的一个有飞行方向和速度的粒子。所有的粒子都有一个被目标函数决定的适应值，且记忆了自身曾经获得的最好位置及当前位置，视为自身的飞行经验。同时每个粒子还知道整个群体所有粒子已获得的最优位置，视为群体的飞行经验。在迭代过程中，所有的粒子将不断地统计个体的飞行经验和整个群体的飞行经验，以此动态调整本身飞行的方向和速度。在此过程中，个体逐步迁移到较优的区域，使群体最终搜索到问题的最优解。
粒子群算法的应用领域众多，如模式识别与图像处理、工程应用、神经网络训练、模糊系统控制、化工系统处理、滤波器设计、仿人智能控制参数优化、数据聚类等。
2.3 人工鱼算法
2002年由我国的李晓磊等受鱼群运动行为的启发而提出了人工鱼群算法 （Artificial Fish-Swarm Algorithm， AFSA）。
人工鱼群算法的思想是：将人工鱼随机地分布于解空间中，解空间中包含着若干局部最优值和一个全局最优值。可将最优值视为食物的浓度，而全局最优值为最大的食物浓度，且人工鱼将移动聚集到食物浓度较大的区域，通过移动策略来控制人工鱼个体的四种行为（觅食、聚群、追尾和随机），用视野来限制个体的邻域，用步长来控制个体探索的进度，用拥挤度来控制群体的过度密集。寻优期间，每次迭代执行完，人工鱼都将对比自身状态和公告板状态，如自身具有优势，则更新公告板状态，确保公告板为最优状态。
人工鱼群算法已在参数估计、组合优化、前向神经网络优化、电力系统无功优化、输电网规划、边坡稳定、非线性方程求解等方面得到应用，且取得了较好的效果。
2.4 混合蛙跳算法
2003年Eusuff等人受青蛙觅食特征的启发而提出了混合蛙跳算法[4] （Shuffled Frog Leaping Algorithm， SFLA）。
混合蛙跳算法的思想是：将青蛙个体随机地分布于解空间中，每只青蛙表示解空间的一个解。在进化更新的过程中既有全局性的信息交流，还有内部的信息交流。根据青蛙个体的适应度值的优劣进行排序和分组，组内只有适应度最差的青蛙更新，元进化并混合各组，在各组一轮元进化后，将组中的青蛙重新排序、分组并记录全局最优解，之后再继续局部搜索的过程。青蛙更新的学习对象首先是组内最优，其次是群体最优，若两次都未能进步，则随机初始化。
混合蛙跳算法已经应用于多个领域，如水资源网络优化、数据聚类、桥面修复、风电场电力系统动态优化、装配线排序、流水车间调度、PID控制器参数调节等。
2.5 人工蜂算法
2005年由土耳其的Karaboga等受蜜蜂采蜜行为的启发而提出了人工蜂群算法（Artificial Bee Colony， ABC）。
人工蜂群算法的思想是：将虚拟蜜蜂群初始时随机分布在解空间中，将食物源的位置抽象成解空间中的点（可行解）。通过三种蜜蜂对食物源位置（解）修正，进行一次循环搜索过程。引领蜂通过对比附近食物源的花蜜量（适应度），来对现有食物源位置（解）进行修正。如果新食物源的花蜜量（适应度）比现有的高，那么引领蜂记忆新食物源（解），放弃现有的。在引领蜂的搜索过程完成后，它们通过跳舞与跟随蜂传递食物源信息。跟随蜂通过汇总和评估所有食物源信息，计算出一个关于花蜜量的概率值，通过比较概率选取食物源。跟随蜂也是根据贪婪选择策略来更新当前食物源的位置。利用侦察蜂来使得陷入局部搜索停滞的蜜蜂跳出。
人工蜂群算法已经应用于多个领域，如车辆路径问题、人工神经网络训练、作业车间调度问题、数据聚类以及各类连续优化问题等。
2.6 萤火虫算法
2009年由剑桥大学的Xin-She Yang受萤火虫发光行为的启发而提出了萤火虫算法（Firefly Algorithm， FA）。
萤火虫算法的思想是：将萤火虫个体作为解随机地分布于解空间中。解的搜索和优化过程视为每只萤火虫的移动和吸引过程。个体所在位置的优劣用来度量所求问题目标函数。个体进化的过程用来模拟优化中较差的可行解被具有优势的可行解替代的迭代过程。萤火虫根据自身亮度和吸引度两个要素来更新自己的位置。萤火虫所在位置的目标值决定其能产生的荧光亮度，所处位置（目标值）越好其亮度越高。萤火虫的亮度与吸引力成正比，视线范围内，亮度稍弱的萤火虫将被吸引，朝着较亮萤火虫的方向移动，以完成的位置进化。当亮度相同时，萤火虫则随机地进行位置移动。萤火虫之间的距离与亮度和吸引度成反比，也即距离越大，亮度和吸引度越小。
目前萤火虫算法已应用在生产调度、路径规划、神经网络训练、天线阵列设计优化、图像处理、机械结构设计优化、负载经济均衡分配问题、复杂函数优化等方面。
3 结论
本文在简述群智能算法的基础上，对近年来发展的几种典型的群智能算法的生物原理、算法思想和应用进行了阐述和研究，为群智能算法的深入研究奠定了基础。
参考文献
[1]Colomi A，Dorigo M，Maniezzo V.The Ant System： An autocatalytic optimization process，Technical Report 91-016，Dept.of Electronics，Politecnicco di Milano，Italy，1991.
[2]Kennedy J，Eberhart RC.Particle swarm optimization[C].IEEE International Conference on Neural Networks，Perth，Piscataway，NJ，Australia： IEEE Service Center，1995，1942-1948.
[3]李晓磊，邵之江，钱积新.一种基于动物自治体的寻优模式：鱼群算法[J].系统工程理论与实践，2002，11，32-38.
[4]Eusuff，M.M.，Lansey.K.E.Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm [J].Water Resources Planning and Management，2003，129（3）： 210-225.
路径规划典型算法范文6
【关键词】智能机器人；路径规划；应用
路径规划在嵌入式智能机器人的研究过程中有重要的意义。随着我国科学技术的提高，机器人技术得到了广泛的发展和应用，我国智能机器人技术进步的最显著特征是嵌入式系统与机器人技术的结合，嵌入式系统具体集成度较高、功耗较低等方面的优势，不仅可以充分满足系统的实时性，在一定程度上还能够使控制软件的开发工作变得简化。
1嵌入式智能机器人路径技术的研究
智能机器人路径规划是指处于有障碍物的工作条件下，如何寻找一条适当的运动路径（从给定起点到终点），在运动过程中，使机器人能够安全的规避全部障碍物。
（1）嵌入式智能机器人路径规划的发展趋势
从近些年的研究成果来看，有以下趋势：第一，以功能或行为为基础的智能机器热的路径规划。以功能或行为为基础的机器人具有一种典型的慎思结构，又被称为基于功能的控制体系结构，其主要内容是基于模型自顶向下的感知、建模、规划和动作。智能机器人路径规划问题，建模时，能够设置成为有约束性的规划问题，确保机器人能够完成路径规划、路径规避和定位等方面的任务。由于不同的机器人掌握信息环境的程度存在差异，可将智能机器人的路径规划分为两种，其一是以传感器为基础的局部路径规划，具体是获知了作业环境中的所有信息，主要包括：自由空间法、构型空间法以及神经网络法等；其二是以模型为基础的全局路径规划，具体是指已经全部获知或部分获知作业环境中的信息，主要包括混合法、滚动窗口法、人工势场法等。第二，神经网络、模糊控制等一系列算法不断涌现并相互结合形成新的算法。第三，智能机器人的系统路径规划。智能机器人的工作环境逐渐复杂化，再加上工作任务的增加，单智能机器人无法负荷这样的工作要求。因此，将会出现单个智能机器人路径规划与多智能机器人的合作相结合的发展趋势。
（2）机器人智能规划中的特点
智能机器人路径规划中主要存在以下特点，①复杂性，是指环境复杂，机器人的路径规划复杂，且路径规划过程中需要很大的计算量支持。②随机性，是指工作环境的变化复杂，存在较多的不确定因素和随机性。③约束性，在机器人运动的过程中，其速度、形状等方面均存在约束。
2智能机器人路径规划的算法研究
（1）局部路径规划算法研究
1）模糊逻辑控制法
在环境模型不完善的情况下，可以使用模糊逻辑算法。这种算法的推理和计算简单，对传感器信息的要求较低，且对机器人的行为有较高的稳定性、一致性以及连续性，能够有效的解决在路径规划过程中遇到的一些问题。虽然这种算法能够圆满的解决未知环境下的规划问题，但仍存在灵活性较差、无法学习的不足之处。
2）遗传算法
遗传算法是解决最佳化的搜索方法，属于进化算法的一种。这种算法最初借鉴了进化生物学中突变、自然选择、交叉和变异等现象而发展起来的，它采用群体搜索技术，实施选择、交叉、变异等一系列遗传操作后，使种群在迭代中不断进化。这种算法的理论推导简单，问题的最优解能够直接得出。遗传算法的基本思想是路径转换为二进制串，首先将路径群体实施初始化操作，然后对路径群体实施选择、复制等一系列遗传操作。通过多次进化后，达到最佳的进化状态，停止进化并将当前存在的最优个体输出。虽然遗传算法得推导理论简单，但路径规划过程中仍存在效率低、个体编码不合理等问题。
（2）全局路径规划算法研究
1）构型空间法
构型空间法主要包括优化算法和可视图法。第一，优化算法。第二，可视图算法。路径图主要由机器人中的一维网络曲线自由空间中的节点构成。因此，在同路径图中，路径初始状态的点一一与目标状态的点相对应，从而促使点间搜索路径问题替代了路径规划问题。这就要求点与点之间的连线是无法穿越障碍物，即机器人与障碍物点、目标点与障碍物点、以及顶点与障碍物顶点之间的连线是可视的，然后，采取有效的搜索方法，搜索最优路径（起始点到目标点），从而使搜索最优路径问题演变为可视直线最短距离的问题。可视图法虽然能够得到最短路径。第二，优化算法。采用优化算法時，为了简化可视图和减少路径搜索时间，有部分可有可无的连线可以删除，最终实现求得最短路径的目的。
2）神经网络法
人工神经网络一种自适应非线性动态系统，主要是由大量神经元组成。在工作环境广泛、精度要求高的条件下，采用神经网络法表示环境，将会取得显著效果。在全局路径规划中应用神经网络法，能够将障碍约束变成惩罚函数，并用神经网络来描述碰撞惩罚函数进而将约束优化问题转变为无约束最优问题，实现全局路径规划。神经网络法具有较强的学习能力，但整体应用于路径规划中的效果不明显，这是因为智能机器人的工作环境复杂，并伴有一定的随机性，数学公式无法进行准确的描述。
3嵌入式智能机器人路径规划算法的应用与实现
嵌入式智能机器人的组成部分主要有驱动控制器和嵌入式微处理器。嵌入式智能机器人的硬件结构有较高的可扩展性、良好的独立性以及较小的功耗等特征，且能够得到嵌入式系统的充分支持。嵌入式智能机器人的主板是机器人的大脑，主要担任机器人运动过程中的实时计算工作。随着嵌入式技术的不断发展，为智能机器人的路径规划算法的实现和运用提供了无限的可能性，再加上以SOC技术为基础的高性能32位嵌入式微处理器的广泛应用，为智能机器人研究领域中，引入实时操作系统提供了强有力的物质基础，同时这将是机电控制系统的未来发展趋势。嵌入式智能机器人路径算法的主要从获取和决策两方面实现，获取是指通过感知系统获取所需要的环境信息，决策是指通过决策运算后，得出的控制数据由伺服控制系统接收，同还能够实现与其他机器人的通讯和人机交互。嵌入式智能机器人路径规划的运用，需要嵌入式操作系统有较好的实时性、可靠性，并对系统成本提出了更高的要求，此外，根据系统拥有的定制和裁减的特点，在开展多任务管理的同时也能够保证工作的实时性能。嵌入式智能机器人路径算法，不需要使用复杂的系统即功能，如文件系统等。嵌入式智能机器人路径技术的研究重点主要在仿人智能和仿生智能两方面，随着我国科学技术的发展，嵌入式智能机器人与多种学科交叉和结合，比如，人工智能、认知科学等，使其智能化的行为程度不断的提升。此外，嵌入式系统还适用于在功能、体积等方面有严格规定的专业计算机系统，使计算机系统具体专用性强、实时性好、微内核精简等优势，由此可见将嵌入式智能机器人路径规划算法与嵌入式技术相结合是未来智能化机器人的重要发展方向。
4总结
随着我国科技水平的不断提高，遥感技术、控制技术等诸多技术的进一步发展，在智能机器人研究领域，嵌入式智能机器人路径技术也已经取得了显著的成就。在未来的机器人系统中，遗传算法、神经网络法、模糊逻辑控制法等将会进一步应用于嵌入式智能机器人的研究中，使机器人的各方面性能得到显著提升。
【参考文献】
[1]王思德.基于Cortex A9平台的双目立体视觉机器人路径规划研究[D].山东大学，2016.
