路径规划范例6篇

前言:中文期刊网精心挑选了路径规划范文供你参考和学习,希望我们的参考范文能激发你的文章创作灵感,欢迎阅读。

路径规划

路径规划范文1

关键词:分层路网;拓扑结构提取;路径规划;A算法;二叉堆

0引言

路径规划是车载导航系统最重要的功能之一[1]。根据图论中最短路径理论,不管是最短路径规划、最短时间规划还是最低消费规划,都可以通过赋予图中的边以相应的权值来满足用户的不同需求。

通常情况下,路径搜索可以分为平面搜索和分层搜索两大类。平面搜索算法中最经典的是20世纪60年代初期由Dijkstra提出的Dijkstra算法,非常适合在带权有向图中解决最短路径问题。但是该算法的时间复杂度为O(n2),效率比较低,因此在实际应用时受到了很大的限制。后来许多学者在存储结构和排序算法上对Dijkstra算法进行了改进[2-3],通常改进算法的时间复杂度与节点数成正比,如O(mlbn)或O(m+nlbn)[4]。也有学者通过引入启发函数的方式进行改进,启发式搜索以1968年Hart等提出的A*算法为代表,现在仍被广泛应用,但这些改进算法的效率会随节点数的增加而急剧下降。此外,平面搜索算法计算出的“最短”路径并不一定是“最优”路径,最短路径中可能存在大量的窄小拥挤的小巷,而最优路径要尽可能多地包括主干道等快速路段[5],这就有了分层思想。文献[6]首先提出了层次空间的推理过程,文献[7]又将层次空间推理法则引入到行车最优路径搜索中,但这两篇文献均没有给出具体的路网层次拓扑结构的表达方法[8]。有代表性的分层算法有最近E节点法[9]和最佳E节点法[10],其中最近E节点法简单但准确率不高,最佳E节点法能够得到最优解,但效率低[11]。

本文试图设计一种实用的分层路径规划算法。首先建立分层路网的拓扑结构,然后从搜索空间、搜索策略和数据结构三个方面进行研究,采用启发式的A*算法作为主搜索方式,引入优先队列二叉堆作为数据存储结构,最后通过实验验证每项措施的改善效果。

1分层路网拓扑结构提取

路径规划范文2

关键词:企业物资;配送;车辆路径问题;路径规划;里程节约法

一、前言

随着信息技术在现代企业中的广泛应用和高速发展,企业信息化程度大幅提高,企业的许多革命性的创新成果得益于此。在激烈的市场竞争中,仓储配送和信息技术的有机结合为企业带来了新的机遇,建设智慧仓储网络的理念应运而生。而配送作为衔接各个物流节点的关键流程,使仓储网络形成为一个系统性的整体,保证了物资的正常供应。优化配送车辆路径能提高配送效率,降低配送成本,并提升配送准确性。

物资公司作为公司的专业分公司,负责管理在上海区域所有工程及运维检修物资的供应。工程项目物资的供应分为供应商直送现场和仓库供应现场两种类型。其中,供应商直送现场为一次配送,关键点在于供应计划与供应商的有效衔接与调度协同;而利用公司仓储配送网络,通过中心库向各周转库配送以供应现场物资需求的过程为二次配送。合理二次配送车辆路径规划与实施,能提高后续工程建设、运维检修及应急抢修的需求响应速度,增强物资供应的计划性和准确性,可有效提升物资供应管理水平。

二、车辆路径问题定义

车辆路径问题是指存在几个物资需求方,各有一定数量的物资需求,由一个配送中心提供物资,并安排一个车队配送物资。为此需要规划合理的行车路线以使他们的物资需求得到满足,且能在一定的约束条件下,达到路程最短或耗时最少的目标。

公司有十二个周转库,当周转库内某种物资数量低于安全库存时,由中心库提供物资进行补库。由于工程项目对响应速度要求较高,当需要对多个周转库进行补库时,必须综合周转库的地理位置、物资需求量、车辆的运载量、配送次数等,设计出合理的车辆配送路径。

三、配送路径规划意义

1.避免交叉运输

中心库车辆配送路径规划,将原先零散配送的物资进行整合后,以合理的配送路径集中配送,避免了交叉运输的情况,缩短了总配送距离,降低了运输成本。

2.推进节能环保

车辆配送路径优化在满足各周转库的物资需求的前提下,以缩短配送车辆的总行驶距离为目标,能提高能源利用效率,推动公司更积极地承担节能环保的社会责任。

四、配送路径规划过程

1.组织结构

物资公司仓储配送网络包括了集中的物资调配中心、一个中心库以及十二个周转库。

(1)物资调配中心作为信息汇集、指令的中心,实时获取中心库和周转库内库存物资数量、物资需求数量等信息,并根据这些信息判断是否需要补库。

(2)如果周转库需要补库,物资调配中心发送补库指令给中心库。

(3)中心库综合需补库的周转库数量、地理位置及物资需求量等,规划所需的车辆数、配送路径等信息,将物资配送至周转库。

2.车辆路径问题描述

对于物资仓储配送网络,配送车辆路径问题可以描述为,十二个周转库的位置固定且各有一定的需求量,中心库用多辆载重量固定的汽车进行配送,要求合理安排汽车路线以使总距离最短,并能满足以下条件:

(1)每个周转库的物资需求到能满足;

(2)每个周转库的物资必须由尽可能少的车辆配送,例如在周转库的需求能由一辆汽车满足的情况下,必须只由一辆汽车配送;

(3)每条配送路径上各周转库的需求量总和不能超过汽车载重量。

3.车辆路径规划

将中心库及十二个周转库构成的13个的节点两两连线,共有C132=78种组合,即这13个仓库中任意两个仓库间的路径共计78条。利用Google、百度等电子地图软件,将两个仓库分别作为起点和终点,搜索出这78条路线以及之间的行驶距离。以字母O表示中心库,字母A至L表示十二个周转库。当有多个周转库需要补库时,配送路径确定步骤如下:

