时间：2023-03-01 16:32:11
序论：速发表网结合其深厚的文秘经验，特别为您筛选了11篇路径规划范文。如果您需要更多原创资料，欢迎随时与我们的客服老师联系，希望您能从中汲取灵感和知识！
一、哪些内容是课题研究过程设计时需要考虑的？
所谓课题研究过程，是指为完成课题研究工作而经历的程序、阶段。课题研究的过程设计，也就是指研究者根据一定的研究内容和研究目标，对课题研究活动作出安排的预设程序。它是课题研究方案的重要组成部分，既是对研究内容、研究阶段、研究方法、研究成员等诸多要素进行分析与思考的结果，更是一个根据研究假设调动各类资源进行实践的过程。
研究内容往往是课题研究过程设计的基本依据。不同的内容，其研究程序也是有所区别的。如课题“小学生家庭作业习惯调查及对策研究”，其研究程序一般先要有相应的现状调查，然后根据调查了解到的问题设计针对性的策略，再通过实践尝试，检验预设的策略是否有效解决了相应的问题，最后分析提炼相应的对策。又如“小学语文‘特色作业’设计研究”这个课题，在过程设计时则首先要对“特色作业”作一定的思考，分析其具备的特征，然后再进行相关设计、应用实践、分析提炼等。
研究阶段则是课题研究过程设计的重要内容，它首先涉及一个课题通过几个阶段的研究完成研究任务的问题，其次则需要考虑对具体的研究工作有大致时间上的确定。如上面提到的“小学生家庭作业习惯调查及对策研究”这一课题，一般分为现状调查、问题分析、对策思考、实践尝试、效果分析等阶段，且每前一阶段研究活动都是后一阶段研究活动的基础，后一阶段研究活动则是前一阶段研究活动的延续。
这里的研究方法不仅指严格意义上的研究方法，如调查法、观察法等，还包括在研究活动中采用的一些具体的操作策略，如问题设计、教学实践等。研究方法设计同样是研究过程设计中的一个重要组成部分。
研究过程设计除了受到以上三个方面的基本要素影响之外，其实有时也会受制于某个课题研究成员的影响。如有的课题涉及的部门较多，牵涉的人员也就比较多，此时，在研究过程设计中，需要对相关成员的任务作出相应的分配，目的是保证在研究活动具体展开时能够作出及时有效的协调。
二、怎样的过程设计才能保证课题研究工作的顺利进行？
从一个课题来看，其研究过程的设计一般可以从行动路径和研究策略两个方面来体现。其中行动路径是大方向，是对课题研究工作的整体把握;研究策略则是具体研究活动中的操作方法的总和。
（一）规划课题研究行动路径，细化各项研究任务
课题研究的行动路径是课题研究整体推进的重要基础，它是一个课题顺利开展研究工作的保障。行动路径一般包括三方面的内容：研究阶段及其说明、内容选择及其说明以及环节设计及其说明。可用图表的方式加以呈现，并配以一定的文字作解释。如《区域实施“绿色评价”的实践与研究》，将课题研究的行动路径作了如下表述：
在以上图例表述研究的行动路径基础上，又作了简要的说明：“理论学习，内涵理解”阶段，主要是通过学习国家、省、市的相关文件精神，切实把握中小学教育质量综合评价改革的核心思想，深入理解评价理念及内容的变化，明确教育评价改革的方向，为本区实施“绿色评价”奠定基础;“多部门联动，整体推进”阶段，结合各部门本身的职能，在基于综合素养评价理念背景下，实践教育质量综合评价过程，推进课题研究的深入;“梳理成果，总结推广”阶段，主要在策略性成果和对象性成果方面作较为完善的分析与提炼。
在以上的“行动路径”中，我们很明显地看出本课题研究分为三个阶段进行，且每个阶段的研究主体与研究任务都比较明确。因为有了清晰明确的“行动路径”设计，不但对整体课题的研究工作作出了整体规划，同时还有相应研究内容的分工与阶段性推进的计划，显然有利于课题研究人员在不同的研究阶段，落实好研究工作，而且还能对研究工作作出即时的反思与调整。
（二）想明白各个环节的研究方式，具化研究活动中的操作策略
课题研究过程的设计中，还有一块相当重要的内容，便是针对具体的研究内容与研究活动作出的策略设计、方法选择以及环节预设。这是课题研究过程中最为具体的工作，一般需要基于相应的研究内容进行思考与设计。
如我区有一位教师在研究“运用几何直观培养小学生解决问题能力的实践研究”这一课题时，针对“培养小学生运用几何直观解决问题能力”这样一个研究内容，提出了“数形结合，以数化形”“强调直观，以形析文”和“重视图例，突出关系” 这三种策略。并在每一种策略的具体阐述中，又通过一张流程图来表达策略的操作过程。
第一步是化境为数，经历从实际情境中抽象出数的过程，体验抽象。第二步是以数化形，经历将数转化成多种形的过程，体验演绎。第三步将形归数，经历多形中发现共同点的过程，体验归纳。三步流程使学生经历数（式）与形转化的过程，积累数形结合的基本活动经验，奠定运用几何直观解决问题的能力基础。以上研究策略设计，内容明确，路径清晰，有很强的可操作性，显然为后续研究活动的顺利开展奠定了扎实的基础。
又如一位幼儿教师在研究课题“幼儿园‘五乐游戏’活动的设计研究”时，提出了“乐运动、乐表达、乐交往、乐探究、乐表现”等五乐游戏后，于每一种游戏活动的研究中，设计了相当具体的操作策略――支架。如在“讲述类”游戏研究时，设计了如下的一个支架：
有了相应的支架，研究者也就有了具体的实践操作依据，后续研究实践活动也就有了“落地”的保证。
0 引 言
流通领域中,许多物流配送企业借助外部经济的发展,实现了规模扩张与快速发展,但对如何控制成本,提高运营效率的迫切性并不强。现在随着经营环境的变化,物流需求量更大,客户、网络更复杂,对服务的要求更多样化。但面临的竞争更加激烈,不管是从事跨区域配送还是城市配送,首先需要考虑顾客服务水平,赢得客户的认可,然后考虑配送运营的成本问题,因而如何创新物流服务,提高运营效率和控制日常运营成本成为每个配送企业需要时刻思考的问题。
传统的基于经验的方法,在企业规模有限,客户数量不是非常多,配送网络相对简单的情况下,只要员工和管理者技能过关,执行力好,都应该能够较好地完成配送任务,获得企业的发展。但是随着销售区域扩大,客户数量的不断增加,客户需求持续增长,配送业务量大增,配送周期缩短,配送线路更复杂,并且需求的随机性、变动性加大,光凭经验和手工安排,已无法做到配送计划的优化,必须借助于统计分析、利用数学模型和智能算法,才能获得较好的配送计划,节省时间,提高效率。本文就是针对这些问题,从企业应用的角度,提出先合理划分配送区域,再优化配送路线的方法,从而达到降低成本,提高竞争力的目标。
1 论文总体思路综述
排单和车辆调度是整个配送计划和作业实施的核心,是配送任务和客户服务按时完成的有力保证。
传统的订单排单和车辆调度、路线安排都是由公司里业务能手来完成,送货区域大了,客户多了,这项工作的效率和完成工作的成本控制都会不理想,现在常用的智能优化方法,把它作为一个典型的VSP问题,建立数学模型,利用智能化的算法,求解可行的配送路径规划,作为理论研究,这样的做法是有意义的。但是有两个问题:(1)这个模型数据的收集整理工作量特别大,计算过程也较长,因而成本不会低。(2)模型本身一定要适合实际的作业过程,这就需要有一个不断测试和优化的过程,并且还要适应每天的动态变化,否则反而会影响到日常的作业过程。许多研究理论完备、精深,但是在适应产业化运营时,工程上的可实现性还有待提高和完善。因而影响了这些很有价值的研究在企业实际中的运用。
本文的研究并不针对配送路径规划做理论上的深究,而是立足实际应用,在可接受的范围内,利用较简易实用的智能优化方法,在较短的时间内,以较低的成本获得相对优化的配送路径规划方案。不求最佳,但求有效。为今后电子排单和送货线路优化软件的开发和应用作必要的铺垫。
具体设想:第一步,利用聚类分析法对配送区域进行合理分区,先把复杂问题简单化。第二步,每个分区内就是个典型的TSP问题,有很成熟的解决办法。在平衡好各分区工作时间安排后,就能很快获得较理想的配送方案。
重点是第一步,分区时一定要考虑到客户位置、需求量、车辆载重、作业时间均衡限制等因素,需要花费好多功夫。
2 配送区域动态优化及其方法
2.1 配送区域的初始划分方法。配送区域优化方法对最终优化的结果有很大的影响,因而合理的划分方法的选择十分重要,目前常用的划分方法有扫描法和聚类算法,在配送客户有限、区域较小时运用扫描法就可以了,但是当客户数量很多,区域较大,又要考虑约束条件时,聚类算法就是我们必然的选择了,聚类算法中K- means比较成熟,操作简单,原理是:把大量d维(二维)数据对象n个聚集成k个聚类k 在运用聚类分析法时有几个问题要注意:第一,k的选择,以一天送货总量/单车载重量,也可以放宽一些,到:一天送货总量/单车载重量+1。第二,k个聚类内的密度,分区密度大,效率高,成本低。第三,每个分区内工作时间大体相当,这样便于运行的稳定,进行成本控制和人员、车辆的考核。第四,每个聚类间不重合。做到这样分区效果会比较好。
传统的K-means聚类法,k个聚类区内,初始点是随机产生的,运行时间长,收敛效果差。基于均衡化考虑,在配送对象分布不均匀时,用密度法效果较好,初始中心点以密度来定义,运用两点间欧氏距离方法,求解所有对象间的相互距离,并求平均数,用meanD表示,确定领域半径R,n是对象数目,coefR是半径调节系数,0 coefR=0.13时,效果最好。如果使用平均欧
氏距离还不理想,可增加距离长度,甚至用最大距离选择法,收敛速度比较快。 在配送对象分布较均匀时,可考虑用网格法,效果较好,整个配送区域划分用k=Q/q,k为初始点个数,假设k=mn,将地图划分成m行n列,以每格中心点为初始点,通过网格内的反复聚类运算,达到收敛,获得网格稳定的聚类中心。
2.2 分区内配送工作量的均衡。这样就完成了配送区域的初步划分,但是没有考虑各个分区内工作量的均衡问题,如果工作量不均衡,对于客户服务水平的保证,成本的控制,作业的安排,人员、车辆的考核都存在问题。
在实际的物流企业配送作业过程中,一般一辆车一天也就送货10多家或20来家,多余的时间要用于收款,与公司财务部门交账,核算出车相关费用,所以不考虑同一车同一天出车多次的情况,多次出车待以后深入探讨。那么就意味着每个分区就是一辆车一条线路,把问题大大简化了,需要说明的是:这种方法对于配送规模不是特别大的单个城市配送是适用的,也具有广泛性。
各分区内的每日配送工作量是以配送作业耗用时间来衡量的,耗用时间有两部分构成:(1)车辆行驶时间;(2)客户服务时间。由于配送分区有限,每个分区内的客户数量不是很多,可以采用实地测时的方式,把每条线路的配送时间统计出来,这是一种手工办法,但比较符合实际来调整超过差值的分区内的客户,从而使得各区作业时间基本均衡。
如果客户数量众多,分区也较复杂,就需要借助统计学方法,通过对样本线路车辆行驶时间以及服务时间,拟合出分区作业时间函数,然后,计算出所有线路作业时间,即使分区重新调整,线路重新组合,仍可以很快计算出线路作业时间。本文不在这个方面进行深入探讨。
2.3 重新组合客户,确定最终区域划分。观察各线路作业时间超过允许差值的部分,由大到小来调整,将离聚类中心最远的数据点弹出,使本区T值下降,直至在差值以内,将弹出点加入到临近的不足均衡作业时间的分区内,如果临近分区作业时间超过允许差值,这个点就不能弹出,只能弹出另外的次远数据点,以此类推,任何一个数据点只能弹出一次,直到所有数据点和分区调整完毕。
这样最终确定的分区,既能做到区域划分紧密,效率、成本更低,又能做到各区作业时间均衡,便于工作指派,车辆、人员核算。
以上是本文的第一部分工作,也是最有意义的工作,确定好合理的区域划分,不仅是配送作业合理化的重要步骤,也是业务人员访销工作和客户服务的重要依据。
3 基于改进蚁群算法的分区线路优化方法
分区内线路安排,就是一辆送货车由DC出发,依次经过分区内每一个客户点,完成送货后返回DC,求出近似最优的行车顺序,这是个典型的旅行商问题(Traveling Salesman Problem,TSP),TSP是NP完全问题,解法很多,有精确算法,也有启发式算法,目前许多智能算法就属于启发式算法,可以解决较复杂的线路优化问题,对于一般线路优化也能做得更准确,这里介绍蚁群算法解决实际问题。原因是蚁群算法与其他启发式算法相比,在求解性能上,具有较强的鲁棒性和搜索较好解的能力,是一种分布式的并行算法,一种正反馈算法,易于与其它方法结合。克服基本算法缺点,改善算法性能。
3.1 蚁群算法简介。蚁群算法(Ant Colony Algorithm, ACA)是由意大利学者M.Dorigo等人于20世纪90年代初提出的一种新的模拟进化算法,其真实地模拟了自然界蚂蚁群体的觅食行为。 M.Dorigo等人将其用于解决旅行商问题TSP,并取得了较好的实验结果。
蚁群算法用于解决优化问题的基本思路是:用蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素数量较多,随时间推移,较短路径上积累的信息素浓度逐步增高,选择该路线的蚂蚁数量也越来越多,最终整个蚂蚁会在正反馈的作用下集中到最佳线路上,这个路线就是最有解。
蚁群算法解决TSP问题具体步骤:(1)基本参数设置:包括蚂蚁数m,信息素重要程度因子0≤α≤5,启发函数重要因子1≤β≤5,信息素消逝参数0.1≤ρ≤0.99,信息素释放总量10≤Q≤10 000,最大迭代次数iter_max,迭代次数初值iter=1。用试验方法确定α、β、ρ、Q值,以获得较优的组合,有助于改进基本蚁群算法,提高整体优化效果,并缩短运算时间。(2)初始解的求解:利用最近邻算法,以缩短算法运算时间,并以此算法产生初始解的路径长度作为产生初始信息素的基础。 (3)构建解空间:将各个蚂蚁随机地置于不同出发点,对每个蚂蚁,按公式(1)计算其下一个待访问的网点,直到所有蚂蚁访问完区域内所有网点。(4)更新信息素:计算各个蚂蚁经过的路径长度Lk=1,2,…,m,记录当前迭代次数中的最优解。同时,根据(2)式和(3)式对各个网点连接路径上的信息素浓度进行更新。(5)判断是否终止:若iter 蚁群算法如结合其他启发式算法,建立混合算法,能够解决许多现实问题,达到较好运算效果,结合具体问题,可以深入研究。
所谓电子地图是一项结合计算机制图以及数据库处理和信息系统等学科为一体的图形表现形式。在现代社会中，电子地图在各个行业中应用广泛如在车载导航系统中，它已成为路径规划中一项较为重要的技术。但有关电子地图的详细应用主要在快速生成卫星影像和航空相片以及行数据的记录和新数据的派生方面。存在的问题是其技术的应用还不够广泛和深入。所以，本文结合实例对电子地图中的数据特点以及路径算法和算法的改进进行分析，同时对路径规划中电子地图的应用进行探讨。
1.实例应用
在计算机的相关软件的运行环境下，用VisualC++开发某市实验用地图上提取的300个道路所用点，同时添加附加信息，实施路径规划。在地图上制定路径的起始点和终止点之后，电子地图可在很短的时间内确定最优化的路径，同时该路径的各种辅助设备能够满足实际车载和各种应急需求。
2.电子地图的数据特征与路径算法
2.1数据特征
电子地图的数据特征是按照一定图层进行叠加的，在电子地图中的各种点、线、面等的集合就是图层。在电子地图中的数据分为两种：（1）空间数据。它主要是对空间对象的几何特征、位置关系以及拓扑关系进行存放。（2）属性数据。主要是对空间对象的类别、名称以及特征等进行确定。在本文所引用的Shape File中，属性数据主要以dbf的形式储存于数据库中，相对的空间数据则主要以Shape File所固有的格式进行数据的储存。这两种数据通过一定的形式联系在一起。电子地图中，将城市的道路网建设成一个图层，将其命名为道路网，同时在地图上实施路径规划，要对道路进行操作，那么就不涉及其它图层。
2.2电子地图的路径算法
在电子地图的路径规划中，路径算法是重要的工作过程之一。现在电子地图中最长用的算法是启发式搜索算法，其主要的模型为f（x） =g（x）+h（x）.（1）式中：g（x）表示从起点到搜索点的实际花费；h（x）表示从起点到终点的预估花费，称为启发函数；f（x）表是总花费。在采用启发模型之后，可以对驱动模型进行改进：（1）在每次新生成的节点展开之前，要对显示的同一位置两个节点的花费进行比较，在新生成节点大于已生成节点的前提下，可放弃已生成节点，反之用原节点。（2）将最小距离作为搜索信息，其花费的现实随节点的开展而增加。（3）在节点的数量增加后，综合代价增加，在每次新生成的节点的花费大于原来节点的情形下，可将新生成的节点淘汰用原来的路径。
3.路径规划中电子地图的应用
在路径规划过程中，电子地图重新定义了地图在人们心中的形象。在电子地图的帮助下，可以将现成的路径规划中出现的各种要素进行不同形式的组合最后连接成新的地图；同时交通部门可以根据电子地图在路径规划中的应用，对各种交通情况诸如交通事故、天气变化、不同路段的情况进行不同程度的监管；此外，路径规划中电子地图的使用为各种市民和公民进出入不同的城市提供便捷的服务，可以在现有的地址、地址范围和地理位置以及道路的交叉口等进行准确的定位，帮助人们在不熟悉路径以及路况的情况下正确的选择道路。
3.1起终点问题
在实际的生活过程中，电子地图上的起终点并不能代表实际路线中的出发点和结束点。在我们的日常生活中较为常见的是起点和终点都位于某一个路段的中间部分，在此时，必须将路段的出发点作为起点，目的地作为终点，在电子地图中输入该城市的行政规划图，通过电子地图对该路径数据的处理和分析，得出最佳路径区划图。
3.2最优路径模型的确立
电子地图在路径规划中的应用中所要解决的最优路径问题并不仅仅指最短的路途。它还包括利用电子地图在最短时间和最小花费内寻找到最合适的通向目的地的路径或者在电子地图的帮助下，将这几个问题全部综合在一起，最后使问题得到解决。同时在电子地图对路径的道路级别、人流量的大小以及转弯限制等做出详细的判断之后，确定最佳的路径模式。此时可将启发式模型中的g（x）进行一定程度的修改：g（x）=∑aijLij+∑bmnTmn。在该式中，Lij表示的是i和j之间的路径长度；其中aij表示的是相应的权值，这个参数与道路的级别和流量有关；Tmn表示的是从路段m到路段n之间所需要的花费（如时间等）；与之相应的bmn代表的是穿越的权值。若在该路段处禁止转弯则可将其设置为常数，g（x）则表示从起点到所要到达的地点之间的花费。在电子地图启用最佳模型的情况下，进行路径的选择。
3.3确立加权模型
中图分类号:TP393文献标识码:A文章编号:1009-3044(2010)16-4487-03
Research on Path Planning for Mobile Multi-Agent
CHEN Cui-li, GAO Zhen-wei
(Henan Normal University, Xinxiang 453007,China)
Abstract: A path planning method based on both the benefits of global and local path planners is proposed for mobile Multi-Agent path planning in dynamic and unstructured environments. The global path planner uses A*algorithm to generate a series of sub-goal nodes to the target node, and the local path planner adopts an improved potential field method to smooth and optimize the path between the adjacent sub goal nodes. Taking into full consideration the kinematical constraints of the mobile robot, this method cannot only effectively generate a global optimal path using the known information, but also handle the stochastic obstacle information in time. and is simulated on simulation platform developed by using Visual Studio 2005 software, simulation result presents the validity and utility of the algorithm.
Key words: mobile Multi-Agent; global path; local path
在移动智能体相关技术研究中,路径规划技术是一个重要研究领域。移动智能体路径规划问题是指在有障碍的环境中,寻找一条智能体从起始点到目标点的运动路径,使智能体在运动过程中安全、无碰撞地绕过所有的障碍物。这不同于用动态规划等方法求得最短路径,而是指移动智能体能对静态及动态环境下做出综合性判断,进行智能决策。在以往的研究中,移动智能体路径规划方法大体上可以分为三种类型:其一是基于环境模型的路径规划,它能处理完全已知的环境下的路路径规划。而当环境变化时(出现移动障碍物)时,此方法效果较差,具体方法有:A*方法、可视图法、栅格化和拓扑图法等;其二是基于传感器信息的局部路径规划方法,其具体的方法有:人工势场法、模糊逻辑法和遗传算法等;其三是基于行为的导航行为单元,如跟踪和避碰等,这些单元彼此协调工作,完成总体导航任务。随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。
一个好的路径规划方法需要满足如下性能[1]:合理性、完备性、最优性、适时、环境变化适应性和满足约束。有些方法没有高深的理论,但计算简单,实时性、安全性好,就有存在的空间。如何使性能指标更好是各种算法研究的一个重要方向。
在未知的(或部分已知的),动态的非结构的环境下,多智能体利用传统的路径规划方法很难满足前面的性能要求,本文提出了一种将全局路径规划方法和局部规划方法相结合,将基于反应的行为规划和基于慎思的行为规划相结合的路径规划方法,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。
1 路径规划方法
1.1 相关研究
1) A*算法
在最佳优先搜索的研究中,最广范围应有的方法为A*搜索,其基本思想[2]是:它把到达节点的代价g(n)和从该节点到目标节点的代价h(n)结合起来对节点进行评价:f(n) = g(n) + h(n)(1)。A*算法用于移动多智能体的路径规划时,多智能体分别按照已知的地图规划出一条路径,然后沿着这条生成路径运动,但智能体传感探测到的环境信息和原来的环境信息不一致时,智能体重新规划从当前位置到目标点的路径。如此循环直至智能体到达目标点或者发现目标点不可达[3]。重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且由于采用A*方法规划出的最优路径并没有考虑到机器人的运动学约束,即使机器人可以采用A*方法规划出一条最优路径,机器人也未必可以沿着这条路径运动。
2) 人工势能法
人工势能法由 Khatib 提出的一种虚拟力法[4]。人工势场方法结构简单,便于低层的实时控制,在实时避障和平滑的轨迹控制方面得到了广泛的应用,但根据人工势场方法原理可知,引力势场的范围比较大,而斥力的作用范围只能局部的,当智能体和障碍物超过障碍物影响范围的时候,智能体就不受来自障碍物引起的排斥势场的影响。所以,势场法只能解决局部空间的避障问题,他缺乏所在的全局信息,,这样就造成产生局部最优解不能进行整体规划,智能于局部最小点的时候,智能体容易产生振荡和停滞不前。
1.2 路径规划方法描述
鉴于A*算法全局路径搜索的全局性与改进人工势场算法局部路径搜索的灵活性,通过一定的方法把两者结合起来,其思路如下:多智能体分别采用A*算法进行全局路径规划,各自生成到达目标点的子目录节点序列,同时采用改进的人工势能对子目录节点序列中相邻节点进行路径的平滑和优化处理,该方法不但能够充分利用已知环境信息生成全局最优路径,而且还能及时处理所遇到的随机障碍(其它智能体)信息,从而提高了多智能体整体的路径规划的性能。由于A*方法采用栅格表示地图,栅格粒度越小,障碍物的表示也就越精确,但是同时算法搜索的范围会按指数增加。采用改进人工势场的局部路径规划方法对A*方法进行优化,可以有效增大A*方法的栅格粒度,达到降低A*方法运算量的目的。
2 环境构造
目前主要有三种比较典型的环境建模方法:构型空间法、自由空间法和栅格法,本文仿真实验采用的环境建模方法是栅格法,栅格法将机器人路径规划的环境划分成二维网格,每格为一个单元,并假设障碍的位置和大小已知,且在机器人运动过程中不会发生变化。栅格法中的网格单元共有三种类型,即障碍网格、自由网格和机器人所在网格。目前常用的栅格表示方法有两种,即直角坐标法和序号法。这两种表示方法本质上是一样的,每个单元格都与(x, y)一一对应。本文采用序号法表示栅格,设栅格的中心点坐标为栅格的直角坐标,则每个栅格编号都与其直角坐标一一对应,地图中任意一点(x,y)与栅格编号N的映射关系为:N=INT(xGs)+xmaxGs×INT(yGs),(1)式中,xmax表示x轴的取值范围,Gs表示栅格尺寸的大小,INT函数表示取整,而栅格中心点的坐标为(xG,yG),它与栅格编号N之间的关系为:xG=(N%M)×Gs+Gs/2,yG=INT(N/M)×Gs+Gs/2,(2)式中,M=xmax/Gs,符号%表示取余操作。本文中根据机器人的尺寸来确定栅格的粒度,假设一个栅格能容纳一个智能体,这里选择栅格的大小为40cm×40cm[5]。本文的仿真环境为800cm×800cm,栅格号N=0~399,机器人的初始位置的栅格号为N=42,目标位置的栅格号为N=314。在Visual Studio 2005中进行仿真,仿真结果如图1所示,长方形和椭圆图形代表障碍物栅格,小圆圈所代表的栅格为机器人的起始栅格和目标栅格,剩下的是自由栅格。在路径规划中机器人可以选择自由栅格作为它的路径点。
建立栅格后,对栅格进行初始化。设置变量G_Obstacle为0表示自由栅格,G_Obstacle为1表示障碍网格包括机器人栅格。若障碍物或智能体占当前位置栅格面积大于1/3则设置变量G_Obstacle为1.
3 数据的采集
对于简单地形,我们将实际地形就行考察并进行测量、量化,转化为平面坐标数据最后转换相应的栅格编号。对于复杂地形在没有航摄资料的情况下,本实验以地图为数据源的DTM数据获取方法在,可利用已有的地形图采集地形数据,用手扶跟踪式数字化仪将平面图形转化为平面坐标数据,最后转换相应的栅格编号。
4 实现过程
第1步:对环境信息进行数据采集并转化成相应的平面坐标数据。
第2步:确定各个智能体的初始位置和目标位置。
第3步:建立栅格,对栅格进行初始化。
第4步:智能体S(i)首先根据已知信息规划出各自的一条目标序列S(i)n。
第5步:智能体S(i)利用测试传感器探测到临界危险区L范围内的信息与原有信息是否一致,当智能体利用传感器探测到临界危险区L范围内的信息与原有信息一致时,利用改进后的人工势能算法搜索相邻目标点之间的轨迹,否则智能体搜索从当前序列点S(i)n到S(i)n+4路径。定义临界危险区L、目标序列点S(i)n(n>=1)。
第6步:智能体一旦移动到达目标栅格,则程序终止;否则返回第5步。系统的工作流程如图2所示。
5 仿真结果及结论
在Visual Studio 2005平台上进行了仿真,,首先根据已知环境信息,进行数据采集量化并进行栅格化处理,设置障碍和智能体的大小及位置(为了简单化,本实验所有障碍都设置为圆形),再进行初始化操作,采用0、1二元信息数组存储栅格化的地形。
智能体运用A*算法进行全局路径规划,图3显示两个智能体的运动过程,显然两个智能体的路径相交可能会发生碰撞,智能体为了避免碰撞应重新规划算法依旧是从当前位置到目标点的全局搜索的过程,运算量较大。而且显然只用A*算法规划出二维路径点序列,相邻两点之间的夹角一定是π/4的整倍数,机器人很难按照所生成的序列点运动。智能体采用改进后的人工势场进行目标序列点之间的局部路径规划,图4显示智能体的运动过程。显然智能体的整条运动轨迹显得比较平滑同时又实现实时避障的目的。
6 总结
本文对多智能体在动态环境下路径规划技术进行了研究探索,提出了一种能够将全局路径规划方法和局部路径规划方法相结合,通过仿真取得了很好的结果,证明A*和人工势场算法的结合可行。
参考文献:
[1] 刘华军,杨静宇,陆建峰,等.移动机器人运动规划研究综述[J].中国工程科学,2006,8(1):85-94.
随着科技的不断进步，我国自动化技术发展越来越好，这对提高人们的生活质量有着较大帮助。应用自动化技术，可以生产出具有更多功能的机器与设备，比如，自动导航小车就是一种新型的机器，其具有自动定位与行驶的特点，可以利用计算机技术，对小车的行驶路径进行规划与控制。自动导航小车的设计与制作涉及多个领域，在科技不断发展的背景下，我国自动化控制水平越来越高，这也促进了自动导航小车的发展。下面笔者对自动导航小车的路径规划以及控制方法进行简单分析。
1.自动导航小车路径规划的定义与方法
1.1自动导航小车路径规划的定义
有学者对自动导航小车这类机器的路径规划有着如下定义：在自动导航小车中，设有自动导航系统，该系统是由较多的刚体部件构成的，而且有着不同的自由度。如果该系统可在二维或者三维空间中运行，则说明小车可以在不破坏自身运动约束的条件下，进行自由运动。另外，在工作空间中，也存在较多的几何参数障碍。路径规划指的是自动导航小车在系统设定的连续动作下，由给定的初始位形运动到目标位形的设计。位形指的是自动导向小车位置与形态，相关设计人员通过改变位形，可以控制小车的行车路线。
1.2路径规划的方法
自动导航小车路径规划的方法主要有两类，其一是传统方法，其二是智能方法。第一类传统路径规划方法中，常用的有自由空间法、图搜索法、人工势场法等；第二类智能路径规划方法中，常用的是基于遗传算法的路径规划、基于人工势场的路径规划等等。在现代自动导航小车设计中，应用智能方法比较多，其可以提高路径规划的准确性，下面笔者对自动导航小车的路径规划常用的几种智能方法进行简单的介绍。
1.2.1基于遗传算法的路径规划
基于遗传算法的路径规划在自动导航小车路径研究中应用比较广泛，其是由国外的学者提出的，是在模拟达尔文生物进化论的基础上创建的，应用这种方法可以解决传统路径规划中存在的漏洞。遗传算法具有随机性，而且具有针对性，利用遗传算法可以对自动导航小车的移动路径进行准确的规划，其具有高效的特点。
1.2.2基于人工势场的路径规划
人工势场是一种虚拟的方法，其将自动导航小车的运动路径看做是人工受力场下运动，应用虚拟的方法，主要是利用障碍物对自动导航小车所产生出的斥力，以及目标点对小车产生的引力而完成运动路径的。在斥力与引力的共同作用下，自动导航小车可以从初始位形移动到目标位形，由于斥力与引力对小车的速度有着较大影响，所以，利用加速力相关人员还可以计算出小车所处的位置，从而控制小车的运动方向以及路径规划。
2.不同环境下自动导航小车的路径规划策略
自动导航小车是一种新型的机器，其在未知的环境下，收集信息的情况也有一定差异，通过分析发现，其收集信息主要有两种类型，一种是在已知的信息环境下，全局路径的规划；另一种是在未知的环境信息下，局部路径的规划。下面笔者主要对静态已知环境下局部路径规划方法以及静态未知环境下局部路径规划方法进行分析。
2.1静态已知环境下局部路径规划方法
静态已知的信息环境下，对小车局部路径进行规划是一种比较容易实现的方法，这种规划方法有着广泛的应用空间，这种方式最早应用的是可视图算法，随着科技的不断发展，相关人员又提出了随机路图法，这两种方法有着各自的适用范围。可视图算法提出的时间比较早，其广泛应用是在1987年，研究人员利用可视图算法，解决了小车路径规划问题。可视图是由节点与可视边组成，在已知的环境下，技术人员通过设置障碍点以及目标点，可以帮助小车快速到达指定位置。为了提高小车运动的效率，设计人员需要了解可视图算法的最短路径定理，该定理指出，从初始点到目标点含有穷路径集合，为了得到最短路径的算法，需要全面考虑可视图构造，这种方法在二维空间中发挥较高的效用，但是在高维空间中并不适用。
2.2静态未知环境下局部路径规划方法
静态未知环境下，自动导航小车需要利用自身传感器对环境进行感知，在获得局部信息后，对局部路径进行规划，这种规划方式主要采用了势场法，但是在应用的过程中也存在一定局限性，设计人员需要重点考虑梯度以及积分问题，而且需要通过分析多个局部信息，掌握全局信息。这种路径规划法效用的发挥与传感器性能有较大关系，为了更好的掌握全局信息，设计人员多采用的是实时传感器。这种规划方法的基本思路是：自动导航小车向目标点运动的过程中有多种路径，相关人员需要将所有可能性进行量化，在通过分析障碍物信息，从而得出最佳的规划路径。在对通路进行检测时，要避免小车进入死路，通过测量障碍物间的距离，判断小车是否可以通行，如果通路被堵塞，则需要重新优化路径。
3.自动导航小车的路径控制
控制软件与各模块驱动程序是保障系统正常运行不可或缺的部分。控制软件在主机上实现，各模块驱动程序在各自模块中运行，控制软件与各模块驱动程序之间可通过主从式结构进行必要的通信联系。子机可向主机发出异常情况处理信号，利用通信技术，还可以控制各子模块的运行状况。
3.1运动控制的位置环调节
参数调节运动控制驱动器的位置控制回路时，运用基于观测器的状态变量控制技术。采用此技术，运动控制驱动器的优点是：⑴系统将具有很高的动态刚度；⑵即使负载和电机的惯量有较大差别，仍可有效减少跟踪误差。在运动之前，必须进行轨迹参数设置及完成参数设置。初始调节时，一般设定运动速度、加速度、加加速度为较大值，而运动位置为一较小值。
3.2轴的运动
轴运动有两种，一种是单轴运动，另一种是多轴协调运动。单轴运动是指某一种运动模式设定后，该轴将保持这种运动模式，直到设置新的运动模式为止。多轴协调运动是指运动控制器可以实现两种轨迹的多轴协调运动。对于各模式之间的切换，除电子齿轮模式之外，其他模式必须是在当前轴运动完全停止的情况下进行。控制器中不同的轴可以工作在不同的运动模式下，在某些情况下，为了安全起见，需要在某些位置或某个时刻使运动停止。
4.结语
通过上文的分析可以看出，自动导航小车具有较高的性能以及较多的功能，其性能体现了我国科技的进步性。在计算机技术的影响下，相关设计人员利用传感器，使自动导航小车获取周围环境的信息，其获取的方式有两种，一种是在已知的信息环境下，获取全局信息，另一种是在未知的环境下，获取局部的信息。为了更好的控制小车路径，相关人员需要掌握传感器信息融合算法，还要避免外界环境对信息准确性的影响，这样才能提高路径规划与控制测量的可行性。
【参考文献】
Abstract：this article simulated biological immune process，and established the mathematical model of immune algorithm.It is studied the application of mobile robot path planning in static and dynamic environment.
Key words：Immune algorithm;Intelligent vehicle path planning;Simulation experiment
1.概述
随着机器人相关技术的发展，对于智能车辆控制的准确性要求越来越高，控制系统的数学模型的好坏直接影响着控制的有效性和准确性。智能算法用于建模困难或本质为非线性或复杂对象的控制系统，效果优于常规控制方法，若系统的转动惯量，结构参数等存在误差是仍能实现精确跟踪，鲁棒性良好。
为解决路径规划及壁障问题，我们在局部环境中，出现智能车辆必须放弃期望轨迹避开障碍物的情况下，研究基于免疫算法的智能车辆避障控制方法：首先在局部环境下，生成占有栅格地图;再生成障碍物的极坐标柱状图;设计了基于免疫算法的车辆避障方法。
2.免疫算法
人工免疫系统（Artificial Immune Sys-tem，简称AIS）是在免疫学及其理论的基础上发展而来的，因此需对生物免疫系统进行研究。生物免疫系统是复杂程度很高的系统，在检测和消除干扰问题上表现出了精确的调节能力。免疫系统展示了许多可以将其融入人工智能系统的性质：如多样性、动态性、适应性、鲁棒性、自适应、自治性、自我监测、错误耐受等等。
在免疫算法用于路径规划中，我们有如下，如表1所示。
表1 对应关系
免疫系统 路径规划
障碍物 抗体
可行栅格 抗原
亲和力 路径选择可行度
抗体变异 动态障碍物
算法步骤：
考察车辆的路径规划问题，智能车从初始点gs出发，寻找一条通往目标点的最优路径。如果智能车某时刻ti位于栅格点的gi，那么它下一步必然选择gi周围的可行栅格。
步骤1：确定载入的抗原（障碍物），随机产生初始抗体即随机产生候选解，创建一个总量为N的初始种群抗体集合P（可行栅格）。
步骤2：计算抗体亲和力：对于每个vP，评估g（v）和创建克隆种群C，亲和力g设为对应的函数。
步骤3：从种群C中选择n个亲和力最高的抗体形成临时抗体集v’。
步骤4：克隆亲和力高的抗体：克隆上一步n个亲和力最高的抗体，其中每个抗体被单独克隆，抗体亲和度越高，被克隆的抗体规模越大。通过评估g（v'），如果g（v'）>g（v）那么通过克隆v'取代v。即，选择路径最优。
其中：
（1）
g（v）是抗体克隆总数量，是一个克隆因子，N是抗体集合P的总数量，i是以递减排序的最有抗体序号，ceil是向上取整算子。通过上述的条件判断和克隆取代操作，可使最优抗体的规模逐步扩大。
步骤5：对新的种群中的部分抗体进行变异操作（加入动态障碍物）。
步骤6：重新计算变异后的亲和力并令n加1，重复第四步操作。
步骤7：判断gi是否满足终止条件，即是否到达目的地gd;若不是返回步骤2，将gi设为gi+1，否则算法结束，输出最优路径。
3.免疫算法路径规划仿真
3.1 环境模型
假定：①移动机器人在二维有限空间中运动;②机器人的工作空间中分布着有限个障碍物;③把障碍物边界向外扩展机器人体在长、宽方向上最大尺寸的l/2，机器人中心位置可用点来表示，即所谓“点机器人”。
记A为移动机器人R在二维平面上的凸多边形有限运动区域，以A的左下角为坐标原点，水平向右为X轴正方向，垂直向上为Y轴正方向，建立直角坐标系XOY，则有A在X、Y轴上的最大值分别为Xmax和Ymax。以占为步长将X，Y分别进行划分，由此形成环境的栅格图表示。每行的栅格数Nx=Xmax/，每列的栅格数NY=Ymax/，考虑到A为任意形状，可在其边界补以障碍栅格，使其成为正方形或者是长方形。每个障碍物至少占有一个栅格，当不满一个栅格时，算一个栅格。任意一个栅格g，都有确定的坐标g（x，y）及相应的序号S，其中x为g所在的行号，y为g所在的列号。定义g（l，l）的序号为1，g（l，2）的序号为2，…，则坐标g（x，y）与序号S之间的关系可表示为：
式中，mod为求余运算，int为舍余取整运算，i=l，2，…，M，M为地图中栅格的总数。由此，我们可构建一个8x8的栅格地图如图1所示。
3.2 静态路径规划
为了验证算法的有效性，我们建立了在各种复杂环境下，只要有通路存在，本算法都可以迅速的规划出最优路径。如图2所示。
图1 栅格地图
图2 最优路径
3.3 动态路径规划
本实验的目的是让移动机器人避开所有的障碍物，并且追捕到运动目标。即，通过变异操作实现动态障碍物的克隆取代。其仿真结果如图3（a）、（b）、（c）在动态障碍物，在不同位置时的路径规划。只要存在到达目标点的通路，本算法必能快速的规划出最优路径。
图3 动态路径规划
4.结论
本文研究了静态和动态环境下移动机器人的路径规划问题。首先，描述了仿真环境建立，然后，较为详细地介绍了免疫算法，并研究了它在静态和动态环境下移动机器人的路径规划中的应用。并验证其应用的有效性。
参考文献
DOIDOI：10.11907/rjdk.161914
中图分类号：TP301文献标识码：A文章编号文章编号：16727800（2017）001017703
引言
自20世纪80年代末以来，多机器人系统开始引起广大学者关注，并且得到了迅速发展。相较于传统的多个单机器人系统而言，多机器人系统具有更大的优势。比如，多机器人系统在时间和空间分布性上更加具有优越性。具有分布性的多机器人系统中单个机器人的传感器信息可以有效互补，因此整个机器人系统具备较高的数据冗余度和更强的自适应性、鲁棒性；在多机器人系统中，由于单个机器人可以不必具有极强的功能和极高的性能，因此多机器人系统本质上具备低成本、强鲁棒性的优势；尤其是在完成复杂任务时，多机器人的优势更加突出，通常多机器人系统能够借助先进的协作架构和协同策略，完成多个单台机器人难以实现的复杂任务等。
多机器人系统的主要特点有：由于高科技快速发展，机器人的研究和开发更加容易、自适应性更好。随着多机器人协作策略的不断进步，其完成复杂任务的成本更低、效率更高、可扩展性更好。近年来，由于材料科学等边缘科学及交叉科学的发展，机器人的研发成本逐年降低，同时多机器人的应用范围和领域更加广泛。因此，越来越多的学者们重视多机器人系统及其应用研究，多机器人系统已经成为机器人学研究中一个飞速发展、具有良好应用前景的研究方向。
近年来，随着科技不断进步，多机器人系统相关研究得到快速发展，多机器人系统中的实现技术也取得较大突破[12]。目前，多机器人系统的关键技术主要包括任务规划、运动规划、协调控制等[35]。
1多机器人系统国内外研究现状
目前，多机器人系统的研究无论在理论中还是在实践上都取得了很大进展，建立了许多仿真系统和硬件实验平台，为进一步研究机器人系统夯实了基础。日本属于较早开展多机器人系统研究与实践的国家之一，1989年设计出了著名的ACTRESS系统和CEBOT系统。图1为日本名古屋大学Fukuda等研制的CEBOT（Cellular Robotics System） 系统，该系统采用分布式体系结构设计，将多机器人系统中功能简单的自主机器人视为“细胞元”（Cells），研究“细胞元”机器人自组织地构成功能强大的多机器人系统。特别是通过传感器感知环境的动态变化，“细胞元”间相互耦合并自组织重构得以实现更加优化的体系结构。
1996年第一届机器人足球世界杯在韩国隆重举行，来自7个国家的23支参赛队参与了竞赛，如图2所示。1997年过多方共同努力，成立了国际机器人足球联合会，联合会总部设在韩国，其任务包括：每年组织一次机器人足球世界杯大赛；同时还要举办相关学术会议，给参赛者提供充分交流的学习平台，探讨机器人足球研究方面的经验和技术，从而有效地促进该学科方向的不断发展。
图3为美国南加州大学Mataric等人研制的The Nerd Herd 系统。该系统由20个机器人组成，每个机器人上装有碰撞传感器、定位系统和通讯系统，可以实现游弋（Safe Wandering）、跟随（Following）、聚集（Aggregation）、分散（Dispersion）和回家（Homing）等行为。研究人员主要将该系统应用于多机器人学习、群体行为、协调与协作等方面的试验研究与探讨，图4为利用该系统进行的推箱子实验装置。
图2机器人世界杯图3The Nerd Herd系统 C.R.Kube等人研制的Collective Robotics 系统如图5所示。该系统从自然界里昆虫的社会行为得到启发，利用多个功能简单的机器人组成功能强大的合作机器人群体。该系统在无显式通信的条件下，能够充分利用分布式控制策略实现移动机器人之间的协作。因此，单个简单智能的机器人通过交互作用实现了多机器人系统复杂的群体智能行为。
图6为美国MIT的计算科学和人工智能实验室（CSAIL）研制开发的多机器人系统。该实验室在多机器人系统上开展了协调多个机器人行为的算法设计、多机器人协调算法性能预测等问题的研究。这些关键问题及其研究成果形成多机器人控制算法的重要基础。
我国在多机器系统的研究方面也开展了卓有成效的工作，虽然起步相对较晚，但到目前为止也取得了丰硕的研究成果。沈阳自动化研究所以制造环境中多机器人的装配为研究背景，建立了多机器人协作装配系统MRCAS（Multi-Robots Cooperative Assembly System）。通过采用集中和分散相结合的分层体系结构，该系统可以完成自主编队行进、队形变换、自主避障等功能，进一步通过多机器人间协调与合作，完成装配工件任务。南京理工大学在早期开展的地面微小型机器人研究基础上，进行了移动机器人协作编队、自主定位、智能导航等关键技术研究，并取得一定成果。目前，由清华大学、国防科技大学、浙江大学和南京理工大学等著名高校联合研制的第四代无人驾驶车辆实现了多车无人干预下的编队行驶、超车行驶等核心技术。此外，上海交通大学、哈尔滨工业大学、中南大学等知名高校纷纷开展多机器人系统关键技术研究，也取得了一系列突破性研究成果，为我国机器人系统研究与发展奠定了重要基础。
2多机器人路径规划问题研究
多机器人路径规划问题是多机器人系统的关键技术，该技术也是多机器人协作完成任务的根本保障。多机器人路径规划问题定义为：利用已知的静态环境信息或者依靠传感器获得的动态环境信息，多机器人系统各个机器人自主规划一条从已知起点到目标终点的无碰撞最优路径，该最优路径不仅要求单个机器人与所有障碍物之间避障，而且还需满足多个机器人之间也无碰撞要求。
由单个机器人路径规划问题发展而来的多机器人路径规划问题，首先需要解决单个机器人路径规划问题，其次还要求解决多机器人之间的协调运动和多个机器人之间的协作问题，重点就是避免机器人之间的碰撞和避免出现机器人之间的路径死锁等问题。其中，环境建模方法、路径规划算法、协调避碰算法等都是关键技术问题[6]。
2.1环境建模
最有效的环境建模方法是建立环境地图，栅格地图、拓扑地图、特征地图等是目前常用的环境地图。
为了方便机器人的定位，栅格法将整个环境划分为许多大小相同的正方形单元格，并给予每个单元格唯一的整数标示。栅格地图模型最大的优点是简单，其缺点是栅格地图的粒度不好控制，若粒度较小，计算复杂度增加，若粒度较大，真实环境无法准确表示。
拓扑地图是利用节点间相关联的边所构成的拓扑结构来标示环境，拓扑地图模型将环境中的重要位置视为节点（如障碍物的棱角），将节点间存在的直接连接的路径视为地图中的边。拓扑地图虽然适用于环境比较简单的情况，也不需要机器人准确的位置信息。但拓扑地图通常难以直接获取，且对于相似环境的识别也比较困难。
特征地图模型不同于以上两种方法，本文利用抽象的几何特征（如点、直线、曲线等）表示机器人感知的外部环境。此模型便于位置估计和目标识别，但抽象的几何特征需要对感知的环境信息作进一步处理才能获取，一般适用于特定的环境。
2.2规划方法
按照多机器人系统运动规划的控制方式，多机器人的运动规划方法可以分为以下4种类型：①完全集中的规划：需要一个集中控制器来规划所有机器人的运动；②不完全集中的规划：每个机器人规划好自己的路径，但是有一个集中控制器来管理多机器人系统中单个机器人如何走自己的路径以保证机器人间不发生冲突；③不完全分散的规划：多机器人系统中单个机器人规划各自的路径以及如何走好自己规划的路径，在不安全情况下才由集中控制器进行统一规划；④完全分散的规划：单个机器人的运动完全自主规划，不存在集中控制器。
2.3协调避碰策略
协调避障是多机器人系统路径规划问题的重要技术之一，也是多机器人系统路径规划和多个单机器人路径规划的本质区别体现。多机器人系统协调避障问题除了要解决单个机器人自身路径规划问题，还必须解决多个机器人之间的碰撞、堵塞及死锁问题。目前，学者们提出的协调策略主要有速率调整法、交通规则法、优先级法、几何修正法以及基于行为的避碰方法等。随着“智能制造2025”的深入推进，服务机器人应用领域还在不断扩展，多机器人系统协调避碰策略亟需进一步探讨。
3多机器人系统展望
多机器人系统是一个多学科高度交叉的前沿学科，多机器人系统的进一步发展也必定会受到相关学科发展的限制。研究多C器人系统需要借鉴这些学科或学科中解决某些问题的理论和方法，才能产生突破性进展，这是未来研究多机器人系统的发展方向和重要趋势，具体而言，这些学科有：分布式系统、生物学、传感器技术、机械工程等。可从以下几个方面探讨多机器人路径规划问题：
（1）先进的传感技术。移动机器人中传感器设备被视为人类的五官，实现移动机器人的视觉、听觉、嗅觉等功能。在环境建模中依靠先进的传感技术，机器人能完成高效实时采集环境信息的任务。
（2）多传感器的信息融合技术。移动机器人导航方式正在向多传感器发展，使用多个传感器可以同时采集和处理信息，从而提高机器人系统的速度和性能。通过合理支配并充分利用传感器及其采集信息，并采用信息融合技术以获得环境的一致性解释及描述形式，可以提高机器人路径规划的精准度和鲁棒性。
（3）智能优化算法的发展。随着复杂问题规模呈现指数级增长，智能优化方法迅速成为多机器人系统路径规划研究新的发展方向。但由于算法实时性、自适应性、鲁棒性还不够好，智能优化算法在实际应用中必然存在一定的局限性。因此，多机器人系统路径规划问题研究中，智能优化算法还有很大的发展空间。
4结语
多机器人系统的研究与应用已经对人类社会产生深刻影响，随着科学技术的不断进步，其还将会对人类生活和社会进步带来巨大变革。不久的将来，人们的生活质量和工业、农业和国防现代化水平都将得到极大提高。但目前对于多机器人系统的研究还处于初级阶段，多机器人系统关键技术研究还亟需深入探讨，特别是多机器人系统路径规划算法还有待进一步改进，多机器人系统无论在理论研究上还是技术实现上都需要更多学者进行不懈努力和积极探索。
参考文献：
[1]吴军，徐昕，连传强，等.协作多机器人系统研究进展综述[J].智能系统学报，2011，6（1）：1326.
[2]原魁，李园，房立新.多移动机器人系统研究发展近况[J].自动化学报 2007，33（8）：785795.
[3]蔡自兴，崔益安.多机器人覆盖技术研究进展[J].控制与决策，2007，2（3）：17.
[4]张嵛，刘淑华.多机器人任务分配的研究与进展[J].智能系统学报，2008，3（2）：115120.
中图分类号：F252.14 文献标识码：A
关于物流配送路径规划一直是物流领域研究的热点和难点问题，从国外研究情况来看，1993年Ronald 等人提出物流系统设计的四个核心战略规划区域模型（Four major strategic planning areas in logistics system design），他认为四个核心区域为客户服务水平、选址决策、库存决策和运输决策（Customer service levels，Location decisions，Inventory decisions，Transport decisions），对于配送中心选址方法可简单分为定性和定量两大类，定性方法主要是层次分析法和模糊综合评价相结合对各个方案进行指标评价，找出最优地址。定量方法包括重心法、运输规划法、Cluste法、CFLP法、Baumol-Wolfe模型、混合0—1整数规划法、双层规划法、遗传算法等。蚁群算法是一种新型的优化方法，该算法不依赖于具体问题的数学描述，具有全局优化能力。
本文提出了一种基于改进蚁群算法的物流配送路径规划方法，将物流配送中心看成一个聚类过程，再利用蚁群系统中蚂蚁通过信息素留存寻找最优路径的机制，结合蚂蚁使物体聚堆的行为模式，合理设计转移概率、禁忌列表及信息素更新方式，使系统配送中心的配送路径最短，从而确定配送中心的配送路径。
1 蚁群算法
仿生学家经过大量细致观察研究发现，蚂蚁个体之间通过一种称为外激素的物质进行信息传递，蚂蚁在运动过程中，能够在它所经过的路径上留下信息素，而且蚂蚁在运动过程中能够感知这种物质，并且以此指导自己的运动方向。受此启发，它由意大利学者Marco Dorigo于1991年在他的博士论文中引入，提出了一种基于蚂蚁种群的新型优化算法——蚁群算法。
蚁群算法（ant colony optimization， ACO），又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。其灵感来源于蚂蚁在寻找食物过程中发现路径的行为，蚂蚁总能找到巢穴与食物源之间得最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上叫做信息素（Pheromone）的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取得基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。
1.1 研究目的
本研究拟通过学习蚂蚁觅食回巢的生物本能，对物流配送进行仿真模拟，找出优化的配送路径，提高物流配送的效率和效益。
1.2 研究的对象
先对6个同配送点的配送方案进行研究，然后延伸到100个配送点，并找出最佳路径。以上步骤均通过计算机编程进行演化分析。把研究的成果进行实际应用的演算和验证。
1.3 研究方法
本文使用蚁群算法，进行人工模拟配送路线，并用计算机编程进行模拟，就如同一只人工蚂蚁，背着背包，到若干个结点，搬运食物回蚁巢。
规则1 环境：人工蚂蚁所在的环境是一个虚拟的世界，有确定的路线桥，且两点间路线桥不相交；有信息素，信息素都同质（不区分，找到食物时分泌的信息素和回巢时分泌的信息素），环境以一定的速率让信息素消失。
规则2 移动：人工蚂蚁只会沿着路线桥觅食，当走到结点（觅食点），人工蚂蚁会判断是否有信息素及其浓度，优先选择信息素浓度大的路线桥为路径；同时会有一定的概率，随机选择别的路线桥；如路线桥上均无信息素则随机选择路线桥。
规则3 觅食：人工蚂蚁沿路线桥到各个结点觅食，当到达该觅食点后，为防止人工蚂蚁原地转圈，它会记住最近刚走过哪些点（禁忌表），如发现下一个结点是已觅食过的结点，则会避开该点。
规则4 信息素：每只人工蚂蚁在遍历完各点后，系统会利用蚁周算法更新信息素，对总路径最短的路线进行精英激励，会大量增加该路线信息素；如果总路径较长则少量增加信息素；信息素在人工蚂蚁遍历完后，将会按一定速率自动挥发所有路线桥上的信息素。
2 研究步骤
2.1 初始化结点
各个结点进行坐标化，数据存入zuobiao（序号：X，Y）表中，见表1，然后构造成路线桥距离矩阵存入jiedian（序列：1，2，3，…，n）表中，见表2，此次研究拟选用zuobiao表中的结点和数据：
2.2 信息素表示
所有的路线桥上的信息素全部为0，并把信息素数据存入xinxisu（序号：1，2，3，...，n）表中，见表3，用0表示无信息素。
2.3 初始化禁忌表
人工蚂蚁比较聪明，当到达该觅食点后，它会记住已找到的结点，并把结点信息存入jinji（序号，禁忌，先后顺序）表中，其中0表示未用，1表示已用，详见jinji表，见表4。
第1只人工蚂蚁运行状态：人工蚂蚁从巢穴出发，判断与该结点连接的各个路线桥上的信息素的浓度，因信息素均为0，则用随机函数进行选择路线在jinji表中把起点设置为1（已用），先后顺序为1，离开起点沿着该路线桥到达下一觅食结点，信息素为0，则用随机函数进行选择路线同样在jinji表中把第1个觅食结点设置为1（已用），先后顺序为2，离开第1个结点沿着该路线桥到达下一觅食结点，判断信息素，随机函数选择路线桥……当6个觅食结点全部走完后，人工蚂蚁自动沿着路线桥回到巢穴结点，从而形成完整的闭合回路计算总路线桥长度，用L1表示，同时更新xinxisu表，在路线桥闭合回路全部洒上强度为3的信息素。
第2只人工蚂蚁运行状态：人工蚂蚁从巢穴出发，判断与该结点连接的各个路线桥上的信息素的浓度，原则上沿着信息素浓度大的路线桥通往下一觅食结点，但也会有“叛逆”的情况，用随机函数产生这种小概率事件，如人工蚂蚁遇到小概率事件，则沿着小概率事件选择的路线桥爬行到下一觅食结点在jinji表中把起点设置为1（已用），先后顺序为1，离开起点沿着该路线桥到达下一觅食结点，判断连接该觅食结点各个方向上的信息素浓度，正常是沿着信息素浓度大的方向移动，同时考虑小概率事件是否发生，如发生则沿着小概率选择的优先路线前进。同样在jinji表中把第1个觅食结点设置为1（已用），先后顺序为2，离开第1个结点沿着该路线桥到达下一觅食结点，判断信息素浓度，并优先考虑小概率事件……当6个觅食结点全部走完后，人工蚂蚁自动沿着路线桥回到巢穴结点，从而形成完整的闭合回路计算总路线桥长度，用L2表示，更新xinxisu表，判断该轮路线桥总长度是否是最短，如最短则在第2只蚂蚁走过的路线桥上全部洒上激励的信息素，其值为3，同时，在全部路线桥上按1个信息素/每轮的速率，挥发信息素。
2.4 总路线长度最优的判定
判断路线桥该轮路线桥总长度是否是最短，可分为如下三种情况。
L1
L1=L2 增加L2闭合回路上的信息素+3 把L2设为最短路径，用Lmin表示，后续人工蚂蚁的Ln均与Lmin比较
L1>L2 增加L2闭合回路上的信息素+3 把L2设为最短路径，用Lmin表示，后续人工蚂蚁的Ln均与Lmin比较
后续n只人工蚂蚁和第2只蚂蚁一样觅食（n=80），最终沿着信息素最浓的路线桥爬行各个觅食点，其路径桥为最短路线。
2.5 参数选取
（1）随机小概率为0.05，结点6个，信息素对精英蚂蚁奖励+3，对一般蚂蚁+1，信息素挥发速率为1/轮。
（2）人工蚂蚁选取80只（迭代80轮）。
（3）觅食结点的状态。其中第1只人工蚂蚁比较特殊，路线桥选择不是按信息素的浓度进行选择，而是人工赋予随机选择函数。在离开原点时选择概率为1/6，到第一个结点后选择概率为1/5，到第二个结点后选择概率为1/4，……，1/1回到巢穴。
2.6 进行演算
觅食结点的状态选取3种状态：离散型、聚合型、平均型；随机小概率事件按分形理论选取20个不同的参数，如下值：0.5、1.5、2.5、3.5、4.5、5.5、6.5、7.5、8.5、9.5、5、15、25、35、45、55、65、75、85、95；每轮蚂蚁选择80只；为了剔除异常收敛，每轮均进行10次演算求出平均值，作为该轮稳定的最短路径。综合考虑状态的聚合度、觅食结点个数、随机小概率事件，通过编程和建立数据库，模拟最优路线结果如下：
1354261 其中Lmin=45.2
3 实例分析
为了验证本算法的正确性，在Matlab平台上对其进行了仿真实验。建立如下数学模型，选取福州市某配送中心10个点进行配送，并且要求路径最短，如表5所示，10个点经过坐标化后是接均型分布，小概率事件选取0.5，人工蚂蚁选取80只，每轮进行10次迭代并取平均值。结合迭代运算，得出最优路径如下：
23456810912
蚁群算法可以比较完美地解决配送路径问题，但也存在不足之处，特别是在信息不完全的情况下，比如两点之间有捷径，模拟最优线路与实际线路会有偏差，同时算法可能会陷入局部最优，可以通过控制收敛速度和加快趋向最优路径对蚁群算法进行优化。
参考文献：
[1] 李云清. 物流系统规划[M]. 上海：同济大学出版社，2004.
[2] 秦固. 基于蚁群优化的多物流配送中心选址算法[J]. 系统工程理论与实践，2006（4）：120-124.
[3] 魏娜. 关于物流配送中心选址优化问题研究[D]. 大连：东北财经大学（硕士学位论文），2006.
[4] 高雷阜，等. 基于最大最小蚂蚁系统的物流配送中心选址算法的研究[J]. 运筹与管理，2007（12）：42-46.
中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)11-2717-02
医药物流是指医药器械从医药配送中心分发、配送到各个医院和医疗中心的过程,甚至包括通过医院到达消费者(患者)手中的过程,其中所产生的物流成本是医药器械成本的重要组成部分。降低医药运输成本是减少患者医疗负担的重要途径之一。而药物配送实际上就是旅行商问题[1]。遗传算法作为一种求解问题的高效并行全局搜索方法,成为目前解决NP完全问题的较为有效的方法之一。
1 旅行商问题与遗传算法
1.1 旅行商问题原理
旅行商问题(Traveling Saleman Problem,TSP)是VRP[2]的特例,已证明TSP问题是NP难题。旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题。TSP问题可描述为:给定一组n个城市和它们两两之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次而且总的旅行路径最短。TSP问题的描述很简单,简言之就是寻找一条最短的遍历n个城市的路径,或者说搜索整数子集X={1,2,…,n}(X中的元素表示对n个城市的编号)的一个排列π(X)={v1,v2,…,vn},使取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。
1.2 遗传算法基本原理与描述
1.2.1 算法原理
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法,由美国J.Holland教授提出,其主要内容是种群搜索策略和种群中个体之间的信息交换,搜索不依赖于梯度信息。该算法是一种全局搜索算法,尤其适用于传统搜索算法难于解决的复杂和非线性问题。
1.2.2 算法描述
该算法包括以下6个基本要素:
1) 编码:遗传算法不能直接处理解空间的数据,必须通过编码将它们表示成基因型串数据。常对参数采用二进制编码,编码当作一条染色体,编码前应先量化[3]。
2) 生成初始种群:初始种群的个体通过随机方法产生,且对应研究问题的一个解。
3) 评估适应度:遗传算法在搜索过程中用适应度来评估个体的优劣,并把它作为遗传操作的依据。适应度函数常取非负数,且适应度增大的方向与目标函数的优化方向一致。
4) 选择:根据适者生存的选择原理,从当前种群中选择生命力强的个体(即适应度高的个体),产生新的种群。适应度越高的个体,被选择的机会就越大,但并不意味着适应度高的个体一定会被选择[4]。
5) 交叉:将选择出的个体存入配对库,用随机的方法进行配对,以产生新一代的个体。
6) 变异:在交叉过程中可能丢失一些重要的遗传信息(特定位置的0或1)1必须引入适度的变异,即按一定的概率改变染色体基因位。
2 优化路径遗传算法的构造
针对优化物流配送路径的特点,本文构造了求解该问题的遗传算法。
2.1 初始种群的生成与编码方法的选定
随机生成规模为N的初始种群。采用巡回旅行路线所经过的各个城市的顺序排,列来表示各个个体的编码串,这是TSP问题最自然的一种个体编码方式。例如对于一个10个城市的TSP:2-5-3-4-7-1-6-8-9(可简单表示为[253471698]),表示从城市2出发依次经过城市5,3,4,7,1,6,8,9,然后返回城市2的一条路径。这种编码方式满足TSP问题的约束条件,保证了每个城市经过且只经过一次,在任何一个城市子集中不形成回路[5]。
2.2 适应度评估
对于某条染色体,设其对应的配送路径方案的不可行路径数为Ni(Ni=0表示该个体对应一个可行解),其目标函数7值为Td,则该个体的适应度可用下式表示:,式中α为对每条不可行路径的惩罚权重,可根据目标函数的取值范围取一个相对较大的正数(α值太小则会影响适应度的比较)。
2.3 遗传操作
2.4.1 选择操作
选择将使适应度较大个体有较大的存在机会,而适应度较小的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制,令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额fi/Σfi。作为其被选中的概率Psi。这方法既可保证最优个体生存至下一代,又能保证适应度较大的个体以较大的机会进入下一代。
2.4.2 杂交操作
采用顺序编码法后,若用简单的一点杂交或多点杂交,必然会导致未能完全遍历所有城市的非法路径。如城市9的TSP问题的两个父路径为:1 2 3 4 |5 6 7 8 9; 9 8 7 6 |5 4 3 2 1,若采取一点杂交,杂交点随机选为4,则杂交产生的两个后代为:9 8 7 6 |5 6 7 8 9;1 2 3 4 |5 4 3 2 1,显然,这两个子路径均未能遍历所有9个城市都违反了TSP问题的约束条件,为解决这一问题,既要进行杂交操作,又要满足约束条件,就必须对杂交操作进行修正[6]。关于路径表示的常用的几种修正的杂交操作方法为:
1) 部分映射杂交(PMX, partially-mapped cross-over)。
在PMX操作中,先随机地在父体中选取两杂交点,并交换相应段。再根据段内的城市确定部分映射。在每父体中先填入无冲突的城市,而对有冲突的城市分别执行这些部分映射直到填入无冲突,则获得杂交后的两后代。例如,两父体A1、A2为('|'标记截断点) A1=(2 6 4 |7 3 5 8 |9 1), A2=(4 5 2 |1 8 7 6 |9 3)。则由交换段确定的部分映射为:7-1,3-8,5-7,8-6,先交换相应的段得B1=(### |1 8 7 6|##),B2=(### |7 3 5 8 |##)。此处'#'表示城市待定。再从各自的父体中填入无冲突的城市得B1=(2#4 |1 8 7 6 |9#),B2=(4#2 |7 3 5 8 |9#)。个体B1第一个'# '处原处为6,映射到8后仍有冲突,再将8映到3填入。第二个'#'处原处为1,映射到7后仍有冲突,再将7映到5填入。类似地求得B2。于是两后代为B1=(2 3 4 |1 8 7 6 |9 5), B2=(4 1 2 |7 3 5 8 |9 6)。这样,子代仍是遍历的,但每个子代的次序部分地由其父代确定。
2) 次序杂交(OX, order crossover)。
次序杂交的操作与部分映射杂交的操作非常类似。也是首先随机地在父体中选择两杂交点,再交换杂交段,其它位置根据保持父体中城市的相对次序来确定。例如,设两父体及杂交点仍为前述的A1和A2, A1=(2 6 4 |7 3 5 8 |9 1), A2=(4 5 2 |1 8 7 6 |9 3)。交换杂交段于是仍有B1=(### |1 8 7 6 |##),B2=(### |7 3 5 8 |##)。从B1的第二个杂交点开始,将路径依原次序排列,即: 9-1-2-6-4-7-3-5-8去除杂交段中的城市,得子路径9-2-4-3-5。依次顺序从第二个杂点开始填入得B1=(4 3 5 |1 8 7 6 |9 2),类似地有B2=(2 1 6 |7 3 5 8 |9 4),虽然, PMX法与OX法非常类似,但它们处理相似特性的手段却不同。PMX法趋向于所期望的绝对城市位置。本算法采用此方法交杂交。
3) 循环杂交(CX, cycle crossover)
循环杂交将另一父体作为参照以对当前父体中的城市进行重组。先与另一父体实现一个循环链,并将对应的城市填入相应的位置。循环组成后,再将另一父体的城市填入相同的位置。例如,仍考虑前两个父体路径A1=(2 6 4 7 3 5 8 9 1), A2=(4 5 2 1 8 7 6 9 3)。先从A1中取第1个城市作为B1的起始点,于是B1=(2########),由于后代中第一个城市都必须从父体相同位置的城市中选取,于是根据循环原则,2对应于A2中的城市4,而在A1中位于第3位,所以应有B1=(2#4######),又A1中城市4对应于A2中的2,于是组成了一个环。再将A2中剩余的城市填入对应的相同位置得到B1=(2 5 4 1 8 7 6 9 3),类似地可得到B2=(4 6 2 7 3 5 8 9 1),由此可见,循环杂交保持其父体串中城市所处的绝对位置。
3 算法实现和结果
下面对某市一医药公司的销售点的物流配送路径规划用遗传算法进行优化。该公司有56处销售点,通过路径规划希望找出最优路径以节省运输成本。
3.1 运行参数设计
本实验采用n城市的遍历顺序编码法,适应度函数取总长度Td的倒数(无惩罚函数)。选择机制是保留M个较优个体,在每一代运算中,个体被选中的概率与其在群体中的相对适应度成正比。杂交操作采用OX(次序杂交)法。为使算法尽快地收敛,在经过杂交变异操作后,增加了局部优化过程,提高个体对环境的适应。群体规模取56,交叉概率和变异概率分别取0.9和0.01, 最大迭代数2000。
3.2 实验结果
运行环境:操作系统Microsoft Windows XP;仿真软件:MierosoftVisualC++6.0。
在实验计算中采用以上设定参数对该公司配送路径问题求解,所得到的优配送化路径最优长度为862,用时126秒,迭代次数1528。得到的路径线路如图1所示。
4 结论
在此也可以看到,运用遗传算法解决实际问题,算法是使用参数的编码集,而不是参数本身,参数的选择十分方便;遗传算法与其他计算机算法不同,相比之下,它比较具有随机性而不是稳定性,遗传算法是在点群中,而不是在一个单点寻优。因此利用遗传算法解决实际问题需要选取大量数据,通过多次实验的数据分析不断改进算法和设置参数来求得更优的结果。用遗传算法求解组合优化问题具有巨大的优越性[7]。非常有助于物流企业根据自己的实际情况科学、有效地制定物流决策,降低风险,降低成本,提高经济效益和自身的竞争力。
参考文献:
[1] 田贵超,黎明.旅行商问题(TSP)的几种求解方法[J].计算机仿真,2006,23(8):153-157.
[2] Holland J H.Adaptation in natural and artificial systems[M].Ann Arbor,Ml:The University Michigan Press,1975.
[3] 余有明,刘玉树.遗传算法的编码理论与应用[J].计算机工程与应用,2006,42(3):86-89.
[4] 陈国良,王煦法,庄镇泉,等.遗传算法及其应用[M].北京:人民邮电出版社,1996.
一、问题的提出
2003年，党的十六届三中全会上提出“建立绩效预算评价体系”，七年来，我国已经在绩效预算评价研究上取得了一定的成果，学界对绩效预算的关注程度也逐渐提高，各级地方政府纷纷开展了绩效预算的理论探索和试点实施工作。但是关于绩效预算的一些基础问题却没有得到明确的解决，比如绩效预算的内容包括哪些？各部分内容的逻辑关系是什么？推行绩效预算的根本目标是什么？具体目标是什么？为了实现各阶段的目标，哪些部门应当完成哪些工作？如果这些问题没有搞清楚，那么实施绩效预算就像开了一艘没有罗盘的轮船，不知道前进的方向在哪里。正是由于这些问题没有得到回答，目前我国在实施绩效预算过程中遇到了许多障碍，例如绩效预算实施受到一些部门的抵触、绩效预算评价体系不规范、绩效评价没有贯穿预算全过程、绩效评估工作流于形式等。本文的研究目的就是试图对上述一系列基本问题给出一个清晰的回答，对如何正确、有效、规范地实施绩效预算给出一个明确的可行的路径规划。
二、绩效预算包含内容的逻辑关系界定
1.绩效预算所包含的内容
绩效预算的内涵是：绩效预算是以结果为导向的，注重预算的效率和效果的科学化、民主化的预算。它的根本目的是试图学习私人部门的绩效管理和运行方式，以更有效率的方法为公众提供公共产品。但仅仅了解绩效预算的内涵是不够的，我们同时应该弄清楚绩效预算的具体内容，及其各方面内容之间的逻辑关系，以理解各种情况下所指“绩效预算”的真实意思。笔者认为绩效预算的内容应该包括以下几个层次：
(1)将绩效理论应用于财政资金支出结果的事后评
(2)将绩效理论应用于财政资金的分配、使用、结果
(3)将绩效理论应用于预算部门自身的工作评价
(4)将绩效评价的结果应用于绩效沟通和绩效管理
(5)将绩效理论扩展应用于政府行政管理的全过程
2.绩效预算所包含内容的逻辑关系界定
绩效预算是一个系统工程，短短四个字却包含了十分丰富的内容。绩效预算应包括5个层次的内容，他们之间是循序渐进，由浅入深的关系。第一个层次只是对财政资金支出结果的评价，是实施绩效预算试水阶段。第二个层次是对预算的全程评价，主要目标是将绩效方法引入到预算资金的分配和使用阶段，实现预算全过程的绩效管理。第三个层次是对预算工作自身的评价，即预算工作的的绩效评价，它和第一和第二个层次的绩效评价对象不同，预算绩效评价的对象是预算工作或者预算部门自身，而第一、二层次的绩效评价对象则是预算资金。第四个层次则是在获得全面的绩效预算评价结果的基础上，有效地应用结果，切实发挥绩效预算结果的价值，促进部门之间的预算工作的沟通，并为下一年度的预算制定作出指导。绩效预算的第五个层次则是将绩效管理的思想应用到政府的各个部门和各项行政工作中，这既可以说包括在绩效预算之中，因为它构成了绩效预算实施的环境，也可以说已经超越了预算本身，成为政府的绩效管理。
三、我国实施绩效预算的目标规划
在了解了绩效预算的内涵与内容之后，我们进而探索绩效预算是否可以在我国实施以及用它达到什么样的目标。至于可行性和必要性研究，许多学者已经从理论和实践方面给予了充分的论证，此处不再赘述。此处笔者试图探索绩效预算的根本目标，及其短期和长期的目标，以为绩效预算的实施提供明确的行动方向和优先次序。
1.根本目标
政府实施绩效预算的根本目标就是对预算过程实施科学化管理，追求财政资金的使用效率，并最终更加有效地向公众提供公共产品。
2.短期目标
在绩效预算实施的过程中普遍面临的问题是绩效评价指标的选择，尤其是定性指标。相比较而言，项目预算比一般预算的结果和产出更容易定量化，更容易测量和评估。所以在短期，我们主要的主要目标是实现项目预算的全程绩效管理，具体分为以下几个目标：
(1)实现各地区、各部门项目预算的财政资金支出结果的绩效评价，建立和完善绩效预算评价指标体系，将绩效预算的理论和方法在政府部门普及开来。
(2)将绩效理论应用于预算资金的分配环节。即要求部门在申请项目预算时提交绩效预算计划报告，其中应包括该项目预算的绩效目标，具体的绩效评价指标，评价方法，以及该项目的工作程序、方法、所需资源等。由财政部门和相关主管部门共同对该项目的绩效预算计划报告进行绩效预测和评估，决定是否拨款和拨款数量的多少，实现事前的绩效评估。
(3)将绩效预算应用于预算的执行环节，用事前的绩效计划报告对项目的实施进行全程监督。不仅要看花钱的进度，更追踪促实际项目的实现的数量、质量；资监督源分配合理性、资金使用情况等，促进项目的按时、保质、保量的完成。
(4)在项目执行完成以后，由对该项目执行结果进行绩效评价。绩效评价的指标和方法主要依据初期项目预算申请部门提交的绩效预算计划报告中的各项指标；绩效评价的执行主体是财政部门、主管部门、专家学者和公众代表，公众对项目实施结果的评价应当是绩效评价的主要参考意见，注重公民取向。最终整理、分析出该项目的绩效评价总体结果，并将评价结果向公众公开说明。
3.中期目标
(1)实现对一般预算的绩效管理
在实现对项目预算绩效管理的基础之上，我们可以开始对一般预算进行绩效管理。这一预算的主要产出就是各单位的行政效率，行政人员工作技能，各单位提供特定公共产品的效率等。对一般预算进行绩效管理，其实是为政府部门实现全面的绩效管理奠定了基础。
(2)建立绩效评价结果与预算编制相结合的约束激励机制
在实现对预算过程实施全面的绩效管理的基础上，绩效评估的结果就应当开始发挥它的价值。通过对绩效评价结果进行分析，财政部门可以辨别各个部门预算执行的质量，因而可以为后期的预算决策提供科学指导。对于预算执行质量高的部门，给予激励，而对于预算执行质量差的部门给予指导，并且在后期的预算中调整预算计划。这样一来，就可以形成了预算决策、预算执行、预算评估的三位一体的激励约束机制。
4.长期目标
通过一般预算的绩效管理推进政府部门的全面绩效管理，完成绩效预算实施的制度环境改革。这一目标已经不仅仅局限于预算本身，而是扩展到整个政府行政管理体制的绩效改革。也就是说绩效预算的长期目标是以绩效预算为突破口，最终实现政府绩效管理，实现为公众更好地提供公共产品的目的。
四、我国实施绩效预算的路径规划
由于实现项目预算的全面绩效管理是绩效预算工作的当务之急，笔者仅就如何实现这个短期目标进行探讨。笔者认为我国实现绩效预算的路径，就是一条扫除前进障碍，提供有利条件的路径，其实也就是为绩效预算的实现提供各种支持的这样一条路径。要成功地实现绩效预算的短期目标，主要需要以下几点现实支持：
1.思想支持
首先要突破传统的行政观念约束，转变政府行政人员的思想，遏制官僚作风，树立公共产品提供者和负责人的意识；其次要突破传统的预算观念，加强对绩效预算的宣传和推广力度，树立一种全新的要产出、要效果的预算意识；第三，要增加公众参与预算的机会与能力，真正体现公众作为公共产品需求者的角色，提高公众对预算决策、预算执行、预算评估的参与度，因为一项预算执行好坏的最终评判标准是公众的满意度。最后，绩效预算还需要领导者的高度支持，因为绩效预算的改革必然会影响到部分既得利益者，必然会跟新兴的模式作顽固抵抗，这就需要领导者有足够的决心和魄力，推进绩效预算的顺利进行。
2.法律支持
完善预算法案，将绩效预算思想融入法案，以法律的形式固定下来。在绩效预算的法案中应当明确指出负责绩效预算工作推进的具体机构，明确绩效预算的主体、目标、绩效评价体系构建原则、绩效评估工作的要求、绩效评估结果的应用等等。这样一来，绩效预算就不会仅仅是一句口号，一种意向，一种提倡，而是成为一项方针，一项具体的有明确负责人和明确执行计划的改革任务。这样，各个部门才能明白明确什么是绩效预算，目的是什么，各个行政人员必须按照何种标准完成何种事项，以及相应的奖惩措施是什么。法律支持能够让绩效预算的实施有法可依，增强绩效预算实施的规范性和强制性。
3.技术支持
绩效预算的核心就是构建规范、科学的财政资金支出的绩效评价体系。首先要构建的便是项目预算的绩效评价体系。在评价体系构建过程中应当注意以下几点：
首先，当一些指标难以确定，或者指标评价之间存在冲突时，坚持以公众的满意度为最根本的评价标准。
其次，改变目前各地区、各部门各设一套体系，导致绩效评价水准参差不齐，绩效评价结果可信度差，可比性较差的局面。中央部门应该在百花齐放的同时，博采众长，集中力量研究出一套质量较高的，并且可以在全国普遍使用的绩效评价体系，使得绩效评价更加规范化，统一化。另外，当制定一套固定的针对各个部门和各项支出的评价体系存在困难或者不合理性时，我们应当确立一些指定评价指标的原则、规范和指导思想，这样就可以在遵循一定根本原则的基础上，又能够随机应变，适应各种特殊情况。
第三，不同部门应设置不同的评价标准、模式，有的侧重于定量分析，有的侧重于定性分析。由此设置相应的共性指标，与个性指标。主要从预算执行情况、财务管理状况、资产管理情况以及衡量绩效目标完成程度的社会效益和经济效益等方面评价。对适用于不同部门的个性指标，要针对项目实际，结合部门职能和项目管理目标，根据评价的目的，按照一定的程序来制定评价指标和确定评价标准。
4.人员支持
实现项目预算的全面绩效管理需要大量的人员支持。一方面要培养绩效预算、绩效管理的专门人才，建立绩效预算学者库，专门对绩效预算的相关理论进行研究。另一方面要对行政人员进行绩效预算知识的培训，使之具备绩效预算操作的技能。除此之外，我们也更应当重视对公众的培养，提高公众对绩效预算的参与积极性和参与能力，因为科学的绩效预算的评价离不开公众的广泛和深度的参与。
5.制度支持
成功地实现绩效预算同样需要相关的制度支持。在实现短期目标的过程中，我们应当完成对以下制度的改革：进一步完善目前的部门预算制度；完善国库集中收付制度；改革政府采购制度；完成会计制度由收付实现制向权责发生制度的过度；完善预算的监督制度，并且对预算过程实行问责机制，向单位问责，向个人问责；最后，要增加预算的公开透明度，对于预算信息哪些应该公开，公开到什么程度，政府应该做出明确的要求。
当然上述的每项制度的变革都是非常艰辛和复杂的过程，必然会对绩效预算的实施形成阻力，但是它并不能够阻止绩效预算的脚步。即使制度环境不是那么优越，条件不是那么成熟，绩效预算的推进也势在必行。等待，只会延长上述一些不合理制度存在的时间。笔者认为，绩效预算既是一种目标，也是一种手段，可以成为改革不合理制度的压力和动力，最终在实现绩效预算的过程中也完成了制度的改革。
参考文献：
[1]马国贤: 政府绩效评价[M] . 上海:复旦大学出版社,2005.
[2]彭锻炼 左武:推行政府绩效预算管理改革的难点与目标[J]. 中南财经政法大学学报,2009,(6)
[3]白景明:全面认识绩效预算[J].中国财政.2009.(24).
本文首先对车辆路径规划问题和算法应用，以及运输货损理论的研究现状进行充分调研。在此基础上，对鲜花配送车辆路径规划问题所关注的目标进行分析，除常规的车辆使用数量和车辆行驶里程外，加入了鲜花行业特有的运输货损目标，应用遗传算法与节约算法相结合的两阶段启发式算法，结合企业物流配送现状及远期发展规划，得出一种鲜花配送车辆路径规划的可行方法。
1.车辆路径规划理论与研究现状
作为物流配送中的一个热门问题，车辆路径规划问题最早由Ramser和Dantzing提出，其可以描述为：在一定数量的配送中心和客户构成的节点网络中，通过安排合适的行车路线，使配送车辆从配送中心取货并根据预先设定的路线至每个客户点卸货，完成各客户点所需求的货物配送量。
1.1车辆路径规划理论
1901年，美国的John F.Crowell在政府报告中最早提及物流的概念，用于分析影响农产品流通的不同因素和相关费用。随着理论研究和实践应用的不断深入，为统一对物流的认识，需要对其进行准确的规范化定义。中国的物流术语标准将物流定义为：物流是物品从供应地向接收地的实体流动过程中，根据实际需要，将运输、储存、流通加工、包装、装卸搬运、配送、信息处理等功能有机结合起来实现用户要求的过程。
1.2车辆路径规划问题研究现状
VRP是一类具有极强应用性的优化调度问题，它在物流配送、交通运输等领域获得了广泛的应用，其范例大量存在于日常生活之中。由于VRP在应用上的广泛性和经济上的重要价值，自1959年由Danzig和Ramser提出以来，一直是学界研究的重点和热点问题，50多年来已经取得了大量的研究成果。从解法上来看，对VRP的求解算法主要可分为精确算法和启发式算法，而最近10年来，对于VRP的求解算法研究，主要集中在现代启发式算法。
2.车辆路径规划问题算法分类与概述
自从VRP问题被提出以后，由于其同时具有理论价值和现实意义，VRP问题迅速受到越来越多研究人员的重视，力求能够发现求解各类VRP问题的高效算法。按照VRP问题发展与研究过程来看，算法大致可分为三类，即精确算法、经典启发式算法和现代启发式算法。
通过对大量文献的分析研究，归纳得出三类算法的优势与劣势对比如下：
精确算法，能够求出问题的精确解，当问题规模较大时，往往会导致计算量过大、存储信息太多等问题，降低了计算效率，主要适用于较小规模的简单路径规划问题求解。
经典启发式算法，不断对解的结果进行优化，能够保证每次迭代后求得的解都是当前最优解；计算速度快、复杂度低，容易陷入局部搜索，可能无法跳出局部范围找到全局最优解，与其他算法结合，广泛应用于复杂大规模路径规划问题。
现代启发式算法，具有能够跳出当前搜索领域而进行全局搜索的能力；结构开放性，与问题无关性，应用理论要求较高，针对不同问题的研究还不完善，广泛应用于复杂大规模路径规划问题。
3.考虑运输货损的鲜花配送车辆路径规划问题概述
中国鲜花行业伴随供给侧结构性改革与消费升级的浪潮，近几年也在发生翻天覆地的变化。
随着线下连锁店数量逐渐增加，物流配送压力与成本也不断上升，配送车辆路径规划便成为亟待考虑并解决的问题。对于中心仓库-连锁店运营模式，采用巡回配送方式更优于点对点的直送方式。通过对运输货损研究的分析，一般整个配送过程中的货损可分为两部分：一是在配送运输过程当中的损耗，由生鲜品时间累积产生损耗和路况引起的颠簸、碰撞损耗组成；二是在客户点装卸货物时，由温度变化与时间累积产生的损耗和装卸操作（例如野蛮操作）引起的货损损耗组成。
3.1参数定义及约束条件
设有n个客户节点，每个客户节点的需求量为（i=1，2，…，n）；有m辆配送车辆（型号种类完全一致），每辆车的最大载重量为Q。客户i到客户j的距离为， 0表示配送中心，则配送中心到客户点的距离为 （i=1，2，…，n）。由于一条线路上所有客户点由一辆车进行配送，所以要求考虑货损量的前提下，每条线路客户点需求量之和不超过每辆车的最大载重量。
4.小结
通过对考虑运输货损的鲜花配送车辆路径规划问题进行概述，介绍了中心仓库-连锁店运营模式下，车辆路径规划问题的多目标函数。本文求解的VRP问题属于大规模VRP问题，参数定义和约束条件与一般VRP问题类似，同时根据问题实际情况增加了货损相关的各类参数、例如多种货物损耗比例等。具体建模阶段，遵循“化繁为简”思想以及多目标函数求解思路，将目标函数通过各自独立的成本转换因子转化为成本相关的目标函数，最终通过叠加得到了以总成本为目标的车辆路径规划单目标函数，从而确定最经济鲜花配送路径。
参考文献：
[1]丁秋雷，胡祥培，李永先.求解有时间窗的车辆路径问题的混合蚁群算法[J].系统工程理论与实践，2007，10：98.104.
[2]刘勇，崔炳谋，王小东.物流配送路径优化问题的模型及改进混合算法[J].物流科技.2008（4）：88-90.
[3]李大卫，王莉，王梦光.遗传算法在有时间窗车辆路径问题上的应用[J].系统工程理论与实践，1999，8：65.69.
