动态充电路径规划

动态充电路径规划（共6篇）

动态充电路径规划 篇1

建筑物内发生重大突发性事故(如火灾、爆炸以及人员拥挤踩踏等)将给事故现场人员的生命安全带来极大的威胁。在现有的物质设施基础上,选择最优撤离路径,动态调整疏散方案是避免和减轻人员伤亡的有效途径。目前,我国的建筑设计防火规范对安全疏散楼梯的数量、到达楼梯的距离、楼梯的宽度、防排烟设施、内部装修材料等都做了明确的规定。但是由于火灾等突发事件具有极强的不确定性,造成建筑疏散结构的重大改变在所难免,确定动态的安全疏散路径具有十分重要的意义。

笔者以系统优化理论为指导,以动态规划为手段,建立安全疏散路径和人员分流的网络模型,对安全疏散预案的制定提供技术支持。

1 动态规划原理及模型

动态规划是解决多阶段决策问题的优化方法。建筑安全疏散过程中,随着时间或空间的变化会出现人员拥堵、道路障碍、烟气毒气扩散等情况,造成疏散不畅或中断,所以疏散过程会被人为划分为若干个相互联系的阶段,每个阶段都要做出一定的决策,即多阶段决策过程。解决安全疏散问题即是在不同阶段采用不同的决策方案,决策方案的全体称为疏散策略,其目的是疏散总过程最优。

动态规划最优性原理:作为整个过程的最优策略具有这样的性质:无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。

R Bellman方程见式(1)。

undefined (1)

式中:fk*(i)为在第k步中点i到终点的最短路径;dk(i,j)为由点i到达点j的距离。

式(1)说明点i到终点的最短路径是这样选定的:使j到达终点的路径是点i到达终点路径的一部分,并由条件dk(i,j)+fk+1*(j)取最小选定。

动态规划的求解步骤是:由最后阶段的各种状态取其最优决策开始计算,直到初始阶段各种状态的最优决策为止。

2 建筑安全疏散问题的提出与基本假设

建筑内发生突发事件时,人员自救至关重要。有效的疏散计划对于减轻灾害或事故损失,保证人民生命财产安全具有重要意义。疏散计划是应急预案的重要内容之一,研究疏散路径、人员分流以及动态疏散引导的数量化,将会使疏散更加合理、有效、安全。

基本假设:以全体人员安全撤离作为动态调整网络总体目标;根据突发事件和建筑结构特点人为划分疏散阶段,定义状态,状态与状态间的连接即为通路,未必与实际疏散通道一一对应;建筑安全出口在疏散网络图合并为一个,室外即为安全;网络模型中所示权重,代表通过安全疏散路线的综合代价,用无量纲数字表示,对于无量纲数字的确定,在多种文献中均有论述,如文献[1]～文献[4];人员训练有素,状态一致。

3 最优疏散路径的选择

3.1 问题描述

某三层商业楼,有三个疏散楼梯可供逃生,一层有两个安全出口。每层均为敞开式大厅。发生突发事件,需要对人员进行疏散,寻找安全疏散路线。

3.2 建立模型

疏散以建筑内全体人员全部撤离为目的,故以三层最远端人员(甲)撤离为目的,建筑中其他人员的行动通过对行为人甲的影响(如人员拥堵影响撤离速度)表现出来。因为建筑内为敞开式营业厅,假设没有造成疏散拥堵,故仅将楼梯和安全出口作为节点考虑,构造网络模型如图1所示。

在图1中,A点表示疏散起点,位于三层某点;B1、B2、B3是三层楼梯下端点(位于二层地面),A与Bi的连线值表示人员穿行于大厅与通过三层楼梯的代价;C1、C2、C3是二层楼梯的下端点(位于一层地面),Bi与Cj的连线值表示人员穿行于二层大厅与通过二层楼梯的代价;安全出口有两个,分别为D1、D2,Ci与Dj之间的连线值为从二层楼梯下端到安全出口外的代价;E为安全出口外端,意味安全。

疏散过程可以看作如图1所示的多阶段决策过程。寻找最优疏散路径以疏散代价之和最小为目标。

3.3 动态规划方法求解

由图1表示的最短线路问题中,可将线路网络分成4个阶段,即A至Bi(i=1,2,3)为第一阶段,Bi(i=1,2,3)至Ci(i=1,2,3)为第二阶段,Ci(i=1,2,3)至Di(i=1,2)为第三阶段,Di(i=1,2)至E为第四阶段。

求解是从后向前逆向进行的。第四阶段有两条路:f4(D1)=d(D1,E)=3,路线是Di→E;f4(D2)=d(D2,E)=4,路线是D2→ E。第三阶段见式(2)。

undefined

这说明由C1到终点E的最短距离为7,其路线是C1→D1→E;同理,计算得C2到终点E的最短距离为11,其路线是C2→D1→ E;由C3到终点E的最短距离为10,其路线是C3→D1→E。

第二阶段见式(3)。

undefined

同理计算得f2(B2)=18,f2(B3)=19,相应的疏散路线是B1→C1→D1→E,B2→C1→D1→E以及B3→C3→D1→E。

第一阶段见式(4)。

undefined

说明从A点进行安全疏散,最优路线为路线是A→B1→C1→D1→E,最短距离为19。

在实际应用中,任意点的疏散路线都可以类似考虑。

4 人员优化分流

以某三层公共阅览室为例,其二、三层平面示意图如图2所示。

图2中S区域为天井,人员只能从天井四周疏散,图书馆一楼为敞开式大厅,在一楼疏散只需考虑从楼梯口到安全出口的行走距离因素即可。

如果在阅览室满员时疏散必然会在楼梯处发生拥堵,所以撤离时疏散楼梯的应用,即人员的合理分流至关重要。一般情况下,每一层楼梯人员的疏散相对独立,就近选择疏散楼梯,直到发生拥堵才会考虑选择其他路径,会造成时间的浪费。制定疏散预案,从开始时刻优化人员分流可以大大提高疏散效率。

案例中建筑有两个疏散楼梯,假设二楼人员就近选择楼梯疏散。由于两个阅览室的人员数目不均等,如果再选择就近疏散,三层人员会在二层楼梯处与二层人员会合,出现两部楼梯上人员密度失衡的情况。故考虑人员分流的行动应从三层开始,建立网络疏散图,优化疏散预案。

4.1 初始节点的处理

从图2可知,三层有两个阅览室,每个阅览室有两个出口。在疏散中,每个阅览室被人为划分为两个空间(动态),以每个空间距离出口最远端的距离为疏散起点,那么三层共有4个疏散起点Ai,i=1,2,3,4,而疏散以最后一人撤离为目标,所以设定一个虚拟初始节点,连接4个疏散起点,之间连线上的距离是该疏散起点的疏散代价与4个节点的最大疏散代价之差。即疏散以undefined为评价指标,那么初始节点S与各节点Ai之间的连线值为Z*-Zmin(Ai,E),i=1,2,3,4。

4.2 人员分流的处理

设综合报刊阅览室n人,其中流向电梯一n1人,则流向电梯二n-n1人,根据阅览室情况,该阅览室人员有k种划分;科技及外文阅览室m人,其中流向电梯一m1人,则流向电梯二m- m1人,该阅览室人员有l种划分。设三层楼梯下端与二层汇合处为节点Bj,j=1,2,从节点Ai到Bj的连线值dj(x,y)(j=1,2)表示相应路段上的疏散代价,x、y为两个阅览室流向每个电梯的人员数,对应着人员分流方案。

4.3 人员会合的处理

三层电梯下方出现两层人员会合的情况,人员密度增加,速度变慢。二层待疏散人员也存在疏散初始节点的问题。为此,在网络模型中引入虚拟节点Ck,k=1,2,设置在Bj的后面,意味着三层人员排在二层人员后面疏散,这样不影响对整个建筑人员疏散时间的评估。Ck与Bj间连线值表示三层人员等待二层人员撤离所付出的代价。

4.4 动态疏散引导

由于动态规划是由最后阶段的各种状态取其最优决策开始,直到初始阶段各种状态的最优决策为止。所以在安全疏散时,从开始救援的安全点开始,依次向里考虑,安排疏散路径,遇到瓶颈或故障点可以及时进行调整,确定的疏导方案是与实际相契合的。

(1)临时故障点的处理。

设dk(i,j)表示疏散节点i和j之间的距离,如果突发事件导致两点间的道路中断,则将dk(i,j)的值改变为+∞,由于求解从后向前,在dk(i,j) +fk+1*(j)取最小的过程中,经过j点的路径自然会被删除,从而不需改变网络结构图就能够动态调整疏散路线。

