时间：2022-06-18 13:11:38
开篇：写作不仅是一种记录，更是一种创造，它让我们能够捕捉那些稍纵即逝的灵感，将它们永久地定格在纸上。下面是小编精心整理的12篇路径规划，希望这些内容能成为您创作过程中的良师益友，陪伴您不断探索和进步。
Key words:distribution regional division; distribution vehicle routing optimization; algorithm
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 蚁群算法如结合其他启发式算法,建立混合算法,能够解决许多现实问题,达到较好运算效果,结合具体问题,可以深入研究。
4 本文的局限与进一步研究的方向
关键词:移动多智能体;全局规划;局部规划
中图分类号: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.
[2] Nilsson N J. Princip les of Artificial Intelligence[M].Berlin, Ger2 many: Sp ringer,1980.
移动机器人遗传算法完全遍历路径规划
1引言
完全遍历路径规划（ Complete Coverage Path Planning， CCPP）是一种特殊的路径规划，它要求移动机器人在满足一定的指标下完遍历目标环境中的可达区域。在机器人的许多应用领域，大都需要用到遍历路径规划算法，例如军事用的地雷探测、家居及办公环境的地面清洁、不同应用领域地图的创建等。在这些应用中要求机器人覆盖环境中所有未被障碍物占据的区域。按照对环境知识的了解，在已知环境覆盖算法中让清洁机器人规划出一条能走过环境中的所有地方并目.是代价最小路径，这个时候的问题就相当于旅行家问题，未知环境的覆盖要求清洁机器人必须借助身体上携带的不同类型的传感器来感知周围的环境并进行规划。
为克服上述路径规划中存在的问题，本文比较了基于遗传算法的完全遍历路径规划方法的优缺点，提出了基于遗传算法与单元分解法、启发式搜索和障碍物逼近算法结合的完全遍历路径规划新方法，将该方法应用于清洁机器人的完全遍历路径规划，与基于其他算法的路径规划方法进行比较，在多个性能指标上都得到了改善与提高。
2完全遍历规划性能指标
移动机器人的完全遍历路径规划常用的性能评价指标有遍历面积百分率，遍历重叠率。
（1）遍历覆盖率，是指机器人沿可行轨迹线遍历完成后，己遍历面积与可达区域面积的百分比。
（2）遍历重叠率，指所有遍历重叠面积之和与可达区域面积的之比的百分数。
为了保证相邻区域之间不留有遍历盲区，相邻遍历区域必须有一定程度的重叠，显然，
重叠区域越小越好，但因受机器人本身的系统误差，定位误差，控制精度以及环境状态的影响，重叠区不可能太小，如果一个机器人性能越高，则遍历重叠率能控制在很小的范围内。
从遍历重叠率，还可以推出未遍历面积百分率，它指机器人沿着可行轨迹线遍历完成后，未遍历面积与可达面积的百分比。
如果一个机器人性能越高，则遍历覆盖率越高，遍历重叠率越低，遍历效果越好，本文中主要结合遍历重叠率和未遍历面积来综合评价完全遍历路径规划。
3基于遗传算法的完全遍历路径规划
本文的环境地图采用几何表示法表示，即用点、线及其组合来表示环境中的特征，并用参数来表明各个特征在环境中的具置。将地图进行Boustrophedon单元分解后，地图将由若干障碍区和若干遍历区组成。电子地图则表示为各个区域信息的集合，而其中单个区域的信息包括区域的属性（障碍区属性或遍历区属性）及区域顶点的坐标。通过 Boustrophedon单元分解，环境可以分解为如图 1所示的若干遍历区和障碍区。
如图1所示，区域 2和区域 5之间的连通距离是不方便求解的，本文通过定义一个距离来表示两者之间的实际距离。虽然这个距离与实际距离之间有一定的差距，但距离值的大小趋势是一致的，而且距离的定义主要考虑了两个区域之间的直线距离、区域之间的连通关系、区域之间的障碍物情况。对于非毗邻关系的区域之间的距离，我们用D%= bDJN%来表示。其中， b是一个可调系数，可以通过仿真来调整该值以得到一个较好的数值；D为环境中两个区域之间的直线距离矩阵，对于该表达式中的各个参数， D、N可以根据划分后的区域的边界信息来确定，而J需要通过下面的算法实现。
由图2我们可以得到矩阵A
aij = 1表示遍历子区域i和j毗邻，aij = 0表示不毗邻。矩阵A为对称矩阵，其对角线的元素值为0，即不存在通过一次连通的路径连通区域1与它自身。aij = 1表示存在一条从区域i到区域j的一次连通路径，如a12 = 1，从图 2看出，区域1、 2存在一次连通路径。那么如何得到非一次连通的区域之间的连通关系呢？我们可以通过求矩阵 A的n次幂来得到两个区域之间的n次连通关系。对于i、j、k三个区域，如果区域i和区域j连通，区域j和区域k连通，则区域i和区域k连通，即当元素aij为非零值，ajk也为非零值，则通过计算
得到区域i和k的有几条连通路径。图2中各区域之间的连通关系矩阵如下：
在电子地图中两个遍历子区域的最近顶点分别为 A（ x i ， y i ）、 B （ x j ， y j ） ，判断两者之间的障碍物个数就是判断AB连线通过的障碍物个数。障碍物顶点在向量AB的顺时针方向还是在逆时针方向可以通过向量的叉乘来判断，即
电子地图中遍历子区域之间的障碍物数矩阵 N如下：
为了只保留对角线元素为 0，将矩阵 N的非对角线元素加1，得到规格化后的障碍物矩阵N。
距离矩阵 D表示遍历子区域之间的实际距离，其元素dij为子区域i和j的最近顶点之间的距离，对于毗邻区域的距离值定为a，非毗邻区域的距离值由电子地图根据区域坐标定出。图 1区域之间距离矩阵 D实测如下：
通过对障碍物矩阵、距离矩阵、连通矩阵的相同位置的元素相乘，再对非一次连通的区域距离乘以系数b，得到一个重新定义的综合距离矩阵D'，其中
图1区域综合距离矩阵D'如下：
4仿真研究
基于本章提出的完全遍历路径规划算法，进行了大量的仿真实验。下面是对图3的仿真地图完全遍历结果。
经过大量地图的仿真表明，该遍历算法的覆盖率达到90%以上，有的甚至达到95%以上，而且重复率在10%以下。对于不同的地图覆盖率和重复率是不同的，不过对大多数地图而言，该算法是高效的、实用的，具有很强的适应性。该完全遍历算法特点是系统要处理的信息量很少，机器人实时性控制更强。特别是提出了基点这一重要概念，使得在未知环境中实现完全遍历更有效、更方便。
5结论
本文根据遍历环境内区域关系和区域连通图，将已有的连通图补充为完全连通图，并根据区域信息和连通信息定义一个区域之间的距离矩阵，赋予区域之间的连接权值。根据距离矩阵，采用遗传算法对区域的遍历顺序进行优化。仿真研究表明，该方法用于不确定环境下的移动机器人遍历路径规划，不但能保证遍历所有可达工作空间，并且规划的路径较短、路径重复率小，具有较高的规划效率。
参考文献：
[1]丁学恭.机器人控制研究[M].浙江大学出版社，2006.
[2]杨高波，元波.精通MATLAB7.混合编程[M].电子工业出版社，2006.
关键词：精英策略；蚁群算法；配送中心；信息素；路径
中图分类号：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.
[5] 许慧，王正友，杨欢庆. 蚁群算法及其聚类应用[J]. 矿山机械，2007（1）：115-117.
［关键词］ 绩效预算 目标路径
一、问题的提出
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).
[4]孔志峰:绩效预算论. [M].北京:经济科学出版社.
1、蒋巷村——农业起家、工业发家、旅游旺家
蒋巷村以农业起步，在先天农业条件较差的情况下，上世纪60年代通过大力治水改土工程改良土地，实现农业的快速发展；80年代，蒋巷村瞄准市场先机，通过自筹资金发展建材加工业，迅速跃升为该省的龙头产业，提高了村庄经济实力；进入新世纪，蒋巷村在大力巩固拓展工业的同时，以工业发展带来的经济效益反哺农业，打造农民新居、农业规模化生产以及生态种植园，并建立起一系列景点设施，发展乡村生态旅游业。蒋巷村的成就与当地政府扶持和推广分不开。早期农业经营分散，规模效益不高，当地政府及时提供涉农优惠政策，引导蒋巷村依托成立农民专业合作社组织，带动了广大农户增收。工业方面，当村级龙头企业遭遇金融危机以及其他企业的激烈竞争时，政府部门主动对接企业，实行增值税转型政策助推企业转型升级，将其推入一个新的发展阶段。旅游业方面，该村旅游资源并不突出、旅游吸引力较低，政府一方面大力推广宣传，一方面积极开展旅游业税收优惠措施，支持和鼓励企业开拓市场，大力扶持其乡村旅游品牌。蒋巷村在资源条件相对贫瘠的情况下，走出了一条“改天换地、农业起家、工业发家、三产协同”的创新发展之路，以农业为基础、以工业为重点大力发展经济建设，并通过工业经济反哺农业、旅游业的发展，实现了一、二、三产业的互动发展，带来经济效益的良性循环。
2、大山村——本底良好、政府拉动、旅游慢村
早期大山村由于处地偏僻交通不便，经济发展缓慢，但生态环境保持良好，2005年高淳确定“生态立县”的发展方向，重点打造“国家生态示范区”，在此机遇下大山村走上了一条快速发展的生态旅游转型之路。在政府主持和出资下，大山村积极开展基础设施建设、对建筑风貌进行改造，打造田园风光特色，扶持农家乐专业户，一跃成为本省内的乡村旅游示范点。2011年，随着桠溪镇被评为“国际慢城”，大山村作为“国际慢城”的核心组成部分，具备非常突出的发展条件和优势。通过实施新农村建设工程、调整农业产业结构、发展休闲农业，打造高标准的乡村旅游业。为保障旅游配套服务业的高水平化，桠溪镇政府出台了统一的农家乐资格认证标准，并出资对环境整治进行改善和提升。目前村内已建成16家特色农家乐，可同时接纳上千名游客，每户年均收入达30-40万元。该村还通过招商及合资的方式开发休闲精品旅游项目，打造特色旅游产品，扩大“国际慢城大山生态之旅”的影响力和知名度。大山村在本底条件和区域环境基础上，通过政府扶持，以“整体打造、标准管控和庭院经济”的重点，实现了旅游产业的跨越式发展。政府主导的整体打造有效地保证了旅游产业的整体质量，强调政府对旅游硬件设施的标准性把控有效避免了接待设施的参差不齐，推广庭院经济充分利用村民房前屋后的院落以及零星的土地、水塘，形成果蔬种植、家禽养殖、居住、餐饮接待等复合功能，打造出家家门前有绿树、户户门前有花香的生态经济循环发展模式。
3、张阳村——农业起步、发展苗木、拓展旅游
同大多数村庄一样，张阳村早期发展仍以基础农业起步，该村用地较为平坦，水资源丰富，气候温暖湿润，农田规模集中，粮食产量也较高。良好的农业条件为张阳村的发展打下了坚实的基础。70年代初期以前，张阳村依托10多个矿山宕口大搞矿业开采，以采石、采矿为主导产业，当时大量山体破坏严重、植被遭到砍伐，路面坑洼，造成了严重的污染。80年代，随着张公洞风景区的打造，部分村民意识到市场先机，上山挖来木桩制成盆景，受到游客青睐。越来越多的村民投入到苗木盆景的制作中，张阳村开始了规模化的苗木盆景栽培，在政府的帮助下，建立起专业的花卉苗木基地，取得了良好的经济效益和示范作用。随着花卉苗木品牌的扩大，以及张公洞、玉女潭等旅游景点的知名度上升，张阳村开始转型为乡村休闲旅游与自然观光旅游。2003年该村成立了花卉苗木专业合作社，开辟了1000亩的花卉盆景基地，打造以苗木、吊瓜、茶叶、杨梅、青梅、板栗等六大特色的种植基地5000多亩。培养出龙潭苑树桩苗木基地、伟达开心农场、瑞龙潭生态园等集观光旅游与农事体验为一体的旅游景点。张公洞、玉女潭的开发更是吸引了大量省外游客，张阳村前后投入4000多万实施美丽乡村建设，整治环境景观和旅游配套服务设施，形成了以景点观光、农业体验、养生度假为主的休闲旅游业。张阳村的发展路径经历了由农业起步，高污染的矿业开发治理到特色化农业生产再到休闲旅游业四个阶段，其特色在于依托良好的自然环境和独特的旅游资源，打造苗木盆景特色产业，借助景区效益推广乡村旅游品牌，并在此基础上以苗木产业为依托积极融入区域旅游的大圈子，形成了农业、苗木、乡村旅游三业并举的发展格局。
作者：刘方 单位：重庆市规划设计研究院
针对标准遗传算法解决机器人处于障碍环境下寻找最优路径局部寻优精度较差、规划效率低的问题，提出一种改进遗传算法的机器人路径规划方法。该算法采用一维编码表示路径， 构造了路径最优化的目标函数和适应度函数，利用多个种群拓宽搜索空间，提高了规划效率，采用保优选择策略，避免陷入局部最优。仿真结果表明，改进遗传算法比标准遗传算法路径规划质量高，能够获得平滑的低代价路径，稳定性好，是机器人路径规划的一种较好的方法，且具有一定的推广意义。
机器人路径规划问题一直是机器人学的一个重要研究课题. 也是目前研究的热点领域。机器人路径规划问题是指在有障碍物的工作环境中， 如何寻找一条从给定起点到终止点的较优的运动路径， 使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物， 且所走路径最短.本质是多约束多目标的最优化问题[1]。
采用智能优化算法求解航迹规划问题是目前使用的主流方法。文献[2]中，蚁群算法的机器人路径规划需要存储的信息多，在搜索过程中易出现停滞现象或陷入死循环;文献[3]中的人工势场法虽便于底层的实时控制，但缺乏全局信息，存在局部最优值的问题;文献[4]中，模糊推理法最大的优点是实时性非常好， 但是模糊隶属函数的设计、模糊控制规则的制定主要靠人的经验。遗传算法[6]已证明是一种全局搜索能力强的算法，具有强的鲁棒性，并行性，但大量实验结果表明，应用标准遗传算法对该问题求解时局部寻优精度较差，稳定性不好[6]。
对此，本文提出一种改进遗传算法的机器人路径规划方法，并进行了仿真实验，结果证明了该方法是有效可行的。
结束语
针对标准遗传算法解决机器人处于障碍环境下寻找最优路径局部寻优精度较差、规划效率低的问题，提出一种改进遗传算法的机器人路径规划方法，并进行仿真，实验表明该算法具有高的稳定性，并减少了陷入局部最优的可能，且规划出的路径精度更高。同时，提出的模型可引申应用于类似情况下的路线规划问题，具有一定的推广意义。
有些学者从微观经济理论的角度探索消费和投资的最优比率。例如,Phelps构建了不确定收入下的最优消费率[2]。基于这一模型,Merton以布朗运动模拟不确定收益,利用动态规划建模的方式,求出在连续时间假设下获得最大消费效用的消费和资产投资组合[3]。然而Merton的模型采用了Pratt的绝对风险厌恶度(absolute risk aversion)[4],即假设投资者的风险偏好是和年龄、财富无关的常数,从而把家庭总财富比率设计成常数。为了改进过于严格的常系数风险厌恶假设,Farhi和Pan-ageas假设投资者可以通过控制退休时间来调整劳动供给,从而实现最优消费和投资[5]。另外有些学者拓展了Merton等人的模型,如Hakansson和Richard研究了存在保险时的生命周期最优消费[6][7];Karatzas使用鞅方法研究了个人如何选择消费率来实现消费和财富效用最大化[8];Bodie等人探讨了退休期间的最优消费投资问题[9]。有些学者则从宏观经济学的角度阐述消费和投资对消费效用最大化的影响。李嘉图的古典消费理论强调了消费对经济的刺激。凯恩斯绝对收入假说认为消费主要取决于当期绝对收入,平均消费倾向(APC)随收入增加而减少。按此假说,一战后,美国人民收入增加,储蓄应随之增加。但是,Kuznets实证研究发现战后储蓄并未增加,长期APC稳定[10]。为解析上述矛盾现象,Duesenberry提出相对收入假说,家庭会比较其他家庭的收入,即相对水平,来决定自己的消费水平[11](P3)。相对收入假说的缺陷在于家庭的消费是短视行为,没有考虑未来收入。为克服相对收入假说存在的问题,Friedman提出了家庭将根据终生收入来决定消费的持久收入假说[12](P26-135)。内生增长理论被广泛用于分析投资和消费的最优分配。该理论假设在生产过程中的规模收益不变,即凸性生产技术,经济增长的决定因素是生产要素,生产率是由模型内生所决定的,而不是由资源、人口等外部因素决定。典型的内生增长模型有AK模型、Rebelo模型等[13]。
曾经有人质疑AK模型是否可以用来评估经济增长。Jones建立了技术为常数的AK模型,对函数关于物质资本和人力资本求最大值,并基于1950~1988年加拿大、法国、德国等15个OECD国家的时间序列数据,研究发现战后投资额同经济增长无关,并由此推断AK模型对投资和经济增长关系的预测是短期的或不正确的[14]。为了反驳AK模型不适用于研究经济增长的结论,McGrattan建立了技术为常数的AK模型,对函数关于消费和资本求最大值。McGrattan用1870~1989年11个国家的数据验证了投资率和经济增长之间的正相关关系,证明政府投资诱导政策会永久性影响经济增长[15]。McGrat-tan发现Jones之所以用AK模型测不出投资和经济增长的相关性,一是数据期限短,二是模型设计存在缺陷。McGrattan的模型假设如下:(1)代表性家庭选择投资和消费,从而实现生命周期效用最大化;(2)家庭有两种资本,分别是结构资本和设备资本,家庭收入来源于把结构资本和设备资本租给公司的租金;(3)家庭收入要向政府缴纳税收,因此政府政策可以影响投资产出比和劳动闲暇选择。这样一来,McGrattan就解释了Jones观察到的投资增加而产出稳定的短期离差,并从理论和实证角度验证了AK模型的有效性。本文在持久收入假设和内生增长理论框架下,研究经济增长的最优消费投资比率,从理论上指导国民收入的合理分配。之所以选择资本产出弹性为单位弹性的AK模型,是因为资本对发展中国家很重要。发展中国家可以通过购买技术先进的国家的设备得到知识,这种由投资带来的技术溢出可以加速整个国家的现代化。另外,由于行业间存在溢出效应,当资本提高某个行业的生产率时,与之相关行业的生产率也随之提高[16],所以不仅要考虑资本对单个行业的作用,还需要考虑资本的社会回报。Ljungqvist和Sargent建立的AK模型与本文有类似的目标函数yt=Akαt,也猜测了相同的值函数形式,并得到了类似的策略函数[17],但本文与之不同的是:第一,他们假设资本产出弹性大于零而小于1(0<α<1),从而使资本边际效用递减,通过数学推导发现资本收敛,而本文假设资本产出弹性等于1(α=1),从而使资本没有边际效用递减,通过数学推导发现资本不收敛,而值函数收敛;第二,本文考虑了资本折旧;第三,本文通过真实数据,再现改革开放以来消费和投资对提高社会效用的贡献。本文余下部分的结构安排如下:第二部分建立包含资本折旧率和贴现因子的最优消费模型,通过猜解求出策略函数,讨论了消费、资本积累序列的意义,并通过求导分析了各变量对值函数的影响;第三部分比较了不同贴现因子下的值函数,并用三维效果图展示了1978~2010年中国消费、资本和值函数的演变关系;最后是本文的结论。
模型
本文考虑生产单一商品的经济,此商品既可消费又可投资,投资以资本的形式体现,消费品和资本品可以相互转换。消费数量和消费投资比决定代表性行为人的效用,社会计划者的目标是通过政策引导消费路径,使代表性行为人在任意时期都能获得最大效用。经济增长由资本驱动,因此设生产函数为yt=Akt,其中A反映技术水平,yt、kt和ct分别表示在时期t的生产量、资本存量和消费。对于任意t期,有ct≥0,kt≥0;且初始资本k0已知。由此,可得模型:max∑!t=0βtln c(t)s.t.kt+1=yt+1-(δ)kt-ct, yt=Ak烅烄烆t(1)其中δ为资本折旧率,0≤δ≤1;β为贴现因子,0<β<1;βtln c(t)是消费效用。式(1)是终生消费效用,资本积累规则为下期资本的数量取决于本期的有效商品总供给和本期的消费。令f k(t)=Akt+1-(δ)kt=(A+1-δ)kt表示包含资本折旧的有效商品总供给,则式(1)可转化为:max∑!t=0βtln c(t)s.t.kt+1=f (kt)-ct,f (kt)=(A+1-δ)k烅烄烆t(2)式(2)目标函数的含义是代表性行为人追求一生消费的贴现效用最大化,其中消费ct是控制变量,资本kt为状态变量。由约束条件kt+1=f (kt)-ct,可得ct=f (kt)-kt+1,即控制变量可表示为状态变量的函数。求式(2)的最优解,就是在给定约束条件下,找到一个恰当的序列ct,k{t+1}!t=0,使目标函数∑!t=0βtln (ct)取得最大值。(一)猜解求值函数和策略函数为方便求极值,将式(2)由离散形式转化为连续形式,并定义值函数()V k为投资者在给定财富下所能达到的期望终生总效用。在竞争性均衡中投资者的效用得到了最大化,则根据汉密尔顿-雅可比-贝尔曼方程(Hamilton-Jacobi-Bellman equation,HJBE)可得:()V k=maxk'()ln [f k-k]'+β{V (k)}'()=ln [f k-g(k)]+βV [g(k)](3)式(3)中,k是当前时期的资本存量(相当于kt),k'是下一时期的资本存量(相当于kt+1)。g(k)是利用HJBE进行递归迭代的策略函数,且g(k)=k',表示计划者面临的决策为:究竟是应该用政策引导代表性行为人当期多消费一些,还是当期少消费,留作下一期的资本,从而使下一期能消费更多。()V k和g(k)都是连续可微的。根据动态规划理论,可猜测值函数的形式为:()()V k=E+Fln k(4)其中,E、F是待定常数。对式(3)和(4)计算一阶最优的必要条件,并根据式(2)可得:g(k)=k'=βF A+1-(δ)k1+βF(5)()c=f k-k'=A+1-(δ)k1+βF(6)式(5)是策略函数g(k)关于k的显式解,F是待定系数。(二)最优消费、资本累积序列令n=1,式(3)变成式(7)。由式(2)可知当t=1时,以下两式成立:V1()k=maxk'()ln f k-k[]'(7)V1()k=maxk'()ln f k-k[]'+βV0k()'(8)式(7)是目标函数(2)的最大值,即社会计划者最优问题中的值函数;式(8)表示代表性行为人一生的效用贴现值等于当期效用、未来效用的贴现值之和。当期消费和期末资本的选择c,k{}'产生了当期效用ln(c),下期的资本k'将按照策略函数g(k)来选择。此处可获得的最大期望效用是V k()',而k'的贴现值为βV0k()'。类似的,利用式(5)、式(3)逐期递归迭代可得到值函数Vn()k序列。对任意t期,有:Vn()k=∑n-1i=1(β)i-1 lnA+1-δ1+β()F+βn-1ln (A+1-δ)+ ∑n-1j=1j(β)j lnβF A+1-(δ)1+β[]F+∑ns=1(β)s-1()ln k由于0<β<1,根据级数理论容易证明:当n!时,Vn()k是收敛的,且其极限值()V k=limn!Vn()k就是无穷序列的唯一解。也就是说,得到的函数方程与式(4)的猜测完全符合。可以解出E=11-βln (1-)βA+1-[(δ)]+β1-(β)2lnβA+1-[(δ)],F=11-β。将E和F代入式(4)可得到函数方程(3)的具体表达式和相应的策略函数:()V k=11-βln (1-)βA+1-[(δ)]+β1-(β)2lnβA+1-[(δ)]+11-β()ln k(9)g(k)=βA+1-(δ)k(10)式(9)也就是式(1)的解。对于任意给定的k0>0,值函数()V k采用策略k'=g(k)=βA+1-(δ)k恒可取得最优值。回到式(1)的离散形式,对任意时期t(t≥0),当资本存量按策略kt+1=βA+1-(δ)kt逐步演变时,式(1)必定取得最优解。相应地,ct=1-(β)A+1-(δ)kt。综上所述,可得式(1)的最优消费、资本累积序列ct,k{t+1}!t=0为:ct=1-(β)A+1-(δ)ktkt+1=βA+1-(δ)k烅烄烆t(11)从式(11)可以看出:资本折旧率δ和当期消费ct以及下期资本kt+1负相关。资本折旧率反映了资本的使用成本,折旧率越大,资本越少,收入越少,可供消费也越少。对资本的良好维护,可以降低资本折旧率。宏观政策能改变折旧率,比如政府推出投资刺激政策,会使维护既有资本的成本高于重新投资,从而提高资本折旧率;再如,高利率增加贷款成本,导致生产者更倾向于用廉价原材料,产品耐用度降低,资本折旧率提高。贴现因子β和当期消费ct负相关,和下期资本kt+1正相关。贴现因子反映了资产预期总收入超出当期总收入的部分折现到当期末的值。贴现因子越小,代表性行为人越倾向于当期消费ct;贴现因子越大,代表性行为人越希望把消费推迟到将来。贴现因子是随机的、主观的,受真实的经济发展变化的影响,可以通过宏观经济政策引导贴现因子变化。比如福利保障制度可以提高当期消费者的信心,而提高利率会导致人们推迟当期消费。α=1时,AK模型y=Akαt的资本增长率kt+1kt=βA+1-(δ)更大,而且资本不收敛。0<α<1时[1 7],AK模型y=Akαt的资本增长率kt+1kt=αβAkα-1t更小,而且资本收敛。另外,根据方程(1)最优解的一阶必要条件可以断定,当且仅当ct+kt+1=Dkγt(D为常数,γ是大于零的任意实数)的形式时,即ct+kt+1必须与kγt成正比关系,AK模型才可能求出显式的最优解。
关键词：GPS手机导航；移动GIS；ArcGIS for Android；Dijkstra算法；最短路径
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）06-1294-05
Research and Application of Campus Navigation System Path Planning Based on Android
WU Qi1，LIN Jing1，YANG Jiang-tao2，3
（1.School of Computer Science and Control Engineering， North University of China，Taiyuan 030051，China； 2.Science and Technology on Electronic Test and Measurement Laboratory， North University of China，Taiyuan 030051，China；3.Key Laboratory of Instrumentation Science&Dynamic Measurement of Ministry of Education， North University of China，Taiyuan 030051，China）
Abstract： Regarding colleges and universities as the research objects and combining the digital campus with GPS mobile navigation system， a smartphone campus navigation system is designed by using the mobile GIS， Android platform and ESRI's ArcGIS Android API plug.Taking the campus of The North University of China as an example， the paper realizes the design of system architecture， describes data organization and the function of system. After comparing three kinds of classical shortest path algorithms， the authors select Dijkstra algorithm to achieve the shortest path selection in the smartphone campus navigation system.The implementation of the system provides a convenient， fast and intelligent navigation services for freshmen and visitors.
Key words： GPS mobile navigation； mobile GIS； ArcGIS for Android； Dijkstra algorithm； shortest path
随着高校校园的逐渐扩建以及对外交流的日益增多，来高校参观、访问的人也越来越多，但高校面积一般都很大，机构和重要建筑分布错综复杂，来访者要经过一番周折才能到达目的地。而且高校一般很少提供纸质的地图向来访者提供导航服务，因此，建立具有校园信息查询、智能导航服务等功能的系统，对高校提高人性化服务水平很有必要。
目前，国内高校对于基于PC的校园智能导航研究得比较多，如清华大学虚拟校园、华中科技大学校园导航系统。相比之下，大部分高校对Android系统上的校园导航都缺少研究，而今Android开发技术日新月异，将传统PC机的导航系统用Android技术实现已成为可能。随着移动通信的发展，手机已经不仅仅是解决通话的问题了，它渐渐成了集通信手持电脑于一体的移动计算工具，人们对手机所赋予的功能也已经扩展到分布式计算、移动位置服务等更高端的领域。导航软件在智能手机中的应用现已成为研究热点之一，越来越多的互联网应用被移植到智能手机中来，不但充分发挥数据业务运营商的潜力，而且极大的提高了用户对手机多功能需求的满意度，给人们的生活带来了方便。本课题基于这种考虑，设计了一种基于Android的校园智能手机导航系统。采用Dijkstra算法并利用GIS系统的空间数据特性，根据实际情况对任意两点间最短路径进行规划，在智能手机平台上实现了优化路径选择，为新生和校外来访人员提供了非常便捷的服务。本系统实用性强，易于开发、管理和升级，很好地解决了初次来学校的新生和校外来访人员所遇到的问题，既方便了新生和校外来访人员，又提高了学校的美誉度，具有很好的应用价值[1]。
1 系统开发理论基础
1.1 系统背景介绍
校园是大学生日常活动的主要空间。大学校园通常具有面积大、开放性强、建筑布局分散、各类设施杂乱等特点，校园地理信息相对来说比较复杂。这给校园内的每一个人尤其是对大一新生和校外来访人员带来诸多不便。因此，开发出一个为新生和校外来访人员提供校园信息服务的智能手机导航系统十分必要[2，3]。
1.2 移动GIS技术
地理信息系统（简称GIS）[4]是一种特定的十分重要的空间信息系统，是在计算机软、硬件系统支持下，对整个或部分地球表层（包括大气层）的有关地理分布数据进行采集、存储、管理、运算、分析、显示和描述的技术系统。移动GIS[5]是GIS（地理信息系统）从静态走向动态环境的重大发展，通过综合运用GPS的精确定位技术、便携移动设备（如掌上电脑、智能手机）、移动通信技术和GIS的空间信息处理能力，使野外工作者能够利用该系统实时地获取、存储、更新、处理、分析和显示地理信息。
1.3 ArcGIS for Android介绍
ArcGIS for Android将GIS的适用范围从办公室扩展到移动Web。时，ArcGIS for Android 将包括一个应用程序，您将能够从Android Market应用商店下载这款称为ArcGIS的应用程序。这个应用程序类似于已经的ArcGIS for iOS和Windows Phone应用程序。使用该ArcGIS应用程序，您能够浏览或ArcGIS Server提供的地图，并且利用程序中提供的工具进行搜索，识别位置和要素，测量线和面，以及编辑[6]。
2 系统设计
2.1 系统结构设计
本系统的结构分为服务器端的搭建和客户端软件的开发。使用ArcGIS Server在服务器计算机上搭建一套完整的地图服务，能够自己的地图和随时对地图信息进行编辑。客户端软件所要开发的功能有地图显示、地图定位、位置搜索、选择图层、路径导航等。系统功能结构图如图1所示。
图1 系统功能结构图
2.2 数据库设计
1）在图层中创建一个线要素Road，用于表示地图中的道路，再给该要素添加属性，为了方便与最短路径的计算，添加了道路的长度、限速值、行驶时间、端点信息等属性，OBJECTID是自动生成的用于唯一标识一个要素，SHAPE是指要素的类型，这里是几何类型，由于Road是线要素，所以系统也会自动生成SHAPE_LENGTH属性，默认表示该线段的几何长度，SpeedLimit和DriveTime都是自己另外添加的属性，为计算最短路径功能所用。如表1所示。
2）为了实现智能导航系统的选择图层功能，再向图层中添加一些生活常用的信息点，如医院、停车场、电影院、美食、银行、加油站、超市等，所以又添加了11个点要素：Food、Hospital、Shop、Park、KTV、Movie、Bank、Gas、Medicine、KFC、Mcdonald。每个要素各对应有自己的属性表，由于他们都类似，下面只列出其中的一个表，如表2所示。
表1 道路信息表
表2 医院信息表
3 核心问题和难点问题
路径导航功能是该系统最核心且最有难度的功能，路径导航就是用户设定一个起点（或以当前定位点为起点）和一个终点，系统采用一种最短路径算法来通过计算求出所设起点到终点的最优路径。在空间决策模型中，实现行驶最优路径的规划算法是空间决策的核心内容。只有构建出最优路径模型，系统终端获取的地理位置信息才能够最迅速快捷地用到校园导航路线的选择和优化中。
3.1 三种最短路径算法的比较与选择
本系统最核心的算法就是导航功能中的最短路径选择算法，为了选择最适合于本系统的最短路径算法，对常见的三种最短路径算法进行分析和比较，归纳出这三种最短路径算法的对比如表3所示。
表3 三种最短路径算法对比表
根据对比可以看出，Dijkstra算法在时间和空间上都是优于Floyd算法和Bellman-Ford算法的。不足之处就是Dijkstra算法不能处理含负权边的图。但根据本系统的实际情况，地图中的道路长度一定为正数，最短行驶时间也一定为正数，所以对于本系统来说，Dijkstra算法的这个缺陷可以忽略不计。因此，本系统选用Dijkstra算法来计算导航功能中的最短路径问题。
3.2 经典Dijkstra算法过程分析
Dijkstra算法也是求单源最短路径的算法，思想就是以源点s为中心，向外层层扩展，直到扩展到终点为止。算法思路如下[7]：
1）初始化：设源点s的dis[s]=0，除源点外的其他点dis[i]=无穷大，同时把所有的结点的状态都设为未扩展状态；
2）循环V次：在未扩展的点中取一个dis值最小的点i，把结点i标记为已扩展的，并对和点i相邻的每一个点j进行松弛操作，即更新dis[j]的值；
3）算法结束后，对于任意的点i，dis[i]就是源点s到结点i的最短距离。
算法的伪代码如下：
For each v ∈ V（G）
do dis[v] = INF；
dis[s] = 0；
把结点都插入优先队列Q
while Q非空 do
i = Q.top（）；
把i标记为已扩展
For each edge（i，j） do
If j未标记 and dis[j] > dis[i] + w[i，j] then
dis[j] > dis[i] + w[i，j]
如果用普通的邻接矩阵来存储图的结构，只能在每次循环里面再用一个循环来找出dis值最小的结点，那么时间复杂度将是O（V2）。所以为了优化时间，可以使用优先队列来保存所有结点的dis值，优先队列的内部实现一般都是使用二叉堆，所以建立和维护这个优先队列的时间复杂度是O（log|V|），所以Dijkstra算法的总时间复杂度是O（E+V*log|V|），空间复杂度是O（V+E）。
4 系统功能及其实现
4.1 系统主要功能
我们要实现的是校园智能手机导航系统，服务的对象是入学不久的新生和初到校园的校外来访人员，所以此系统的设计应遵从“界面直观，功能鲜明，使用简便”的原则，从而为新生和校外来访人员了解校园环境提供便捷和帮助。系统具有的功能大致如下：
1）数据的更改和删除。由于高校校园逐渐扩建，校园地理环境不断变化，对于已经建成的校园导航系统，进行及时准确的更新十分必要。系统可以在数据库中对现有的数据进行删除、修改，从而实现对校园地图和属性的及时更新。2）数据的查询和显示。用户可以通过输入关键词后在地图上搜索地点。对于显示在地图窗口的地图可以进行放大、缩小、漫游等操作，用户还可以根据自己的需要及兴趣点控制各个图层的显示，使查询的信息更加明显。3）空间分析查询。打开客户端软件时，手机进行实时GPS定位，获取当前位置后在地图上显示位置坐标，并显示附近的地图信息。基于“Dijkstra算法”的最短路径导航功能还可以对任意两点可以进行最短路径的查询和导航，这是系统最核心的功能，用户通过输入起点（或以当前定位点为起点）和终点可以迅速查询出两点间最短路径，为新生和校外来访人员提供了非常便捷及人性化的服务。
4.2 性能测试分析
1）GPS定位功能实现。在移动端采用坐标定位的方法，如果手机的GPS定位功能已开启，地图会自动定位，获取到当前的坐标时，地图控件会自动平移到当前的位置。界面如图2所示。
2）搜索地点功能实现。在搜索框中输入关键词地名，例如“金虎超市”，点击搜索按钮，就会向服务器发送请求，若能找到，则返回它的坐标，然后客户端就在地图中显示一个蓝色的点，表示搜索的位置。界面如图3所示。
3）选择图层功能实现。基于用户兴趣点选择图层，其中包含的图层有：美食、医院、超市、停车场、KTV、电影院、银行、加油站、药店等。用户选择感兴趣的图层后，可以在地图上显示对应的图标。界面如图4所示。
4）路径导航功能实现。采用Dijkstra算法实现最短路径的选择，当用户设置起点（或以当前定位点为起点）和终点后地图会在该两点显示标记，点击导航按钮后，地图上就会显示出从起点到终点的一条最优路径。界面如图5和图6所示。
图2 GPS实时定位界面 图3 关键词搜索地点界面 图4 兴趣点选择图层界面
图5 最短路径导航界面（用户设置起点） 图6 最短路径导航界面（以当前定位点为起点）
5 结束语
校园智能手机导航系统的建立是校园数字化的一种体现，为学校日后建立综合校园管理体系奠定了基础。利用Dijkstra算法实现了最短路径的选择，获得的最短路径的属性数据得以显示，提供了及时且更直观的校园导航系统的信息。通过测试，本系统起到了为新生报到和校外来访人员提供指南导航的作用，提供了方便、快捷的智能导航服务信息，从而提高了学校管理水平和工作效率。系统服务于高校的规划和建设，可以为高校的发展做出一定的贡献。基于Android平台可以快速有效地进行系统开发，极大地减少了程序开发工作量，缩短了开发周期。可以实现高效、无缝的系统集成，这是未来GIS程序开发的发展趋势。随着GIS的发展的日新月异，相信其应用领域也将有更大拓展。希望该系统的设计方案和核心模块的功能实现方法能为此类系统的设计提供一定的参考。
参考文献：
[1] 王福平，乔丹，王俊彩，胡长中.基于嵌入式的校园智能导航系统设计[J].计算机应用，2011，31（z1）：146-148.
[2] 刘永轩，原凯敏，刘芬等.基于GIS的山西师范大学新生报到导航系统[J].科技情报开发与经济，2010， 20（32）：107-109.
[3] 虞昌彬，谢潇.基于.Net平台的校园新生导航系统[J].福建电脑，2008，10：121-122.
[4] 唐伟奇.校园地理信息系统的开发与实现[J].科学技术与工程，2006，6（8）：1102-1118.
[5] 袁满，于海洋.基于ArcGIS Mobile的油田移动GIS系统架构与实现[J].科学技术与工程，2011，11（20）： 4800-4803.
关键词：农民工；职业生涯规划；路径
中图分类号：F241文献标志码：A文章编号：1673-291X（2011）12-0111-02
浙江是一个劳务输入大省，温州也是一个劳务输入比较集中的城市。2005年起温州市政府把到温州务工的农民工称为“新温州人”，充分体现了政府号召人们对进城务工人员的认可和尊重，从思想观念上消除对农民工的歧视和偏见，切实让农民工享有平等待遇。据温州市公安局统计，2008年12月，温州市公安局对外公布全市登记在册的外地暂住人口为3 396 053，主要以湖南、湖北、贵州、江西、安徽、四川等省，暂住人口中务工的为3 135 307人，从事服务业的58 805人，务农的24 250人，温州已经成为创业的第二故乡。温州对农民工有着巨大的吸引力，温州的发展也同样离不开农民工。
一、职业生涯规划内容
随着越来越多的农民工朋友进入到城市里展开个人的城市生涯，每个人都要借助于谋求职业而实现自我的发展。职业生涯规划，简称职业规划，就是对个人的职业历程乃至整个一生进行持续的、系统的、规划性的设计的过程。从个人角度和企业角度，职业生涯规划又划分为两个方面的内容：
1.个人职业生涯规划：企业中的大多数员工，其中包括受过良好教育的员工，都有从自己现在和未来的工作中得到成长、发展和获得满足的强烈愿望和要求。为了实现这种愿望和要求，他们不断地追求实现职业的理想，能主动根据个人的特点、企业发展的现实和社会发展的需要，制定自己的职业规划。
2.企业员工职业生涯管理：在广大员工希望得到成长、发展的强烈要求推动下，企业人力资源管理部门（或人事部）为了更好地开展工作，在了解员工个人的特点，成长和发展的方向及兴趣的基础上，通过一些宣传、教育和咨询等活动，帮助员工制订有关个人成长、发展的计划以及与组织需求和发展相结合的计划，不断地增强他们的满意感，并使他们与企业组织的发展统一协调起来。可见，职业生涯规划既要体现员工发展的需要，又要体现企业发展的需要，是员工个人发展与企业发展的一种协调与相融。
二、农民工做好职业生涯规划的意义
职业生涯规划对所有工作年龄的人来说都很重要，在人一生的历程中，需要靠职业来生存和发展。每个人都需要规划好自己的职业生涯，主动去把握它、迎合它、顺应它才是生存之道。有些农民工朋友会说，职业生涯规划，那是大学生的事，我们居无定所，四处漂泊，生活如无根的浮萍，天天生活在变化中，甚至工作有没有着落也不清楚，还需要做职业生涯规划吗？实际上这样的看法并不在少数，正是由于存在这样的观点，很多农民工朋友的城市生活才没有更多的长进。离开家乡进城工作，可不能像当年游击队一样，打一枪换一个地方，如果没有合理的、长远的、多方面的规划，就无法进一步实现个人的职业理想和生活理想。那么怎样看待农民工做职业生涯规划这个问题呢？
1.从社会的角度看。每年一度的春节，大量的农民工返乡，春节过后又有大批农民工进城，在上亿的劳动力大军流动过程中，许多人完成了一年的职业劳作，来年又重归游离的状态，不能也无法重新回归从前的单位，也不能从事原先的职业。于是乎，大量的人力资源耗费在等待、煎熬、徘徊和痛苦之中。这中间有很多原因是由于农民工朋友在自己进入城市之后，没有对自己能做什么，个人想要什么，有什么基础，个人发展的方向是什么等问题，做深入、系统的分析和探讨而造成的。农民工朋友做好自己的职业生涯规划，有利于建立科学的择业观，提高就业的成功率，还可以减少失业、被辞职的情况，从社会角度来看对降低就业压力是有较大帮助的。因此，农民工朋友做职业生涯规划是社会现实的需要。
2.从企业发展的角度看。长期以来，由于中国拥有巨大的劳动力资源优势，整个劳动力市场呈严重的供过于求的状态。大量进城务工人员一方面为企业提供了大量的廉价劳动力，另一方面上到国家、下到企业都逐渐产生了员工流动和使用的依赖，中外企业招聘员工一般不用发愁。但是，目前大多数企业对待农民工劳动力，都是重在使用而轻视培养，重视招聘新员工而轻视已有劳动力的再提高，更不用说对员工进行职业发展规划和技能提升。实际上，企业员工缺乏职业安全感和职业发展需求的满足感，员工的安心工作就会出现波动，企业发展就会有隐患。如果农民工劳动力资源没能及时有效地得到规划、开发与储蓄，大部分农民工很可能将永久性地退出劳动力市场。为了农民工的“再出发”与产业的“再发展”，就必须做好劳动力供给的“蓄水池”，进行科学的职业发展规划与开发。
3.从个人发展的角度看。从个人的角度来讲，农民工朋友绝大多数原来是在土地上从业的农民，由于寻求个人的发展等动力促进，离开了自己熟悉的家乡，来到全新的城市环境里，谋求有所发展，但是如果个人在进入城市职场之前，对自己的未来发展没有规划和目标，那么会对个人的发展造成障碍的。特别对刚刚成长起来的步入城市的年轻打工者（新生代农民工），该用怎样的眼光来看待自己未来的发展道路，将对其一生的成就产生重大影响。农民工做好个人的职业生涯规划，对个人发展的意义主要体现为以下几个方面：（1）做好职业生涯规划，可以分析自我，个人可以准确评价自身的职业能力、性格特点、价值追求、优势与劣势等，在职业竞争中发挥个人优势。以既有的成就为基础，确立人生的方向，提供奋斗的策略。（2）通过职业生涯规划，可以重新安排自己的职业生涯，突破原有生活的局限，塑造全新、充实的自我。即使自己已经进城打工多年，还可以评估个人目标和现状的差距，提供前进的动力。（3）通过职业生涯规划重新认识自身的价值并使其增值。通过自我评估，知道自己的优缺点，然后通过反思和学习，不断完善自己，使个人价值增值。还有助于全面了解自己，增强职业竞争力，发现新的职业机遇。（4）职业生涯规划通常建立在个体的人生规划上，因此，做好职业生涯规划将个人生活、事业与家庭联系起来，让生活充实而有条理。
三、农民工做好职业生涯规划的路径
根据职业生涯规划理论，农民工朋友规划自己的职业生涯可以从以下几个方面入手。
1.评价自我。即审视自己、认识自己、了解自己，做自我评估。自我评估就是对自己做全面分析，通过自我评估才能对自己的职业作出正确的选择，才能选定适合自己发展的生涯路线，才能对自己的生涯目标作出最佳抉择。因此，自我评估是职业规划的重要步骤之一。自我评估包括自己的兴趣、特长、性格、学识、技能、智商、情商、思维方式、思维方法、道德水准以及社会中的自我等内容。也许农民工朋友会说，我没有什么特长，其实不是这样的，每个人都有自己的特长，只是平时没有去挖掘发现而己，仔细分析自己，就会发现原来我还有这样或那样的特长。
2.评估职业机会。主要分析内外因素对自己职业选择的影响，每一个人都处在一定的环境之中，离开了这个环境，便无法生存与成长。所以，在制定个人的职业规划时，要分析环境条件的特点，环境的发展变化情况，自己与环境的关系，自己在这个环境中的地位，环境对自己提出的要求，以及环境对自己的有利条件与不利条件等等。只有对这些环境因素充分了解，才能做到在复杂的环境中避害趋利，使职业规划具有实际意义。农民工要把自己作为一个职业人来了解周围的环境、你所在的地区、你将要就业的行业等，只有清晰掌握周围的环境，才能权衡利弊。
3.选择职业。通过自我评估、生涯机会的评估，认识自己、分析环境，在此基础上对自己的职业作出选择。也就是在职业选择时，要充分考虑到自身的特点，即自己的能力、性格和兴趣，特别是个人的工作能力，工作能力往往是限制一个人在劳动力市场选择合适岗位的因素。分析自我、了解自己、分析环境、了解职业世界，使自己的性格、兴趣、特长与职业相吻合。通过对自己以往的经历及经验的分析，找出自己的特长与兴趣点。选择职业重要的是能正确地分析自己，找到自己最适合做的专业，然后努力成为本行业的佼佼者。职业的选择决定以后的成长道路，所以每一位农民工朋友千万不要简单的认为找一份工份就是自己以后的职业，随意从这个工作跳到那个工作，这里不行就到那里。对待自己的工作选择要慎重。
4.制订职业计划。在做个人职业发展计划的时候，要考虑你所选择的工作，能否帮助你实现人生的最终目标？你是否有办法可以让你现有的职业与你的人生基本目标一致起来？简单的说，就是你希望在多少年之内达到什么目标，根据这个目标我又该怎么做？通常在制订职业计划时，先制定一个长期目标，然后把长期目标分解成一个个短期和中期目标，这样对于每一个短期目标就会变得贴近生活、容易达到。
5.实施行动。开始行动，这是所有生涯设计中最艰难的一个步骤，因为行动就意味着你要停止梦想而切实地开始行动。如果想法不转换成行动，就是一纸空文，目标也只能停留在梦想阶段。如果你想成为一个电工或家政人员，当你制定职业规划后就立即行动起来，你可以参加政府提供的免费技能培训，针对大量需要培训的农民工，政府每年都会提供大量的资源为农民工进行多种形式的免费培训的，那农民兄弟们可以充分利用这些机会，提升自己的能力。立即行动，无论你是处于刚刚踏上职业路途的年轻人，还是40岁左右并且正陷在一份你不喜欢的工作之中的中年人，现在都是你进行职业规划的好时机。只要你还没有到安享晚年的地步，任何时候开始你的职业规划都不为晚。
参考文献：
[1]邹树新.中国城市农民工问题[M].北京：群言出版社，2007.
[2]陆汉洲.聚焦中国民工[M].北京：中国经济出版社，2005.
[3]沈立人.中国农民工[M].北京：民主与建设出版社，2005.
关键词：水利；发展；经济
一、水利经济发展概述
水利经济是指水资源、水环境、水利工程为要素所从事的生产经营活动的统称，水利行业的一个重要组成部分就是水利经济的发展。我国建国以后在水利建设方面取得了很大的成就，水利经济也伴随着国家经济的发展而不断的发展。水利行业逐渐的形成了以水利建设的勘测、施工、运行管理为主的产业结构，我国水利企业无论在人员、规模及技术方面都在朝好的方向发展，企业的未来也充满了希望，但如何使水利经济的发展能够更迅速，水利企业能够真正实现可持续发展，依然是我们要研究的课题。
二、水利经济发展的客观必然性
1.水利经济存在与发展的客观必然性
水是一种自然资源，以一种生态要素的形式出现，发挥着不可替代的生态效益与环境效益。但当水以一种经济资源存在时，其在经营活动中就是一种生产要素，能够增值且有经济效益。以水为原料的生产包括：水产养殖、水路运输、水能资源开发、水利工程对水资源的优化配置等。我们长期以来一直强调水的自然属性和公益性作用，而忽视了水的经济属性，这使得水利经济的发展失去了很多机会，影响了行业的现代化建设进程。可以说水利经济发展是社会经济发展的客观需要。
2.水利经济与实行水务管理体制的客观必然性
水资源是人类社会极为重要的基础性资源，我们既要保持水资源的可持续利用，又要充分发挥其经济功能效益，这就要求我们必须对水资源科学管理、统一规划。只有协调好水资源保护与水资源开发利用之间的关系，使二者可以有机的结合起来，才能真正意义上的实现对水资源的统一管理，对水资源进行保护及科学利用。
3.水利经济与水利现代化建设的客观必然性
与交通、通讯、电力等行业相比，水利同样作为社会经济发展中的基础性行业，而在发展中却明显落后。在我国经济飞速发展的今天，水利经济发展要与社会经济发展同步，甚至要超越社会经济发展的速度，水利行业要根据水资源的双重属性创新水利的投入机制，充分利用市场机制和政府财政的力量，加大水利投入的规模，加强安全水利、环境水利、民生水利的建设，为我国社会经济发展提供牢固的基础支撑及保障。
三、关于发展水利经济的主要措施
1.多渠道筹集水利建设资金
对于水利建设资金的凑集要采取多渠道、多方式的办法，要挖掘民间资本，推荐民营水利建设。对投资大、收入高的项目可成立股份公司，在行业内部或是面向社会凑集资金，水利企业的内部员工可以参与投资入股，共同开发水利市场。值得注意的是，水利建设是关系到民生的大事，设计到人民群众的生命安全，所以水利建设部门必须对相关审批严格控制，对水利公共事业的安全性负责。
积极开展招商引资活动来满足城市水务建设的需要，将有实力的大企业集团引入来做大做好水利项目。目前我国很多的公司已经和水利部门合作参与到水利市场中来，共同来发展水利经济，并在水务市场中占据了一定的位置。这样水利部门达成了预定的目标，参与企业也实现了经济效益，达到一种双赢的结果。
2.法制经济、依法收费
水利建设必须形成一种法制经济，目前中央及地方也出台了很多保障水利经济发展的政策，但水利建设实现法制经济还是存在着法规不完善、法规政策落实不到位等问题。水利行业要坚持实行依法收费，将政府制定的法律法规真正的落实到实际工作中去，同时要杜绝企业内部资源浪费的现象，做好水土资源保持工作。
3.实行体制改革
我国现行的区域分割治理方式容易造成地区利益争夺，也不利于水资源的合理分配及发挥其最大的经济效力，会出现一个地方水资源充沛浪费严重，而另一个地方水资源又极度紧张的情况。所以要注意城市供水由水利管理部门统一分配、农村用水要由水利行政部门管理、发动地方群众参与当地的水利建设兴休等问题。
4.重视人才
一个行业的发展离不开人才，人才是技术及经验的载体，是企业发展的宝贵财富。我国水利行业的发展中培养了很多懂水利建设的人员，但精通管理、善于经营的人才却较少。所以水利行业在寻求发展的同时也要关注对人才的培养、培育，企业内部要重视人才，建立起人才培育的体系。另外，企业也要敢于在市场中引入高端人才，使企业可以更好的发展。
5.提高科技含量
相对于欧美等一些西方发达国家，我国水利科技的发展程度、水利科技的含量都较低，水利行业内部员工的素质、科学文化水平也都不高，这些因素的存在阻碍了我国水利经济向世界一流水平前进。我国水利行业应该改变原来那种仅仅依靠经验来进行生产经营活动的思维方式，变成依靠高科技、劳动技术、经验等相结合的方式来实现水利建设科技化发展。加快水利企业技术改造，鼓励水利企业技术创新，努力形成低投入、高产出的企业经营状态。
参考文献：
关键词：移动机器人；路径规划；A*算法；栅格法
中图分类号：TP391.4 文献标志码：A
Mobile Robot Path Planning Based on an Improved A* Algorithm SUN Wei1， LV Yunfeng1， TANG Hongwei1，2， XUE Min1
（1. College of Electrical and Information Engineering， Hunan University， Changsha 410082， China；
2. Department of Electrical Engineering， Shaoyang University， Shaoyang 422000， China）
Abstract：An improved A* algorithm was presented for global path planning of mobile robot. Firstly， the environment model was described using the grid method， and the preliminary path was obtained by traditional A* algorithm. Secondly， the path planned by A* method was flaw with much redundant points， large path length， and turning angle. The original path was partitioned by tiny step to obtain a series of path point. The finish point from the start point was connected by using straight line in sequence. To decrease the path length and turning angle， the path node can be removed if there are no obstacles on the line. The analysis and comparison between the proposed algorithm， traditional A* algorithm and another improved A* method were then given in the simulation experiment and physical experiments. Additionally， the merits of the proposed algorithm and other algorithms were compared when the obstacle rate， amount of task point， and step length were different. The experiment results show that the proposed algorithm effectively reduces the path length and turning angle.
Key words：mobile robot； path planning； A* algorithm； grid method
路径规划问题一直是智能机器人领域的一个研究岬.移动机器人路径规划是指机器人基于机载传感器获得的环境信息规划出一条从起点到终点的无碰、安全的可行路径，并在此基础上尽可能地优化路径[1].移动机器人路径规划主要解决以下三个问题：第一是规划出的路径能使机器人从起点运动到终点；第二是采用相应的算法使得机器人能够避开环境中的障碍物；第三是在满足前面两点要求的基础上，尽可能地优化机器人的运动轨迹，通常是以规划出的路径最短作为优化目标[2].根据机器人对环境信息的感知程度，路径规划问题分为全局路径规划和局部路径规划.前者是指机器人在拥有全部环境信息的基础上进行的路径规划，又称为离线路径规划；后者是指机器人在只有部分环境信息的基础上进行的路径规划，又称为在线路径规划[3].本文主要讨论全局路径规划.
移动机器人路径规划的研究起始于20世纪70年代，到目前为止，已有大量的研究成果.针对全局路径规划，主要方法有可视图法、拓扑学法、人工智能算法和栅格法[4].文献[5]针对自由空间法当环境发生变化时，需要重新建立网络连接模型，因而导致路径规划算法的环境适应性差和实时性不高的缺陷，提出了一种基于可视图的全局路径规划算法，该方法是直接在环境地图上进行路径规划，从而提高了算法的环境适应能力和实时性.神经网络作为人工智能中一种重要的算法也被应用到了移动机器人路径规划领域，如文献[6]，首先建立了一个障碍物罚函数的神经网络模型，并得到了整条路径的能量函数；然后求得该函数的极小值点，且应用了模拟退火算法避免陷入局部最优；最终对得到的路径进行了优化，使得路径更加平滑和安全.除此之外，学者们还采用其它的智能算法来解决移动机器人路径规划问题，如模糊逻辑[7-9]，蚁群算法[10]，粒子群优化[11]，遗传算法[12-13]等.
栅格法是将机器人运动环境建立成一系列具有二值信息的网格模型，再用搜索算法获取最优路径.文献[14]提出了一种改进的A*算法，解决了传统A*算法得到的路径包含过多冗余点问题，并得到机器人在拐点处的最小转折角度.但该算法并没有减小机器人的路径长度和转折角度.文献[15]针对传统A*算法得到的路径折线多、累计转折角度大的问题，提出了一种平滑A*算法，减少了不必要的路径点并减小了路径长度和转折角度.但只是在原有的路径点上进行处理，路径长度和转折角度的减少量有限.本文提出了另一种改进的A*算法，将进一步地减少移动机器人的总路径长度和总转折角度.
1 环境模型描述
众所周知，移动机器人工作环境地图建立是路径规划中十分重要的一步.地图建立是指将各种传感器获得的环境信息进行融合并抽象成地图模型[16].采用栅格单位描述二维环境信息非常简单有效，应用广泛.所以，本文也使用栅格法来建立移动机器人工作环境模型.如图1所示，栅格法将机器人工作环境分割成一系列具有相同尺寸的栅格，并将这些栅格分成两类：可通过栅格和不可通过栅格.图1中，空白栅格表示可通过栅格，即移动机器人能自由通过的地方，黑色栅格表示不可通过栅格，即该栅格有静态的障碍物.
为了方便研究又不失一般性，本出以下3点合理的假设：1）障碍物边界是在实际边界的基础上加一个移动机器人安全距离得到的，这样就可以将移动机器人看作是环境中的一个质点；2）在这有限的二维空间中，机器人的移动方向可以是任意的，并且不考虑高度的影响；3）在整个路径规划过程中，环境信息是不变的.图1是一个10*10的移动机器人工作环境，S是机器人起点，D是终点.本文的工作就是找到一条从起点到终点的无碰的最优路径.
2 A*全局路径规划算法
A*算法是一种典型的启发式搜索方法.通过估价函数来引导和决定它的搜索方向.从起点开始搜索周围的节点，由估价函数得到每个节点的价值，选择价值最低的作为下一个扩展节点，循环重复这一过程直到搜索到终点，则停止搜索，获得最终路径.由于每一次都是以估价值最低的节点作为扩展节点，所以最终的路径代价是最低的.估价函数由式（1）给出：
式中：g（n）是状态空间中从起始节点到节点n的实际代价，h（n）是从节点n到终点的启发式估计代价函数，本文采用曼哈顿距离作为启发式函数[14].
xd是目标点的横坐标，yd是目标点的纵坐标，xn是节点n的横坐标，yn是节点n的纵坐标.
在A*算法搜索路径的过程中，需要不断地更新两个列表，一个是开启列表，另一个是关闭列表.开启列表存储的是所有的周围节点.A*算法从开启列表中选择具有最小估价值的节点作为下一个扩展节点.关闭列表存储的是所有经过的节点和环境中的障碍节点.应用A*算法进行路径搜索的具体流程如下所述：
Step1 把起始节点放入开启列表.
Step2 检查开启列表是否为空，如果为空，则表示搜索失败；不为空，则执行Step3.
Step3 选取开启列表中具有最低f（・）的节点作为当前扩展节点，对扩展节点的每个周围节点作如下处理：①当该节点的周围节点是障碍点或者是关闭列表中的节点，则没有任何动作；②当该节点的周围点不在开启列表中，则把该节点的周围节点添加进开启列表中，并将当前扩展节点作为该节点的周围节点的父节点，计算该节点的周围节点的f（・）和g（・）；③当该节点的周围节点在开启列表中，如果以当前扩展节点作为父节点，该节点的周围节点的g（・）比原来更低，则把当前扩展节点作为父节点，并重新计算该节点的周围节点的f（・）和g（・）.否则，不作任何改变.
Step4 将当前扩展节点放入关闭列表中，并检查终点是否在开启列表中.如果不在开启列表中，则跳回Step2继续搜索；否则，最优路径已经找到，结束搜索.
Step5 从终点开始，沿着每一个父节点移动，回到起始点，这就是最终的路径.
3 改进的A*算法
采用A*算法进行移动机器人路径规划虽然能获得一条安全无碰的路径，但路径点较多，折线多，导致路径的总长度和总转折角度较大.这在移动机器人实际应用中将消耗更多的能量和花费更多的r间.本文提出了一种改进的A*算法，能有效地减少路径长度和转折角度.
图2的实线是在一个任意环境中A*算法规划出的路径，本文方法是在原路径的基础上，从起点开始以较小的步长分割原路径，得到更多路径点，如图2的路径点a1到a20.按照一定的规则剔除冗余路径点，将剩余的路径点按顺序连接，最终获得更加优化的路径.
图3是本文算法的流程图，图中符号的定义如下：
k为分割路径的步长；c，m，i分别是当前路径点下标、待连接路径点下标和新路径点下标；A为以步长k分割原始路径得到的路径点集合A={a1，a2，…，aN}，其中a1是起始点，aN是终点；ac为当前路径点；am为当前待连接点；
lcm为连接ac与am的直线；lc，c+1为连接ac与ac+1的直线；B为新的路径点集合，B={b1，b2，…，bs }.
注意，以步长k分割路径是在原路径的直线段进行的.例如，对图4中A*算法得到的路径进行分割，先进行直线段L1的分割，从起点开始依次得到路径点a1，a2，…，a7，此时a8与原路径点的距离小于步长k，则将原路径点作为a8，并从路径点a8开始重复上述过程，分割直线段L2和L3直到将终点作为路径点a20时，分割过程结束.
图4中的实线是在任意环境中A*算法规划出的路径1，由直线段L1 ，L2 和L3组成，本文方
法规划出的路径3由直线段La1a6，La6a9，La9a10和La10a20组成，其中Laiaj是指起点为ai，终点为aj的直线段.由图4可以直观地看出：路径1的路径长度明显大于路径3的路径长度.另外，路径1的总转折角度：
路径3的总转折角度：
其中α2=∠ba6a9 ， β2=∠da9a10，γ1=∠ca10a20.而α1=α2+β2，β1=γ1+γ2，γ2=∠a15a20a10，则θ1=α1+β1=α2+β2+γ1+γ2=θ3+γ2.所以，θ1>θ3.相对于A*算法，本文方法缩短了总路径长度，减小了总转折角度.
文献[15]提出的平滑A*算法直接地剔除A*算法规划出的路径点，使得路径更加平滑.而本文方法是先进行分割，再剔除冗余的路径点.图4中直线段La1a8，La8a11和La11a20是文献[15]中平滑A*算法得到的路径2.显然，路径2的长度大于路径3的长度.另外，路径2的转折角度：
其中α1=∠ba8a9，β3=∠a15a20a10，而α1=α2+β2，β3=γ1+γ3，γ3=∠a11a20a10，则θ2=α1+β3=α2+β2+γ1+γ3=θ3+γ3，所以θ2>θ3.相对于文献[15]提出的平滑A*算法，本文方法得到的路径也更加优化.
4 实 验
为了验证本文算法的可行性和有效性，进行了计算机仿真实验和实物实验.考察了不同情形下算法的性能，以下将从4个方面进行仿真实验： 1）探究同样的条件下本文算法与A*算法以及文献[15]的平滑A*算法的性能；2）环境障碍率p对各算法的影响；3）不同目标点数n下算法的优劣；4）本文算法在不同的分割步长k下的效果.以下的4种情形都是在边长为200个单位的正方形环境下进行实验，将实验环境分割成20*20个栅格元素，每个元素是边长为10个单位的正方形栅格.将实验环境分割成20*20个栅格元素，每个元素是边长为10个单位的正方形栅格.
情形1 环境障碍率（障碍栅格数量占总栅格数量的比例）p=30%，取本文算法的分割步长k=0.1，目标数n=1即只有一个终点，起点是（4，4），终点是（198，198），机器人在起点的角度为90°.进行了50次实验，图5和图6是不同算法规划出的路径长度和转折角度，表1是3种算法50次实验的各项平均值比较.从实验结果中可以看出，本文提出的改进A*算法相对于A* 算法和文献[15]的平滑A* 算法，有效地减少了路径长度和转折角度.注意，虽然环境障碍率都是30%，但障碍栅格是随机分布的，这就导致了不同的环境复杂度，所以同样的算法和实验条件在不同的实验次数下却有不同的实验结果.
情形2 考察在不同的环境障碍率下，各个算法的性能.令分割步长k=0.1，目标数n为1，起点（4，4）、终点（198，198），机器人在起点的角度为90°.分别在环境障碍率为10%，20%，30%，40%，50%时，进行了50次实验，并求得不同障碍率下路径长度的均值和转折角度的均值，实验结果如图7、图8所示.可以看出，一方面当环境障碍率增大时，各个算法得到的路径长度和转折角度也在不断增大.这是因为环境障碍率一定程度上代表了环境的复杂度，当环境越复杂时，那么规划的路径长度和转折角度也就越大；另一方面，在图7和图8中，方框内的数据是本文算法相对于A*算法路径长度和转折角度的减少量.当环境障碍率越大时，路径长度和转折角度的减少量也不断增大，这说明相对于A*算法，本文方法更加适合在障碍物较多的环境中使用.
情形3 在移动机器人的工作空间中可能存在多个任务点，这就意味着环境中会有多个不同的终点.这里将研究当机器人有多个任务点时，各个路径规划算法的优劣性.这里做以下两点规定：1）对环境中的任务点进行了编号，任务点1，（198，198）；任务点2，（4，198）；任务点3，（95，95）；任务点4，（198，4）.2）当机器人有n个任务需要执行时，它的执行顺序是由任务点1递增至任务点n.取障碍率p=30%，分割步长k=0.1，分别在n等于1，2，3，4时，进行了50次实验，并求得路径长度和转折角度的均值，实验结果如图9和图10所示，图中方框内的数据是本文算法相对于A*算法路径长度和转折角度的减少量.显而易见，当机器人的任务点越多，本文算法相对于A*算法规划的路径长度和转折角度的减少量越大.
情形4 本文算法中存在一个分割步长k，这里将考察参数k对算法效果的影响.令环境障碍率p=30%，仅有一个任务点（198，198），起点是（4，4），机器人在起点的角度为90°.在不同的分割步长下进行了50实验，并求出相应的均值，验结果如图11和图12所示.可以得出这样的结论：当分割步长越小时，本文算法得到的路径长度和转折角度也越小.显然，这是因为分割步长越小，路径分割得越精细，路径长度和转折角度也就相应减小.
在实物实验中，本文采用的移动机器人是Turtlebot2，移动底座的最大移动速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C笔记本电脑作为移动机器人的控制器.移动机器人的实际运动空间如图13所示，是3.6 m×6.6 m的矩形环境.起点（0.9 m，0.9 m），终点（2.7 m，6.3 m），机器人在起点的角度为90°.为了使用本文改进的A*算法进行路径规划，需要先建立环境的栅格模型，设置栅格元素为0.6 m×0.6 m的正方形，对实际障碍物进行膨化处理，映射成图14的黑色栅格.分别采用A*算法、文献[15]的平滑A*算法和本文算法进行移动机器人的路径规划.图14的直线段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和
La44a53是A*算法规划出的路径；文献[15]中平滑A*算法得到的路径是直线段La1a5，La5a11，La11a21，La21a27，La27a32和La32a53；直线段La1a8，La8a24，La24a25，La25a35和La35a53是本文算法得到的结果.由于移动机器人的运动总是存在外界干扰和运动精度等因素，其运动的实际路径长度与转折角度总是比规划的路径长度和转折角度要稍稍大一些，如表2所示.但无论是规划的路径长度和转折角度，还是移动机器人实际运动的路径长度和转折角度，本文算法得到的实验结果都比A*算法和文献[15]平滑A*算法更加优化.
5 结 论
采用A*算法进行移动机器人路径规划，可以得到一条从起点连接终点的无碰安全路径，但路径的冗余点较多，路径长度和转折角度较大.针对这些问题，本文提出了一种改进A*算法，能有效地减少路径冗余点和减小路径长度及转折角度.并且，分析比较了不同的环境障碍率、任务点数量、分割步长对算法性能的影响.一方面，相对于A*算法，本文方法更加适合多任务点，高障碍率环境下的移踊器人路径规划；另一方面，采用较小的分割步长可使得规划出的路径更加优化.
参考文献
[1] 席裕庚，张纯刚.一类动态不确定环境下机器人的滚动路径规划[J].自动化学报，2002，28（2）： 161-175.
XI Yugeng， ZHANG Chungang.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J]. Acta Automatica Sinica， 2002，28（2）：161-175.（In Chinese）
[2] 张捍东，郑睿，岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报，2005， 17（2）： 439-443.
ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and future development of mobile robot path planning technology[J]. Journal of System Simulation， 2005，17（2）：439-443.（In Chinese）
[3] 朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010， 25（7）： 961-967.
ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision， 2010，25（7）：961-967.（In Chinese）
[4] 吴乙万，黄智.基于动态虚拟障碍物的智能车辆局部路径规划方法[J].湖南大学学报：自然科学版，2013，40（1）： 33-37.
WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University：Natural Sciences， 2013，40（1）：33-37.（In Chinese）
[5] 杨淮清，肖兴贵，姚栋.一种基于可视图法的机器人全局路径规划算法[J].沈阳工业大学学报，2009，31（2）： 225-229.
YANG Huaiqing， XIAO Xinggui， YAO Dong. A V-graph based global path planning algorithm for mobile robot[J]. Journal of Shenyang University of Technology， 2009，31（2）：225-229.（In Chinese）
[6] 梁瑾，宋科璞.神经网络在移动机器人路径规划中的应用[J].系统仿真学报，2010，22（增刊1）： 269-272.
LIANG Jin， SONG Kepu. The application of neural network in mobile robot path planning[J]. Journal of System Simulation， 2010，22（s1）：269-272.（In Chinese）
[7] 郝冬，刘斌.基于模糊逻辑行为融合路径规划方法[J].计算机工程与设计，2009，30（3）： 660-663.
HAO Dong， LIU Bin. Behavior fusion path planning method for mobile robot based on fuzzy logic[J]. Computer Engineering and Design， 2010，30（3）：660-663.（In Chinese）
[8] ARPINO C P， MELENDEZ W M， GUZMAN J， et al. Fuzzylogic based speed planning for autonomous navigationunder velocity field control[C]//2009 IEEE Int Conf on Mechatronics. Malaga， 2009： 201-212.
[9] ZOUMPONOS G T， ASPRAGATHOS N A. Fuzzy logic pathplanning for the robotic placement of fabrics on a worktable[J]. Robotics and Computer Integrated Manufacturing， 2008， 24 （2）： 174-186.
[10]邓高峰，张雪萍，刘彦萍.一种障碍环境下机器人路径规划的蚁群粒子群算法[J].控制理论与应用，2009，26（8）： 879-883.
DENG Gaofeng， ZHANG Xueping， LIU Yanping. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009，26（8）：879-883.（In Chinese）
[11]吴宪祥，郭宝龙，王娟.基于粒子群三次样条优化的移动机器人路径规划算法[J].机器人，2009，31（6）： 556-560.
WU Xianxiang， GUO Baolong， WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. ROBOT， 2009，31（6）：556-560.（In Chinese）
[12]王雪松，高，程玉虎，等.知识引导遗传算法实现机器人路径规划[J].控制与决策，2009，24（7）： 1043-1049.
WANG Xuesong， GAO Yang， CHENG Yuhu， et al. Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision， 2009，24（7）：1043-1049.（In Chinese）
[13]THEODORE M， KAVEH A， ROGER L W. Genetic algorithms for autonomous robot navigation[J]. IEEE In Strumentation and Measurement Magazine， 2007，12（1）： 26-31.
[14]王殿君.基于改进A*算法的室内移动机器人路径规划[J].清华大学学报：自然科学版，2012， 52（8）： 1085-1089.
WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University：Science and Technology，2012，52（8）：1085-1089.（In Chinese）
[15]王红卫，马勇，谢勇，等.基于平滑A*算法的移动机器人路径规划[J].同济大学学报：自然科学版，2010，38（11）： 1647-1651.
WANG Hongwei， MA Yong， XIE Yong， et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University：Natural Science， 2010，38（11）：1647-1651.（In Chinese）