(1)确定各个周转库需要的物资数量;

(2)与汽车载重量进行比较,确定需要的汽车数量;

(3)根据各周转库的需求量,运用里程节约法,就近的仓库由同一汽车配送,同时避免交叉运输的情况,形成配送路径;

(4)根据实时路况,对配送路径进行一定调整,避免高峰期路段拥堵导致无法及时配送。

由于从实际情况考虑,为减少最后配送到的几个仓库的等待时间,在12个周转库中按地理位置分为两块区域,在郊环附近的7个仓库为一个配送区域,郊环线以内的4个仓库和崇明区域为一个配送区域。

以郊环线附近7个仓库的配送为例,如下图所示,每汽车载重量为5吨,A至G共7个周转库需中心库O配送物资,直线上的数字为距离,括号内的为对应的周转库的物资需求量。

4.路径信息

配送路径规划完毕后,将行车路线信息给对应的汽车司机。车辆出发后,利用短信在途跟踪获取车辆实时的位置信息,并将实时路况信息传递给司机,减少因交通拥堵造成的配送延误。

五、结语

本文综合各周转库地理位置、需求数量、汽车运载量等方面,运用里程节约法规划出车辆配送路径。车辆配送路径规划将对原先粗放式的配送方式进行优化,积极配合政府及上级公司对节能环保提出的要求,在满足各仓库需求的前提下缩短总配送距离,提高物资配送效率,降低配送成本。物资公司后续将逐步加强自动化和信息化建设,推进仓储网络各类信息的实时共享、获取、分析和处理,运用先进信息技术提高配送准确性和效率效益,确保智慧仓储网络的配送脉络高效稳定,构建一个现代化、智慧化、特色化的仓储配送体系。

参考文献:

[1]张玲,王朝霞.物流配送路径优化的模型与求解[J].商场现代化,2006.11.

路径规划范文3

【关键词】虚拟场景;路经规划;八叉树;A*算法

中图分类号:TP39文献标识码A文章编号1006-0278(2013)06-172-01

一、引言

随着虚拟现实技术的日益成熟,只有景色、建筑物等一般视景信息的虚拟场景已不能满足人们的视觉需求,迫切需求一个有生命的对象引入到虚拟场景中,增加浏览者的沉浸感。虚拟场景中虚拟人的路径规划是虚拟现实研究中的一项关键技术。目前,研究者们已经把研究的重心放在如何为虚拟人规划出一条行走的最优路径,使虚拟人的路径导航更具有真实感和可信度。

由于虚拟环境中的模型多由三角面网格组成,通过使用基于空间多层次划分的八叉树方法,充分发挥了其空间划分的优势,加快了场景的渲染速度,减少了确定对象的处理时间以及存储空间①。

文章采用八叉树和A*算法相结合的方法,对路径进行规划,并对A*算法做了改进,以适应八叉树的存储结构。

二、密集型区域八叉树划分算法

八叉树是由四叉树推广到三维空间而形成的一种三维栅格数据结构,它作为一种场景组织方法,广泛应用于虚拟现实系统,可显著减少对场景中多边形进行排序的时间。

由于传统八叉树对空间的划分是均匀的,导致了最终生成一个结构不平衡的八叉树,从而增加整个八叉树的存储空间以及各结点的遍历时间。文章采用了对传统八叉树算法进行改进,采用基于密集型区域八叉树划分方法。密集型区域八叉树的网格划分算法是对每一子空间重新建立最小包围盒,这样避免了在建立顶点树时,由于该部分顶点在空间上分布不均匀而导致树的深度的增加,进而减少了存储空间,加快了网格模型数据的读取速度。另外,由于建立了顶点的最小包围盒,在误差较小时,只有空间距离比较近的顶点才会聚合在一起;而相距较远的顶点只有在深层次简化时才会聚合,这些特点在一定程度上保证了简化时网格模型的逼真度。

密集型区域八叉树划分方法的算法描述如下:

步骤1使用OBB包围盒方法建立模型的最小包围盒。

步骤2以包围盒的X轴、Y轴、Z轴方向的中分面作为分割基准,将包围盒平均划分为八个子包围盒。

步骤3如果每个子空间内存在物体的属性不相同或未达到规定的限差,则重新从步骤1开始进行划分。否则,划分结束,并对划分后的每一个结点记录下结点编号、划分标志、结点在顶点树中的深度以及它所含的景物面片表的入口指针。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的,是由Hart,Nilsson,Raphael等人首先提出的。该算法的创新之处在于选择下一个被检查的节点时引入了已知的全局信息,对当前节点距终点的距离做出估计,作为评价该节点处于最优路线上的可能性的量度,这样就可以首先搜索可能性较大的节点,从而提高了搜索过程的效率。

下面是对A*算法的介绍,我们首先来介绍一下启发式搜索中的估计函数。因为在启发式搜索中,对位置的估价是十分重要的。估价函数的表示如下:

其中是节点的估价函数,是已知的,指在状态空间中从初始节点到节点的实际代价;是从结点到目标节点最佳路径的估计代价,它体现了搜索的启发信息,启发信息决定着算法的启发能力。启发信息越多,估价函数就越好,即约束条件越多,则排除的节点就越多,说明这个算法越好。这种做法存在一个平衡的问题,也会使算法的准确性下降。具体的说,代表了搜索的广度优先趋势,当时,可以省略,这样就提高了搜索效率。

A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为:

这里,是估价函数,是起点到终点的最短路径值,是到目标的最短路经启发值。由于这个其实是无法预先知道的,所以我们用前面的估价函数做近似。代替,但需要满足(在大多数情况下都满足时,可以不用考虑)。代替,并满足。可以证明应用这样的估价函数是可以找到最短路径的。