(2)临时救援点的处理。

在突发事件发生时,人们可以从建筑底部安全出口撤离,但是对于高层建筑,面对突发事件如火灾、毒气时,全部人员从底层撤离耗时太长不切实际,避难层、顶部的应用变得尤为重要。这时在网络图中安全出口的数量明显增加,疏散距离也会成倍缩减。此外在救援中,抢先救援人员可能根据实际情况增加外部救援点,那么在网络图中就会增加新的终点,与临近节点的距离改变为零,相邻区域的节点间的距离也会相应减小,新的疏散路线也会产生。

5 结束语

动态规划方法能够有效解决多阶段决策问题的求解问题。安全疏散路径选择和人员优化分流可以作为多阶段决策问题来处理。笔者构造网络模型,利用动态规划方法解决该类问题,为科学制定和评估消防疏散预案提供新的思路。

摘要：针对建筑安全疏散预案的设计问题,将动态规划设计方法分别应用于最优路径的选择和人员分流的预案设计中,在合理构造安全疏散网络模型的基础上,依据动态规划的原理进行科学计算。实验证明该方法能够定量分析人员分流问题,动态调整网络模型,有效地适应疏散中遇到的变化。

关键词：动态规划,安全疏散,网络模型

参考文献

[1]肖国清,温丽敏,陈宝智,等.毒气泄漏时的最佳疏散路径[J].东北大学学报,2001,(6):674-677.

[2]李引擎,肖译南,张向阳,等.火灾中人员安全疏散的计算机模型[J].建筑科学,2006,(1):1-5.

[3]崔喜红,李强,陈晋.大型公共场所动态引导人移动路径设计方法[J].中国安全科学学报,2008,(11):48-54.

[4]孔维伟,刘栋栋.北京复兴门地铁火灾时人员安全疏散研究[J].北京建筑工程学院学报,2009,(4):29-32.

[5]孙宽.基于运输模型的安全疏散方案优化方法探讨[J].安全与环境工程,2010,7(3):74-77.

[6]杨海潮,孙冰.基于PERT和最短路理论的人员疏散最优化[J].消防科学与技术,2011,30(2):103-105

[7]张海卿,闫明仁.安全疏散中人的行为研究及模糊综合评价[J].消防科学与技术,2010,29(3):252-255.

[8]刘伟,邢志祥,常建国.针对不同人员特征的安全疏散模拟[J].消防科学与技术,2010,29(4):297-300.

动态充电路径规划 篇2

随着机器人技术的不断发展, 移动机器人在工业生产、军事、服务、科学探索等领域得到了广泛的应用。在移动机器人相关技术的研究中, 路径规划一直是热点和核心课题。路径规划是指按照一定的技术标准 (如距离、时间、能量) , 搜索一条从起始点到目标点, 并能避开障碍物的最优或次优的安全路径。根据对环境信息的掌握程度, 路径规划可分为环境信息完全已知的全局路径规划和环境信息完全未知或部分未知的局部路径规划。此外, 还可以根据目标、障碍物的运动与否分为动态路径规划和静态路径规划。早期的路径规划研究大都在静态环境下, 主要方法有:可视图法、自由空间法、A*搜索算法等。然而, 随着机器人应用领域的扩大和现代工业环境的变化, 要求机器人能适应更加复杂和多变的工作环境。动态环境的路径规划问题随之成为机器人路径规划研究的重要方向, 常见的方法有:人工势场法、神经网络法、遗传算法、模糊逻辑法等。

近几年, 人们对动态路径规划的研究朝着智能化和多元化方向发展。文献[1]采用模糊遗传算法解决自主移动车辆在非结构空间和变化环境中的导航问题。通过避障行为的在线学习, 该系统能够不断更新知识库从而动态地适应不断变化的新环境。文献[2]分析了差动轮式移动机器人的运动学和动力学特性, 提出了一种基于传感器的混合式路径规划算法。该算法通过模糊控制器和瞬时目标引导机器人沿障碍物边界向目标运动, 利用多项式产生弯道处的光滑路径, 对于非完整约束机器人全局收敛。文献[3]利用调和函数和混合边界条件建立势场, 通过有限元法解决局部微分方程。该算法能够处理外形复杂的障碍物和边界, 并用于移动机械手和车辆的动态路径规划。文献[4]引入虚拟面板的概念并提出了基于运动学的反应式导航算法。通过虚拟面板移动障碍物被映射为静态障碍物, 碰撞检测和路径规划过程都得到简化。文献[5]提出了人工协调场的概念, 将吸引力、排斥力和协调力结合起来有效克服了传统人工势场法常遇到的局部最小和抖动问题。在蚁群算法的基础上, 文献[6]提出了一种采用模糊推理评估路径的优化算法。该算法记录蚁群经过的节点, 计算时间比一般蚁群算法节约10%左右。文献[7]提出了一种嵌入式神经网络算法。该算法无需检测机器人或神经节点的位置也无需建立环境地图, 适用于救援机器人的路径规划。文献[8]提出了生物激励神经网络算法, 机器人的运动空间是由神经网络组成的拓扑状态空间, 机器人向神经元活性最大的位置运动。该算法能够适应动态不确定环境, 无局部最小且计算复杂度低[8,9]。文献[10]在神经网络方法的基础上结合距离传播模型提出了一种高效的动态路径规划方法, 该方法将抽象的神经元活性转化为更直观的距离信息。

本文在移动机器人路径规划研究中引入了混沌理论。混沌理论的一个基本问题, 当混沌有害时需要对其进行削弱或抑制称为混沌控制;当混沌有用时可以对其进行强化或有目的的产生混沌称为混沌反控制[11]。混沌反控制主要用于保密通讯、密码学、脑科学、激光物理等领域。随着混沌理论的发展其应用领域不断扩大。在机器人研究中, 人们结合混沌理论对人工势场法、遗传算法等原有的路径规划方法进行了改进和优化[12,13]。本文提出了一种基于混沌反控制并具备一定预测能力的导航算法。该算法通过在路径规划的关键位置即目标运动方向不明的位置控制机器人混沌运动, 待目标运动趋势明朗后再进行路径规划, 可以减少随机选择造成的非最短路径的出现。此外, 该算法针对目标振荡运动且速度大于机器人的情况进行了分析。通过目标运动趋势的短期预测, 机器人可以在速度较慢的情况下成功追踪到目标。

1基本原理

本文所研究的动态路径规划算法是以神经网络和距离传播模型为基础, 用拓扑地图描述机器人的运动空间。拓扑地图由自由栅格和障碍物栅格组成, 栅格顺序编号并且只与临近栅格相连。对于编号为i的栅格, 定义Bi为与i相邻的自由栅格的集合, dij代表i和j两个自由栅格间避开障碍物的最短距离。xi (n) 代表n时刻目标到i栅格的最短无碰距离, xi (n) 的定义如下[10]:

$x{}_i(n+1)=\{\begin{array}{l}0(i\text{为}\text{目}\text{标}\text{位}\text{置})\\ D(i\text{为}\text{障}\text{碍}\text{物}\text{位}\text{置})\\ \min (x{}_i(n),f(i,n))\text{其}\text{它}\end{array}$

(1)

其中D表示一个足够大的距离, f (i, n) 定义为:

$f(i,n)=\underset{j\in B{}_i}{{\displaystyle \min }}(d{}_{ij}+x{}_j(n))$ (2)

自由栅格i仅存储它到相邻栅格的距离dij (j∈Bi) 以及它到目标点的最短距离xi (n) 。

为简化分析过程保证算法的可行性, 对机器人及其运动空间做出以下假设:

1) 目标和障碍物的位置是实时更新的, 并且更新的频率远小于整个系统更新的频率。

2) 机器人位置和速度已知, 目标和障碍物的位置和速度可以实时探测到。

3) 目标、障碍物、机器人都只能从一个栅格点向另一个栅格点作直线运动, 只有到达栅格处才能改变运动方向。

