时间：2023-06-08 09:15:56
序论：速发表网结合其深厚的文秘经验，特别为您筛选了11篇路径规划典型算法范文。如果您需要更多原创资料，欢迎随时与我们的客服老师联系，希望您能从中汲取灵感和知识！
交通运输的现代化使人们享受便利的同时，也面临道路拥堵、事故频发等问}。近年来，智能交通系统越来越受到人们的重视，它涉及到交通领域诸多方面，如最优路径选择、车辆路径规划、动态车辆调度、交通流量控制等。其中一个重要的应用是一类典型的以数学理论为基础的组合优化问题，而蚁群算法具有内在的搜索机制及正反馈性，适合求解一系列的组合优化问题。
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-），女。工学硕士学位。现供职于厦门软件职业技术学院软件工程系。主要研究方向为软件工程、智能算法。
1 引言
在移动机器人导航技术应用过程中，路径规划是一种必不可少的算法，路径规划要求机器人可以自己判定障碍物，以便自主决定路径，能够避开障碍物，自主路径规划可以自动的要求移动机器人能够安全实现智能化移动的标志，通常而言，机器人选择的路径包括很多个，因此，在路径最短、使用时间最短、消耗的能量最少等预定的准则下，能够选择一条最优化的路径，成为许多计算机学者研究的热点和难点。
2 背景知识
神经网络模拟生物进化思维，具有独特的结构神经元反馈机制，其具有分布式信息存储、自适应学习、并行计算和容错能力较强的特点，以其独特的结构和信息处理方法，在自动化控制、组合优化领域得到了广泛的应用，尤其是大规模网络数据分析和态势预测中，神经网络能够建立一个良好的分类学习模型，并且在学习过程中优化每一层的神经元和神经元连接的每一个节点。1993年，Banta等将神经网络应用于移动机器人路径规划过程中，近年来，得到了广泛的研究和发展，morcaso等人构建利用一个能够实现自组织的神经网络实现机器人导航的功能，并且可以通过传感器训练网络，取得更好的发展，确定系统的最佳路径。神经网络拓扑结构模型可以分为：
2.1 前向网络
网络中各个神经元接受前一级的输入，并输出到下一级，网络中没有反馈，可以用一个有向无环路图表示。这种网络实现信号从输入空间到输出空间的变换，它的信息处理能力来自于简单非线性函数的多次复合。网络结构简单，易于实现。反传网络是一种典型的前向网络。
2.2 反馈网络
网络内神经元间有反馈，可以用一个无向的完备图表示。这种神经网络的信息处理是状态的变换，可以用动力学系统理论处理。系统的稳定性与联想记忆功能有密切关系。Hopfield网络、波耳兹曼机均属于这种类型。
3 基于人工神经网络的移动机器人路径规划算法
神经网络解决移动机器人路径规划的思路是：使用神经网络算法能够描述机器人移动环境的各种约束，计算碰撞函数，该算法能够将迭代路径点集作为碰撞能量函数和距离函数的和当做算法需要优化的目标函数，通过求解优化函数，能够确定点集，实现路径最优规划。神经网络算法在移动机器人路径规划过程中的算法如下：
（1）神将网络算法能够初始化神经网络中的所有神经元为零，确定目标点位置的神经元活性值，并且能够神经网络每层的神经元连接将神经元的值传播到出发点；
（2）动态优化神经网络，根据神经网络的目标节点和障碍物的具置信息，在神经网络拓扑结构中的映射中产生神经元的外部输入；
（3）确定目标值附件的神经元活性值，并且使用局部侧的各个神经元之间，连接整个神经网络，并且在各个神经元中进行传播。
（4）利用爬山法搜索当前邻域内活性值最大的神经元，如果邻域内的神经元活性值都不大于当前神经元的活性值，则机器人保持在原处不动；否则下一个位置的神经元为邻域内具有最大活性值的神经元。
（5）如果机器人到达目标点则路径规划过程结束，否则转步骤（2）。
4 基于人工神经网络的移动机器人路径规划技术展望
未来时间内，人工神经在机器人路径规划过程中的应用主要发展方向包括以下几个方面：
4.1 与信息论相融合，确定神经网络的最优化化目标解
在神经网络应用过程中，由于经验值较为难以确定，因此在神经网络的应用过程中，将神经网络看做是一个贝叶斯网络，根据贝叶斯网络含有的信息熵，确定神经网络的目标函数的最优解，以便更好的判断机器人移动的最佳路径。
4.2 与遗传算法想结合，确定全局最优解
将神经网络和遗传算法结合起来，其可以将机器人的移动环境设置为一个二维的环境，障碍物的数目、位置和形状是任意的，路径规划可以由二维工作空间一系列的基本点构成，神经网络决定机器人的运动控制规则，利用相关的神经元的传感器作用获未知环境的情况，将障碍信息和目标点之间的距离作为神经网络的输入信息，使用遗传算法完成神经网络的权值训练，神经网络的输出作为移动机器人的运动作用力，实现一个可以在未知环境中进行的机器人运动路径规划。
4.3 与蚁群算法相结合，降低搜索空间，提高路径规划准确性
为了提高神经网络的搜索准确性和提高效率，可以将蚁群算法与神经网络相互结合，蚁群算法的路径规划方法首先采用栅格法对机器人工作环境进行建模，然后将机器人出发点作为蚁巢位置，路径规划最终目标点作为蚁群食物源，通过蚂蚁间相互协作找到一条避开障碍物的最优机器人移动路径。
5 结语
随着移动机器人技术的发展，路径规划作为最重要的一个组成部分，其得到了许多的应用和发展，其在导航过程中，也引入了许多先进的算法，比如神经网络，更加优化了移动的路径。未来时间内，随着神经网络技术的改进，可以引入遗传算法、信息论、蚁群算法等，将这些算法优势结合，将会是路径规划更加准确和精确。
参考文献
[1]朱大奇,颜明重,滕蓉. 移动机器人路径规划技术综述[J].控制与决策,2010,25(7): 961-967.
[2]刘毅.移动机器人路径规划中的仿真研究[J].计算机仿真,2011,28(6): 227-230.
[3]熊开封,张华.基于改进型 FNN 的移动机器人未知环境路径规划[J].制造业自动化,2013,35(22): 1-4.
[4]柳长安,鄢小虎,刘春阳.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5).
二、算法模型
基于时间成本的物流线路优化计算主要运用到三个求解算法，分别是聚类算法、最优路径算法和订单日规划算法。基本求解方案是：第一步按照车辆装载率完成对客户兴趣点聚类；第二步细致优化配送路径；第三步平衡每日订单分布。
1.聚类算法
聚类是空间数据挖掘中的一个重要研究领域，是指将物理的或抽象的对象分组成为由类似对象组成的多个类（簇）的过程。
以绍兴烟草为例，聚类计算时首先采用自下而上的一阶段方法对全地区26000个零售户点进行聚类，获得411个初始聚类结果。再根据实际需求，按照类容量将前408个类作为直接指派的初始类核，以配送车装载率90%作为类容量上限，进行直接指派聚类，最终获得聚类结果。
2.最优路径算法
最优路径算法的目标是寻找给定起点和终点间的最短路径，文章采用Dijkstra（迪杰斯特拉）算法。Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
⑴初始时，S只包含源点，即S=v。U包含除v外的其他顶点，U中顶点u对应的距离值为边上的权（若v与u有边）或 （若u不是v的出边邻接点）。
⑵从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
⑶以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。
⑷重复步骤（2）和（3）直到所有顶点都包含在S中。
3.配送工作量模型和订单日规划算法
进行订单日规划时，文章引入工作量模型概念，将综合作业时间作为线路优化的单一标准，把送货户数、送货量、行驶里程等多维度统一转换成工作时间，解决线路优化时指标过多，计算困难的问题。
综合作业时间=装车交接时间+车辆行驶时间+基本服务时间+客户交接时间+现金缴款时间。装车交接时间=（装车准备时间车次）+（装车框数单框装车时间）
订单日规划算法的目标是确定各配送线路的配送车辆和配送日，规划要求满足以下约束条件：车辆数最少；一周内各配送车辆工作时间基本均衡；每天各配送车辆工作时间基本均衡；每天工作时间上限设定6.5小时。
订单日规划算法模型：
约束条件：
（1.1）
（1.2）
（1.3）
（1.4）
i 需要安排的路线序号；取值范围从1到路线的最大数；
j 送货车序号；取值范围从1到指定车辆数；
k订单日的序号；取值范围从1到5，表示一周配送5天；
b每天所有车辆工作时间的上限；
c每辆车一周工作量上限；
d每辆车每天工作量的上限，d为6.5小时。
公式（1.1）一条路线有却只能有某辆车在某一天配送；
公式（1.2）每天所有车
的工作量不能超过上限b；
公式（1.3）每辆车每周的工作量不能超过上限c；
关键词：多机器人；路径规划；强化学习；评判准则
Abstract:This paper analyzed and concluded the main method and current research of the path planning research for multirobot.Then discussed the criterion of path planning research for multirobot based large of literature.Meanwhile，it expounded the bottleneck of the path planning research for multirobot，forecasted the future development of multirobot path planning.
Key words:multirobot；path planning;reinforcement learning;evaluating criteria
近年来，分布式人工智能(DAI)成为人工智能研究的一个重要分支。DAI研究大致可以分为DPS（distributed problem solving）和MAS（multiagent system）两个方面。一些从事机器人学的研究人员受多智能体系统研究的启发，将智能体概念应用于多机器人系统的研究中，将单个机器人视做一个能独立执行特定任务的智能体，并把这种多机器人系统称为多智能体机器人系统（MARS）。因此，本文中多机器人系统等同于多智能体机器人系统。目前，多机器人系统已经成为学术界研究的热点，而路径规划研究又是其核心部分。
机器人路径规划问题可以建模为一个带约束的优化问题，其包括地理环境信息建模、路径规划、定位和避障等任务，它是移动机器人导航与控制的基础。单个移动机器人路径规划研究一直是机器人研究的重点，且已经有许多成果[1~3]，例如在静态环境中常见的有连接图法、可视图法、切线图法、Voronoi图法、自由空间法、栅格法、拓扑法、链接图法、DempsterShafer证据理论建图等；动态环境中常见的有粒子群算法、免疫算法、遗传算法、神经网络、蚁群算法、模拟退火算法、人工势场法等。然而，多机器人路径规划研究比单个机器人路径规划要复杂得多，必须考虑多机器人系统中机器人之间的避碰机制、机器人之间的相互协作机制、通信机制等问题。
1 多机器人路径规划方法
单个机器人的路径规划是找出从起始点至终点的一条最短无碰路径。多个机器人的路径规划侧重考虑整个系统的最优路径，如系统的总耗时间最少路径或是系统总路径最短等。从目前国内外的研究来看，在规划多机器人路径时，更多考虑的是多机器人之间的协调和合作式的路径规划。
目前国内外多机器人路径规划研究方法分为传统方法、智能优化方法和其他方法三大类。其中传统方法主要有基于图论的方法（如可视图法、自由空间法、栅格法、Voronoi图法以及人工势场方法等）；智能优化方法主要有遗传算法、蚁群算法、免疫算法、神经网络、强化学习等；其他方法主要有动态规划、最优控制算法、模糊控制等。它们中的大部分都是从单个机器人路径规划方法扩展而来的。
1）传统方法 多机器人路径规划传统方法的特点主要体现在基于图论的基础上。方法一般都是先将环境构建成一个图，然后再从图中寻找最优的路径。其优点是比较简单，比较容易实现；缺点是得到的路径有可能不是最优路径，而是次优路径。薄喜柱等人[4]提出的一种新路径规划方法的基本思想就是基于栅格类的环境表示和障碍地图的。而人工势场方法的基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力，目标点产生引力，引力和斥力周围由一定的算法产生相应的势，机器人在势场中受到抽象力作用，抽象力使得机器人绕过障碍物。其优点是适合未知环境下的规划，不会出现维数爆炸问题；但是人工势场法也容易陷入局部最小，并且存在丢失解的部分有用信息的可能。顾国昌等人[5]提出了引用总体势减小的动态调度技术的多机器人路径规划，较好地解决了这个问题。
2）智能优化方法 多机器人路径规划的智能优化方（算）法是随着近年来智能计算发展而产生的一些新方法。其相对于传统方法更加智能化，且日益成为国内外研究的重点。
遗传算法是近年来计算智能研究的热点，作为一种基于群体进化的概率优化方法，适用于处理传统搜索算法难以解决的复杂和非线性问题，如多机器的路径规划问题。在路径规划中，其基本思想是先用链接图法把环境地图构建成一个路径节点链接网，将路径个体表达为路径中一系列中途节点，并转换为二进制串；然后进行遗传操作（如选择、交叉、复制、变异），经过N次进化，输出当前的最优个体即机器人的最优路径。遗传算法的缺点是运算速度不快，进化众多的规划要占据很大的存储空间和运算时间；优点是有效避免了局部极小值问题，且计算量较小。
孙树栋等人[6，7]在这方面较早地展开了研究，提出的基于集中协调思想的一种混合遗传算法来规划多机器人路径方法较好地解决了避障问题。但不足的是该方法必须建立环境地图，在环境未知情况下的规划没有得到很好的解决；且规划只能保证找到一个比较满意的解，在求解全局最优解时仍有局限。
文献[8]中提出的一种基于定长十进编码方法有效降低了遗传算法的编码难度，克服了已有的变长编码机制及定长二进制编码机制需特殊遗传操作算子和特殊解码的缺陷， 使得算法更加简单有效。
智能计算的另一种常见的方法——蚁群算法属于随机搜索的仿生算法。其基本思想是模拟蚂蚁群体的觅食运动过程来实现寻优，通过蚂蚁群体中各个体之间的相互作用，分布、并行地解决组合优化问题。该算法同样比较适合解决多机器人的路径规划问题。
朱庆保[9]提出了在全局未知环境下多机器人运动蚂蚁导航算法。该方法将全局目标点映射到机器人视野域边界附近作为局部导航子目标，再由两组蚂蚁相互协作完成机器人视野域内局部最优路径的搜索，然后在此基础上进行与其他机器人的碰撞预测与避碰规划。因此，机器人的前进路径不断被动态修改，从而在每条局部优化路径引导下，使机器人沿一条全局优化的路径到达目标点。但其不足是在动态不确定的环境中路径规划时间开销剧增，而且机器人缺乏必要的学习，以至于整个机器人系统路径难以是最优路径。
强化学习[10，11] (又称再激励学习)是一种重要的机器学习方法。它是一种智能体从环境状态到行为映射的学习，使得行为从环境中获得积累奖赏值最大。其原理如图1所示。
强化学习算法一般包含了两个步骤：a）从当前学习循环的值函数确定新的行为策略；b）在新的行为策略指导下，通过所获得的瞬时奖惩值对该策略进行评估。学习循环过程如下所示，直到值函数和策略收敛:
v0π1v1π2…v*π*v*
目前比较常见的强化学习方法有：Monte Carlo方法、动态规划方法、TD（时间差分）方法。其中TD算法包含Sarsa算法、Q学习算法以及Dyna-Q算法等。其Q值函数迭代公式分别为
TD（0）策略： V(si)V(si)+α[γi+1+γV(si+1)-V(si)]
Sarsa算法： Q(st，at)Q(st，at)+α[γt+1+γQ(st+1，at.+1)-Q(st，at)]Qs′学习算法： Qπ(s，a)=∑Pαss′[Rass′+γVπ(s′)]
近年来，基于强化学习的路径规划日益成为国内外学者研究的热点。M. J. Mataric[12]首次把强化学习引入到多机器人环境中。而基于强化学习的多机器人路径规划的优点主要体现在：无须建立精确的环境模型，简化了智能体的编程；无须构建环境地图；强化学习可以把路径规划、避碰、避障、协作等问题统一解决。
张芳等人[13]提出了基于再激励协调避障路径规划方法，把再励函数设计为基于行为分解的无模型非均匀结构，新的再励函数结构使得学习速度得以提高且有较好的鲁棒性。同时，证明了在路径规划中，机器人的趋向目标和避障行为密切相关，对反映各基本行为的再励函数取加权和来表示总的再励函数要优于取直接和的表示方式，也反映了再励函数设计得合理与否及其确切程度将影响再励学习的收敛速度。王醒策等人[14]在动态编队的强化学习算法方面展开了研究。宋一然[15]则提出了分段再励函数的强化学习方法进行路径规划。其缺点是学习次数较多、效率不高，当机器人数目增加时，它有可能面临维数灾难的困难。所以，基于强化学习的路径规划在多机器人环境下的学习将变得比较困难，需要对传统的强化学习加以优化，如基于人工神经网络的强化学习[16]等。
3)其他方法 除了以上国内外几种比较常见且研究较多的方法外，还有唐振民等人[17]提出的基于动态规划思想的多机器人路径规划，把运筹学中的动态规划思想与Dijkstra算法引入到多机器人的路径规划中，用动态规划的基本思想来解决图论中的费用流问题和路径规划中的层级动态联盟问题。其选择距离邻近法作为联盟参考依据。一个机器人的邻居是指在地理位置上分布在这个机器人周围的其他机器人；与该机器人最近邻的机器人为第一层邻居，第一层邻居的邻居为该机器人的第二层邻居， 依此类推。那么层级越高（即越近)的邻居，它满足协作要求的可能性越大。动态规划算法实质上是一种以空间换时间的技术，它在实现的过程中，必须存储产生过程中的各种状态，其空间复杂度要大于其他算法，故动态规划方法比较适合多机器人的全局路径规划。
孙茂相等人[18]提出了最优控制与智能决策相结合的多移动机器人路径规划方法。其首先构造一个以各机器人最优运动状态数据库为核心的实时专家系统， 在离线状态下完成; 然后各机器人在此专家系统的支持下， 以最优规划策略为基础， 采用速度迁移算法， 自主决定其控制。该方法拥有较好的稳定性与复杂度。焦立男等人[19]提出的基于局部传感和通信的多机器人运动规划框架较好地解决了多机器人路径规划在局部在线规划的系统框架问题。沈捷等人[20]提出了保持队形的多移动机器人路径规划。以基于行为的导航算法为基础，把机器人队列的运动过程划分为正常运动、避障和恢复队形三个阶段。在避障阶段，引入虚拟机器人使队形保持部分完整;当队形被严重打乱时，规划机器人的局部目标位姿使队列快速恢复队形。其算法重点为避障机器人进入避障状态，暂时脱离队列，并以虚拟机器人代替避障机器人。
2 多机器人避碰和避障
避障和避碰是多机器人路径规划研究中需要考虑的重点问题之一。避障和避碰主要讨论的内容有防止碰撞；冲突消解、避免拥塞；如何避免死锁。在路径规划中常见的多机器人避障方法[21]有主从控制法、动态优先法（建立在机器人之间的通信协商上）、交通规则法、速率调整法，以及障碍物膨胀法、基于人工势场的方法等。
目前国内外对于多机器人避障展开的研究还不是很多，比较典型的有徐潼等人[22]以Th.Fraichard的思想为基础，扩充并完善了路径/速度分解方案来协调多机器人，设立集中管理agent进行整体规划，为每个机器人规划路径；并根据优先级规则对运动特征进行分布式规划以避免机器人间的冲突。周明等人[23]提出分布式智能避撞规划系统，将原来比较复杂的大系统转换为相对简单的子系统问题，由各智能机器人依据任务要求和环境变化， 独立调整自身运动状态，完成任务的分布式智能决策体系结构。任炏等人[24]提出了基于过程奖赏和优先扫除的强化学习多机器人系统的冲突消解方法。该算法能够显著减少冲突，避免死锁，提高了系统整体性能。欧锦军等人[25]提出了通过调整机器人的运动速度实现多机器人避碰，将避碰问题转换为高维线性空间的优化问题， 并进一步将其转换为线性方程的求解。该方法的缺点是系统的复杂度较高、计算量太大。
人工势场方法的特点是计算简洁、实时性强、便于数学描述，且适合于多自由度机器人环境，但容易产生抖动和陷入局部极小。为了克服其缺点，景兴建等人[26]提出了人工协调场的方法，在传统排斥力场中增加一个协调力，并将吸引力、排斥力和协调力与局部环境下机器人的运动状态和运动要求结合起来，有效地保证机器人的安全性，提高机器人在复杂动态环境下行为决策的准确性和鲁棒性。
3 多机器人协作和协调机制
多机器人间的运动协调[27~31]是多机器人路径规划的关键，也是多机器人与单机器人路径规划相区别的根本所在。多机器人系统在复杂动态实时环境下，由于受到时间、资源及任务要求的约束，需要在有限时间、资源的情况下进行资源分配、任务调配、冲突解决等协调合作问题，而机器人间的协调与协作，能够大大地提高整个系统的效率和鲁棒性，成为系统完成控制或解决任务的关键。
目前已有的协调方式分为集中式、分布式和混合式三种。在集中式协调中，集中规划器详细地规划出每个机器人的动作，通常的做法是将多个机器人看做一个多自由度的机器人进行规划；而分布式协调规划中，机器人之间进行合作，将一个任务分成多个子任务，根据各自的特点完成不同的子任务，从而共同完成总任务；混合式协调是集中式和分布式混合在一起的形式。
多机器人间典型的协调方法[32]有合同网协议[33]、黑板模型、结果共享的协同方法、市场机制。近年来强化学习在多机器人协作方面也得到很好的应用，陈雪江[32]在基于强化学习的多机器人协作方面展开了研究，提出了多智能体协作的两层强化学习方法来求解在多智能体完全协作、有通信情况下的协作问题。其主要通过在单个智能体中构筑两层强化学习单元来实现：第一层强化学习单元负责学习智能体的联合任务协作策略；第二层强化学习单元负责学习在本智能体看来是最有效的行动策略。陈伟等人[34]提出基于多目标决策理论的多机器人协调方法；通过对环境的拓扑建模，从基于行为的机器人学角度出发，对任务进行分解并设计目标行为，以多目标行为决策理论作为决策支持，从而达到多机器人运动协调的目的。
4 多机器人路径规划方(算)法的判优准则
通常评价机器人路径规划方(算)法的标准文献[35]有正确性、时间/空间复杂度、并行性、可靠性、扩展性、鲁棒性和学习。而多机器人的路径规划除了以上一些衡量标准之外，还需要考虑整个系统的最优化以及机器人间的协调性。
1)正确性 是分析算法的最基本的原则之一。一般来说算法的正确性是指:在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。但在多机器人路径规划算法中，正确性主要指:路径规划算法要生成多个机器人协调运动的无碰安全路径;这条路径是优化的。
2)安全性 一般指多机器人所生成的各路径中节点与障碍物有一定的距离。但在实际的应用背景下，有人认为安全性可以从两个方面来理解：a）狭义地讲，它就是机器人在行走过程中所做的功。在一定的条件下，它与路径长度准则是一致的。b）广义地讲，它是各种优化条件加权综合而得到的结果。
3)复杂度 一个算法的复杂性高低体现在该算法所需要的计算机资源的多少上面。所需要的资源越多，该算法的复杂性越高；反之，所需要的资源越少，该算法的复杂性就越低。算法的复杂性包括时间复杂度和空间复杂度。
在多机器人的路径规划算法中，算法的复杂度分析显得尤为重要。一般地，单机器人路径规划算法的时空复杂度已经颇高，它们的数量级至少是O(n2)；多机器人的路径规划算法不仅是m-O(n2)(即m个机器人路径规划简单地叠加)，它们之间还存在着对运动空间竞争的冲突，面对不断变化的冲突的协调需要花费大量的时间和空间。通常多机器人的路径规划算法与机器人的个数呈指数关系O(km×n2)（k为常数）。这对多机器人路径规划算法的时间/空间复杂度控制是一个很严峻的考验。
4)并行性 算法的并行性从算法设计、编写程序、编译和运行等多个不同的层次来体现。路径规划过程需要大量的计算，当处理的环境比较复杂，机器人工作的环境过于紧凑，尤其是机器人数量很多时，算法的时间/空间复杂度势必会成为算法效率的关键。因此，在算法设计和运行上的并行性是通常考虑的方法。对多个机器人的路径规划尽量采用分布式多进程的规划机制，以实现每个机器人路径规划的并行性。
5)可靠性 把多个机器人及其工作环境看成是一个系统，多机器人处于它们各自的起始点时，称该系统处于初始状态；当它们处于各自的目标点时，称该系统处于目标状态。多机器人的路径规划就是在该系统的这两个状态间建立一串合理的状态变迁。这一状态变迁过程可能会历经许多状态，如果在状态变迁过程中，路径规划算法控制不好各状态间的转移关系，就会导致系统紊乱，出现机器人间的碰撞、找不到路径等恶性后果，使任务失败。所以这就对算法的可靠性和完备性提出了挑战。为了很好地克服这一困难，需要对系统的各种可能状态建模，分析它们相互间的关系，建立有限状态自动机模型或Petri网模型，并以此为指导，按照软件工程的思想，构造恰当的算法输入来对算法的可靠性进行检验。
6)可扩展性 在多机器人的路径规划算法中，可扩展性主要是指一种路径规划算法在逻辑上，或者说在实现上能否容易地从2D空间扩展到3D空间，从低自由度扩展到高自由度，从较少的机器人数到更多的机器人数。可扩展性在各种路径规划算法之间没有一种量的比较标准，只能从实际的具体情况出发、从对环境描述的适宜程度出发、从算法解决这一问题的复杂度出发、从算法本身的自适应出发等来考虑。
7)鲁棒性和学习 鲁棒性对于多机器人系统非常重要。因为许多应用，如路径规划要求连续的作业、系统中的单个机器人出现故障或被破坏，要求机器人利用剩余的资源仍然能够完成任务。学习是在线适应特定的任务。虽然通用的系统非常有用，但将它用于特定应用上时，通常需要调整一些参数。具有在线调整相关参数的能力是非常吸引人的，这在将体系结构转移到其他应用时可以节省许多工作。尤其是多机器人系统中机器人的自身学习和相互间的学习能够大大提高整个系统的效率和系统的稳定性。
8）最优化 对动态环境有优化反应。由于有些应用领域涉及的是动态的环境条件，具有根据条件优化系统的反应能力成为能否成功的关键。
5 结束语
综上所述，国内外研究者在多机器人路径规划取得了一些成果，但是在协作、学习、通信机制等方面仍面临很大的困难和不足。如何进一步提高机器人间的协调性，增强机器人自身以及相互间的学习以提高多机器人系统的效率和鲁棒性都有待深入研究。近年来无线通信技术得到长足发展，但在目前的技术条件下，在多机器人系统中实现所有机器人之间的点对点实时通信还有较大困难，这也是大多数多机器人系统仍然采用集中通信方式的主要原因。因此，如何降低多机器人系统对通信速度的依赖程度也是一个非常重要的问题。
总之，多机器人路径规划设计和实现是一项极其复杂的系统工程，展望其能在结合计算智能方法，如差分进化、遗传算法、粒子群算法、免疫算法、模糊逻辑算法、BP网络、人工势场的改进、模拟退火和环境建模方法等方面取得新的突破。
参考文献：
［1］WEISS G.Multiagent systems:a modern approach to distributed modern approach to artificial intelligence[M].Cambridge， Massachusetts：MIT Press，1999：121-161.
[2]蔡自兴，徐光祐.人工智能及其应用:研究生用书[M].3版.北京：清华大学出版社，2004：124-198.
[3]谭民，王硕，曹志强.多机器人系统[M].北京：清华大学出版社，2005：6-81.
[4]薄喜柱，洪炳熔.动态环境下多移动机器人路径规划的一种新方法[J].机器人，2001，23（5）：407-410.
[5]顾国昌，李亚波.基于总体势减小的动态调度技术解决多机器人的路径规划[J].机器人，2001，23（2）：171-174.
[6]孙树栋，林茂.基于遗传算法的多移动机器人协调路径规划[J].自动化学报，2000，26（5）：672-676.
[7]周明，孙树栋，彭炎午.基于遗传算法的多机器人系统集中协调式路径规划[J].航空学报，2000，21（2）：146-149.
[8]CAI Zixing，PENG Zhihong.Cooperative coevolutionary adaptive genetic algorithm in path planning of cooperative multimobile robot systems[J].Journal of Intelligent and Robotic Systems:Theory and Applications，2002，33(1):61-71.
[9]朱庆保.全局未知环境下多机器人运动蚂蚁导航算法[J].软件学报，2006，17（9）：1890-1898.
[10]SANDHOLM T W，CRITES R H.Multiagent reinforcement learning in the iterated prisoner’s dilemma[J].BioSystems，1996，37(1):147-166.
[11]高阳，陈世福，陆鑫.强化学习研究综述[J].自动化学报，2004，30（1）：
86-100.
[12]MATARIC M J.Interaction and intelligent behavior[D].Massachusetls:Department of Electrical Engineering and Computer Science，MIT，1994.
[13]张芳，颜国正，林良明.基于再励学习的多移动机器人协调避障路径规划方法[J].计算机工程与应用，2003，39（3）：80-83.
[14]王醒策，张汝波，顾国昌.多机器人动态编队的强化学习算法研究[J].计算机研究与发展，2003，40（10）：1444-1450.
[15]宋一然.基于强化学习的多机器人路径规划方法[J].莆田学院学报，2006，13（2）：38-41.
[16]韩学东，洪炳熔.基于人工神经网络的多机器人协作学习研究[J].计算机工程与设计，2002，23（6）：1-3.
[17]唐振民，赵春霞，杨静宇，等.基于动态规划思想的多机器人路径规划[J].南京理工大学学报，2003，27（5）：610-615.
[18]孙茂相，周明，王艳红，等.多移动机器人实时最优运动规划[J].控制与决策，1998，
13（2）：125-130.
[19]焦立男，唐振民.基于局部传感和通讯的多机器人运动规划框架[J].计算机工程与应用，2007，43(17)：89-93.
[20]沈捷，费树岷，郑波.多移动机器人保持队形路径规划[J].东南大学学报，2005，35(3):391-395.
[21]MANSOR M A，MORRIS A S.Path planning in unknown environment with obstacles using virtual window[J].Journal of Intelligent and Robotic Systems，1999，24(3):235-251.
[22]徐潼，唐振民.多机器人系统中的动态避碰规划[J].计算机工程，2003，29(17):
79-81，104.
[23]周明，孙茂相，尹朝万，等.多移动机器人分布式智能避撞规划系统[J].机器人，1999，21（2）：139-143.
[24]任炏，陈宗海.基于强化学习算法的多机器人系统的冲突消解的方法[J].控制与决策，2006，21(4):430-434，439.
[25]欧锦军，朱枫.一种多移动机器人避碰规划方法[J].机器人，2000，22(6):474-481.
[26]景兴建，王越超，谈大龙.基于人工协调场的多移动机器人实时协调避碰规划[J].控制理论与应用，2004，21(5):757-764.
[27]PANAIT L，LUKE S.Cooperative multiagent learning:the state of the art[J].Autonomous Agents and MultiAgent Systems，2005，11(3):387-434.
[28]TZAFESTAS C S，PROKOPIOU P A，TZAFESTAS S G.Path planning and control of a cooperative three robot system manipulating large objects[J].Journal of Intelligent and Robotic Systems，1998，22(2):99-116.
[29]薛宏涛，叶媛媛，沈林成，等.多智能体系统体系结构及协调机制研究综述[J].机器人，2001，23（1）：85-90.
[30]周风余，李贻斌，宋锐，等.基于混合式多智能体系统的协作多机器人系统研究[J].山东大学学报:工学版，2005，35(1):82-87.
[31]夏冰，张佐，张毅，等.基于多智能体系统的动态路径选择算法研究[J].公路交通科技，2003，20（1）：93-96.
[32]陈雪江.基于强化学习的多机器人协作机制研究[D].杭州：浙江工业大学，2004.
引言
物流与国民经济及生活的诸多领域密切相关，得到越来越多的重视，甚至被看作是企业“第三利润的源泉”。因此，作为物流领域中的典型问题，旅行商问题(Traveling Salesman Problem，TSP)的研究具有巨大的经济意义。
TSP(Traveling Salesman Problem)问题, 是VRP[2]的特例，也称为巡回旅行商问题,货担郎问题。简称为TSP问题，已证明TSP问题是NP难题。。TSP问题可描述为:给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单,简言之就是寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X={1,2,…,n}(X中的元素表示对n个城市的编号)的一个排列π(X)={v1, v2,…, vn},使取最小值.式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。它是一个典型的、容易描述但却难以处理的NP完全问题。同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。所以,有效解决TSP问题在计算理论上和实际应用上都有很高的价值。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法 (如遗传算法、神经网络优化法、列表寻优法、模拟退火法等)的间接比较标准。
1 遗传算法与蚁群算法
1.1 遗传算法原理
遗传算法(Genetic Algorithms，GA) 是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息.该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题.。选择算子、交叉算子和变异算子是遗传算法的3个主要操作算子.遗传算法中包含了如下5个基本要素:①对参数进行编码;②设定初始种群大小;③设计适应度函数;④设计遗传操作;⑤设定控制参数(包括种群大小、最大进化代数、交叉率、变异率等)
1.2 蚁群算法原理
研究表明：蚂蚁在觅食途中会留下一种外激素．蚂蚁利用外激素与其他蚂蚁交流、合作，找到较短路径．经过某地的蚂蚁越多，外激素的强度越大．蚂蚁择路偏向选择外激素强度大的方向．这种跟随外激素强度前进的行为会随着经过蚂蚁的增多而加强，因为通过较短路径往返于食物和巢穴之间的蚂蚁能以更短的时间经过这条路径上的点，所以这些点上的外激素就会因蚂蚁经过的次数增多而增强．这样就会有更多的蚂蚁选择此路径，这条路径上的外激素就会越来越强，选择此路径的蚂蚁也越来越多．直到最后，几乎所有的蚂蚁都选择这条最短的路径．这是一种正反馈现象．
2.算法改进
在传统解决方法中，遗传算法以其快速全局搜索能力在物流领域获得了广泛的应用。但遗传算法在求解到一定程度时，往往作大量的冗余迭代，对于系统中的反馈信息利用不够，效率较低；蚁群算法也以其较强的鲁棒性和智能选择能力被广泛应用于旅行商问题 。蚁群算法是通过信息素的累积和更新而收敛于最优路径,具有分布、并行、全局收敛能力，但由于蚁群算法的全局搜索能力较差，易陷入局部最优，很难得到最优解。
为了克服两种算法各自的缺陷,形成优势互补。为此首先利用遗传算法的随机搜索、快速性、全局收敛性产生有关问题的初始信息素分布。然后,充分利用蚁群的并行性、正反馈机制以及求解效率高等特征。算法流程如图1
图1 遗传混合算法流程
2.1遗传混合算法的具体描述如下：
Step1 给出，放置m个蚂蚁在n个城市上。
Step 2 把所有蚂蚁的初始城市号码放置到tabuk中，列表tabuk纪录了当前蚂蚁k所走过的城市，当所有n个城市都加入到tabuk中时，蚂蚁k便完成了一次循环，此时蚂蚁k所走过的路径便是问题的一个解。
Step 3 蚂蚁K从起点开始，按概率的大小选择下一个城市j,k∈{1，2，…,m},j∈allowedk如果蚂蚁k转移到j ,从allowedk中删除,并将j加入到tabuk直至allowedk= 时重新回到起点。
Step 4 是否走完所有的城市，否，则转入Step 3。
Step 5 计算,记录，更新信息素浓度，所有路径信息更新，如果,清空tabuk则转入Step 2。
Step 6 当时，得到相对较优蚂蚁的序列。初始化种群。
Step 7 计算适应度值。
Step 8 进行遗传交叉与变异操作。
Step 9 输出得到的最短回路及其长度。
2.2 算法过程实现
（1）种群初始化
用蚁群算法进行初始化种群，放m只蚂蚁对所有城市进行遍历，将得到的结果进行优化，做为蚁群算法的初始种群。每只蚂蚁走过的路径的就代表了一条基因（a0、a1、…、am-1、am），对于这条基因表示这只蚂蚁首先从a0出发，次之访问a1、…然后依次访问am-1、am最后再回到a0。
（2）状态转移规则设置
转移概率，为t时刻蚂蚁由i城到j城的概率。
（1）
式中，allowedk表示蚂蚁k下一步允许选则的城市，表示信息启发因子，其值越大，该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性超强；β为期望启发因子，β的大小表明启发式信息受重视的程度，其值越大，蚂蚁选择离它近的城市的可能性也越大，越接近于贪心规则［6］。为启发因子，其表达式为: ，每条路上的信息量为：
（2）其中
其中ρ表示路径上信息的蒸发系数，1-ρ表示信息的保留系数；表示本次循环路径(i,j)上信息的增量。表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量，如果蚂蚁k没有经过路径(i,j)，则的值为零，表示为：
（3）
其中，Q为常数， 表示第k只蚂蚁在本次循环中所走过的路径的长度。
（3）交叉算子的设计
首先随机地在父体中选择两杂交点,再交换杂交段,其它位置根据保持父体中城市的相对次序来确定。例如,设两父体及杂交点的A1和A2, A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 8 1 6 7 9 3)。交换杂交段于是仍有B1=(2 6 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 3)。在新的城市序列中有重复的数，将杂交段中对应次序排列,即: 7-8、3-1、5-6，依此对应关系替换杂交段中重复的城市数。将B1中(2 6 4)重复的6换为5，B2(9 3)中重复的3换为1.。杂交后的两个体为B1=(2 5 4 1 8 7 6 9 1),B2=(4 5 2 7 3 5 8 9 1)。本算法采用此方法交杂交。
3.仿真实验
对TSP问题仿真所用的数据库是TSPLIB典型51城市的数据。仿真平台如表1所示。
表1 仿真试验平台
设备名称
型号
CPU
Pentium(R)M 1.66 GH
内存
512M
操作系统
Microsoft Windows XP
仿真软件
MierosoftVisualC++6.0
3.1 遗传算法仿真
基本遗传算法仿真。对51城市路径优化路径优化。参数设置如下:种群:50,最大迭代数:5000,交叉概率:0.8,变异概率:0.2
遗传算法找到最优解的时间是95 s, ,路径长度497。
3.2 蚁群算法仿真
基本蚁群算法对51城市路径优化。其参数设置如下：ρ=1α=1，β=8，τ0=0.001Qu=100., m=51
基本蚁群算法找到最优解的时间是68 s, 路径长度465。
3.3遗传混合算法
遗传混合算法对51城市路径优化。其参数设置如下：种群:51,最大迭代数:5 000,交叉概率:0.8,变异概率:0.001;ρ=1α=1，β=8，τ0=0.001Qu=100，m=51；
遗传混合算法找到最优解的时间是50 s, 路径长度459。
遗传算法、基本蚁群算法、遗传混合算法对TSPLIB典型51城市的数据进行仿真,仿真结
果对比如表2所
算法名称
所用时间（s）
最优结果
遗传算法
95
497
基本蚁群算法
68
465
改进混合算法
50
456
4.结论
本文为了更好地解决物流领域中的旅行商问题，充分发挥遗传算法的全局搜索能力和蚁群算法的正反馈能力和协同能力，采用了遗传算法与蚁群算法混合算法进行求解，并且进行了模拟仿真。仿真结果表明，利用遗传与蚁群混合算法可以找到较好解的能力，大大提高计算效率，结果质量也较好。
参考文献：
［1］小平,曹立明.遗传算法———理论、应用与软件实现[M].西安交通大学出版社,2002.
［2］[日]玄光男,程润伟.遗传算法与工程设计[M].科学出版社, 2000.
［3］胡小兵，黄席樾。蚁群优化算法及其应用[J]. 计算机仿真 2004，24（5）
一、概述各移动运营商及移动通信相关技术咨询单位在进行规划方案验证时，传统的方法是通过规划仿真软件使用宏蜂窝传播模型及20米精度三维电子地图对规划方案进行仿真验证；然而，宏蜂窝传播模型的应用范围和自身局限性限制了规划方案仿真验证的精度：首先，宏蜂窝传播模型的应用范围一般在500米以上，而CBD区域基站的覆盖半径一般在500米以下。其次，宏蜂窝传播模型只能从宏观上反映方案覆盖效果，无法根据建筑物的高度从微观上反映局部的覆盖情况。因此，需要采用更合适的传播模型配合高精度的三维电子地图对CBD区域的规划方案进行仿真验证，以确保该重点区域无线网络建成后的网络性能。
目前射线跟踪模型作为一种高精度的规划仿真传播模型在大中型城市覆盖重点区域的规划方案仿真验证中得到广泛应用。本文首先对射线跟踪模型的原理进行探讨，然后以WaveCall公司的WaveSight模型为例说明射线跟踪模型的应用方法。其结果有助于应用射线跟踪模型对规划方案进行精确验证，对规划工作有积极的参考和指导作用。
二、射线跟踪模型简介2.1 微蜂窝传播模型介绍 当前传播模型根据应用范围可分为宏蜂窝传播模型和微蜂窝传播模型，宏蜂窝传播模型应用范围为1km至几十km；而微蜂窝传播模型应用范围仅为几百米，一般只适用于基站附近区域。免费论文。由于CBD区域基站的覆盖一般在500米以内，因此应用微蜂窝传播模型对该区域规划方案的效果进行仿真验证更为合适。
微蜂窝传播模型根据模型建立方法，可分为经验模型，确定性模型以及混合模型；
l经验模型
经验模型是在大量测量的基础上产生的，该模型与室外传统宏蜂窝传播模型类似，不考虑理论计算，对基站附近测量大量数据后统计归纳出经验模型。
l确定性模型
确定性模型是依据电波传播理论计算出接收点与发射点之间的传播损耗。射线跟踪模型是一种典型的确定性模型，确定性模型不考虑测量，仅在确定计算公式中的个别参数时需要测量验证。
l混合模型
混合模型结合了经验模型和确定性模型，一方面混合模型以电波传播理论为依据得出电波的传播模型，同时需要对基站附近测量大量数据以统计确定传播模型中的参数值。
2.2 射线跟踪模型介绍 射线跟踪模型是一种确定性模型，其基本原理为标准衍射理论（Uniform Theory ofDiffraction，简称UTD）。根据标准衍射理论，高频率的电磁波远场传播特性可简化为射线（Ray）模型。因此射线跟踪模型实际上是采用光学方法，考虑电波的反射、衍射和散射，结合高精度的三维电子地图（包括建筑物矢量及建筑物高度），对传播损耗进行准确预测。
由于在电波传播过程中影响的因素过多，在实际计算预测中无法把所有的影响因素都考虑进去，因此需要简化传播因素；射线跟踪算法把建筑物的反射简化为光滑平面反射、建筑物边缘散射以及建筑物边缘衍射。
根据考虑路径的种类不同，射线跟踪模型可分为三种：
l2D射线跟踪模型
只考虑水平切面的传播路径，即第一类路径。
l3D射线跟踪模型
只考虑水平切面以及垂直切面的传播路径，即第一类及第三类路径。
l全3D射线跟踪模型
考虑所有传播路径，即考虑所有第一、二、三类路径。
三、射线跟踪模型基本原理射线跟踪模型的基本原理是简化传播因素，采用光学方法定位传播路径并计算各接收点与发射点之间的路径损耗；因此，射线跟踪模型的关键在于如何定位接收点与发射点之间的传播路径并计算路径损耗。免费论文。
3.1 水平切面的传播损耗从发射源在接收点之间可能存在很多传播路径，但是一般只有一到两条强度最强，在传播中起主导作用的主导传播路径。路径损耗计算时只需计算主导传播路径的损耗即可。免费论文。
3.2 垂直切面的传播损耗 相对于水平切面的传播损耗，垂直切面的传播损耗计算要简单一些，计算垂直切面的传播损耗时，需要首先确定发射源与接收点之间的垂直传播路径，然后计算其中各个刀锋衍射损耗，其路径损耗为各刀锋衍射损耗之和。
3.3 射线跟踪模型简要结论 根据射线跟踪模型的理论以及相关资料，可以得到射线跟踪模型的简要结论如下：
1.对近距离的场强预测， 水平切面算法（2D射线跟踪算法）起主导作用。
2.全3D方向算法中全3D路径（即第三类路径）对远距离的场强预测准确性影响很大。
3.在整齐规划的建筑群中，对远距离的场强预测，垂直切面算法可取代全3D方向算法。
四、射线跟踪模型的应用 本节主要以WaveCall公司的WaveSight射线跟踪模型为例，对射线跟踪模型的应用进行说明。
WaveCall公司的WaveSight射线跟踪模型作为AIRCOM公司的规划软件Enterprise的插件，可用于高精度的规划方案仿真验证。该模型基于标准衍射理论及射线跟踪算法，综合考虑电波传播范围内建筑物的轮廓、高度、地形剖面图，对电波的传播特性进行准确预测。
WaveSight模型是一种3D射线跟踪模型，该模型包括两种类型路径：水平切面路径以及垂直切面路径。
对比传统射线跟踪模型，WaveSight 具有优点十分明显：首先，WaveSight射线跟踪模型采用了不同于传统射线跟踪模型的算法，空前地提高了计算效率：该模型完成一个基站的覆盖预测所需时间仅是传统射线跟踪模型所需时间的1/3左右，不仅保证了覆盖预测的精度，同时还保证了覆盖预测的速度。此外，WaveSight 模型使用简单，该模型不需要使用测试数据对其进行调校，仅需要输入两个参数：使用频率及接收端高度。
WaveSight 射线跟踪模型的缺点是：仅适用于市区环境，对电子地图精度要求较高，不仅要求地图精度必须达到5m 以上，而且要求提供建筑物矢量信息以及高度信息。
五、结论及后续工作 本文首先对射线跟踪模型的原理进行探讨，然后给出射线跟踪模型的简要结论，最后以WaveCall公司的WaveSight模型为例说明射线跟踪模型的应用方法。其结果有助于应用射线跟踪模型对规划方案进行精确验证，对规划工作有积极的参考和指导作用。
今后研究工作可以再上述研究基础上进一步展开，对全3D射线跟踪算法进行进一步的探讨，同时也可以对其它射线跟踪模型如WinProp模型等进行研究，
进一步研究射线跟踪传播模型算法，更精确地城市CBD区域进行预测，指导网络的规划及优化工作。
【参考文献】
1．WaveCall公司；《WaveCallPropagationWhitePaper》；2001
中图分类号：P208 文献标识码：A 文章编号：1007-9599 （2013） 02-0000-02
1 概述
物流产业随着基础工业的不断壮大及消费市场的蓬勃发展而快速兴起。而中国的物流企业不论从技术装备还是管理水平与国外仍存在较大差距，概括起来有一下几个方面：对现代物流理念上的差距，企业规模方面的差距，社会需求方面的差距，管理体制方面的差距，专业手段方面的差距，专门人才方面的差距。据对美国物流业的统计与分析，以运输为主的物流企业年平均资产回报率为8.3%（irr），仓储为7.1%，综合服务为14.8%。在中国大部分物流企业的年平均资产回报率仅为1%。这一数据，不仅说明了中国物流效率低下，同时企业仍有很大的空间通过物流来降低成本。
如何应用先进的技术手段来提高物流业的经营效率，及时高效、经济地将商品配送到客户手中，成了大家探讨的话题，这也就是现代物流领域中备受关注的车辆路径问题（vehicle routing problem，VRP）。物流配送路径规划的优化与否，对物流配送效率、费用和服务水平影响较大。而此类问题都涉及如何处理大量的空间数据与属性数据而缩短物流时间、降低成本的问题。
地理信息系统作为不仅具有对空间和属性数据采集、处理和显示功能，而且可为系统用户进行预测，监测、规划管理和决策提供科学依据。它可以有效的结合最优路径、各种VRP模型、车辆行驶成本等要素，在可视化分析以及物流规划路径分析等方面具有不可替代的作用。GIS技术与现代物流工程技术相结合，给现代物流行业提供了巨大的发展空间，为物流企业完善管理手段、减低管理成本、提高经济效益、最终提升核心竞争力提供了机遇。
2 技术实现途径研究
物流配送车辆路线优化问题由Dautzig和Ramser于1959年首次提出，该问题一般定义为：对一系列给定的顾客（取货点或送货点），确定适当的配送车辆行驶路线，使其从配送中心出发，有序地通过它们，最后返回配送中心。并在满足一定的约束条件下（如车辆容量限制、顾客需求量、交发货时间等），达到一定的目标（如路程最短、费用最少等）。配送中心的每次配送活动通常面对多个非固定用户，并且这些用户分布在不同的地点，同时他们的配送时间和配送数量也都不尽相同。如果配送中心不合理规划车辆、货物的运输路线，常会影响了配送服务水平，还会造成运输成本的上升，因此对车辆及货物的配送路线进行规划是配送中心的一项重要工作。
车辆路线优化问题一般可根据空间特性和时间特性分为车辆路线规划问题和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆线路或车辆路径规划问题（VRP）。当考虑时间要求安排运输线路时称为车辆调度问题（VSP）。本文不考虑时间要求，主要针对第一类VRP问题，提出相应的技术实现方案研究。
典型的VRP具有以下特征：（1）所有车辆从仓库出发，并最终回到仓库；（2）所有车辆必须满足一定的约束；（3）多辆车负责多个客户；（4）每个客户由一辆车访问一次；（5）车辆的路线上可以取送货。目前研究的车辆路线规划的模型主要有两类，一类为网络图模型，另一类为数学模型。由于VRP难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。
物流公司的业务一般具有配送范围广的特点，本文主要针对大范围跨省配送的案例进行智能路径规划，因此影响因素较多，主要包括：（1）大范围、跨省的配送交通网络图；（2）复杂的车辆运作规则，包括运行时间、运载能力、运行成本计算、驾驶员工作时间限制等；（3）复杂的道路选择优先级；（4）复杂的运输车辆优先级；（5）客户订单及运输车辆数据；（6）取货及分发过程；（7）繁杂的配送规则，如仓库、货物、客户的时间等；（8）运输车辆的重复利用，要求同一辆车在符合多个约束条件下尽可能多的参与到不同路线的配送中。
本文主要基于ArcObjects的网络分析和地图展示等组件进行二次开发，同时对其提供的车辆路径规划算法进行了拓展性研究。
3 功能模块设计方案
3.1 软件架构设计
系统建设遵循SOA架构，由数据资源层、组件层、服务层和表现层组成。数据资源层包括各种数据库、关系型数据库和空间数据库引擎ArcSDE，实现对物流业务数据的存储和管理；组件层包括接口协议、GIS组件、其他中间件；服务层实现计算功能，接受表现层的请求进行计算；表现层采用多种形式展现分析结果。
3.2 软件功能设计
本系统是物流业务管理系统的一部分，主要提供历史数据管理模块、线路优化分析模块、地图操作模块，同时提供与其他相关业务系统的扩展功能。
（1）线路优化分析模块
线路优化分析模块是系统的关键，提供两种分析结果：一种是基于AO自带的网络分析模块设计，计算分析结果；另一种是历次根据具体路况等信息的实际调度结果。
实际调度结果来自车辆GPS监控数据，并将实际调度结果作为输入，用来校正线路优化分析方法，最后生成最优路径规划。
（2）地图展示模块
地图展示模块，在配送交通网络图上展示道路基本信息、周边环境、仓库及客户地点、车辆位置信息等。同时将各种车辆路径规划分析结果以地图形式展示。基于ArcGIS提供的基础地图操作功能，实现地图缩放、浏览、鹰眼、图层控制、测量、选择、标注、信息查询等功能。
（3）历史数据管理模块
历史数据管理主要存储历史客户订单数据、实时路况信息、历史路径规划分析结果、实际运输路径等，可支持对历史数据的查询和修改。
（4）扩展功能模块
提供与其他相关业务系统、车载GPS设备、车辆监控设备等的接口，便于系统的扩展。
3.4 数据库设计
本系统中涉及的数据库主要包括元数据库、基础地理空间数据库、业务数据库、分析模型数据库、历史数据库等。
4 结束语
本文将物流车辆路径规划理论算法的研究与地理信息系统的网络分析模块相结合，经过二次开发，形成了用于实际的物流车辆路径规划信息系统。另外车辆路径规划设计约束较多，本文中不考虑时间要求，仅根据空间位置安排车辆的线路，同时不考虑装箱问题。
车辆路径规划问题是现代物流业的热点问题，但是基本停留在理论算法层面，随着技术的不断进步，必然出现考虑更多约束的先进算法，希望将这些算法真正与现代物流业结合，那将会是一个跨越式的进步。
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）32-0190-04
Design and Implementation of Order Routing System Based on iOS
XU Jing-hui
（North China University of Technology， Beijing 100144， China）
Abstract： The routing problem of multi-warehouse and multi-distribution task in order distribution has the characteristics of picking from the warehouse and returning to the starting warehouse after completing the delivery task by multiple distribution points. In view of the current path planning applications on the mobile platform to solve the known starting point to the end of the route planning， after a number of points along the planning has not yet been a good application to achieve. Therefore， this paper combines the path planning and iOS platform to make full use of the characteristics of electronic map application， design and implement the order routing system based on iOS in order to provide the optimal path results. This paper focuses on how to realize the function of map display and operation， map location， mark drawing， route planning and so on. Finally， using the real order data of inventory management platform， the test proves the effectiveness and convenience of the system.
Key words： route plan； multi-warehouse multi-distribution tasks； iOS； digital map； optimal path
在实际订单配送环节中，路径规划要求找出车辆从仓库取货出发依次经过一系列配送点后返回仓库的最短回路路径。目前关于路径规划的研究多数集中在常见路径算法的改进及优化方面[1-3]，对于路径规划应用系统的研究还较少。国内iOS平台上有关路径规划的热门应用有高德地图、百度地图等App，但它们也只提供了支持公交、驾车及步行三种出行方式的点到点的路径规划，对于从起点经过多个沿途点到达终点的路线规划并未涉及。鉴于目前尚未有将路径规划与iOS移动平台的应用特点充分相结合的应用，本文就设计开发了iOS平台上基于电子地图的路径规划系统――称之为“易配送系统”。易配送系统可在用户使用期间自动定位用户当前所在位置，同时提供仓库到各配送点的路线规划和导航等主要功能，还通过服务端的接口服务将数据封装成XML编码格式通过网络提供给客户端，保障了订单数据的真实性与实时性。在系统开发过程中利用高德iOS地图SDK进行应用开发，提供了可视化的路径规划人机交互界面。
本文的内容首先对iOS平台开发相关技术进行了简要介绍，然后对订单配送路径规划系统进行分析，设计出了整体的技术方案与系统架构，然后对系统功能进行详细实现，包括仓库、订单查询，地图位置显示、路线规划及导航等功能，最后进行结果分析与总结。
1 iOS开发平台介绍
1.1 iOS系统架构
iOS平台应用的开发语言主要有Objective-C和Swift语言，由于swift作为一门新生语言使用人数较少的原因，本系统采用了主流开发语言Objective-C进行编码开发。Objective-C作ANSI C的超集[4]，不仅扩展了面向对象设计的能力，如类、消息、继承，同时它可以调用C的函数，也可以通过C++对象访问方法，具有对C和C++语言的兼容性。
苹果公司最新推出的iOS 10 SDK （Software Development Kit， 软件开发工具包）增加了新的API （Application Programming Interface， 应用程序编程接口）和服务，能够支持更多新类型的应用程序和功能。目前基于iOS平台开发的应用程序可以扩展到消息、Siri、电话和地图等系统自带服务，拥有了更吸引人的功能。图1为iOS系统架构图：
图中可触摸层主要提供用户交互相关的服务如界面控件、事件管理、通知中心、地图，包含以下框架：UIKit、Notification Center、MapKit等；媒体层主要提供图像引擎、音频引擎及视频引擎框架；核心服务层为程序提供基础的系统服务如网络访问、浏览器引擎、定位、文件访问、数据库访问等。最底层的核心系统层为上层结构提供了最基础的服务包括操作系统内核服务、本地认证、安全、加速等。
1.2 iOS 地图SDK
iOS 地图SDK 是高德提供的一套基于 iOS 6.0.0 及以上版本的地图应用程序开发接口，供开发者在iOS应用中加入地图相关的功能[6]。它提供的四种地图模式包括：标准地图、卫星地图、夜景模式地图和导航模式地图。开发者不仅可以利用其地图计算工具实现坐标转换和距离或面积计算，而且可以调用API完成出行路线规划及点标注、折线、面的绘制等工作。这些实现的提前需要注册并认证成为高德开发者，接着为应用申请APIKey，然后将iOS地图SDK配置到应用工程中，这里可以采用手动和自动化两种配置方式。前者的配置过程简单易操作，但更新操作代价大，后者配置过程稍显负杂，但更新很方便。手动配置的方式则需要手动向工程项目中导入MAMapKit.framework和AMapSearchKit. framework两个包，当框架有更新时需将工程中旧框架删除并添加新框架，其使用稍显麻烦。本系统的实现采用了自动化配置工程的方式，利用第三方库管理工具CocoaPods通过命令：pod ‘AMap3DMap’， ‘～>4.0’和pod ‘AMapSearch’， ‘～>4.0’完成自动导入框架的目的，当框架更新时只需执行pod update即可实现项目中框架的更新。
2 整体方案设计
通常App功能复杂的情况下需要有后台服务器的业务处理支持，本文涉及的路径规划功能需要处理的计算量会随着配送点个数的增长呈指数阶上升，因此需要后台服务器的强大计算能力处理路径规划结果，进而减轻客户端内存使用压力。
本系统整体技术方案的设计综合考虑了移动应用端、服务端（包括应用服务器和提供商服务器）以及数据库服务器三部分所涉及的技术及其简要的功能模块划分，如下图2所示：
其中应用服务端是典型的电商进销存管理系统，移动端LBS应用――易配送App的实现需要在进销存Web系统的表示层、业务逻辑层、数据持久层添加相应的订单配送接口，该接口将服务端经过处理的数据结果封装成XML标准的数据格式通过HTTP协议传输给App。
3 基于iOS的路径规划App设计
3.1 App开发模式
易配送App采用Objective-C开发语言，开发工具为Xcode7.0，主要针对iPhone进行设计的。系统的设计模式采用了MVC范型如图3。由于系统所涉及的内容数据均通过网络请求服务器实时更新获取，故采用了iOS App开发模式中的Native App，以保证有较好的网络环境以及节省的带宽，以便利用充分的设备资源来提供良好的交互体验。
该系统平台中的位置信息主要体现在：位置服务和地图。位置服务是由Core Location框架负责，它将用户的位置及方向信息以Objective-C语言能识别的形式罗列出来[4]；地图服务通过应用中集成的高德开发平台提供的MAMapKit框架负责，利用它可以展示出地图和图钉标注等信息。易配送App的路径规划模块有效地将Core Location框架和MAMapKit框架结合起来，以实现地图定位、距离测试、路线显示及导航功能。
3.2 重要功能设计及关键技术实现
系统的主界面设计采用了图文结合的布局方式如图4，使用户能够快速便捷的操作系统。对于信息查询类似功能的界面多采用表视图结构，得到了清楚地展示大量内容信息的效果如图5所展示的待配送订单列表。
图4 主界面 图5 待配送列表
图6 路径规划
系统主要的路径规划功能在电子地图的地理信息背景下完成了标注及路线可视化如图6所示，其关键技术的实现如下：
1）初始化地图服务
系统中地图服务的使用首先需要初始化地图控件，这需要在创建MAMapView之前需要先绑定APIKey：[MAMapServices sharedServices].apiKey = APIKey； 和[AMapSearchServices sharedServices].apiKey = APIKey；接着初始化MAMapView地图控件：_mapView = [[MAMapView alloc] initWithFrame： self.view. frame]；并o系统添加地图视图：[self.view addSubview：_mapView]；
2）分组待配送订单
因为业务要求需要将待配送订单按各自对应的出货仓库进行分组配送，系统中通过自定义实现分组方法：-（void）groupAction：（NSMutableArray *）array； 其中参数array中存储着多个配送单对象XJDeliveryOrder。方法实现中利用可变的集合对象NSMutableSet保存的内容对象不重复的特性，用_warehouseSet记录不同的仓库信息：_warehouseSet = [NSMutableSet set]； [array enumerateObjectsUsing Block： ^（ XJDeliveryOrder * _Nonnull order， NSUInteger idx， BOOL * _Nonnull stop） {[_warehouseSet addObject：order.warehouseName]； }]； 同时该方法中利用谓词NSPredicate过滤数组array实现按仓库名称分组：[_warehouseSet enumerateObjectsUsingBlock：^（NSString * _Nonnull warehouseName， BOOL * _Nonnull stop） {NSPredicate *predicate = [NSPredicate predicateWithFormat： @"warehouseName = %@"， warehouseName]；NSArray *tempArr = [NSArray arrayWithArray：[array filteredArrayUsingPredicate：predicate]]； [groupArr addObject： tempArr]；}]；
3）添加标注及气泡视图
给地图添加标注需要调用地理编码请求：[self.search AMapGeocodeSearch： geo]； 其中对象geo为AMapGeocodeSearchRequest类对象且其属性值address不为空，该请求会回调AMapSearchDelegate中的方法：- （void）onGeocodeSearchDone： （AMapGeocodeSearchRequest*）request response：（AMapGeocodeSearchResponse *） response；其中response对象中包含了经纬度信息并且该方法中调用了添加标注方法：[_mapView addAnnotation：pointAn]；其中对象pointAn为MAPointAnnotation类对象。
实现触摸标注弹出气泡的效果需要实现MAMapViewDelegate委托中-（MAAnnotationView*）mapView：（MAMapView*）mapViewviewForAnnotaion： （id< MAAnotation>）annotation；和-（void）mapView：（MAMapView*）mapView didSelect AnnotationView：（MAAnnotationView *）view；方法。
4）路径规划及绘制路线
iOS地图API提供了按参数顺序进行路径规划的方法：[_search AMapDriving RouteSearch：request]；其中request为AMapDrivingRouteSearchRequ -est对象，需要给定request的属性：起点origin、终点destination和沿途点waypoints的值。而对于最优路径的规划只能通过自定义方法：-（void）planBestPaths WithLoaction：（CLLocationCoordinate2D）location wayPoints： （NSArray*） wayPoints；该方法中调用了网络请求服务器方法，并能够获取服务器返回的处理结果，其结果中包含了多个经纬度字符串，需要利用方法- （CLLocationCoordinate2D *）coordinatesForString：（NSString*）string coordinateCount：（NSUInteger *）coordinate Count parseToken：（NSString *）token；来解析经纬度，然后系统利用解析得到的经纬度调用[MAPolyline polylineWithCoordinates：coordinates count：count]来绘制路线。
5）最优路径算法
本系统的服务端路径规划接口实现中采用了适合解决单回路最短路径问题的算法――最近c插入算法。最近插入法是一种启发式算法，它不仅适用于各种复杂的TSP问题，对于中小规模问题同样适用。图7为算法具体流程。算法的实现是在后台服务端通过java语言实现的，这里就不做详细说明了。
4 系统测评与应用实例
为了对系统的功能及路径优化效果进行测试，采用了如下的实验环境：客户端是所有系统为iOS 7.0及以上iPhone手机，安装App后即可使用；服务端为可安装运行在windows平台下的进销存管理系统；数据库为Oracle数据库安装在Linux数据库服务器上。
本系统中路径规划功能的实现采用了将多个仓库多配送点的路径规划分解为多个单仓库多点配送的思想。下面一系列图示说明了多个单仓库出发到多个配送点的路径规划对比结果。
图8中显示当天需要规划路径的所有点，包括三个仓库和八个客户位置。接下来分别对三个仓库进行出货配送安排，如图9为从总仓库出发的配送路线对比，其中上图为按下单顺序依次配送的路线图，下图为根据与出发仓库距离由近到远的依次配送的路线图，从图中可以明显看出两者各自的路程代价，表1为各仓库配送路径的对比结果。
通过实验测试结果表明，当单次规划的配送数量小于等于6时，本系统的最优路径准确且计算处理很快，几乎网络无延迟。当单次规划的配送数量大于6小于17时，优化结果准确但是处理速度变慢，并且处理响应时间虽配送数量呈现指数阶增长。当单次规划的配送数量大于16时，服务端需通过一定路径优化算法处理大规模计算，但其结果往往是最优解的近似值而非最优路径值。
5 结束语
本文是在iOS系统上基于电子地图的应用开发，基本实现了小规模订单配送的路径规划功能。经过优化的路径的确节省了许多里程，真正意义上为企业提高了效益。但是本系统还存在一些不足之处，如适合处理小规模订单配送路径规划的局限性，系统的可扩展性有待加强。在今后的学习和研究中，将进一步深化和扩展该应用的功能，提供更加丰富的视图信息和交互方式，实现更良好的路径规划体验。
参考文献：
[1] WANG Tiejun，WU Kaijun. Study multi-depots vehicle routing based on improve -ed particle swarm optimization[J]. Computer Engineering and Applications，2013， 49（2）： 5-8.
[2] 马建华，房勇，袁杰.多车场多车型最快完成车辆路径问题的变异蚁群算法[J].系统工程理论与实践，2011（8）.
[3] 李波，邱红艳.基于双层模糊聚类的多车场车辆路径遗传算法[J].计算机工程与应用，2014（5）.
中图分类号:TP312文献标识码:A文章编号:1009-3044(2010)09-2132-02
Application of C-W Algorithm in Logistics Distribution Vehicle Scheduling
CAO Jing-xia1,2
(1.School of Information Engineering, Jiangnan University, Wuxi 2141222, China; 2.Jiangyin Polytechnic College, Jiangyin 214400, China)
Abstract: Logistics Distribution Vehicle Scheduling is a very crucial step in the process of logistic distribution. This paper briefly describes the most representative algorithm, points out that the heuristic algorithm is the main method to solve vehicle routing problem, and demonstrates its applicability to solving the problem of vehicle scheduling by citing the examples of C-W algorithm, a typical method among the heuristic algorithm.
Key words: C-W algorithm; delivery vehicle scheduling; heuristic algorithm
随着我国市场经济的建立和发展,作为“第三利润源泉”的物流日益受到政府有关部门和广大企业的重视,成为当前最重要的竞争领域。配送是物流活动中直接与消费者相连的环节,在物流的各项成本中,配送成本占了相当高的比例。配送车辆调度的合理与否对配送速度、成本、效益影响很大,采用科学、合理的方法来进行配送车辆调度,是物流配送中非常关键的一环。
1 物流配送车辆路径问题(VRP) 概述
物流配送车辆路径问题(Vehicle Routing Problem ,VRP) 最早是由Dantzig 和Ramser于1959年提出的,一经提出立即引起了运筹学、物流科学、计算机应用等学科专家和运输问题制定和管理者的极大关注。
该问题的研究目标是对一系列的顾客需求点设计适当的路线,使车辆有序地通过它们,在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下, 达到一定的优化目标(如里程最短、费用最少、时间尽量少、车队规模尽量小、车辆利用率尽量高等)。
2 VRP问题的求解算法
VRP问题是组合优化领域著名的NP难题之一,即随着客户数量的增加,可选的配送路径方案数量将以指数速度急剧增长,即出现组合爆炸现象,因此通常的做法就是应用相关技术将问题分解或者转化为一个或者多个已经研究过的基本问题,再使用相对比较成熟的基本理论和方法求解。VRP问题的求解方法基本上可以分为精确算法和启发式算法两大类。
2.1 求解VRP问题的精确算法
求解VRP问题的精确算法主要运用线性规划、整数规划、非线性规划等数学规划技术来描述物流系统的数量关系,以便求得最优解。求解VRP问题常用的精确算法有分枝定界法、割平面法、动态规划法、网络流算法等。这些方法从理论上给出了VRP问题精确求法,在可以求解的情况下,其解通常要优于启发式算法。由于精确算法在求解时引入了严格的数学方法(手段),因而无法避开指数爆炸问题,使其获得整个系统的最优解越来越困难,因此,这些算法都是针对某一特定问题设计的, 适用能力较差, 在实际中其应用范围很有限。
2.2 求解VRP问题的启发式算法
为了克服精确算法的不足,可以运用一些经验法则来降低优化模型的数学精确程度,并通过模仿人的跟踪校正过程来求取运输系统的满意解,为此专家们主要把精力花在构造高质量的启发式算法上。启发式算法能同时满足详细描绘和求解问题的需要,较精确式算法更加实用。
目前己经提出的启发式算法很多,按照Cesar Reg的分类法,基本可以分为构造启发式算法(节约算法、最邻近法、插入法、扫描法)、两阶段启发式算法、不完全优化算法和智能化启发式算法(禁忌搜索算法、模拟退火法、遗传算法、神经网络算法、蚁群算法、微粒群算法等)四类。启发式算法中由Clarke 和Wright 在1964 年提出的节约法(简记为C-W算法)具有非常典型的代表性。
3 C-W算法的应用
3.1 定义与原理
C-W算法是根据物流中心的运输能力和物流中心到各送/ 取货点以及各个送/ 取货点之间的距离,制订使总的车辆运输吨公里数(或者时间或者费用)最小的方案。
C-W算法的基本思路如图1所示,已知P点为配送中心,它分别向用户A 和B送货。设P点到用户A 和用户B 的距离分别为a 和b。用户A 和用户B 之间的距离为c,现有两种送货方案,如图1(a)和(b)所示。
在图1(a)中配送距离为2(a+b);图1(b)中,配送距离为a+b+c。对比这两个方案,2(a+b)-(a+b+c)=a+b-c,很明显,由三角形的几何性质可知, 三角形中任意两条边的边长之和大于第三边的边长。即:a+b-c>0 。连接AB所得的节约量是a+b-c。
3.2 实例
为了使C-W算法体现较为明了,选取较典型的实例介绍。假设配送中心使用同类型的配送车(主要是装载量和容积相同),保证一条线路上各用户的货运量之和不大于车辆的载重量。
基本资料介绍:
现有6个用户(标号是1,…,6),各个用户的货运量是gi(吨)(i=1,…,6),这些用户由配送中心(标号是0)发出的载重量为8吨的车辆完成配送任务,要求最后的路线安排使总距离最小。具体数据见表1、表2。
首先,把各个点单独与配送中心相连,构建仅含一个点的初始路线,得到总的距离为:2*(40+60+75+90+200+100)=1130km
然后,连接两两用户到同一条线路上得到节约值(节约量公式a+b-c),节约值越大,说明两用户连在一起时运距减少的越多,如果是负值就不应该把两用户连在同一条线路上。
C-W算法解题步骤:
1)计算各用户之间的节约值(节约量公式a+b-c)
例如:连接用户1和用户2时,节约量=40+60-65=35
连接用户3和用户5时,节约量=75+200-50=225,类似可以得到其他,如表3。
2)按照从大到小的顺序排序,见表4。
表4 节约里程排序表
3)连接点对,见表5。
根据表,得到最后的路线安排如下:
0-3-5-6-0
0-1-2-4-0
比初始路线节约运距:230+225+50+35=540km
通过使用C-W算法,对配送线路进行组合以后,由原来的6条初始化线路,减少到2条组合线路, 运行距离从开始的1130km 缩短为590 km ,节约的里程相当可观。不难明白, 中国的物流行业是一座金山。只有不断进行物流管理和技术创新,提高物流效率, 才可能大幅降低整个业务成本。
参考文献:
[1] 李如姣.“节约里程法”在某物流公司配送中心的实际运用[J].科技咨询,2008(28):156-158.
中图分类号：TP393文献标识码：A文章编号：1009-3044(2011)21-5080-03
Research on Technology of Nodes Localization Based on Mobile Beacon for Wireless Sensor Network (WSN)
DING Hui, LI Bo-yong, AI Shu-liang
(Chenzhou Vocational and Technical College, Chenzhou 423000, China)
Abstract：Wireless sensor network has been used in many field. Nodes location of WSN has provided the basic information for many applications. Nodes location based on mobile beacon is one of the important research fields. Some basic principles and performance evaluating criterions of nodes localization based on mobile beacon for WSN are introduced. Some issues which need to be resolved in future are discussed.
Key words: wireless sensor network (WSN); mobile beacon; nodes localization
随着传感器技术、无线通信、微电子技术以及嵌入式计算等技术的发展，无线传感器网络(Wireless Sensor Network 简称WSN)得到了广泛应用，成为当今活跃的研究领域。无线传感器网络是新型的传感器网络，同时也是一个多学科交叉的领域，与当今主流无线网络技术一样，均使用802.15.4的标准，由具有感知能力、通信能力和计算能力的大量微型传感器节点组成，具有低成本、低功耗的优点和强大的数据获取和处理能力。
在无线传感器网络的众多应用中,如：国防军事、环境监测、交通管理、医疗卫生、目标跟踪、物流管理、入侵检测、交通流量监控和勘测应用等领域, 监测到事件之后需要确定事件发生的位置，信息融合后得到的相关数据信息如果不包含事件位置信息将毫无意义，只有带有标识位置信息的传感数据才有实际的意义。传感器节点自身的正确定位是提供事件位置信息的前提, 因此节点的精确定位基础而关键[1] 。
1 无线传感器网络节点定位的分类及基本方法
节点定位是指确定传感器节点的相对位置或绝对位置，节点所采集到的数据必须结合其在测量坐标系内的位置信息才有意义。人工部署传感节点和为所有节点安装GPS接收器都会受到成本、功耗、节点体积、扩展性等方面的限制，甚至在某些应用中是根本无法实现的。通常是为部分节点配置定位装置（如GPS接收器）或事先标定其准确位置，这些节点称为信标节点（也称锚节点），再利用信标节点的相关信息采用一定的机制与算法实现无线传感器网络节点的自身定位。目前人们提出了两类节点定位算法[2]：基于测量距离的定位算法与测量距离无关的定位算法。基于距离的定位方法首先使用测距技术测量相邻节点间的实际距离或方位，然后使用三边测量法、三角测量法、最小二乘估计法等方法进行定位。与测量距离无关的定位算法主要包括：APIT、质心算法、DV-Hop、Amorphous等。
1.1 基于无线传感器网络自身定位系统的分类[1,3-5]
1) 绝对定位与相对定位。绝对定位与物理定位类似，定位结果是一个坐标位置，如经纬度。而相对定位通常是以传感区域某点为参考，建立整个网络的相对坐标系统。
2) 物理定位与符号定位。经纬度就是物理位置；而某个节点在某街道的某门牌的建筑物内就是符号位置。一定条件下，物理定位和符号定位可以相互转换。与物理定位相比，符号定位在一些特定的应用场合更加便于使用。
3) 集中式计算与分布式计算定位。集中式计算是指把所需信息传送到某个中心节点，并在那里进行节点定位计算的方式；分布式计算是指依赖节点间的信息交换和协调，由节点自行计算的定位方式。
4) 移动信标与固定信标定位。移动信标节点是一类装备了GPS或其它定位装置的可移动节点，它在移动的过程中周期性自己的位置信息。基于移动信标的未知节点定位有很多优点，如定位成本低，容易达到很高的定位精度、可实现分布式定位计算、易于实现三维定位等。而固定信标节点是一类装备了GPS或其它定位装置的不可移动节点。
1.2 基于距离的节点坐标计算基本方法
待定位节点在获得与邻近信标节点的距离信息后，通常采用下列方法计算自身的位置[3]。
1) 三边测量法：利用网络中三个信标节点的位置坐标以及未知节点到这三个信标节点的距离，运用几何方法求出未知节点的坐标。
2) 三角测量法：利用网络中三个信标节点的位置坐标以及未知节点为角顶点角边分别为三个信标节点的角度，运用几何方法求出未知节点的坐标。
3) 最小二乘估计法：利用未知节点的相邻节点中的多个信标节点的位置坐标以及它们与未知节点的距离或角度，运用最小均方差估计方法求出未知节点的坐标。
1.3 常用的测距方法
1) 信号接收强度（RSSI）测距法
已知发射功率和天线接收增益，在接收节点测量信号接收功率，计算传播损耗，使用理论或经验的无线电传播模型由传播损耗计算出信源与接收者间的距离。通常使用下列对数-常态分布模型来计算节点间的距离[1]。
PL(d)=PL(d0)+10λ・log(d/d0)+X （1）
PL(d0)=32.44+10λ・log(d0)+ 10λ・log(f) （2）
RSSI=发射功率+天线增益-路径损耗(PL(d)) （3）
其中PL(d)[dB]是经过距离d后的路径损耗，X是平均值为0的高斯分布随机变数，其标准差取为4至10，λ为取衰减因子通常为2至3.5，f是频率，取d0=1(m)，这样根据上述3式可得节点间的距离。
2) 到达时间测距法
到达时间(TOA)技术通过测量信号传播时间来测量距离，若电波从信标节点到未知节点的传播时间为t，电波传播速度为c，则信标节点到未知节点的距离为t×c。
3) 时间差测距法
TDOA测距是通过测量两种不同信号到达未知节点的时间差，再根据两种信号传播速度来计算未知节点与信标节点之间的距离，通常采用电波和超声波组合。
4) 到达角定位法
到达角(AOA)定位法采用阵列天线或多个接收器组合来获取相邻节点所处位置的方向，从而构成从接收机到发射机的方位线。两条方位线的交点就是未知节点的位置。
1.4 典型非测距算法
基于距离测量和角度测量的定位算法的缺点是对专用硬件有一定的要求，从而使传感器节点成本和体积加大，限制了它的实用性。非测距的算法不需要测量未知节点到信标节点的距离，在成本和功耗方面比基于测距的定位方法具有一定的优势，但是精度相对不足。
1) DV－hop算法
为了避免对节点间距离的直接测量， Niculescu等人提出了DV－hop算法[3]。该算法基本思想是：用网络中节点的平均每跳距离和信标到待定位节点之间的跳数乘积来表示待定位节点到信标节点之间的距离，再用三角定位来获得待定位节点的位置坐标。
2) 质心法
质心法由南加州大学Nirupama Bulusu等学者提出[3]，该算法是未知节点以所有可收到信号的信标节点的几何质心作为自己的估计位置，它是一种基于网络连通性的室外节点定位算法。
3) APIT 算法
一个未知节点任选3个能够与之通信的信标节点构成一个三角形，并测试自身位置是在这个三角形内部还是在其外部；然后再选择另外3个信标节点进行同样的测试，直到穷尽所有的组合或者达到所需的精度。
4) Amorphous 算法
Amorphous 定位算法[3]采用与 DV-Hop 算法类似的方法获得距信标节点的跳数，称为梯度值。未知节点收集邻居节点的梯度值，计算关于某个信标节点的局部梯度平均值。Amorphous 算法假定预先知道网络的密度，然后离线计算网络的平均每跳距离，最后当获得3个或更多锚节点的梯度值后，未知节点计算与每个锚节点的距离，并使用三边测量法和最大似然估计法估算自身位置。
2 基于移动信标的无线传感器网络节点定位技术
无论是距离相关还是距离无关定位算法，常采用固定信标节点方式测量距离、相对角度、传播时间差及传播时间等进行节点定位[1]。通常参与定位的固定信标节点越多, 定位精度将越高。但是信标节点的成本远远高于普通节点，当定位工作完成后，信标节点将转成普通的传感器节点使用。因此信标点越多，布设整个网络的成本将会增大, 定位算法的计算负荷以及通讯负荷将会增大[1] ，过多的信标节点将会造成较大的浪费。所以利用移动节点发出的虚拟坐标点进行辅助定位的思想将成为节点定位研究的一个重要研究方向。
假定整个WSN由静止节点以及移动节点(如撒播节点完毕的飞机、运动的车辆、移动的小型机器人或普通的能移动的传感器节点等) 两种类型节点构成。根据传感器网络的规模大小, 可以配置一个或者多个移动节点。各移动节点均配置一个GPS接收器用于定位移动信标节点本身, 并有足够的能量自我移动或捆绑移动机器人、移动车辆或三维空间中的飞机等工具。移动节点在传感器区域内按照一定的运动路径移动, 并周期性地发送坐标位置信息, 待定位节点根据接收到的坐标信息与采用适当的定位算法完成定位[6] 。
近几年有一些研究者对移动锚节点路径规划展开研究，提出了一些比较好的路径规划方案。移动锚节点路径规划主要有两个目标：
1) 移动轨迹能够覆盖网络中的所有未知节点；
2) 为未知节点定位提供质量好的信标点。
如果满足网络节点均匀分布的条件，规划路径通常采用静态规划路径，移动锚节点都按照预先规划的路径移动，不具有根据节点分布状况灵活变化的性能。文献[7]针对移动锚节点的路径规划问题利用空间填充线理论提出了SCAN、DOUBLESCAN以及HILBERT路径规划方法，分别如图1、图2和图3所示。在节点通信距离小和空间填充线密度大的条件下， SCAN路径比HILBERT路径的定位结果准确。但是在节点通信距离大、空间填充线密度较小时，HILBERT路径明显优于SCAN路径。
SCAN路径存在明显的缺点就是提供了大量共线的信标点，HILBERT路径通过增加移动路径长度解决了信标点共线性的问题，只要达到一定的密度就可以为定位提供优质的不共线信标点。为了解决信标点存在共线性的问题，文献[8]提出了圆形规划路径和S形规划路径方法，如图4和图5所示。圆形规划路径完全覆盖方形网络区域时必须增加大圆路径，这很大程度增加了路径的长度。而圆形的直径非常大时，在局部带来了信标点的共线性问题。S形路径通过引入S形曲线代替直线，解决了信标点共线性问题。
而对于实际环境中节点非均匀分布的情况，文献[9]提出了提出了宽度优先和回溯式贪婪算法。这种方法能够根据网络信息自适应进行路径规划，规划路径不再是规则的图形，能够充分利用节点分布信息覆盖所有节点，保证路径最短，克服了静态路径规划的缺点。文献[10]提出让一个携带GPS的移动信标采用随机移动模型的方式尽量遍历传感区域，然后采用分布式算法为未知节点定位，该方法结合了基于测距方法的优点，并且无需布置固定的信标节点，节省了成本开销，但是由于移动信标的移动模型采用随机的方式，难以让其移动范围覆盖整个传感区域，从而有些未知节点无法定位。
3 定位算法的评价标准
定位算法设计的优劣通常以下列几个评价标准[11]来评价：
1）定位精度：一般用误差值与节点无线射程的比例表示，是定位技术首要的评价指标。
2）定位覆盖率：指利用定位算法能够进行定位的节点数与总的未知节点个数之比，它是评价定位算法的另外一个重要的指标。
3）信标节点密度：信标节点占所有节点的比例或者是单位区域内信标节点的数目。
4）节点密度：节点密度通常以网络的平均连通度来表示。
5）功耗：功耗是指传感器节点在单位时间内所消耗的能源的数量。由于传感器节点不会始终在工作的，有时候会处于休眠状态，但这同样也会消耗少量的能量，因此，传感器节点的功耗一般会有两个，一个是工作时的功耗，另一个是待机时的功耗。
6）成本：包括时间、空间和费用。时间指一个系统的安装、配置和定位所需的时间。空间包括一个定位系统或算法所需的基础设施和网络节点的数量、安装尺寸等。费用则包括实现某种定位系统或算法的基础设施、节点设备的总费用。
7）鲁棒性：定位系统和算法必须具有很强的容错性和自适应性，能够通过自身调整或重构纠正错误、适应环境、减小各种误差的影响，以提高定位精度。
上述的这些评价指标不仅是评价WSN自身定位系统和算法的标准，也是其设计和实现的优化目标。
4 结束语
使用移动信标节点来完成WSN所有节点的定位，就必须要足够的时间让移动信标节点遍历完整个网络, 为了减小所有节点定位所需的时间以及提高定位效率，如何进一步优化移动信标节点的运动路径将成为基于移动信标的WSN节点定位技术更研究的重要方向。
参考文献：
[1] 孙利民.无线传感器网络[M].北京:清华大学出版社,2005.
[2] A l-Karaki.JN, Kamal.AE. Routing Techniques in Wireless Sensor Networks: A Survey[J].In Wireless Communications,IEEE,Volume:11,Issue:6, Dec,2004:6-28.
[3] 王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-869.
[4] Kushwaha,M. Molnar,K. Sallai,J. Volgyesi, P. Maroti, M. Ledeczi, A. Sensor Node Localization Using Mobile Acoustic Beacons[C], In proc. 2005. IEEE International Conference on Mobile Adhoc and Sensor Systems Conference, Nov,2005.
[5] 倪巍,王宗欣.基于接收信号强度测量的室内定位算法[J].复旦学报(自然科学版),2004.43(1):72-76.
[6] Mihail L. Sichitiu ,Vaidyanathan Ramadurai. Localization of Wireless Sensor Networks with a Mobile Beacon[C].//IEEE 2004:174-182.
[7] Koutsonilas D, Das S M, Hu Y Charlie. Path Planning of mobile landmarks for localization in wireless sensor networks[J].Computer Communication.2007,30(13): 2577-259.
[8] Rui Huang,Zaruba Gergely V. Static Pathplanning for mobile beaeons to localize sensor networks[C] / /Proc of IEEE PerComW. Piscataway,NJ:IEEE，2007:323-330.
[9] Hongjun Li,Jianwen Wang,Xun Li and Hongxu Ma. Real-time Path Planning of Mobile Anchor Node in Localization for Wireless Sensor Networks[C].//Proeeedings of the 2008 IEEE International Conference on Information and Automation,Zhangjiajie,China,June,20-23,2008.
中图分类号：U116.2 文献标识码：A
Abstract： Vehicle routing problem is the core problem in logistics management and in the organization and optimization of transportation， and is a classic combinatorial optimization problem in operations research. This article systematically summarized the common classifications and the basic model of VRP problems. And through referring to scholars' research situation， summarized the commonly used and efficient heuristic algorithms of solving VRP problems and the present situation of the corresponding research. Finally， summarized the problems in the research of VRP problems and discussed the future research and the solving methods for VRP problems.
Key words： vehicle routing problem； heuristic algorithm； optimization
0 引 言
随着科技的进步和电子商务的飞速发展，作为国民经济中一个重要行业的物流产业已成为拉动国家经济发展与提高居民生活水平的重要动力源泉，而物流行业中的车辆路径问题（Vehicle Routing Problem， VRP）是制约物流行业发展的一个关键要素，其研究也受到人们的广泛关注。车辆路径问题是物流管理与运输组织优化中的核心问题之一，是指在满足一定的约束条件（如时间限制、车载容量限制、交通限制等）下，通过对一系列收货点与发货点客户合理安排行车路线，在客户的需求得到满足的前提下，达到配送车辆最少、配送时间最短、配送成本最低、配送路程最短等目标。该问题由Dantzig和Ramser[1]于1959年在优化亚特兰大炼油厂的运输路径问题时首次提出，现已成为运筹学中一类经典的组合优化问题，是典型的NP-难题。
企业通过选取恰当的配送路径，对运输车辆进行优化调度，可以明显提高配送效率，有效减少车辆的空驶率和行驶距离，降低运输成本，加快响应客户的速度从而提高客户服务质量，提高企业的核心竞争力。VRP作为物流系统优化环节中关键的一环，其研究成果已经应用到快递和报纸配送连锁商店线路优化以及城市绿化车线路优化等社会实际问题中，因而车辆路径问题的优化研究具有很好的现实意义。
1 车辆路径问题的分类与基本模型
VRP的构成要素通常包括车辆、客户点、货物、配送中心（车场）、道路网络、目标函数和约束条件等，根据侧重点的不同，VRP可以分为不同的类型。根据运输车辆载货状况分类可分为非满载车辆路径问题和满载车辆路径问题；根据任务特征可分为仅装货、仅卸货和装卸混合的车辆路径问题；根据优化目标的数量可分为单目标车辆路径问题和多目标车辆路径问题；根据配送车辆是否相同可分为同型车辆路径问题和异型车辆路径问题；根据客户对货物接收与发送有无时间窗约束可分为不带时间窗的车辆路径问题和带时间窗的车辆路径问题；根据客户需求是否可拆分可分为需求可拆分车辆路径问题和需求不可拆分车辆路径问题；根据客户是否优先可分为优先约束车辆路径问题和无优先约束车辆路径问题；根据配送与取货完成后车辆是否需要返回出发点可分为开放式车辆路径问题和闭合式车辆路径问题；还可以将上述两个或更多约束条件结合起来，构成一些更复杂的车辆路径问题。
由于VRP的约束条件不同引起了其分类多种多样，而不同类型的VRP其模型构造及求解算法有很大差别。VRP的一般数学模型为：
在上述模型中，式（1）表示目标函数，式（2）表示约束条件。其他VRP模型大致都是在此模型的基础上根据约束条件完善形成的。
2 VRP的求解算法与研究现状
VRP的求解方法，基本上可分为精确算法和启发式算法两大类。由于精确算法的计算难度与计算量随着客户点的增多呈指数级增加，在实际中应用范围有限，而启发式算法则具有全局搜索能力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分研究者们主要把精力集中在如何构造高质量的启发式算法上，本文也主要讨论一些近年来研究比较多的启发式优化算法。针对VRP问题目前已提出了大量的启发式算法，其中研究较多的主要包括以下算法：
2.1 遗传算法（Genetic Algorithm，GA）
GA是一种通过模拟生物进化过程来搜索最优解的方法，该方法通过对群体进行选择、交叉和变异等操作，产生代表新的解集的种群，根据个体适应度大小选择个体，通过迭代逐步使群体进化到近似最优解状态。但是该算法具有搜索速度慢、易早熟、总体可行解质量不高等缺点。
采用遗传算法研究VRP问题的研究现状包括：蒋波[2]设计了遗传算法求解以配送总成本最小为目标函数和带有惩罚函数的VRPTW模型；赵辰[3]基于遗传算法求解了从生产中心到仓库之间的路径优化问题，设计了配送路径优化决策；张群和颜瑞[4]建立了多配送中心、多车型车辆路径问题混合模型，并采用一种新的模糊遗传算法求解该问题。
2.2 模拟退火算法（Simulated Annealing，SA）
SA同禁忌搜索算法一样，也属于局部搜素算法，但是模拟退火算法是模仿金属加工中退火的过程，通过一个温度函数作为目标函数，使其趋于最小值，是一种基于概率的算法。
采用模拟退火算法研究VRP问题的研究现状包括：郎茂祥[5]研究了装卸混合车辆路径问题，并构造了模拟退火算法求解该问题；穆东等[6]提出了一种并行模拟退火算法，并将该算法的应用领域扩展到其他车辆路径问题和组合优化问题；魏江宁和夏唐斌[7]以模拟退火算法为基础，研究了单个集散点与多个客户之间的运输问题；Mirabi和Fatemi Ghomi等[8]提出了一种基于模拟退火思想的三步启发式算法求解最小化配送时间的多配送中心VRP模型。
2.3 蚁群算法（Ant Colony Optimization，ACO）
蚁群算法是人们受蚂蚁可以快速找到食物的自然现象启发提出的。蚁群算法所建立的机制，主要包括蚂蚁的记忆、蚂蚁利用信息素进行交互通信及蚂蚁的集群活动三个方面。单个蚂蚁缺乏智能，但整个蚁群则表现为一种有效的智能行为。通过这种群体智能行为建立的路径选择机制可使蚁群算法的搜索向最优解靠近。
采用蚁群算法研究VRP问题的研究现状包括：马建华等[9]研究了基于动态规划方法的多车场最快完成车辆路径问题的变异蚁群算法；辛颖[10]通过对MMAS蚁群算法进行了三种策略的改造，指出蚁群算法可以找到相对较好的解和很强的鲁棒性；陈迎欣[11]针对蚁群算法的缺点，分别对信息素更新策略、启发因子进行改进，引入搜索热区机制，有效解决车辆路径优化问题；段征宇等[12]通过最小成本的最邻近法生成蚁群算法和局部搜索操作设计了一种求解TDVRP问题的改进蚁群算法。
2.4 粒子群算法（Particle Swarm Optimization，PSO）
PSO算法是通过对鸟群觅食行为的研究而得出的一种群体并行优化算法，它从随机解出发，通过迭代寻找最优解。蚁群算法具有容易实现、收敛速度快、精度高等优点，在多种优化问题上均取得了较好的效果。但是由于PSO算法是通过粒子之间的相互作用来寻找最优解，缺乏像遗传算法那样的变异机制，因而PSO算法容易陷入局部最优。
采用粒子群算法研究VRP问题的研究现状包括：马炫等[13]提出了一种基于粒子交换原理的整数粒子更新方法求解有时间窗约束的车辆路径问题；吴耀华和张念志[14]以处理集货或送货非满载带时间窗车辆路径优化问题为背景，提出了带自调节机制的局部近邻粒子群算法解决VRP问题。
2.5 蝙蝠算法（Bat Algorithm，BA）
蝙蝠算法是剑桥大学学者Yang[15]于2010年提出的一种新型群智能进化算法，模拟自然界中蝙蝠通过超声波搜索、捕食猎物的生物学特性，是一种基于种群的随机寻优算法。截至目前，蝙蝠算法主要用于求解连续域的函数优化问题，只有少数学者将其用来求解离散型问题，具有很好的研究前景。
采用蝙蝠算法研究VRP问题的研究现状包括：马祥丽等[16]将蝙蝠算法应用于求解VRP问题，在蝙蝠速度更新公式中引入了惯性权重，对基本蝙蝠算法进行了改进，克服了基本蝙蝠算法的不足之处；马祥丽等[16]针对VRPTW问题的具体特性重新定义了蝙蝠算法的操作算子，设计了求解VRPTW 问题的蝙蝠算法，并采用罚函数的方式对目标函数进行了简化求解。
3 总结与展望
车辆路径问题由于约束条件的不同其分类多种多样，数学模型与求解算法也层出不穷。本文总结了近几年一些相关学者对VRP问题的研究和求解算法，通过较为系统地总结VRP问题，本文总结出以下当前研究存在的问题和今后可能的研究方向：
（1）研究目标太过理想化。目前学者研究VRP的研究过于注重成本最小和路径最短，大部分是单目标优化，而在实际应用中，配送的驾驶员也可能会因许多原因耽误计划的行程，顾客的需求各异甚至冲突，顾客满意度与企业成本最小化目标之间存在效益悖反的矛盾。今后的研究可以将成本、路程、驾驶员休息、顾客满意度等多个目标联合起来进行研究，并可以通过线性加权的方式进行综合求解。
（2）单个约束的VRP问题由于研究时间较长，现在已经研究的较为成熟，而且其应用局限也比较大，应该考虑将多个约束条件结合起来，建立符合实际的多约束条件的车辆路径问题，更好地解决企业的配送优化。
（3）虽然启发式算法具有全局搜索能力强，运算方便等优点，但是也存在着局部搜索能力差、收敛时间过长、易陷于局部最优等问题。使用单一的群智能算法不是求解VRP的最有效算法，将两种和多种群智能算法结合起来研究车辆路径问题，取长补短，是今后应该考虑的问题；同时，应考虑寻求更多的智能优化算法来求解VRP问题。
参考文献：
[1] GB. Dantzig， JK. Ramser. The truck dispatching problem[J]. Management Science， 1959，6（1）：80-91.
[2] 蒋波. 基于遗传算法的带时间窗车辆路径优化问题研究[D]. 北京：北京交通大学（硕士学位论文），2010.
[3] 赵辰. 基于遗传算法的车辆路径优化问题研究[D]. 天津：天津大学（硕士学位论文），2012.
[4] 张群，颜瑞. 基于改进遗传算法的混合车辆路径问题[J]. 中国管理科学，2012，20（2）：121-128.
[5] 郎茂祥. 装卸混合车辆路径问题的模拟退火算法研究[J]. 系统工程学报，2005，20（5）：485-491.
[6] 穆东，王超，王胜春，等. 基于并行模拟退火算法求解时间依懒型车辆路径问题[J]. 计算机集成制造系统，2015，21（6）：1626
-1636.
[7] 魏江宁，夏唐斌. 基于混合模拟退火算法的多阶段库存路径问题研究[J]. 工业工程与管理，2015，20（3）：1-8.
[8] M Mirabi， SMTF Ghomi， F Jolai. Efficent stochastic hybrid heuristics for the multi-depot vehicle routing problem[J]. Robotics and Computer-Integrated Manufacturing， 2010，26（6）：564-569.
[9] 马建华，房勇，袁杰. 多车场多车型最快完成车辆路径问题的变异蚁群算法[J]. 系统工程理论与实践，2011，31（8）：1508
-1516.
[10] 辛颖. 基于蚁群算法的车辆路径规划问题求解研究[D]. 长春：吉林大学（硕士学位论文），2015.
[11] 陈迎欣. 基于改进蚁群算法的车辆路径优化问题研究[J]. 计算机应用研究，2012，29（6）：2031-2034.
[12] 段征宇，杨东援，王上. 时间依赖型车辆路径问题的一种改进蚁群算法[J]. 控制理论与应用，2010，27（11）：1557-1563.
[13] 马炫，彭M，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法[J]. 计算机工程与应用，2009，45（27）：200-204.
[14] 吴耀华，张念志. 带时间窗车辆路径问题的改进粒子群算法研究[J]. 计算机工程与应用，2010，46（15）：230-235.