四、基于密集型区域八叉树的A*算法改进

由于使用八叉树存储结构存储的环境地图扩展步长不一致,采用传统的A*算法效率较低,因此对A*算法做了改进,以适应八叉树结构的搜索。改进的办法是从叶节点开始搜索并为Open表设置两个优先队列,命名为队列1和队列2(队列1中存放的节点总是高于队列2),在两个队列中分别存放相邻层次的全部节点,层次越高的优先级越高。通过这种分层次的搜索,也大大缩小了搜索的空间并缩短了搜索时间,这样一来大大提高了搜索效率。

五、结束语

针对于复杂的3D环境,文章根据八叉树适合虚拟场景划分的特点,采用了一种适合密集型区域的八叉树划分方法,进行场景划分。为适合八叉树的存储结构,对A*算法做了改进,引入优先级队列并采用了分层结构,采用了从叶节点到根节点的搜索方法,规划出了虚拟人行走的最优路径。

路径规划范文4

Abstract: This paper guide the roadmapping of industrial integration with the use of frame structure of Technology Roadmapping (Technology Roadmapping, as TRM). Then a conceptual framework with three layers is established, including regional economic development, competitive advantage and bearing capacity. At the same time, each layer of the framework is elaborated. Based on the analysis, with method of TRM, the roadmapping process of industrial integration which includes three main stages is developed. At last, we structure the typical roadmap of industrial integration.

关键词: 产业集成;路径规划;技术路径规划(TRM)

Key words: industrial integration;roadmapping;Technology Roadmapping(TRM)

中图分类号:F062・9 文献标识码:A 文章编号:1006-4311(2009)10-0009-05

0引言

近年来,随着技术路径规划方法使用频率的提高和使用范围的扩大,该方法成为企业或行业为其未来发展识别关键要素(包括技术、组织能力、产业政策等)、从而规划发展路径的有效工具。其应用范围主要体现在如下六类:①产品-技术规划;②业务重组;③流程开发;④战略评价;⑤研究网络的开发;⑥部门预测,并体现出应用领域不断拓展的趋势[1]。值得一提的是,TRM方法在新领域的每一次大胆尝试,都为该领域提供了新的发展契机,甚至引发了本领域管理思想中的文化变革[2]。尽管TRM方法的应用背景千差万别,但是均依托于包含多个层次的概念性框架,经过科学合理的筛选,将各层次的核心要素和指示要素演变的时间轴纳入最终的路径图,从而引导具体实践。这一思想可被产业集成的路径规划所借鉴,用于制定对地方乃至国家产业集成进程有指导意义的路径图。

我国目前对产业集成路径的研究主要在于集成路径的关键点提炼上,对产业集成的研究则侧重于其内涵和特性,以及对该理论的经济学解释[3-6],缺乏可用于路径规划的概念性框架和规划流程。本文以TRM的结构框架为基础,建立指导产业集成路径规划的概念性框架和规划流程,以期为特定产业的路径规划提供理论基础和实践指导。

1TRM的结构框架

技术路径规划的过程就是技术路径图的构建过程。技术路径图有很多形式,最普通的一种是描绘目标如何与资源、能力联系起来的多层图示,并辅之以时间轴,以指示特殊事件发生的时间节点。例如用于新产品开发的技术路径图中,会使用时间轴指示新产品开发过程中的阶段付成果。特定应用领域的概念性框架是技术路径图的构建基础,然而概念框架的建立除了依赖所应用领域的特定知识体系外,在组成部分、以及各部分间关系上还依赖技术路径规划本身的结构框架,表现为技术路径图的层次及层次间关系。

技术路径图的顶层用于代表路径规划要取得的成果或要满足的状态,包括外部市场和产业趋势与驱动(社会的、技术的、环境的、经济的、政治的、和基础设施的),以及内部商业趋势和驱动、里程碑、目标等,根据评价标准识别目标是技术路径规划的第一步。中层代表对顶层的趋势和驱动做出反应所借助的方式、手段、途径等,例如随着时间将要交付的产品、服务或能力,这常常直接与产品(特征和绩效)的演进相关。商业视角和技术视角通过中层得以沟通。底层通常与对趋势和驱动做出反应所需的资源相关,包括基于知识的资源,例如技术、技能和能力,以及其他资源,例如财政、伙伴关系和设施,用于支持中层的方式、手段、途径等。为了使技术路径图尽可能完整的反映路径规划的各个阶段,可根据实际需要把每一层扩充为多层。技术路径图一般指明了两个方向的路径:水平方向的路径指的是市场、产品、技术随着时间的变化过程;竖直方向的路径反映的是研发计划、技术、产品和市场的关系路径。技术路径图就是由这两个维度纵横交错而成的[7]。

2产业集成的概念性框架

产业集成是当产业集群发展到高级阶段时,由主导产业、相关性产业和支持性产业紧密联系所形成的具有整体竞争优势的创新集合体,其实质是具有开放性、创新性、动态性和网络特征的复杂系统。

产业集成的概念性框架是基于技术路径图的层次结构构建的。技术路径图的顶层用于代表路径规划要取得的成果或要满足的状态,鉴于产业集成是依托所在地域而发展起来的,其目的是要以产业集成为载体实现区域经济的持续稳定发展,因此,应把区域经济发展作为产业集成概念性框架的顶层。技术路径图的中层代表对顶层趋势和驱动做出反应所借助的方式、手段、途径等,援引至产业集成中,即是为实现区域经济发展产业集成要具备的能力,表现为产业集成的竞争优势。技术路径图的底层代表对趋势和驱动做出反应所需的资源,用于支持中层的方式、手段、途径等,援引至产业集成中即是区域经济发展所需的资源,用以获得中层的竞争优势,表现为产业集成的承载力。产业集成概念性框架与技术路径图结构的对照如表1所示。