在地图和假设的基础上, 距离信息从目标点向起始点逐层传播称为距离传播过程。距离传播过程从目标点开始向相邻自由栅格扩展, 每个自由栅格保存此点到目标的最短距离值, 直至传到起始点构成一条从起始点到目标的最短路径。传播结束后, 机器人从起始点沿最短路径前进。运动过程中如果目标或障碍物位置发生改变, 重新进行距离传播。设机器人所处环境如图1所示, 其中2、6、7、14、15为障碍物栅格, 其余为自由栅格。1为目标位置, 4为起始点, 水平或竖直相邻栅格间距1。初始时刻x1 (0) =0, 其他自由栅格点xi (0) =D。传播第一步x5 (1) =1, 第二步x9 (2) =2, x10 (2) = 2.414。以此类推, 第五步x4 (5) =5.828, 所有自由栅格传播完毕。从目标位置到起始位置的最短距离为5.828。机器人从起始点开始回溯最短路径, 沿4→8→11→10→5→1运动, 最终到达目标位置。

静态环境下, 经过距离传播所获得的路径为最优路径。动态环境下, 则可能产生非最优或次优路径。尤其当距离相等时, 路径的随机选择可能造成非最短路径和“尖点”的出现。一种最简单的路径选择如图2所示。其中机器人初始位置在1, 目标位于6。经过距离传播过程可以生成两条最短路径1→2→6 (路径1) 和1→5→6 (路径2) 。静态环境下这两条路径都是最优路径。但如果目标运动, 选择不同的路径会有不同的结果。如果选择路径1, 而目标恰向9运动, 机器人只能沿1→2→6→9 (路径3) 运动, 显然是走了弯路。但如果选择路径2, 最终路径为1→5→9, 这条路径比路径3缩短了17%的距离。因此, 动态环境下目标运动的不确定性会造成路径规划的差异。如果在明确其运动方向的情况下再进行规划, 能够有效缩短路径长度。

2混沌与预测

针对动态环境中容易出现非最优路径的情况, 在距离传播的基础上增加了混沌反控制和预测环节。根据机器人和目标的速度关系, 将动态环境中的运动分为:机器人速度大于目标的常规运动, 小于目标的振荡运动以及小于目标的非振荡运动三种。由于第三种情况下机器人追踪到目标的几率很小, 因此本文只对前两种运动进行研究。

2.1常规运动

机器人速度大于目标时作常规运动。为了明确路径规划的关键位置, 定义栅格中心附近且下一时刻即将到达中心的位置为临界位置。当机器人和目标都恰好位于临界位置时容易出现非最优路径, 因此是规划路径的关键位置。本文所提出的动态路径算法控制机器人在关键位置混沌运动直到目标离开且运动方向明确。根据机器人运动空间的第3条假设, 目标运动方向确定后, 其下一步即将到达的栅格也可以确定, 再将该栅格作为距离传播的起点重新规划路径。采用混沌反控制的方法可以减少由于目标运动不明确而造成的非最优路径的出现。还可以避免使用延时控制所造成机器人的频繁启动和停车。而且混沌运动不同于混乱和无规律运动, 它具有随机性、遍历性和规律性的特点, 因此能够使机器人在运动中完成等待功能。

应用混沌理论中经典的广义Lorenz系统[8,9], 方程如下:

$\{\begin{array}{l}\dot{x}=\sigma (y-x)\\ \dot{y}=\gamma x-xz-y\\ \dot{z}=xy-bz\end{array}$

(3)

其中x、y、z表示三个方向的位移, σ为普朗特数, γ为瑞利数, b为几何因子。设γh=σ (σ+b+3) / (σ-b-1) 为霍夫分岔点。当0<γ<1时, 原点为Lorenz系统唯一稳定的平衡点。γ=1时, 系统发生叉式分岔。1<γ<γh时, 有不稳定的平衡点 (0, 0, 0) 和两个稳定的平衡点$(\pm \sqrt{b(\gamma -1)},\pm \sqrt{b(\gamma -1)},\gamma -1)$。在γ=γh处发生亚临界霍夫分岔, 出现了不稳定的极限环。当γ>γh后, 三个平衡点都失稳, 系统进入混沌。因此, 取参数σ=10, b=8/3, γ=28, 且初始条件为x0=y0=z0=10。

由于本文研究二维空间的路径规划, 选x和z两个方向, 其位移变化矢量表示为:

$\overrightarrow{r}=(sxsz){}^{{\rm T}}$ (4)

其中s为正常数, 用于调节混沌运动的强度。混沌吸引子在x-z平面的相图如图3所示。

2.2振荡运动

除了常规运动, 本文还研究了目标振荡运动且速度大于机器人的情况。这种情况下如果只是盲目追踪而没有对目标运动趋势的分析和预测, 机器人很难追到目标。因此解决振荡问题的关键是通过分析运动轨迹预测目标的短期运动趋势, 将追踪问题转化为相遇问题。

设目标最近经过的四个栅格依次为1、2、3、4。$\overrightarrow{s}{}_{ij}(i,j=1,2,3,4)$表示i到j栅格的位移矢量, φ表示$\overrightarrow{s}{}_{12}$与$\overrightarrow{s}{}_{34}$的夹角 (0≤φ≤180°) 。若90°<φ≤180°认为角度改变较大, 运动方向相反或近似相反, 可能出现振荡如图4所示。

判断目标在振荡运动后, 将$\overrightarrow{s}{}_{23}$沿$\overrightarrow{s}{}_{34}$方向和垂直于$\overrightarrow{s}{}_{34}$方向分解, 分别得到$\overrightarrow{s}{}_{23}^1$和$\overrightarrow{s}{}_{23}^2$如图5所示。预测垂直于$\overrightarrow{s}{}_{34}$的$\overrightarrow{s}{}_{23}^2$方向为目标运动趋势, 机器人沿此方向运动即可摆脱振荡。若$\overrightarrow{s}{}_{23}$垂直于$\overrightarrow{s}{}_{34}$, 则机器人沿$\overrightarrow{s}{}_{23}$运动。

2.3算法流程

本文所提出的动态路径规划算法的工作流程如图6所示, 其中VR表示机器人速度, VT表示目标速度。机器人在检测到目标位置后, 判断自身是否位于临界位置。如果不在临界位置按原定路线前进, 若恰好处于临界位置进一步判断机器人与目标速度的大小。VR>VT时, 若目标位于临界位置则机器人混沌运动;若目标不在临界位置则通过距离传播重新规划路径。VR<VT时, 判断目标是否振荡运动。如果振荡运动, 推断其运动趋势进而实现机器人对目标的追踪。否则进入常规运动流程。一个流程完成后, 如果追踪到目标程序结束, 否则进行下一次循环。

3算法仿真

通过与原始距离传播算法的比较, 说明增加混沌反控制和预测环节的新算法在动态环境中的有效性。图7中, 水平或垂直栅格间距为1, 目标以0.35/秒的速度运动, 机器人速度为0.42/秒, 障碍物静止不动。机器人和目标分别从 (2, 2) 和 (4, 1) 同时开始运动, 红线和蓝圈分别代表它们的运动轨迹。经过原始的距离传播, 机器人的运动路线如图7 (a) 所示。当机器人运动到 (6, 5) 的临界位置时, 目标恰运动到 (5, 6) 的临界位置。原始算法此刻仍然以 (5, 6) 为目标栅格, 机器人向其运动并最终在 (6, 7) 附近追踪到目标。从图中可以看出, (6, 5) 和 (5, 6) 两处均出现尖点, 所规划路径并是最佳路径。图7 (b) 中采用增加了混沌和预测的新的动态算法。当运动到 (6, 5) 临界位置后, 机器人混沌运动直到目标越过临界点向东运动。随后, 机器人向 (6, 6) 运动并成功在其附近追踪到目标。从图7 (b) 可以看出, 采用动态算法规划的路径中没有出现尖点为最优路径。整个追踪过程中, 采用原始算法机器人运行距离为10.95耗时26.5秒, 使用新的动态算法运行距离为8.32用时20.4秒。因此, 采用新的动态算法使机器人追踪运动目标的距离和时间都明显缩短。

目标振荡运动且速度大于机器人的情况如图8所示, 其中机器人和目标速度分别为0.3 /秒和0.5 /秒。图8 (a) 至 (e) 使用了新的动态算法。目标第一次振荡时机器人不在临界位置因此无法改变方向。图8 (d) 中, 机器人在临界位置检测到目标振荡运动, 经过预测机器人向北运动。图8 (e) 中, 追击问题转化为相遇问题机器人成功捕获目标。采用原始算法追踪目标的过程如图8 (f) 所示, 直到目标停止在 (8, 11) 位置机器人仍未能追到目标。因此, 新的动态算法能够使机器人在速度小于目标的情况下追踪到目标。

文献[8]中用神经网络算法的Hopfield模型和分流模型规划相似环境的机器人路径。在目标速度快于机器人且振荡运动情况下, 使用Hopfield模型无法追踪到目标。但如果衰减率合适, 使用分流模型能够规划出成功路径。与本文提出的改进算法相比, 神经网络算法虽然能够实现机器人追击速度较快的目标, 然而如何针对不同环境选择合适的模型和参数仍是一个有待解决的问题。

4结论

在神经网络和距离传播模型的基础上, 本文提出了一种基于混沌反控制并具有一定预测能力的动态路径规划算法。通过控制机器人在关键位置进行混沌运动, 减少了由于目标运动不明确造成的非最优路径和尖点的出现。针对目标振荡运动的情况增加了预测环节, 使低速机器人追踪高速目标成为可能。通过与原始距离传播算法的比较, 新的算法在动态环境中能够规划出更合理的路径, 具有更好的适应性。

摘要：针对移动机器人在动态环境中常遇到的非最优路径问题, 提出了基于混沌反控制并具有一定预测能力的路径规划算法。算法结合神经网络和距离传播模型, 无需先验知识并且能适应动态不确定环境。通过在关键位置控制机器人进行混沌运动, 可以减少等距情况下随机选择所造成的非最优路径出现的几率。在目标振荡运动且速度快于机器人的情况下, 通过分析目标的轨迹和方向可以预测目标的短期运动趋势, 进而实现有效追踪。仿真结果表明该算法对于减少非最短路径和路径中的尖点具有一定的作用, 对于追踪速度较快的目标也有较大的成功率。

动态充电路径规划 篇3

作为一个重要研究领域,移动机器人路径规划能够寻找一条起点至终点的最优路径使之安全到达目标。依环境信息预知程度不同,路径规划可分为所有信息预知的全局路径规划、至少部分信息未预知的局部路径规划[1]。

由于难于预知环境中的全部信息,实际中必须依赖传感器所得有限信息实时规划路径,因此局部路径规划成为该领域的研究热点。常用局部路径规划方法主要有人工势场法[2]、改进矢量场图法[3](improved vector field histogram,VFH+)、模糊逻辑算法[4]、人工神经网络方法[5]等。然而上述方法均未考虑动态障碍物的影响,在动态环境中可能导致碰撞并严重影响路径效率,因此动态未知环境中的路径规划问题引起了众多学者关注。席裕庚等[6]提出了基于滚动窗口的路径规划方法,该方法通过场景预测,以滚动方式在线规划。Ko等[7]在建立势场时引入了障碍物速度。韩永等[8]引入了速度势场改进人工势场法。上述方法多假设物体速度已知,而在实际中障碍物速度难于准确获得。因此需综合考虑障碍物速度估计方式及其带来的不确定性。

本文以高斯分布噪声描述物体运动速度及速度估计过程中的不确定性。采用自适应无色卡尔曼滤波[9](unscented kalman filter,UKF)对障碍物进行跟踪,以获得物体运动速度及其概率分布,并据此提出一种新的路径规划算法:①预测可能碰撞位置构建危险区域,并依其概率分布进行扩充;②搜寻可供通行的最优自由路径,引入风险函数评价碰撞风险;③以模糊控制器计算机器人线速度、角速度,获得所需轮速。该算法较充分地考虑了障碍物速度及其不确定性的影响,在动态环境仿真及实验中均表现出良好效果。

1 环境建模

现对本文方法作如下假设:

(1)机器人等效为点,障碍物依安全半径rs膨化处理。以机器人中心为原点建立机器人坐标系,正前方为90°,逆时针为正,角度范围(0°,360°]。后文坐标默认为此坐系中坐标。

(2)机器人能够感知路径目标坐标(rT,ϕT)。障碍物平动,对视野范围内障碍物传感器可提供如下信息:

Oi(oi,ϕil,ϕir) (1)

oi(roi,ϕoi) (2)

其中,中心oi的极坐标roi、ϕoi分别表示障碍物i到机器人的最小距离、i的中心角度;ϕil、ϕir分别为i的左右边界角。式(1)描述了一扇型障碍物区域Oi(图1),它表示了膨胀后障碍物i的碰撞威胁,oi表征了该区域的位置。定义危险区为可能碰撞的区域(对静态障碍物i,其危险区等价于Oi),定义与危险区无相交的扇区为自由扇区,约定本文涉及的长度单位均为m,角度单位为度。由于常用传感器的不可穿透性,对物体的观测往往只及一面,因此假设符合实际。

2 障碍物速度信息获取

实际中障碍物速度信息通常无法直接获取,只能依赖传感器信息进行估计。然而传感器存在噪声,速度估计模型也存在误差。因此以高斯分布噪声描述传感器噪声及速度估计过程中的误差,并采用一种基于自适应UKF滤波器的机动目标跟踪算法,获得物体运动速度及其概率分布。

2.1 速度估计数学模型

对动态障碍物本文采用如下相对速度进行描述:径向速度vL(m/s,远离为正)表征障碍物距离的变化率;角速度ω(rad/s,逆时针为正)表征障碍物角度的变化率。则动态障碍物i可进一步描述为障碍物区域:

ODi(Oi,vLi,ωi) (3)

设t0时刻机器人从位置R0(记机器人坐标系R0)经时间步长Δt运行至t1时刻位置R1(记机器人坐标系R1),如图2所示。另设R0处对障碍物i观测得Oi,此时对应坐标系R1处对i的观测为O′i。则不难由Oi的中心oi映射至坐标系R1中得到O′i的中心o′i,坐标变换关系如式(4)所示。式中,roi、ϕoi为oi的极坐标;r′oi、ϕ′oi为o′i的极坐标,xoi,yoi为oi在R0坐标系的直角坐标,X′oi,Y′oi为o′i在R1坐标系中的直角坐标。xd、yd、θd分别为R1在R0坐标系中的x、y轴坐标以及坐标系R1相对坐标系R0的旋转角度,此三者依机器人运动模型不难由下式得到

式中,dl、dr为Δt时间内机器人左右轮位移;Rd为回转半径;D为机器人左右轮距(易得dl=dr的情况)。

设在坐标系R0中测得i从Oi0移动至Oi1,如图2所示。进一步设在Δt时间内障碍物匀速运动,则对Oi1显然有

其中,vLi0、ωi0为t0时i的相对径向速度、相对角速度;roi0、ϕoi0为中心oi0的极坐标;roi1、ϕoi1为oi1极坐标;函数G(·)表示将弧度转化为度,G-1(·)表示度转化为弧度。依式(4)将坐标系R0中的oi0、oi1分别映射至t1时刻坐标系R1得o′i0(r′oi0,ϕ′oi0)、o′i1(r′oi1,ϕ′oi1),进而得到当前时刻障碍物速度为

2.2 不确定性分析

以$\widetilde{{\rm Z}}$～N(E,B)表示随机变量$\widetilde{{\rm Z}}$服从E为均值B为方差阵的高斯分布。上述数学模型中涉及对中心oi、dl、dr的观测以及数学模型的部分简化,因此存在以下不确定性:

(1)传感器噪声影响观测所得oi坐标。以高斯观测噪声$\widetilde{{\rm M}}$～N(0,δM)描述其影响,本文取

(2)轮子打滑、编码器随机噪声等影响dl、dr。以高斯控制噪声$\tilde{U}$～N(0,δu)描述。本文取

(3)障碍物可能发生机动及前述速度估计模型存在误差影响估计。以高斯模型噪声$\tilde{Q}$～N(0,δQ)描述。

2.3 基于UKF的目标跟踪

考虑到前述模型的严重非线性,本文采用一自适因UKF滤波器跟踪障碍物估计其速度。针对障碍物i有状态及观测模型如下:

其中,状态变量$\tilde{x}$ik($\tilde{r}$oik,$\tilde{\varphi }$oik,$\tilde{v}$Lik,$\tilde{\omega }$ik)～N(Xik,δik)为tk时刻受高斯噪声影响的oi极坐标及i的速度。控制量$\tilde{u}$k($\tilde{d}$l,$\tilde{d}$r)～N(Uk,δu)为tk-1～tk时间段受控制噪声影响的机器人左右轮位移,Uk为dl、dr读数;观测量$\tilde{y}$k($\tilde{r}$oik,$\tilde{\varphi }$oik)～N(Yk,δo)为受观测噪声影响的oi极坐标,Yk为oi观测值;$\tilde{Q}$k-1、$\widetilde{{\rm M}}$k分别为tk-1、tk时刻模型噪声、观测噪声。

依UKF算法[9]由tk-1时刻状态$\tilde{x}$ik-1、位移信息$\tilde{u}$k可得tk时刻状态预测值$\tilde{x}$ik|k-1～N(Xik|k-1,δik|k-1)。利用$\tilde{y}$k更新,不难得到当前状态$\tilde{x}$ik的期望Xik及方差δik,算法流程如图3所示。

2.4 基于协方差匹配技术的自适应调节器

上述模型中噪声$\tilde{U}$、$\widetilde{{\rm M}}$与机器人传感器性能有关,其方差阵可通过实验测定。而模型噪声$\tilde{Q}$难于观测,其方差阵δQ难于直接获得,且为保证跟踪性能δQ需实时调整。因此基于协方差匹配思想[9],通过使更新步骤中残差re的协方差实际值C和其理论值S相一致获得δQ,算法流程如图3所示。图3中tk时刻残差rek的协方差理论值Ck以其极大似然估计近似表示:

$\mathit{C}{}_k=\sqrt{\frac{1}{w}{\displaystyle \sum _{i=i{}_0}^k\mathit{r}}{}_{\text{e}i}\mathit{r}{}_{\text{e}i}^{´}}$ (10)

则模型噪声方差为

δQk=KkCkK′k+δik-(δik|k-1-δQk-1) (11)

i0=k-w+1

式中,w为平均窗口宽度(本文取w=5);Kk为tk时刻更新步骤中的卡尔曼增益矩阵;δik|k-1为$\tilde{x}$ik|k-1的方差阵。

3 重构环境危险区

静态障碍物的障碍物区域即为其危险区。然而对动态障碍物而言,潜在碰撞区而非当前障碍物区域。因此对动态障碍物,本文通过预测潜在碰撞区以获得环境中真实的危险区分布。

设tk时刻对动态障碍物i有障碍物区域ODik($\tilde{r}$oik,$\tilde{\varphi }$oik,ϕilk,ϕirk,$\tilde{v}$Lik,$\tilde{\omega }$ik),其中,$\tilde{v}$Lik、$\tilde{\omega }$ik为跟踪所得障碍物径向速度与角速度。则依机器人当前自身移动线速度vRk(接近障碍物为正)可预测与i可能碰撞的时间为tD后(vRk-vLik<0时不发生碰撞):

$t{}_{\text{D}}=\frac{r{}_{oik}}{v{}_{\text{R}k}-v{}_{\text{L}ik}}v{}_{\text{R}k}-v{}_{\text{L}ik}>0$ (12)

且依$\tilde{v}$Lik、$\tilde{\omega }$ik易得未来碰撞时碍物区域的位置$\tilde{o}$iD($\tilde{r}$oiD,$\tilde{\varphi }$oiD)～N(oiD,δoiD)。其期望oiD(roiD,ϕoiD)、方差阵δoiD分别为

其中,δoik、δivk、δiwk分别为$\tilde{o}$ik、$\tilde{v}$Lik、$\tilde{\omega }$ik的方差。

由于tD后碍物区域预测位置$\tilde{o}$iD的不确定性,为保证路径安全,依$\tilde{o}$iD的概率分布将预测障碍物区域按下式扩充:

即得i在tD后与机器人的碰撞危险区域Oipred(roipred,ϕoipred,ϕilpred,ϕirpred)。其中,roipred、ϕoipred为危险区Oipred中心极坐标,ϕilpred、ϕirpred为Oipred左右边界角。δ(1,1)oiD、δ(2,2)oiD分别为δoiD主对角线的第一、第二个元素。参数α决定区域扩充范围及tD后障碍物i包含于Oipred的概率P(i∈Oipred),概率P(i∈Oipred)由下式计算:

${\rm P}(i\in {\rm O}{}_{i\text{p}\text{r}\text{e}\text{d}})\approx {\rm P}(\tilde{r}{}_{oi\text{D}}>r{}_{oi\text{p}\text{r}\text{e}\text{d}}){\rm P}(\alpha \delta {}_{oi\text{D}}^{(2,2)}>|\tilde{\varphi }{}_{oi\text{D}}-\text{ϕ}{}_{oi\text{D}}|)$ (17)

其值由概率知识不难选取,本文取α=1.3使该概率约为0.8。图4为障碍物0经t0、t1时刻运动后,扩充所得危险区O0pred。

方便起见,后文中对所有危险区统称障碍物区域,即对动态障碍物i障碍物区域Oi实际上指扩充后的危险区Oipred。

4 环境信息压缩

由于传感器所得数据信息量大,不利于快速路径规划,因此采用数据压缩实现以一最优自由路径角及风险值来表征进行规划所需的信息[10]。

4.1 搜索自由路径

定义自由路径如下:由极点发出射线,若未与任何障碍物区域相交则称该射线为一自由路径,其与极轴夹角ϕ称自由路径角,以下简称其自由路径ϕ。令ϕs代表最优自由路径,并以一风险函数评估机器人切入ϕs过程中的碰撞风险Dg。

若路径目标正处于某自由路径上,则ϕs=ϕT。否则需另行搜寻最优自由路径。本文将分两步搜寻:搜索最优自由扇区,并从中确定若干备选自由路径ϕci(i=1,2,…);再于ϕci中以一代价函数寻优求取ϕs。

4.2 评估风险

机器人在切入ϕs中,可能发生碰撞。其风险与90°～ϕs范围内的最近障碍物区域距离romin、该障碍物径向速度vL有关。图5中机器人切入ϕs需经Oi所在扇区。为保安全性,机器人运动路线需控制在扇区A内,A满足:角度ϕ∈[90°,ϕs],距离r∈[0,romin]。可知:romin越小,vL越小(接近速度越高)则碰撞风险越高,因此构造风险函数如下:

$D{}_{\text{g}}=\{\begin{array}{cc}1& r{}_{o\text{m}\text{i}\text{n}}<0.2\\ k{}_4\frac{(r{}_{\max }-r{}_{o\text{m}\text{i}\text{n}})}{r{}_{\max }}-k{}_5\frac{v{}_{\text{L}}}{v{}_{\text{L}\text{Ι}}}& r{}_{o\text{m}\text{i}\text{n}}\ge 0.2\end{array}(18)$

其中,Dg∈[0,1]为风险值,vLI为可忽略该障碍物影响的径向速度阈值(本文取vLI=0.2m/s),即若vL>vLI/k5则障碍物快速远离可忽略。rmax为最大识别距离(本文取rmax=4m)。一般取权值k4>k5即使障碍物距离的影响更大(本文分别取k4=1、k5=0.5)。

5 轮速计算

传统方法多采用比例导引法计算轮速,效率不高。本文采用模糊控制器模拟人的驾驶经验计算轮速。记θs为ϕs与90°间最小夹角,则机器人运动受Dg与θs的影响如下:θs增大,即ϕs尚远,则机器人应减小线速度、增大角速度加速切入ϕs,反之则减小角速度,维持较高线速度;Dg增大,即切入ϕs风险增加;应降低线速度,增大角速度,以减小回转半径;反之应增大机器人线速度,减小角速度以维持运动平稳。此外当θs很小时应维持较高线速度、较低角速度以避免震荡。

因此本文模糊控制器以θs、Dg为输入,以归一化线速度vu、归一化角速度ωu为输出。则由下式易得机器人角速度ωR、线速度vR:

其中,vRmax、ωRmax为设定最大线速度(m/s)、最大角速度(rad/s)。

6 仿真研究

本文使用Webots软件进行仿真,并与VFH+方法进行对比。其中vRmax=1m/s,ωRmax=1rad/s,其余参数均依前文说明取定。仿真效果如图6～图9所示。

图6、图7中障碍物1以左右轮速8rad/s、5rad/s圆周运动。本文方法预测出无需调整运动方向,机器人不会进入危险区,因而获得理想路径。图7给出了仿真运行至1.74s时的相对位置、预测危险区及所得ϕs方向(箭头方向)。而VFH+算法由于仅依赖障碍物当前位置进行判断,引发机器人不必要的避碰行为导致更长路径。表1给出了仿真中的路径长度与到达时间。

图8、图9中障碍物1以左右轮速均8rad/s直线移动。使用本文方法机器人在1.344s前均试图在障碍物前方抢先通过(ϕs方向如图中箭头)。1.344s后,由于未能抢先通过,因此依据预测危险区位置立刻改变运动方向从O1背后绕过(3.52s时ϕs方向如图中箭头)并到达目标。而传统VFH+方法由O1位置判断,始终认为从障碍物前方通过最优,因而导致碰撞,无法到达目标。

7 实验结果及分析

由于诸多实际因素干扰,实验中本文方法优势不如仿真中明显。实验机器人自身直径0.45m,配备Pentium Ⅳ 3.0GHz CPU,256MB内存,实验中vRmax=0.5m/s,ωRmax=0.7rad/s。

在图10静态环境实验中,机器人距目标1.45m,5个直径0.45m圆柱形障碍物依图示放置。机器人移动路径如图中白色圆形所示,其中箭头指向机器人正前。表2给出了与VFH+方法的实验数据对比。VFH+在接近障碍物时存在较长时间慢速调整,其到达时间、路径长度分别为13.27s、4.788m。而本文方法由于采用了模糊控制器更好地计算了轮速,因而到达时间更短。图11为动态环境中的实验示意图,其中机器人与路径目标(球)、障碍物分别相距1.6m、1.4m。障碍物以左右轮速0.46m/s、0.5m/s向前运动,轨迹如图中灰色圆点所示。机器人运动轨迹如图中白点所示(箭头为机器人朝向)。实验中本文方法能够预测碰撞危险区,因而首先企图从障碍物前通过,失败后则从障碍物背后绕过到达目标,而使用VFH+方法则发生碰撞。

实验中,本文算法表现出较好的实时性。跟踪一个物体时平均耗时30ms,随跟踪数目增加,耗时比例增加。原因在于本文算法的主要运算时间均耗费于速度估计阶段。

8 结论

本文提出一种改进的局部路径规划方法,采用自适应UKF滤波器跟踪障碍物获得障碍物运动速度及其概率分布。通过预测危险区并依其不确定性进行扩充,重构环境威胁区分布,使得本文方法得以适应动态环境及其不确定性的影响。

参考文献

[1]张捍东,郑睿,岑豫皖.移动机器人路径规划技术的现状与展望[J].系统仿真学报,2005,17(2):439-443.

[2]樊晓平,李双艳,陈特放.基于新人工势场函数的机器人动态避障规划[J].控制理论与应用,2005,22(5):703-707.

[3]Ulrich I,Borenstein J.VFH+:Reliable Obstacle A-voidance for Fast Mobile Robots[C]//Proceedings ofthe 1998 IEEE International Conference on Roboticsand Automation.Leuven.Belgium:IEEE,1998:1572-1577.

[4]Huang B,Cao G,Fei Y,et al.Fuzzy Controller forthe Autonomous Mobile Robot Path Planning[J].Jour-nal of Computational Information Systems,2007,3(1):1-8.

[5]张明路,彭商贤,曹作良,等.用于移动机器人避障的人工神经网络和模糊逻辑控制技术[J].中国机械工程,1997,8(2):21-25.

[6]席裕庚,张纯刚.一类动态不确定环境下机器人的滚动路径规划[J].自动化学报,2002,28(2):161-175.

[7]Ko N Y,Lee B H.Avoidability Measurein Moving Ob-stacle Avoidance ProblemandIts Use for Robot MotionPlanning[C]//Proceedings of the 1996 IEEE/RSJ In-ternational Conference on Intelligent Robots and Sys-tems,IROS.Osaka,Japan:IEEE,1996:1296-1303.

[8]韩永,刘国栋.动态环境下基于人工势场的移动机器人运动规划[J].机器人,2006,28(1):45-49.

[9]Hide C,Moore T,Smith M.Adaptive Kal man Filte-ring Algorithms for Integrating GPS and Low Cost INS[C]//PLANS-2004 Position Location and Naviga-tion Symposium.Monterey,CA,United states:Insti-tute of Electrical and Electronics Engineers Inc.,2004:227-233.

动态充电路径规划 篇4

关键词：神经动态规划,最优路径,子问题,Matlab仿真

为了减轻交通压力, 人们越来越关心交通系统的智能化进程。智能交通系统主要的研究方向之一就是动态路径诱导系统, 它可根据外出的人们的需求, 为驾驶员提供最新的路况信息和最佳路径选择, 以此避免交通拥堵现象的发生, 从而优化交通状况, 最终使交通时时地保持一个合理的动态分配。目前, 最优路径选择的方法有很多, 但是真正需要解决大型问题时, 计算机需要搜索的选择范围太大, 传统的动态算法基本上无法处理。1995 年, 神经动态规划算法被提出, 该算法把复杂的问题分成若干子问题, 这些子问题被拆分后更容易解决, 使计算过程大幅简化, 且更容易被计算机处理。采用这种方法, 可准确、快速、实时、稳定地选择出最优路径, 值得推广。

1 神经动态规划概述与核心思想

在解决多阶段决策问题时, 动态规划大致思想为:将非常繁琐的原始问题分解为若干个阶段, 这些阶段看似不相关, 却是相互联系的子阶段, 在找到上一阶段的解决方法以后才能处理下一个阶段, 依次求出每个阶段的解, 最后得到全局最佳的解。多阶段决策问题具备很强的顺序性, 同时每个阶段所使用的解决方法也是随着阶段的变化而变化, 所以“动态”意义就得以体现。其中交通网中最佳路径的求解就是典型的多阶段决策问题。

在路径优化中, 动态规划是一种非常经典的计算方法, 但在处理实际问题的时, 我们肯定会遇到缺少一个完整信息或者维数灾等一系列问题, 所以, 引进神经网络对动态规划具有较大的解决实际问题的意义。神经动态规划如图1 所示。

2 基于神经动态规划算法的最优路径实现

(1) 将原来的问题分解成很多个小问题, 即子阶段, 并且找到每个子阶段的最优解决办法。求解多级问题的步骤为:根据每个问题的特点, 划分子阶段。在划分子阶段时, 必须按照一定的规则, 比如根据执行决策的时间、空间的顺序等。本文用x来表示子阶段变量。

(2) 求解状态和状态变量。每个子阶段具体的起始位置可以依靠自然状态来指导, 其中客观条件阶段性数目的状态是自然状态中的一种, 它传达每个子阶段的关键信息, 此外, 一组或者无后效性的变量同样可以用来表示状态变量。本文用Hx来表示第x级的状态变量。

(3) 求解原问题决策变量和集合。从目前阶段到下一个阶段状态选择时, 决策者需要做出恰当的决策, 决策变量的范围称为集合。本文用Dx表示决策集合, 用Ux表示决策变量。

(4) 研究状态转移的方程。假设状态转移方程是:Hx+1=Tx (Hx, Ux) 。次方程式中Tx不定, 根据具体问题才能确定, 如果Hx确定, 一旦变量Ux确定, 那么第x+1 阶段状态变量 (Hx+1) 也将确定。

(5) 研究指标函数。因为n和vi的递进性和可分离性, 所以很容易找到指标函数n和vi之间的关系, 显然, 指标函数的求解也相对简单化。

(6) 动态规划函数的基本方程。边界条件为;

3 仿真结果

将上述模型, 在Matlab仿真软件上进行模拟仿真, 分解原始问题并确定各个子阶段的最佳方案, 将这个问题用网格的形式如图2 进行表示:A为起始地点, E为目标地点, 从起始地点到目标终点有很多路径, 假设经过每个节点需要一定的运输成本, 在Matlab仿真软件上进行仿真后依据动态规则算法的要求, 设定好相应的算法模型以及相应的计算公式, 这样便可以找到最优路径。

由图2可以非常清楚的看出, 成本最低的路线为:, 成本都是110。仿真结果可以看出神经动态规划算法具有较多优点:得到清晰运算结果;很容易找到全局的最优路径;可以找到一组完善的解, 有利进一步的分析。

4 结语

我们在使用神经动态规划算法来探索最优路径的时候, 具有很多优势, 首先其具有稳定、可靠的步骤, 过程并不复杂, 但是给予我们的结果十分清晰明确, 且适用于现实生活。使用这种动态规划算法解决复杂的问题时, 可以非常容易找到解决方案, 而且效率很高。当然, 该算法也有一定的局限, 但只要我们不断地改进完善, 日后继续研究神经动态规划算法, 相信一定可以攻克更多的局限, 能够使其更好地被应用。

参考文献

[1]谬慧芬, 邵小兵.动态规划算法的原理及应用[J].中国科技信息, 2006 (23) :32.

动态充电路径规划 篇5

近年,网上购物迅速发展成为人们购物的重要模式。物流配送是电子商务活动中重要的一环。合理选择配送路径,对加快配送速度、提高服务质量、降低配送成本及增加经济效益都有较大影响[1]。如何提高商品配送效率是诸多物流企业关注的重点。因此,选择合理优化的路径对物流企业提高企业竞争力和服务水平至关重要。

20世纪50年代,美国数学家Bellman为研究最优控制问题提出动态规划法[2,3]。该种方法成为一种通用的算法设计技术来求解多阶段决策最优化问题。文献[4]利用图的广度优先搜索与动态规划法相结合求解关键路径;文献[5]应用动态规划法研究物流配送的最短路径,但不能对于不同时刻下的同一区域进行路径的动态选择。

本文中,对于物流配送路径选择问题建立数学模型,在考虑路径长度基本因素下,在基本的动态规划法基础上进行改进,增加路况,等影响因子随机调整路径权值,提出一种较高效率、切实有效的物流配送路径动态选择算法。

1 动态规划法的基本思想

1.1 适用于动态规划法求解的问题的特征

1)能够分解为相互重叠的若干子问题;

2)满足最优性原理(也称最优子结构性质):该问题的最优解中也包含着其子问题的最优解。