2.1 顶层:区域经济发展

产业集成是实现区域经济持续稳定发展的载体。首先,产业集成使交易成本从本质上降低,进一步促进集成内外企业及相关机构的合作与创新,强化区域经济系统的内外经济联系,增强区域经济的开放程度,降低区域产品成本,使市场扩大,区域经济的比较优势增强;同时令区域经济系统的分工与协作愈加明显和集中,强化其主导产业;再者,产业集成的发展可以增强区域的聚集效应,形成规模经济,强化区域经济子系统之间的联系,使区域主导产业前向、后向扩散的范围和程度扩大,提高区域经济的区位优势,使区域的投资吸引力增强,从而加快新的优势产业的形成,进一步推动区域经济发展。

2.2 中层:竞争优势

竞争优势的增强是产业集成乃至区域经济发展的内源动力。产业集成是由产业集群演化形成的,且产业集群的竞争优势已在理论和实践两个层面得到验证,因此产业集成的竞争优势也就不言而喻了,只是与一般的产业集群相比,产业集成的竞争优势有其特殊性。产业集成的竞争优势以成本优势、创新优势和结构优势为主,辅之以其他优势。

2.2.1 成本优势

产业集成的成本优势体现在成本节约的广度和深度上。产业集成的成本优势离不开由于地理位置临近而引发的成本节约,包括处于同一产品链上的企业通过专业化分工降低原材料和产品的运输成本,节约生产时间与库存,从而降低生产成本;相同生产领域内企业通过合作和联盟等形式共同进行原材料采购,使议价能力提高,节约采购成本和运输成本;产业地理集中能够共同分享各种基础设施、服务设施,节约设施的重置成本;企业的经济活动根植于地方社会网络,良好信任基础的形成能够减少投机行为的发生,从而降低交易成本;企业的集中可引发人才的集中,劳动力的获取和使用成本也得到降低。产业集成特有的成本优势体现在两个方面:一方面,企业通过集成网络紧密联系,频繁的创新活动能够不断创造新的市场需求,在产业和服务的分工程度和专业化程度方面产生更高需求,从而形成正反馈,通过生产效率的提高达到成本降低的目的;另一方面,产业集成的网络特征使得企业间的竞争与合作在更大的空间展开,有利于企业改善官僚制的组织形式,从而通过有效的组织管理从更深层次上节约成本。

2.2.2 创新优势

产业集成具备长期的创新优势,体现在如下方面:第一,产业集成内完善的信息交流平台促进了主体间的资源共享与能力互补。除了群聚使得群内知识和信息不断累加从而为共享提供可能性外,集成的优势主要体现在完善的集成网络使信息的交流壁垒减少甚至消失,加快信息的交流速度,节约企业的学习费用,推动知识创新的增值与扩散,从而提高产业集群的整体技术创新能力。第二,产业集成内的分工协作降低了创新过程中各行为主体需承担的风险。集群使得风险由于行为主体数量增多而被分散,但更主要的是集成后其应对风险的综合能力得到加强,使技术创新过程中的不确定性因素减少,并缩短技术研发和商业转化之间的时间差,从根本上降低了需承担的风险。第三,产业集成的开放性和动态性便于其长期保持创新优势。产业集成能够突破因路径依赖所导致的集群锁定效应,保证区域内不断有新的行为主体加入,使纷繁复杂的信息不断涌入并得到交流,促进技术创新、管理创新等各类创新活动的发生,为集成企业提供更广阔的竞争和发展空间。

2.2.3 结构优势

产业集成内的产业结构虽然也是由主导产业、相关性产业和支持性产业构成,但随着外部环境变化,产业集成内的企业能够根据企业自身条件灵活地在主导产业和相关性产业间转化,同时仍享有其支持性产业所提供的便利,从而不会因主导产业衰落而失去竞争优势。一方面,主导产业和相关性产业可以互相转化。当主导产业已经成熟,竞争者之间面临产能过剩的压力时,企业内的人员和设备往往随着内部创业而重新配置,伴之以产业间的技术转移,促进了新的相关性产业产生。然而,各企业为了满足自身成长需要,往往是同一时间进入到了同一相关性产业中,由于新的相关性产业是由不同领域的不同企业转化而来的,因此从其诞生之日起就能汲取各方面新技术,产生活跃的创新活动,使其发展成为新的主导产业。另一方面,主导产业和支持性产业相互融合。为了使产业间信息流通顺畅、服务更加完善、应变能力增强,处于主导产业的企业往往和其支持性产业中的供应商互相投资控股,企业与供应商长期合作关系能够使主导产业衰落企业转而进入相关性产业时,仍可获得可靠的产品或服务。上述分析与产业集成的经济学解释相一致[5],进一步证实了产业集成的结构优势能够使其获得竞争优势。

除了上述分析的三个优势以外,产业集成也具备其他优势,如营销优势、融资优势、组织优势等,在进行产业集成路径规划时,要根据产业集成的实际情况以及要取得的预期效果选定。

2.3 底层:承载力

“承载力”是从工程地质领域转借过来的概念,其本意是指地基的强度对建筑物负重的能力,应用到产业集成领域,是指产业集成所在区域对其竞争优势的支撑能力,是竞争优势的来源。产业集成的各个竞争优势是由不同的承载力以及承载力间的相互作用共同支撑的,主要包括环境承载力、行为主体承载力、社会资本承载力、体制政策承载力。

2.3.1 环境承载力