1.2 动态规划法的求解过程[6]

动态规划法是求解多阶段决策最优化问题的技术之一,其基本思想是把多阶段决策的复杂问题划分为多个子问题(通常,这些子问题之间相互重叠),每个子问题对应决策过程的一个阶段。如图1所示,Si(i=0,1,2,…,n)是问题求解过程中的各个状态,Pi是依据当前状态做出的相应决策。

各个子问题之间有重叠,这种重叠关系可以在抽象的动态规划函数中表现出来。因此,求解子问题的解后,并填入表中,当在后续阶段需要再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。

动态规划法的求解过程如图2所示。

从图2可知,动态规划法利用问题的最优性原理,以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。动态规划法的三个阶段:

(1)分段:将原问题分解为若干个相互重叠的子问题;

(2)分析:分析问题是否满足最优性原理,找出动态规划函数的递推式;

(3)求解:利用递推式自底向上计算,实现动态规划过程。

2 物流配送路径问题的数学模型

2.1 问题描述

现某一个物流企业有配送中心A,要求送达的配送目的地是M1,M2,…,Mn。配送中心与各个配送目的地,配送目的地两两之间有路可达。要求从配送中心A出发,将货物配送到各个目的地,最终回到配送中心。要求合理安排配送的路线和行车时间,且相应的配送费用最小。