产业集成所在区域的环境承载力是其竞争优势得以形成的前提条件。地理环境在产业集成早期发挥了重要作用,例如硅谷优美的自然环境与适宜的气候吸引了先驱企业进入,其持续衍生与裂变又为集成产生了新的进入企业。基建环境由交通、用水、电力、通信、休闲设施、公共建筑设施共同构成,其中便利的交通与通信条件是影响产业集成的重要因素,特别是信息基础设施建设,可使企业之间信息资源及时并充分共享,实现企业间业务协作,为整体竞争优势获取提供物质保障。同属于环境承载力的还有市场环境、市场发育程度及发育空间决定了产业集成内资源的转化能力,直接影响创新成果转化成产品投入市场的周期,开放的市场环境能够保持集成行为主体的异质性,从而促进新知识获取和创新,从而影响其竞争优势的形成。

2.3.2 行为主体承载力

产业集成的行为主体与产业集群一致,包括企业、高等院校与科研院所、中介服务机构。企业构成了产业集成日常运作的核心,是影响产业集成竞争优势的关键,位于同一价值链上的企业通过合作竞争等行为获取利润,同时还通过经验与知识共享等方式实现企业价值的增值。高等院校和科研院所是产业集成保持竞争优势的动力源泉,其不仅为集成输入大量的高素质人才,更是通过产学研合作等方式加速了技术创新和管理创新,例如在硅谷地区大学与产业界之间建立了产业联盟,加强了本地公司与整个地区基于知识的动态竞争优势。中介服务机构包括行业协会、各种服务中心、事务所和金融机构等,此类组织在形成产业集成竞争优势过程中的主要作用表现在:缩短行为主体相互之间的搜寻与选择的过程,通过综合比较优势、沟通供求信息和规范企业行为等方式促使其走上协同。

2.3.3 社会资本承载力

社会资本是指行为主体建立在相互信任与合作基础之上的持续社会关系网络,以及行为主体在互动过程中所产生的共享知识、规范、合作和信任等各种形式的资源,它能够给拥有主体带来利益。例如硅谷内的非正式交流促进了各种隐性经验类知识的传播,使其区域内信息和知识得以有效交流和扩散,成为其创新优势的来源之一。社会资本有利于拥有主体间信息、知识的快速流动,使拥有主体获取社会稀缺资源,提高创新效率,增强创新能力。产业集成正是这样一种关系网络综合体。值得一提的是,企业与高等院校、中介机构由于特殊的地缘、亲缘、学缘和行缘等多重关系,在长期的、频繁的交互作用中能够形成基于信任的社会关系网络,从而使所属区域具有比大企业等级组织更灵活、比市场效率更高的优势,从而将生产成本和经营成本降到最低[8],从这一角度来讲,社会资本承载力是产业集成竞争优势的显著来源之一。

2.3.4 体制政策承载力

体制政策承载力除了包括国家层面的体制政策外,主要是指产业集成所在地区地方政府对产业集成的特定体制政策支持。在我国,大多数高新区都是由政府规划而产生的,并通过产业政策、税收政策、外资吸引政策、人才保障机制等来吸引资金、人才、技术等生产要素向区内集聚,特别是吸引那些具备产业带动优势和有产业关联效应的企业进入园区,从而有效推动高新区走向产业集成的进程。新竹科学工业园在规划伊始为了保证园区的高科技品质,建立了严格的高新企业审查机制,确保入园企业均是具有较强创新能力的企业,从而使园区发展迅速,产业特色很快形成。班加罗尔工业园则是借助印度对软件产业实行的零关税、零流通税和零服务税等措施,成为全球最成功的软件外包中心。由此可见,源于政府的体制政策支持是产业集成取得竞争优势的重要推动力。

以上对产业集成概念性框架中各层的分析,如图1所示。为了尽可能完整地反映整个框架,特在承载力一层下设微观要素层,作为对承载力层的支撑。

3用TRM进行产业集成路径规划的流程

鉴于路径规划的演变是由管理实践引导,而不是源于管理理论,因此,对于该方法的每一次应用都需要根据特定背景和目的进行定制[9]。产业集成路径规划的流程由三个核心阶段组成,分别是竞争优势选择阶段、承载力评估阶段和规划制定阶段。此外,在路径规划正式开始前,还需建立规划小组、确定规划目标、制定规划进度表,在产业集成路径规划制定完毕并付诸实施后,还需对实施效果进行动态跟踪,将其反馈到先前路径规划的制定流程中,由此开始新一轮的集成路径规划。三个核心阶段具体如下。

图2是按上述方法绘制的典型产业集成路径规划图。规划图中的各层与产业集成概念性框架中的层次一致。ME1,ME2,ME3,BP1,BP2,CA1是对应层次中权重较大的要素,各层中的要素个数可根据路径规划背景和计算结果选定,通常情况下,要素个数自上而下逐渐增多。水平方向的路径指明了各要素随时间推移的预期发展过程,可通过添加字母下脚标的方式区别各时间点的要素状态。竖直方向的关键路径在图中用粗箭线表示,即路径ME2b-BP2a-BP2b-CA1b-REDb。其中ME2是微观要素层中对区域经济发展影响权重最大的要素,BP2是使ME-BP路径权重最大的承载力,CA1是使BP-CA路径权重最大的竞争优势。同时,纵向路径需要指明路径中各要素的状态,因此有必要添加字母下脚标对要素状态进行区分。在图中,路径ME1a-ME1b-BP1a-BP1b-CA1a-CA1b-REDb和路径ME3a-ME3b-BP2b-CA1b-REDb是除关键路径外的另两条纵向路径,连接着各层中权重较大的因素,对规划目标的实现同样有深远影响,故不可忽略。

路径规划图本身,尽管概念和结构相对简单,包含的具体信息也十分有限,但却基于组织内大量的支持性分析,从不同视角整合了组织内的微观要素、信息资源、工具和方法,代表着路径规划过程的最终精炼产出。纵观产业集成路径规划整个流程不难看出,路径规划是一个动态的过程,需要根据环境变化而灵活调整,以维持其生命力,便于其效果的持久发挥。