以上描述的问题符合最优性原理。证明如下:

设s,s1,s2,…,si,s是从s出发的一条路径长度最短的简单回路。

假设从s到下一个城市s1已经求出,则问题转化为求从s1到s的最短路径,显然s1,s2,…,sp,s一定构成一条从s1到s的最短路径。

否则,设s1,r1,r2,…,rq,s是一条从s1到s的最短路径且经过n-1个不同城市,则s,s1,r1,r2,…,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,…,si,s要短,从而导致矛盾。

2.2 建模前的假设

为了便于建立物流配送路径选择的数学模型,使得该模型有一定的实用性且不会过于复杂,假设问题满足以下条件:

(1)到达每个配送目的地的长度不超过配送车辆一次配送的最大可行驶距离;

(2)存在路径,可以使得每个配送目的地经过且只经过一次;

(3)各个配送目的地采用同样的运输手段;

(4)运输费用与运输路径成正比,即单位成本固定;货物应当在可接受的时间范围内运送到。

2.3 建立模型

根据以上描述可知,物流配送路径选择问题的模型如下:

d(s,V')表示从物流配送中心s出发,经过所有配送目的地V'一次且只一次,最后回到出发点s的最短路径长度。

动态规划函数:

2.4 物流配送路径选择的动态规划法

设顶点之间的代价存放在数组c[n][n]中,动态规划法求解问题的填表过程如下:

从以上应用动态规划法填表求解过程可知,表格中的数据安置从左往右逐列求值。在表格的右上角d[0][2n-1-1]即物流配送问题的最短路径。根据最短路径的求解过程,依次倒推,求得最短路径上的配送顺序,即得到问题的最优解。

3 实例

假设物流企业的配送中心S,现需要从S出发将货物分别配送到目的地A、B和C,然后回到S,以进行下一次货物配送。各地点之间的距离,如图3所示。

根据动态规划法,进行填表求解。

假设n个顶点用0~n-1的数字编号,首先生成0~n-1个元素的子集存放在数组V[2n-1]中,设数组d[n][2n-1]存放迭代结果,其中d[i][j]表示从顶点i经过子集V[j]中的顶点一次且仅一次,最后回到出发点0的最短路径长度。

从S出发经点A、B、C然后回到S的最短路径长度是:

d(S,{A,B,C})=min{cSA+d(A,{B,C}),cSB+d(B,{A,C}),cSC+d(C,{A,B})}

这是最后一个阶段的决策,而:

d(A,{B,C})=min{cAB+d(B,{C}),cAC+d(C,{B})}

d(B,{A,C})=min{cBA+d(A,{C}),cBC+d(C,{A})}

d(C,{A,B})=min{cCA+d(A,{B}),cCB+d(B,{A})}

这一阶段的决策又依赖于下面的结果:

d(B,{C})=cBC+d(C,{})d(C,{B})=cCB+d(B,{}))