4结论和展望

将TRM方法应用于产业集成路径规划是一种大胆尝试。该方法的结构框架为产业集成概念性框架构建提供了有益指导,概念性框架中的区域经济发展、竞争优势和承载力构成了路径规划图的三个层次。路径规划流程很好地整合了各层中的核心要素,通过现有的分析技术和分析工具有效地建立起层级间的联系,从而为特定产业的路径规划提供指导。然而,还需从产业集成路径规划实践中提炼出涉及更多层次、更多方面的新内容,并将其他有效的分析工具与分析方法合理引入到规划流程中,从而提高此方法的使用效率并拓展其适用范围,这是后续研究有待深入的方面。

参考文献:

[1]Robert Phaal, Clare Farrukh, David Probert. Customizing Roadmapping. Research Technology Management, 2004,47(2):26-37.

[2] Alec McMillan. Roadmapping――Agent of Change. Research Technology Management, 2003,46(2):40-47.

[3]王海龙、武春友:《基于产业集成的科技创业企业成长路径――以路明科技集团为例》[J];《管理学报》2007(5):668-673。

[4]张贵、周立群:《产业集成化:产业组织结构演进新趋势》[J];《中国工业经济》2005(7):36-42。

[5]黄建康:《产业集成:基于提升传统产业竞争力的分析》[J];《宏观经济》2004(4):16-18。

[6]张立、王学人:《推进我国产业集成的问题、成因及对策探讨》[J];《当代财经》2002(7):56-58。

[7]李雪凤、仝允桓、谈毅:《技术路线图和技术路线图思维》[J];《科学学与科学技术管理》2005(8):26-29。

路径规划范文5

关键词关键词:自动泊车;反正切函数;泊车轨迹;MATLAB

DOIDOI:10.11907/rjdk.171076

中图分类号:TP319

文献标识码:A文章编号文章编号:16727800(2017)005011305

0引言

随着汽车保有量的逐年增加,导致泊车位变得越来越紧张。确保每一个驾驶员安全无碰撞地进行泊车,已日益成为当今汽车技术的一个热门研究方向。本文根据反正切函数对泊车轨迹进行拟合研究,规划泊车轨迹,使车辆顺利进入泊车位。

1平行泊车系y坐标系

把正在泊车的车辆简化成一个刚体,如图1所示,是简化后的泊车运动学模型[1]。

假设车辆从右向左进行泊车,泊车位右上角点D′为坐标原点,A′B′C′D′表示停车位的4个顶点;ABCD表示汽车的4个顶点;abcd代表汽车4个车轮与水平地面的接地点;θ为车身航向角,即汽车中心轴与水平方向的夹角,定义逆时针为正,顺时针为负。汽车自动平行泊车系统流程如图2所示。

2泊车轨迹

如图3所示,当车辆停在泊车起始位置时,即设计好的泊车轨迹起点,驾驶员开始向右打方向盘,车辆以圆形轨迹行驶,直到点O′为止停车,然后再向左打方向盘,汽车同样以圆形轨迹行驶,直到车身回正为止,车辆行驶至泊车目标位置。综上述,可以简单理解为泊车轨迹是以点O1和O2为圆心,R1和R2为半径,车辆行驶经过的两条相交的圆弧组成。

2.1泊车位大小确定

自动泊车实现的难度和泊车位大小直接相关。根据我国实际情况,设定本文研究的泊车车位长为7m,宽为2.5m。假如车辆在泊车过程中都是以最小半径行驶,所以车辆行驶的路程最短,泊车所需空间也最小。具体估算过程如下:

如图4所示,A0B0C0D0表示汽车在泊车目标位置时的4个顶点。Rr_min表示向右将方向盘打到底时,汽车后轴中心的最小半径;Rl_min表示向左将方向盘打到底时,汽车后轴中心的最小半径。图中所示曲线轨迹则为泊车最短路径,图中车位即为极限最小车位。根据Ackerman转向原理,驾驶员向右、向左将转向盘打到底时的前轴中心转角分别为:

式中,R1、R2分别表示汽车向左和向右打方向盘时,汽车后轴中心的转向半径;S1、S2分别表示汽车向左和向右打方向盘时,汽车后轴中心的行驶路径;S0表示汽车从泊车出发位置行驶到泊车起始位置的横向位移;h0表示汽车从泊车起始位置行驶到泊车目标位置的纵向位移;θ′为汽车行驶至O′点时,汽车车身的瞬时航向角。

由式(16)、(17)可得,泊车时如果确定了泊车起始位置,即确定了S0、h0时,R1与R2相加之和即为固定常数。对R1和R2中的任意一个赋值,即可得出泊车轨迹曲线,从而进行平行泊车。但是符合两半径和的R1、R2组合太多,无法确定具体泊车轨迹。所以,还要根据碰撞点约束条件确定有效的泊车路径。

因此,本文对在泊车过程中车辆与周边障碍物发生碰撞的可能性进行分析,并列出了对应的碰撞约束条件[3]。

(1)汽车已经进入泊车位,泊车后期摆正车身时,车身顶点B和泊车位内侧边界线B′C′可能发生碰撞,如图6所示。

式中,Lbac为后悬,Lreal是泊车位长,δ是车位安全系数值,将式(20)、(21)进行联合便可求出R1的最大取值,定义为R1max。

(3)平行泊车初期,车身顶点D距离停车位纵向位置最远时,车身顶点D和泊车位侧向障碍物有可能发生碰撞,如图8所示。

车身顶点D以O2为圆心,RD1为半径进行圆周行驶,车身顶点D和侧向障碍物发生碰撞时,此时R2为半径最小极限值。在泊车起始位置,车身处于水平状态,R2越小,车身转弯越剧烈,点D对于车位的偏移也越大。根据几何关系可得:

RD1=(L-Lbac)2+(R2+W2)2(22)

为防止车身顶点D与泊车位侧向障碍物发生碰撞,要满足以下关系:

RD1-R2+Δy+Wreal≤H(23)

式(23)中,y表示汽车后轴中心和车位边界线A′D′之间的距离,Wreal为实际车位宽,H为车身顶点D能偏移车位边界线B′C′的最大极限距离,取H=6m。将式(22)和(23)进行联合便可求出R2的最小值,定义为R2min。

(4)车辆右后轮将要进入泊车位时,两个后车轮接地点的延长线和汽车右侧BC的交点与车位边界点D′有可能会发生碰撞,如图9所示。

交点以O2为圆心,Re1为半径作圆周运动,点D′坐标为(xD′,yD′),圆心O2坐标为(xO2,yO2),当交点和车位边界点D′发生碰撞时,Re1取最小极限值,所以这时R2也为最小极限值。要避免交点和泊车位边界点D′发生碰撞,需满足以下关系式:

R2-W2≥(xo2-xD′)2+(yo2-yD′)2(24)

由式(24)可求得此情况下R2的最小值,然后和R2min比较大小,将最大值作为最终的R2最值。

综上述,当S0、h0确定时,汽车的泊车出发位置、泊车起始位置、泊车目标位置都会确定。一旦确定泊车起始位置和泊车目标位置,R1、R2两者之和则是唯一的定值[4]。根据汽车在自动泊车过程中可能发生的碰撞情况,求出了R1的最大值R1max和R2的最小值R2min,又当汽车车型确定后,向右和向左打方向盘时所对应的最小转弯半径同样固定。所以,R1、R2的取值范围都可求出,这为设计出有效的泊车轨迹奠定了基础。

泊车轨迹用两段相切的圆弧表示,可以简化倒车过程。然而,两相切圆弧轨迹在相切点处存在曲率不连续性,这就要求驾驶员把方向盘从一个位置反转到另一个位置,使方向盘转角发生阶跃性变化。如果对S0、h0、R1适当赋值,两段相切圆弧轨迹和方向盘转角的阶跃变化如图10、图11所示。

在两段圆弧泊车轨迹切点处,转向盘转角存在突变问题,此处的曲率不连续,导致平行泊车时会出现中途停车转向的问题,从而加剧轮胎磨损,增加电机负担。

3反正切函数拟合平行泊车倒车轨迹

为了解决两段相切圆弧曲率不连续的问题,本文经过反复仿真验证,最终确定了最佳反正切函数[5]:

y=a・arctan(bx+c)+dx3+ex2+fx+g(25)

式(25)中,a、b、c、d、e、f、g榉凑切函数的参数,这些参数对拟合曲线泊车轨迹起到决定形状的作用。

对图10中的平行泊车轨迹用式(25)进行逼近拟合,如图12所示,即运用Matlab中的cftool工具对圆弧轨迹进行拟合的过程。

可以得到拟合参数a、b、c、d、e、f、g取值为:0.535 8、0.635、1.894、-0.004 094、-0.019 85、0.161 6、0.485。此拟合函数可以满足原两相切圆弧泊车轨迹形状的要求,同时可以使泊车车辆在泊车起始位置、泊车目标位置时,车身都可以回正,从而大大降低停车难度。具体拟合情况如图13所示。

从图13中可以看出,反正切函数的拟合效果很好,两条平行泊车轨迹基本处于完全拟合状态,在泊车起始位置与泊车目标位置时,车身基本上可以满足回正的要求。根据已搭建好的数学模型,在Matlab Simulink中创建泊车环境,车辆在不同泊车起始位置对平行泊车过程进行动态仿真,结果如图14、图15所示。

从泊车过程的仿真图中可以看出,在这种拟合方法下,车辆不仅可以比较平顺地进行倒车,解决了车辆中途需要停车转向的问题,而且车辆行驶到泊车目标位置时,车身基本实现回正。为验证仿真结果的可行性,进行了整车实验。采用荣威作为实验车,其基本实验参数如表1所示。

4实验误差与分析

经过多次泊车实验,汽车基本上可以按照仿真结果进行,基本满足了实车泊车要求,顺利泊车到目标位置,说明此反正切函数仿真结果的正确性和可行性,可以进行实用。但是也存在以下问题:①泊车过程中,车辆与车位边界以及周边障碍物之间有可能发生碰撞;②泊车结束后,车辆车身不能完全摆正。对以上问题进行分析研究,得出如下几点可能原因:

(1) 传感器的探测精度不够[6]。传感器感知系统对同样的停车空间进行扫描,检测值并不完全固定,存在一些浮动。

(2)在建立车辆运动学模型时,忽略了轮胎侧向力的影响,这与实际情况存在一定出入,势必造成误差的产生。

参考文献参考文献:

[1]王芳成.自动平行泊车系统的研究[D].安徽:中国科学技术大学,2010.

[2]姜辉.自动平行泊车系统转向控制策略的研究[D].长春:吉林大学,2010.

[3]YANAN ZHAO,EMMANUEL,G COLLINS JR.Robust automatic parallel parking in tight spaces via fuzzy logic[J].Robotics and Autonomous Systems,2005,51(23):111127.

[4]THIERRY FRAICHARD,CHRISTIAN LAUGIER.Smooth trajectory planning for a carlike vehicle in a structures world[C].IEEE International Conference on Robotics & Automation,1991:318323.

路径规划范文6

关键词 路径规划;全局规划;局部规划

中图分类号 TP242 文献标识码 A 文章编号 1674-6708(2009)10-0067-02

路径规划是指机器人从起始点到目标点之间找到一条安全无碰的路径,是机器人领域的重要课题。移动机器人技术研究中的一个重要领域是路径规划技术,它分为基于模型的环境已知的全局路径规划和基于传感器的环境未知的局部路径规划。本文综述了移动机器人路径规划的发展状况,对移动机器人路径规划技术的发展趋势进行了展望。

根据机器人工作环境路径规划模型可分为两种:基于模型的全局路径规划,这种情况的作业环境的全部信息为已知;基于传感器的局部路径规划,作业环境信息全部未知或部分未知,又称动态或在线路径规划。

1 全局路径规划

全局路径规划主要方法有:可视图法、自由空间法、栅格法、拓扑法、神经网络法等。

1.1 可视图法

可视图法视移动机器人为一点,将机器人、目标点和多边形障碍物的各顶点进行组合连接,并保证这些直线均不与障碍物相交,这就形成了一张图,称为可视图。由于任意两直线的顶点都是可见的,从起点沿着这些直线到达目标点的所有路径均是运动物体的无碰路径。搜索最优路径的问题就转化为从起点到目标点经过这些可视直线的最短距离问题。

1.2 拓扑法

拓扑法将规划空间分割成具有拓扑特征的子空间,根据彼此连通性建立拓扑网络,在网络上寻找起始点到目标点的拓扑路径,最终由拓扑路径求出几何路径。拓扑法基本思想是降维法,即将在高维几何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题。

1.3 栅格法

栅格法将移动机器人工作环境分解成一系列具有二值信息的网格单元,多采用四叉树或八叉树表示,并通过优化算法完成路径搜索,该法以栅格为单位记录环境信息,有障碍物的地方累积值比较高,移动机器人就会采用优化算法避开。对栅格的改进采用以障碍物为单位记录的信息量大大减少,克服了栅格法中环境存储量大的问题。

1.4 自由空间法

自由空间法应用于移动机器人路径规划,采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划。自由空间的构造方法是从障碍物的一个顶点开始,依次作其它顶点的链接线,删除不必要的链接线,使得链接线与障碍物边界所围成的每一个自由空间都是面积最大的凸多边形。连接各链接线的中点形成的网络图即为机器人可自由运动的路线。

1.5 神经网络法

可视图法缺乏灵活性,且不适用于圆形障碍物的路径规划问题。神经网络法用于全局路径规划可以解决以上问题。算法定义了整条路径的总能量函数,相应于路径长度部分的能量和相应于碰撞函数部分的能量。由于整个能量是各个路径点函数,因此通过移动每个路径点,使其朝着能量减少的方向运动,最终便能获得总能量最小的路径。

2 局部路径规划

局部路径规划包括人工势场法、模糊逻辑算法、神经网络法、遗传算法等。

2.1 人工势场法

人工势场法基本思想是将移动机器人在环境中的运动视为一种虚拟人工受力场中的运动。障碍物对移动机器人产生斥力,目标点产生引力,引力和斥力周围由一定的算法产生相应的势,机器人在势场中受到抽象力作用,抽象力使得机器人绕过障碍物。

2.2 模糊逻辑算法

模糊逻辑算法基于对驾驶员的工作过程观察研究得出。驾驶员避碰动作并非对环境信息精确计算完成的,而是根据模糊的环境信息,通过查表得到规划出的信息,完成局部路径规划。模糊逻辑算法的优点是克服了势场法易产生的局部极小问题,对处理未知环境下的规划问题显示出很大优越性,对于解决用通常的定量方法来说是很复杂的问题或当外界只能提供定性近似的、不确定信息数据时非常有效。

2.3 神经网络法

模糊控制算法有诸多优点,但也有固有缺陷:人的经验不一定完备;输入量增多时,推理规则或模糊表会急剧膨胀。神经网络法则另辟蹊径。路径规划是感知空间行为空间的一种映射,映射关系可用不同方法实现,很难用精确数学方程表示,但采用神经网络易于表示,将传感器数据作为网络输入,由人给定相应场合下期望运动方向角增量作为网络输出,由多个选定位姿下的一组数据构成原始样本集,经过剔除重复或冲突样本等加工处理,得到最终样本集。

2.4 遗传算法

遗传算法以自然遗传机制和自然选择等生物进化理论为基础,构造了一类随机化搜索算法。利用选择、交叉和变异编制控制机构的计算程序,在某种程度上对生物进化过程作数学方式的模拟,只要求适应度函数为正,不要求可导或连续,同时作为并行算法,其隐并行性适用于全局搜索。多数优化算法都是单点搜索,易于陷入局部最优,而遗传算法却是一种多点搜索算法,故更有可能搜索到全局最优解。

3 移动机器人路径规划技术的发展展望

随着计算机、传感器及控制技术的发展,特别是各种新算法不断涌现,移动机器人路径规划技术已经取得了丰硕研究成果。从研究成果看,有以下趋势:首先,移动机器人路径规划的性能指标要求不断提高,这些性能指标包括实时性、安全性和可达性等;其次,多移动机器人系统的路径规划。协调路径规划已成为新的研究热点。随着应用不断扩大,移动机器人工作环境复杂度和任务的加重,对其要求不再局限于单台移动机器人。在动态环境中多移动机器人的合作与单个机器人路径规划要很好地统一;再次,多传感器信息融合用于路径规划。移动机器人在动态环境中进行路径规划所需信息都是从传感器得来。单传感器难以保证输入信息准确与可靠。此外基于功能/行为的移动机器人路径规划,这是研究的新动向之一。

总之,移动机器人的路径规划技术已经取得了丰硕成果,但各种方法各有优缺点,也没有一种方法能适用于任何场合。在研究这一领域时,要结合以前的研究成果,把握发展趋势,以实用性作为最终目的,这样就能不断推动其向前发展。

参考文献

[1]陈陈.优化方法与最优控制[M].北京:机械工业出版社,1993.

上一篇年度规划

下一篇理财规划