d(A,{C})=cAC+d(C,{})d(C,{A})=cCA+d(A,{})

d(A,{B})=cAB+d(B,{}d(B,{A})=cBA+d(A,{})

而d(A,{})=cAS=5(A→S)d(B,{})=cBS=6(B→S)d(C,{})=cCS=C(C→S)可以直接从图3得到,填入表1的第2列。

由此,可以得到如下,并将其填入表1的第3列至第5列:

同理,得到以下数据并填入表1的第6列至第8列:

最后,得到表1的最后一列:

所以,从顶点S出发的物流配送最短路径长度为10,最优的选择路径是S→A→B→C→S。

由于在物流配送过程中,时间、天气等不确定因素的影响,道路的拥堵通畅情况随时会发生变化。假设配送目的地B位于市中心,上下班高峰时间与B相通的道路通常会比较拥堵。虽然相关道路的长度没有发生变化,但这会延误到达其他目的地的配送时间。因此,引入道路拥堵因子x,在不同时刻随机调整相关道路上的权值,x的取值范围为(0,10]。x=1表示通畅情况下的道路拥堵因子;x<1表示道路状况被提高后的拥堵因子,优于通常情况;x>1表示道路比较拥堵情况,该值越大,道路状况越糟糕。拥堵因子x的引入可能会使得最终选择的物流配送路径距离增加,但是以运输高成本能换取大部分客户的满意度,保证企业的良好信誉。

假设图3中各边的取值为道路通畅情况下的权值,即此时拥堵因子x=1。在上下班高峰时刻,AB段和SC段发生拥堵,提高拥堵因子x,设x=4。调整后如图4所示。

在图4上,再次应用3.4动态规划法,得到表2。

由表2知,在AB,SC段发生拥堵情况下,最优的配送路径长度是17,对应的路径是S->A->C->B->S。

4 算法仿真

引入拥堵因子的动态规划法在Visual Studio.Net环境中使用C#语言进行编程仿真。

将前面描述的实例作为测试程序输入。程序运行后,得到图5。图5中左右两个子图对比同一配送问题在不同路况下的物流配送路径最优解。左图表示在路况良好时(拥堵因子x=1)最优的配送路径;右图中AB和SC发生拥堵,用虚线表示,黑色加粗的箭头所指是此时(拥堵因子x=4)最优的配送路径。

仿真结果表明,引入道路拥堵因子后的改进动态规划法可以根据实时的路况信息,随机调整拥堵因子,在车辆已经出发的情况下,动态调整实时的物流配送路径的最优解。

5 结语

在物流配送路径选择问题中,引入拥堵因子随机调整物流配送路径的权值,改进动态规划法,求解实时的物流配送的最优路径。此算法的改进对于物流企业提高配送效率,提高用户满意度有一定的实际应用价值。

参考文献

[1]郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究[J].中国管理科学,2002,10:51-56.

[2]王晓东.算法设计与分析[M].北京:高等教育出版社,2003.

[3]Thomas H Cormen,Charles E Le.Introduction to Algorithms[M].MITPress,2005.

[4]刘芳,王玲.基于动态规划思想求解关键路径的算法[J].计算机应用,2006(6):1440-1442.

[5]蒋琦玮,陈治亚.物流配送最短路径的动态规划方法研究[J].系统工程,2007(4):27-29.

动态充电路径规划 篇6

近年来,随着市场经济的不断深入以及人们生活水平的不断提高,服装连锁经营在我国有了很大的发展,品牌服装的销售量日益增加,连锁门店市场的竞争越来越激烈[1]。在电子商务出现以后,由于电子商务突破了时空限制、新媒体对服装全方位的展示、低的交易成本与低库存、较少的中间环节所带来的交易费用的优势等,给连锁服装门店的经营带来了新的挑战[2,3]。在人们日益追求服装个性化、高增值服务的时代,在原材料与人力资源成本挖掘的空间越来越小的情况下,服装连锁企业越来越关注作为企业第三利润源泉的物流的作用[3],通过降低物流成本、加快配送速度、优化配送路径等措施来提高企业的竞争力。

在优化配送路径方面,人们做了很多工作。20 世纪50 年代,美国数学家Bellman等人在研究多阶段决策过程的优化问题时提出了动态规划法。动态规划法解决了线性规划和非线性规划无法处理的多阶段决策问题[4]。后来,试图将图的广度优先搜索算法、蚁群算法与动态规划法结合求解关键路径问题[5,6,7,8,9],或者简单使用动态规划法研究物流配送的最短路径[10,11],但所有这些方法都无法对时变环境下的路径进行随机选择。

本文根据动态规划的基本思想,通过对传统动态规划模型的改进,将服装物流配送过程中因道路、天气、车辆状况等引起的突发事件考虑到模型中,提出了一类高效实用的服装物流配送路径优化方法。通过该模型的应用,服装连锁企业可以得到尽量优化的配送路径,对降低配送成本、提高服务质量、提高企业经济效益具有重要的意义。

1 动态规划法简介

1.1 动态规划法的基本思想[4]

美国数学家Bellman等人在研究多阶段决策过程的优化问题时,通过将多阶段过程转化为一系列单阶段问题,然后逐一求解,创立了解决多阶段过程的动态规划方法,即通常所说的Bellman最优性原理。动态规划算法的基本思想是将待求解问题分解为若干子问题,先求解子问题,然后从这些子问题的解得到原问题的解。因此,为了运用动态规划法,所考虑的问题: (1)必须能够分解为相互重叠的子问题; (2) 满足最优子结构的特性———子问题的局部最优将导致整个问题的全局最优; (3) 无后效性———当前状态是此前历史的总结,此前的历史只能通过当前的状态去影响未来的决策。

1.2 动态规划法的求解过程

在多阶段决策过程中,将决策过程分为n个阶段,每个阶段所作的决策用Pll,=1,2,…,n,表示,设Sii=,0,1,2,…,n,为问题求解过程中的各个状态,根据动态规划法的思想[11],可以用图1 表示多阶段决策过程。

这里,决策Pl不是任意确定的,它依赖当前面临的状态,又影响以后的发展。

各个子问题之间的重叠关系通过状态转移方程(或动态规划函数)来表现。为了避免重复计算,将子问题的解填入表中。

动态规划法利用最优性原理,采用自底向上的方式,先求出子问题的最优解,然后逐步求得整个问题的最优解,其求解思路如图2所示。

因此,使用动态规划法进行决策,需要将原问题分解为若干个相互重叠的子问题,进行分段决策;然后根据最优性原理,分析问题,建立状态转移方程(或动态规划函数);最后采用自底向上的求解方法,求出问题的解,从而实现动态规划过程。

2动态规划法在服装配送路径优化中的应用

2.1服装配送路径优化的动态规划模型

服装运输需要考虑服装存储、装卸、流通加工、配送等诸多因素,我们在此只考虑服装配送中的路径选择问题。设某服装企业有一配送中心A,有若干客户M1,M2,…,Mn。各客户的空间位置与需求已知,配送中心到各客户之间是可达的,运载能力给定。车辆从配送中心A出发,完成若干节点(客户) 的配送任务,最终回到配送中心A。要求合理安排最短配送路线与合适行车时间,且配送费用最省。

假设从节点s出发有一条最短回路s,s1,s2,…,sn,s。如果从节点s到节点si是所需要的,那么现在需要求出从节点si到节点s的最短路径,显然这条路径是存在的,假设为si,…,sp,s;反之,如果存在另外一条最短路径si,r1,r2,…,rq,s,则回路s,s1,s2,…,si,r1,r2,…,rq,s比s,s1,s2,…,sn,s更短。因此问题的描述符合最优性原理。

为了构建简单实用的服装运输车辆配送路径选择的数学模型,假设:

(1)配送车辆满足一次配送要求;

(2) 配送点是可达的;

(3)完成一次配送所采用的运输方式相同;

(4)单位成本固定;

(5) 配送时间在可接受的范围内。

因此,从服装配送中心s出发,假设有s0,s1,s2,…,sn个配送点,令,V'为V的子集,则根据动态规划法,从配送中心s出发经过V'中所有配送节点一次(且仅一次),然后回到配送中心s的最短路径长度,即服装配送路径最优化问题可用下式来表达:

这里,,表示符合条件的最短路径长度。

状态转移方程为:

其中,lik表示节点i到节点k的路径长度,lks表示配送点k到配送中心s的路径长度,e为突发事件影响因子,正常情况下,e=1。

2.2 服装配送路径优化的算法实现

用数组l[n][n]存放顶点之间的距离(这里n为配送点的个数),动态规划法的填表过程可用以下算法实现。

(1)初始化

(2)迭代

(3)信息更新

对中的每一个元素,有:

(4)输出最短路径长度

由以上实现算法可知,所求最短路径,即的值。按照此过程进行倒推,即可得到问题的最优解。

3实例

假设某服装企业要从其配送中心S将服装送往其连锁店A、B、C、D,然后再回到配送中心S,以便进行下次送货,其含权路线如图3所示。

根据动态规划法,首先进行填表。为了方便计算机编程,对n个节点进行编号,假设各节点编号为0~n-1,则数组V的大小为2n-1;将迭代结果存于数组中,则根据状态转移方程(2)可知,从配送中心S出发经连锁节点A、B、C、D,然后回到配送中心S的最短路径长度为:

(1)最后阶段的决策

(2)中间阶段的决策

由式(3)所做出的最后阶段决策依赖于下面的决策。

式(4)所做出的决策由下式(5)决定。

式(5)所做出的决策由下式(6)决定。

由图3及式(2)得到:

将相应的数值填入表1的相应位置。

由式(6)可得:

由式(5)可得:

将所得数值填入表1中。

由式(4)可得:

将所得数值填入表1中。

最后由式(3)得到表1的最后一列数值:

所以,从服装物流配送中心S出发的服装物流配送最短路径长度为27,最优路径为S→C→B→A→D→S。

服装连锁企业一般位于人口稠密、交通拥挤的市中心,另外受天气(如广东、福建等沿海地区的台风,北方的雾霾)和道路维护等的影响,在服装配送过程中,随时都会发生道路拥堵、车辆故障等突发事件,而且这种突发事件一旦发生,毫无疑问会延误对其他连锁店的配送时间。因此,在使用动态规划法设计服装物流最短路径时,必须考虑这些因素的影响。假设突发事件的影响因子为e,其取值为0刍e≤10,若e=1表明道路通畅、能见度正常,e刍1表明道路、天气等优于正常情况,e酆1表明道理拥堵、能见度低,此值越大,说明情况越糟。

假设图3中各边的权重是e=1时的情况,CB段和DS段因道路维护造成拥堵,使得突发事件影响因子e酆1,令e=5,则图3调整后得到图4所示。

对图4使用上述动态规划法,得到表2。

由表2可知,当CB段与DS段发生突发时间造成拥堵时,有两条最优路径可选,即S→C→D→B→A→S或S→B→D→C→A→S,且最优路径长度均为28。遇到这种多路径可选的情况,可根据车辆积载情况、配送的具体情况合理选择,在此不作详细讨论。

4 结论

根据动态规划的基本思想,在考虑天气、路况、车况等突发因素的情况下,引入突发事件影响因子,提出了改进的动态规划算法,并通过实例,演示了所提算法求解连锁服装物流配送的最短路径的过程,对降低连锁服装企业的配送成本、提高服务水平和企业经济效益具有一定的实用价值,同时也可以将此算法推广应用到其他行业。

摘要：连锁服装配送中路径的优化对提高连锁服装企业的服务水平、降低成本、提高企业效益具有重要意义。根据动态规划的基本思想,结合连锁服装物流配送过程中的路径选择问题以及时变因素,引入突发事件影响因子,提出了适合连锁服装物流配送过程中改进的路径优化算法。通过具体实例,验证了该方法在连锁服装物流配送的路径随机选择中的实用性和可行性,并可将此算法推广到其他物流配送的路径选择中。