微观仿真模型

微观仿真模型（精选九篇）

微观仿真模型篇1

关键词：风电,微观模型,无功,联网,仿真,功率因数

0 引言

风电作为最具规模化开发和商业化前景的新型能源[1,2,3],已经得到世界各国的重视。中国大力支持风电发展,减少对传统火力发电的依赖。沿海各省以及西部地区的风电装机容量快速增加。以江苏省为例,截至2009年,风电总装机容量已达500.5 MW。江苏省电力公司规划,至2020年,风电总装机容量将达10 GW,是目前的20倍,其中离岸风电场装机容量占总额的70%。

风电的迅速发展以及风电自身特性,给电网带来诸多新挑战和问题。其中风电场无功电压控制是最受关注的问题之一[4,5,6]。许多学者也针对此问题做了许多研究。文献[7]提出一种改善风电场接入地区电压稳定性的无功控制策略,利用系统部分雅可比矩阵推导风电场的电压无功灵敏度信息,并根据风电场无功输出能力计算风电场无功调整量;文献[8]研究了大型风电场接入一个脆弱电力网络而引起的无功电压问题,利用PSCAD建立了12节点的网络,包括2个风电场,容量分别为50 MW和100 MW。其中,风电场建模中做了理想化处理,认为变压器、线路的阻抗可以忽略,并且风电场的无功功率受控于相同母线上的电容器,这些均导致对风电场内部实际无功功率考虑不足。文献[9]指出,大型海上风电场通过海底电缆向大电网同时输送有功功率和无功功率时,海底电缆产生了不容忽视的线损。文献[10]建立了由5台风机组成的小型风电场,虽然考虑了场内线路的阻抗,但是忽略了变压器的阻抗,而且对场内无功功率涉及较少。在文献[11]中,建立了基于异步发电机内部等值电路的含风电场的电力系统无功优化模型,提出风电场无功优化的目标函数和约束条件,利用改进遗传算法进行求解。在文献[12]中,针对风电接入系统后的电网电压稳定问题,分析并指出负特性、风电并网点的选址、系统的无功电源以及风电机组特性等是影响电网电压稳定的主要因素。此外,有许多学者建立较为详细的风机模型,研究风电场的电压暂态问题和无功控制策略[13,14,15,16,17]。然而,所建模型都有一个缺陷,就是忽略了风电场内部其他元件的功率特性,导致仿真结果产生偏差。风电场无功功率的大小取决于控制方式:恒功率因数控制或恒电压控制。实际应用中,国内风电场均采用恒功率因数控制方式[17],而未能根据电网运行状况实时进行无功调节。风机机端功率因数、有功功率对风电场无功功率的影响尚未有文献涉及。

本文建立江苏2个接近实际情况风电场的仿真模型,比较不同机端功率因数和有功功率下的无功功率,并且与风电场电能质量在线实测数据进行比较,掌握风机机端功率因数设定以及风机有功功率对于风电场整体无功功率特性的影响,为风电场无功电压控制提供依据。

1 风电场内部电气组成

并网型风电场由风电机组、风机箱变、风电场升压主变压器以及大量电缆和架空线组成,如图1所示,风电场内若干台风力发电机成为一组,发出的功率在集电线路上汇集,再由集电线路送至风电场的低压侧母线,最后经升压变压器送至外部电网,每一部分都对风电场整体无功特性产生影响。

风电机组在发出有功功率的同时可发出无功功率,定功率因数情况下,这部分无功功率与风机有功功率成正比。风力发电机组发出的电能需逐级升压输送到电力系统中,其中每台风机出口均配备一台升压变压器,即风机箱变,将风机机端电压(一般为690 V)升至中压(一般为35 k V),汇集到中压母线后通过主变升至并网电压(一般为110 k V或220 k V)。箱变和主变均为感性元件,在风机正常输出功率时,箱变和主变会消耗一定量的无功功率,且所消耗无功会随风机输出功率变化。

风电场线路主要包括电缆和架空线路2种,由于风电场的风机台数较多,因此其内部接线形式往往较为复杂,存在着大量的电缆和架空线路的组合。架空线路和电缆的无功功率损耗由两部分组成:其一为线路电抗消耗的无功;其二为线路充电功率,基本恒定。电缆同架空线路相比,其充电功率远大于后者。因此,风电场的充电功率一般主要由电缆提供,当风力较低时,电缆充电功率对功率因数的影响作用将显著增大。

2 风电场微观建模

2.1 风电场总体概况

本文选取江苏沿海地区220 k V和110 k V各一座典型的并网风电场,以江苏主网2009年夏季高峰系统为背景而开展。根据风电场提供的详细结构参数,采用PSASP仿真软件,建立场内包括风机、箱变、主变和各段集电线路的微观模型,开展了不同设定条件下的仿真。

所选2座风电场的风电机组均采用定功率因数控制方式,所以风机均设为PQ节点。为了方便说明,南通沿海地区110 k V并网风电场记为A,盐城沿海地区220 k V并网风电场记为B。

A风电场装机总容量49.5 MW,采用33台1.5 MW双馈机组,机端功率因数设定为0.98;B风电场装机总容量201 MW,采用134台1.5 MW双馈机组,风机机端功率因数基本设定为1,部分设定为0.99,由于资料有限,暂时未知。图1所示即为110 k V风电场简化接线示意图。

2个风电场35 k V侧场内各种线路总长度在表1给出,可以看出,A风电场以电缆为主,而B风电场以单回架空线为主。

2.2 风电场无功功率模型

国内大多数风机采取定功率因数方式运行,仿真中可以将风机作为PQ节点处理。箱变和主变采用常用的变压器模型,场内线路分为架空线路和电缆2种,电缆对地电纳不可忽视,可以将其等值为∏型等值电路。

风电场总无功功率模型可表示为

其中,QiGk为第i台风机输出无功功率;QiTk为第i台箱变吸收无功功率;Qp2j为第j段线路产生无功功率;Qjp1为第j段线路吸收无功功率;QTm为主变吸收无功功率。

3 风电场无功电压仿真分析

首先对于固定的风电机组机端功率因数λ设定值,仿真得到了风电场的有功功率变化对并网点电压和无功功率的影响曲线;为了研究优化风电场λ设定值,通过改变λ重复以上仿真,获得了多条无功-有功、电压-有功仿真曲线,见图2—7,其中阴影部分为进相运行区。

从图2和图5来看,当风机机端功率因数λ<1时,风电场并网点的无功功率随着风机有功功率的增加先上升而后下降;且λ越小,并网点无功功率越大。当设定λ=1时,并网点无功功率随有功功率增加而快速减少,出现从外部电网吸收无功功率的情况,当A风电场有功功率为50 MW时,并网点吸收无功功率为8.5 Mvar,这种情况下,风电场需从外部吸收大量的无功功率。

风电场高压侧功率因数和并网点电压也表现出对应的变化趋势。

4 仿真结果分析

从仿真结果看,风电场并网点无功功率随风机有功功率增加呈现先增加后减少的趋势,甚至出现吸收无功功率的情况,机端功率因数越小,并网点无功功率越大。当风机有功功率为0时,并网点无功功率为正,这是风电场内部线路对地导纳产生的充电功率。随着风机有功功率增加,风机发出的无功功率增加,箱变和主变吸收的无功功率也在增加。当有功功率较小时,风机发出的无功功率大于箱变和主变吸收的无功功率,使得并网点无功功率增加。但是当有功功率较大时,风机发出的无功已经不能满足箱变和主变吸收的无功功率,使得并网点无功功率减少,甚至有功功率达到一定值时,场内线路充电功率以及风机发出无功功率小于箱变和主变吸收无功功率,此时风电场就需要从外部电网吸收无功功率,来维持风电场的运行。特别当机端功率因数设定为1时,从外部电网吸收无功功率的情况尤为明显。

风电场高压侧功率因数λHV与并网点电压受到风电场并网点无功功率的影响。高压侧功率因数随风机有功功率增加而先增加到1后再减小。当场内线路充电功率加上风机发出无功功率正好满足箱变和主变无功需求时,风电场高压侧功率因数就为1;上面已经提到,当风机有功功率再增加时,就需要从外部吸收无功功率,导致高压侧功率因数降低。并网点电压同样随风机有功功率增加先上升而后减少。当风电场并网点发出无功时,电压上升;而当风电场吸收无功时,电压下降。

从仿真结果来看,风电场场内线路的充电功率不容忽视,特别是当风机有功功率较低时,可以为箱变和主变提供足够的无功支持。

图8和图9分别为江苏电网电能质量监测系统中2座风电场2009年实测的有功、无功散点分布,根据上述风电场微观模型,无功与有功存在二次函数关系,对散点采用二次曲线拟合,A风电场各风机实际机端功率因数设定为0.98,仿真结果与实测点拟合曲线基本吻合;而B风电场实际机端功率因数部分设定为1,部分为0.99,实测点拟合曲线处于λ=1和λ=0.99这2条仿真曲线之间,基于微观模型的风电场无功仿真结果能够很好地反映实测情况。

图10为B风电场2009年7月5日至6日典型功率变化曲线,不难看出,风机有功功率变化很快,且幅度很大。当风机有功功率为50~100 MW时,风电场高压侧功率因数接近于1;低于40 MW左右时,其值快速下降;当有功功率大于100 MW时,略微降低。这与图6所反映的仿真结果一致。

5 结论

微观仿真模型篇2

摘要：为弥补常用的景区游客容量分析方法存在的不足,该文提出了基于游客空间行为模拟系统(TSBS)的微观仿真分析方法,分析了重庆仙女山国家森林公园的.生态容量.将公园划分出若干生态容量监测区域,选取游客对草地的践踏作用强度作为监测指标,利用TSBS对游客空间行为、时空分布进行微观仿真,计算监测区域的游客践踏作用时间与次数,求出公园的生态容量,分析生态容量管理的关键区域,提出了提高生态容量的措施.研究表明,基于TSBS的游客生态容量分析方法具有动态、量化、管理效果可预测等优点.作者：张仁军杨远芬 ZHANG Ren-jun YANG Yuan-fen 作者单位：张仁军,ZHANG Ren-jun(重庆工学院土地资源管理系)

杨远芬,YANG Yuan-fen(重庆工学院科研处)

微观仿真模型篇3

摘要：利用微观交通仿真技术可以对快速路上的交通进行短时预测。将快速路上的线圈采集的实时数据输入本文所述的交通仿真系统进行仿真，可以预测一段时间以后的交通状况。沿着这个思路，描述如何利用仿真技术进行短时交通预测，特别是对如何建立满足实时性和动态性要求的交通生成模型进行了详细的阐述。通过对真实历史数据进行仿真预测，并分析对比，结果说明使用微观仿真模型进行短时交通预测是可行的。

关键词：微观仿真; 短时交通预测; 交通生成模型

Short-time Traffic-flow Forecast

Based on Micro-simulation

LI Kui, WANG Jian

(CIMS department, Tongji University, Shanghai 201804, China)

Abstract: Micro-simulation technology was proposed to forecast s hort-time traffic-flow on Freeway. Traffic state on freeway in the future can

be predicted by using real-time data from loop on road as input of simulation s ystem. In the paper the method how to deal with the real-time data so that it c an satisfy real-time and dynamic requirements was expatiated. The experimental

results show that short-time traffic forecast by using micro-simulation model

is feasible.

Key words: micro-simulation; short-time traffic-flow fore cast; traffic generation model

在交通流预测方面，国内外学者作了大量的研究，产生了很多短时交通预测的方法，这包括历史数据平均值法［1］、人工神经网络法［2］和卡尔曼滤波理论［3］等。文献［4］对各种交通流预测方法进行了分析和对比，指出了各种方法的优缺点。基于统计学方法的历史数据平均值法是利用历史交通流的规律进行交通预测，不能处理短时预测的实时性、动态性和不确定性；基于人工神经网络的方法需要大量的样本进行训练来找出交通流的固有规律，其结果一方面依赖于样本的质量，另一方面在交通发生动态变化的时候已经训练好的人工神经网络就失效了；还有其他的一些预测方法，同样对短时交通流预测的实时性和动态变化性处理较差。

本文介绍使用微观仿真模型进行短时交通预测的方法，可以有效的体现交通的实时性和动态变化性，利用本方法进行的预测对更正交通情报版的诱导性有极其重大的意义。文献［5］讲述一种使用元胞自动机模型对大尺度交通网络进行交通流预测的方法。使用微观仿真的方法进行短时交通流的预测需要解决两个方面的问题，一个是微观交通仿真模型；另一个是数据输入问题，包括使用交通实时数据进行仿真系统的初始化和交通网络边界数据的输入问题。在微观仿真模型方面已经有了大量的研究，也产生了许多有效的微观交通仿真模型。本文将简要介绍微观仿真模型，重点讨论如何用实时交通数据对仿真模型进行初始化的问题。

1 模型概述

微观仿真模型基本上由三大部分组成：一部分是路网几何形状的精确描述，包括信号灯、检测器、可变信号标示等交通设施。另一部分是每辆车动态交通行为的精确模拟，包括车辆跟驰模型、车辆换道模型和车辆的路径选择模型；已有大量的学者对微观交通仿真模型进行了研究，微观仿真中的基础模型如跟驰模型和换道模型等都有了在特定条件下适用的有效模型，在本文所述的短时交通预测方法中将利用这些成熟的模型；仿真系统使用的车辆跟驰模型是基于安全距离的避撞模型，换道模型分为自由换道和强制换道两种。第三部分是对交通仿真系统进行数据的输入的模型，这就是交通生成模型；交通生成模型就是在交通路网的边界（如入口）进行车辆的输入，这包括发车数量、车辆类型、发车速度、发车间隔和车辆的OD 等。

跟驰和换道这两个基本模型是微观仿真模型的基础，目前已经有经典的模型可以满足要求。短时交通预测有实时性和动态变化性等特点，在进行仿真预测的开始，快速路上就已经分布了大量的车辆，需要在仿真环境中模拟这样一个状态。传统的微观仿真模型中，交通生成模型只是从交通路网边界的几个入口点产生车辆并发车到道路上，这对本文所述情况并不适用。在本文所述的情况下，需要对实时采集到的数据进行瞬时处理，需要计算出在预测路网上当前的车辆数量、车辆分布、车辆的速度和车辆的OD等信息，利用这些信息才可以生成用于仿真的初始状态，然后通过仿真，得到一段时间以后的交通状况，实现短时交通预测得目的。

2 仿真模型

2.1 交通流量的产生仿真初始状态中交通路网上的车辆数和车辆的初始位置分布对以后的预测影响十分巨大，如何精确计算一个路段上的车辆数就显得十分重要。对于快速路，通过分布在道路上的线圈采集数据，从线圈中只能得到经过某一点的车辆信息。下面的方法充分利用线圈采集的数据，通过分流畅交通流和间断交通流两种情况的处理，计算出分布在两个线圈之间的车辆数。

（1）流畅交通流的情况对于道路上第i个线圈地点Loopi和它的下一个线圈地点Loopi+1之间的路段，计算出所需的时间t，那么从现在向前的t时间内通过Loopi的车辆数就是Loopi与Loopi+1之间路段上的车辆数，车辆数可以从数据库中取得。时间t的计算可通过下面的公式

t=[SX(]Li,i+1[][SX(]1[]2[SX)](Vi+Vi+1)[SX)][JY]（1）

式中：Li,i+1为Loopi和Loopi+1之间的距离；Vi和V i+1分别为车辆到达Loopi和Loopi+1时的速度。

（2）交通拥塞的情况利用M3分布模型［6］，假设车辆处于两种行驶状态：一部分是车队状态行驶；另一部分车辆按自由流状态行驶。分布函数为

集到此路段的车头时距，表示车辆处于车队状态行驶时，车辆之间保持的最小车头时距； t=[SX(]1[]n[SX)]∑[DD(]n[]i=1[DD)]ti，λ=[SX(]1[]tτ-τ[SX)]为参数，其中t τ为车头时距大于t的样本观测指的均值；α=[SX(]m[]n[SX)]为按自由流状态行驶车辆所占的比例，n,m分别为采集点的次数和采集点的车头时距不大于给定值λ0的个数。

设此段路长为L2，则得到此路段上的车辆为N2=[SX(]L2[]F(t)[SX)] 。

微观交通仿真中换道模型的研究综述篇4

车辆跟车模型和换车道模型是交通仿真的2个最基本的动态模型。与跟车行为相比,换车道行为需要考虑的车辆更多,司机的决策过程更加复杂,也更难于描述。为此,针对多数交通仿真系统存在算法内核封装性和保密性问题,本文对目前多数微观仿真系统所使用的几种换车道模型进行综述,介绍了几种模型的构建思想和算法内核,并对这些模型的优缺点进行了评述展望。期望能对换车道模型研究的深入化和精准化起到一定的参考和借鉴作用。

1 换道模型研究

最早对换道模型进行系统研究的是澳大利亚人Gipps, P. G.,本文称之为Gipps模型[1]。在这一模型的基础上许多学者对换道模型进行了研究,目前应用比较多的模型有MITSIM模型、CORSIM模型、SITRAS模型等[2,3,4]。当然还有许多其它模型,如AIMSUN2模型、HUTSIM模型以及基于行为阈值、模糊数学和神经网络等理论的换道模型[5,6,7,8],但目前这些模型的应用范围相对较窄。限于篇幅,在此只针对几种较为常用的模型进行详细论述。

1.1 Gipps模型

Gipps于1986年首先建立了受交通信号、障碍物和重型车等影响的城市道路的换道决策结构框架。Gipps模型假定司机行为是理性的,据此重点分析了潜在冲突影响下的换道决策过程。该模型认为车辆是否换道主要取决于以下6个因素:①换道是否安全、可行,能否避免碰撞发生;②障碍物的位置;③专用车道的出现;④司机预定的转向运动;⑤重型车的出现;⑥当前车道和目标车道的相对速度优势。换道是否安全可行由换道所需的减速度( [Vn(t+T)-Vn(t)]/T )是否大于可接受的减速度(一般假定为-4 m/s2)。Vn(t)为车辆n在t时刻的速度,而Vn(t+T)由下式决定:

$\begin{array}{l} V_{n} (t + Τ) = b_{n} Τ + {b_{n}^{2} Τ^{2} - b_{n} [2 x_{n - 1} (t) - \\ 2 x_{n} (t) - 2 s_{n - 1} - V_{n} (t) Τ - V_{Ν - 1}^{2} / \hat{b}]}^{1 / 2} (1) \end{array}$

式中:Vn(t+T)为车辆n在t+T时刻的速度;bn(<0)为车辆n能接受的减速度;T为速度和位移的计算步长;xn(t) 为车辆n在t时刻的位置;sn-1为车辆n-1的有效长度; $\hat{b}$ 为bn-1的一个估计值。

1.2 MITSIM模型

在MITSIM换道模型是由MIT的Yang, Qi博士在Gipps模型基础上提出的一种新模型。该模型把换道过程分为3步:首先判断是否有必要换道并确定换道的类型,其次是检测间隙并选择换道方向,最后是实施换道。

在MITSIM的换道模型中,其换道需求由当前车道和目标车道的交通状况共同决定。如果车辆由于前方的慢车导致它的速度低于期望速度或车道的最大速度时,将检测旁边车道是否有机会提高速度。忍耐因子和速度差因子等几个参数被用来确定当前速度是否足够低,旁边车道速度是否足够大,据此判断是否有换道的需求。需求产生后,将选择可换入的车道。车道是否可换入需要考虑诸如换道规则、车道使用权、车道间的连接、信号状态、事故、主要交通状况、司机的期望速度和车道的最大速度等因素。

确定可换入的车道后,将检测目标车道的前后间隙是否充足。判断性换道的最小间距可表示为:

$\tilde{g}_{n}^{i} = \tilde{g}^{i} + \tilde{ε}_{n}, i = l e a d, l a g (2)$

式中: $\tilde{g}$ $_{n}^{i}$ 为车辆n在判断性换道时能接受的最小间距; $\tilde{g}$ i为平均可接受间距; $\tilde{ε}$ n为随机误差项。

1.3 CORSIM模型

CORSIM由美国联邦公路署(FHWA)开发,综合了2个微观仿真模型,(用于高速公路的FRESIM和用于城市道路的NETSIM)。

FRESIM换道模型由动机、利益和紧急3个因素组成。动机因素由一个被定义为不可忍受的速度极限值的外生变量决定,当车辆的速度低于这一极限值时,司机便会产生换道的动机;利益因素代表换道获得的利益;紧急因素则指换道愿望的强烈程度,司机可接受的减速度与换道的紧急因素有关。可接受的减速度由下式得出:

$d = {\begin{cases} d_{\min}, U ＜ (1 - 0.05 \times c) \\ d_{\min} + (d_{\max} - d_{\min}) \frac{U + 0.05 \times c - 1}{0.05 \times c}, \\ U \geq (1 - 0.05 \times c) \end{cases} (3)$

其中: dmin, dmax分别为可接受的最小减速度和可接受的最大减速度;c为换道的反应延迟时间;U为紧急因素,它由公式(4)决定:

$U = D A F \times Ν L C \times (V_{F}^{d e s})^{2} \div [20 (x - x_{0})] (4)$

其中,DAF=[1.0+DT-5.5)]/FDA,DT为司机的类型编号,DT=1～10;FDA为司机驾驶倾向性指标;NLC为换道所需的次数;V $_{F}^{d e s}$ 为主车(指有换道意图的车辆,下同)的期望速度;x为车辆的当前位置;x0为换道的目标位置。

NETSIM换道模型包括强制性换道和判断性换道。车辆驶入或驶出交织区、匝道或接近车道终止处时的换道为强制性换道,只有后车能减速不至于与前车相撞时车辆才会实施换道。NETSIM的判断性换道模型主要由换道动机和间隙检测2部分组成。换道动机由主车的实际速度以及它与当前车道前车的车头间距共同决定,该模型假定当车头间距小至不可忍受或实际运行速度小于给定的不可忍受值的1/2时,车辆将尝试换道。不同司机的不可忍受的车头间距值是不同的,具体值由下式决定:

$D Τ ＞ 9 \times \frac{\frac{S - 2 \times (V_{F} - V_{L})}{V_{F}^{d e s}} - h_{\min}}{h_{\max} - h_{\min}} (5)$

其中:DT为司机的类型编号;S为主车与当前车道前车的间距;VF为主车的实际速度;VL为目标车道前车的实际速度;V $_{F}^{d e s}$ 为有换道意图车的期望速度; hmin,hmax分别为所有车都试图换道的最小车头时距和没有一辆车试图换道的最大车头时距。

1.4 SITRAS模型

SITRAS是由Hidas等开发的一个大型多智能体仿真系统。该模型的换道可行性判断基于以下2个条件:①主车跟随目标车道前车的减(加)速度是否大于主车可接受的减速度;②目标车道后车跟随主车时的减速度是否大于目标车道后车可接受的减速度。主车和目标车道后车的减速度由跟车模型算出,而可接受的减速度由下列公式算出,这一公式是对Gipps提出的公式的一个改进,具体为:

$b_{n} = [2 - (D - x_{n} (t)) / (10 v_{n})] \cdot b_{L C} \cdot θ (6)$

其中,bn为车辆n在t时刻可接受的减速度;D为预定的转向或障碍物的位置; xn为车辆n在t时刻的位置;vn为车辆n的期望速度;bLC是车辆愿意接受的减速度的平均值;一般取最大减速值的一半;θ为司机的风险系数,它代表司机间的个体差别,服从正态分布,取值范围为0～99。条件1中的θ为平均风险系数(θ=50)与主车司机的风险系数的比值,条件2中的θ为主车司机的风险系数与目标车道后车司机的风险系数的比值。

2 现有模型评述

Gipps模型在换道需求的判断之前就先进行可行性检测,这与现实逻辑不符,且存在计算量庞大,计算无效率等缺陷;另外,Gipps模型也没有得到实测数据的验证。尽管如此,Gipps模型作为早期工作,首次建立了换道决策的结构框架,具有开创意义,许多后期的模型(如AIMSUN2、MITSIM、SITRAS等)都源于这一思想框架。

MITSIM换道模型继承了Gipps模型的思想,并对其进行了改进,给出了较为详细的判断性换道和强制性换道的规则,并在最小间距中加入了随机误差项。但它没有考虑间隙不足时,车辆间竞争合作下的减速让行行为。

CORSIM模型包括用于城市的NETSIM模型和用于高速公路的FRESIM模型,应用范围较广。但这一模型基于减速度的基础上来判定车辆是否实施换道,而减速度的计算需要多个过程才能完成;况且,模型中需要标定的参数较多,其中一些参数甚至很难通过实测数据去标定。

SITRAS模型把人车单元当作一个多智能体,考虑了后间距不足时,车辆间的竞争合作关系及其减速让行行为,能很好地反映受事故影响的交通状况下的换道行为。正是由于这一模型的专用性,使得它并不能推广到一般的交通状况。

由上可知,目前的换道模型较多,各有优缺点,但还没有那个模型能得到广泛认同和应用,所以,仍需对其进行更为深入、全面的研究。

3 展望

随着ITS等新技术的开发和应用,对车辆行驶关键过程的深入理解再次受到交通学者们的重视。然而,对换道行为及其模型的研究仍不成熟,还有很多方面值得深入探讨。目前的研究还没有分析ITS等新技术对换道行为的影响,未能详细论述换道对周边车辆以及整个交通流的影响,也缺乏基于我国交通特性的实证研究。

3.1 基于ITS等新技术的换道研究将受到重视

随着智能交通系统(ITS)、驾驶员信息诱导系统和车辆自动智能巡航系统(ACCS)等新技术的开发和应用,驾驶员的换道决策行为将在很大程度上有别于过去。比如,随着ITS的迅速发展,在交通控制系统中驾驶员能得到周边多车辆车的速度、间距等精确信息,这些信息的获得都会对驾驶员的换道选择产生影响。

3.2 换道对交通流的影响亟待研究

目前的换道研究大多侧重于需求产生、间隙检测等决策过程,而却较少研究换道对周边车辆的影响及对整个交通流的影响。不同的车流密度下,驾驶员的换道动机以及换道对交通流的影响是不同的。在密度较小时换道主要是为了绕开前面的慢车,提高车速,此时,由于前后间隙较大,换道对周边车辆的影响很小,对提高整条道路的通行有积极作用;当密度较大时,不同车道上的车辆几乎是以相同的较慢速度向前行驶,此时的换道大多是种“见缝插针”行为,对提高本身的车速没有多大益处,反而对周边车辆的影响较大,易导致交通流从有序到无序的转变。

3.3 基于我国交通特性的实证研究有待加强

国外的换道模型大多是基于对他们本国的交通调查数据的基础上建立起来的,而我国的交通环境、交通组成、驾驶员心理特性、法规意识等方面都与国外有着较大差异,国外的模型并不一定适合我国的交通状况,完全运用国外模型所进行的管理控制决策不一定能解决好我国的交通问题。目前,我国在换道模型方面的研究还非常薄弱,尤其缺乏换道行为的实证数据。国内学者建立的换道模型大多缺少实测数据的标定和验证,其成果直接应用于实际仍需谨慎。期望本文能为相关研究人员提供一定借鉴,从基础实验数据出发,建立、发展并完善适合于我国交通流特性的换道模型。

参考文献

[1] Gipps, P. G. A model for the structure of lane-changing decisions[J].Transportation Research, Part B,1986,20(5):403-414

[2] Arif Mehmood. Integrated simulation model for driver behavior using system dynamic[D]. Canada: University of Waterloo, 2003

[3] Yang, Q., Koutsopoulos, H. N. A microscopic traffic simulator for evaluation of dynamic traffic management systems[J].Transportation Research, Part C,1996,4(3):113-129

[4] Hidas, P. Modelling lane changing and merging in microscopic traffic simulation[J].Transportation Research, Part C,2002,10(5):351-371

[5]Ji m,T.,Mussi,P.,Siegel,G.Aroad traffic si m-ulator:car-following and lane changing[R].2002

[6] Zhang, Y. L., Owen, L. E., Clark, J. E. Multi-regime approach for microscopic traffic simulation[J]. Transportation Research Record,1998(1644):103-115

[7]Hunt,J.G.,Lyons,G.D.Modelling of dual-car-riageway lane-changing using neural networks[J].Transportation Research Part C,1994,2(4):231-245

微观剩余油仿真综述篇5

我国东部陆相断陷盆地的大多数油田经过数十年的注水开发, 已进入高--特高含水率开发阶段, 综合含水率超过90%。由于长期水驱开发后地下储层的孔喉网络、岩石骨架、粘土矿物和渗流特性等诸因素都在演化, 因而高含水率开发阶段微观剩余油分布极为复杂。微观剩余油仿真研究不受实验条件、样品等因素的制约, 能够直观的表征长期注水开发后储层孔喉网络的变化、水驱油的过程及剩余油分布模式, 因此对改善注水开发效果及提高采收率有重要的意义[1,2,3,4,5,6,7,8,9]。

1 仿真技术基本原理

1.1 仿真的内涵

计算机仿真是以相似原理、系统技术、信息技术及其应用领域有关专业技术为基础、以计算机为工具, 利用系统模型对真实的或假想的各种系统进行动态研究的一门多学科的综合性技术[2]。

仿真理论的主导思想是将待研究系统进行提炼和简化, 提取其基本特征并建立模型, 通过在模型上进行实验来完成对系统的研究。

1.2 仿真研究的基本流程

目前, 计算机仿真主要有四部分:系统分析、系统建模、仿真建模和仿真实验, 如图1所示。仿真系统的具体步骤如下:a.系统定义:通过系统分析得出要解决的问题, 并提出总体解决方案。b.系统建模:根据系统定义的结果确定模型的边界, 从而得到计算机仿真所要求的数学描述。c.仿真模型:其主要任务是根据系统的特点和仿真要求选择合适的算法。d.计算机编程实现:将所得的仿真模型用计算机程序来实现。该程序中包括仿真试验的要求, 如仿真运行参数、控制参数、输出要求等。e.模型运行及仿真实验。分析模型运行结果是否合适, 如不合适, 从前几步查找问题所在, 并进行修正, 直到满意为止。

2 数字图像处理技术在微观剩余油仿真中的应用

微观剩余油仿真的实现是通过对储层岩石镜下的铸体薄片进行观察、分析, 对储层进行微观研究。在这个过程中, 需要对储层岩石的铸体薄片进行一定的数字图像处理, 提取其中我们需要的

孔隙部分, 计算相应的储层参数, 最终根据所计算出的储层参数进行准确的剩余油仿真。通过显微镜得到的图像背景复杂, 孔隙特征不明显, 为了适应仿真的要求需要对图像进行预处理操作, 本文采用图像锐化的方法对孔隙图片进行锐化, 效果明显, 图像边缘、轮廓线及图像细节更加清晰, 如图2。在对图像预处理取得较好效果后, 下一步就是对图像进行分割, 提取有效孔隙。图像分割是由图像处理前进到图像分析的关键一步, 在图像工程中占有重要的地位, 已经在多个领域得到了应用。我们经过进行大量的实验及数据分析, 最终采用概率松弛迭代方法进行图像分割。分割后, 铸体薄片的分割边缘突出, 孔隙信息明确, 能够准确的分割出非孔隙的重金属矿物, 有利于提高后期对孔隙进行参数计算的准确性。 (见图3)

参数计算

当孔隙被准确提取, 孔隙信息就相应的得到的准确描述, 可以采用形态学的方法计算储层岩石的孔径、面积、周长等各种参数, 应用于计算机仿真。

3 微观剩余油仿真数学模型

为了研究两相渗流规律, 建立毛细管孔道的两相渗流模型[9]。模型同时考虑粘滞力和毛管力, 为亲水模型。根据泊肃叶公式可得出油水界面的运动速度:

可以看到, 速度v受到孔道半径和油水粘度差的影响, 不同半径的孔道, 流速不同;水驱油时, , 在相同半径的孔道中, 流速将会随时间变化而加快, 其结果是会出现前面提到的水驱过程中的指进现象。

4 微观剩余油仿真模型的实现

前期工作结束后, 我们采用VC++和Open GL来实现微观剩余油仿真的计算机实现, 仿真模型可连续观察流体在微观孔喉网络中的渗流过程, 通过对文33块沙二下油藏416层和53层的微观仿真研究, 揭示了储层不同孔喉网络模型中不同含水阶段油水在流场中的运动状况。如图4为文南油田w33-66井孔隙图像的图像识别对比, 识别后的图像用红色表示孔隙, 跟原图符合度高, 比原图更加清晰, 识别效果较理想。选择高含水期井w33-66井2730m的样品进行水驱过程仿真, 如图5所示。可以看到孔喉网络中残留的红色部分为剩余油, 在低含水时期有大部分剩余油滞留, 中含水阶段, 孔喉网络中被驱替部分增加, 剩余油呈网状或簇状;至高-特高含水阶段, 孔喉网络中被驱替部分油呈局部斑块或孤滴状、薄膜状。

摘要：微观剩余油仿真是基于岩石微观孔隙结构理论, 利用现代仿真技术、结合数字图像处理及OpengL技术对长期注水开发后的储集层在宏观、微观上的变化规律及渗流参数在三维空间变化规律进行描述的方法。在仿真过程中充分考虑孔隙非均质性、岩石润湿性、开发流体及温度、压力变化, 经过多次修改和完善, 建立精细仿真模型, 最终根据此模型在高速计算机上进行该仿真实现, 直观模拟水驱油的全部过程。该技术不受试验条件、样品代表性等诸因素的限制, 对揭示地下剩余油的形成与分布具有重要的理论与实践意义。

关键词：仿真理论,微观剩余油,图像处理

参考文献

[1]贾连兴.仿真技术与软件[M].北京:国防工业出版社, 2006:4.

[2]王行仁.先进仿真技术[J].测控技术, 1999, 18 (6) :5-8.

[3]徐守余.油藏描述方法原理[M].北京:石油工业出版社, 2005:51-52, 73-77, 91.

[4]俞启泰.关于剩余油研究的探讨[J].石油勘探与开发, 1997, 24 (2) :46~50.

[5]Davis J.A., Jones S.C.Displacement Mecha-nisms of micellar Solutions[J].SPE1847-PA 1968, V243 (20) :1415-1428.

[6]刘建民, 李阳, 毕延鹏等.应用驱油微观模拟实验技术研究储层剩余油微观分布特征[J].中国海上油气 (地质) .2000, 14 (1) :51-54.

[7]郭尚平, 黄延章, 周娟等.物理化学渗流微观机理[M].北京:科学出版社, 1990:2-16.

[8]孔令荣, 曲志浩, 万发宝等.砂岩微观模型两相驱替实验[J].石油勘探与开发, 1991, 18 (4) :79-85.

微观交通再现仿真系统研究与开发篇6

微观交通仿真系统的研究对象通常是历史调查数据,以对数据进行统计分析的结果为根据进行仿真。当前,交通领域的一个热点研究,就是智能交通技术,智能交通系统的基础是提供精准的实时信息和短时间交通流预测,因而吸引了众多研究人员投身到交通流预测研究中[1]。目前很多国外的微观交通仿真软件例如Paramics,开始通过实时采集的交通数据开展在线仿真方面的实践,能够更准时地为相关部门提供管理控制的数据。在国内,例如DynaCHINA也针对动态交通分配展开了研究,以实时数据为基础,预测未来短时间内的交通状况,从而进行动态交通诱导[2]。总的来说,在交通流预测方面的研究比较多,已有的交通再现方法多从宏观角度来研究交通流的流、速、密关系,关注的是平均速度、密度、流量等集合参数,不能有效体现交通系统中交通运行的复杂过程、再现实际交通状态。很多情况下,针对某个交通事件或结果,如果能再现其产生过程,能为我们分析其形成机制提供依据,从而做出相应控制调整,可以避免某些恶性事件的重复发生。运用微观交通仿真系统,能够在单个车辆级别上模拟人-车-路的相互作用,再现交通流的真实状态,描述各种交通控制策略的实施过程。仿真所得到的各种数据可用于对交通状况的分析、预测,对交通管理控制方案进行评估[3]。本文提出的微观交通再现仿真方法能够有效地利用地面线圈采集的数据,再现交通流时空变化,为交通道路管理规划提供技术依据,对各种交通设施的设计方案、管控措施以及交通需求管理方案进行评价。最后,以上海市中环路的交通采集数据作为实验数据,验证了系统的有效性。

1 微观交通再现仿真系统设计

在微观交通仿真中,我们在不同道路和交通条件下根据静态路网描述模型、交通产生模型、动态驾驶行为模型等,模拟车辆的行驶状况,并动态地显示出来[4]。本系统以线圈采集到的交通流统计数据为基础,选择带约束的卡尔曼滤波法计算出入口之间OD矩阵,采用二项分布和负指数分布实现路网车辆的初始分布,根据基于数据库的车辆产生模型更新车辆,通过微观交通仿真的方法,真实再现城市快速道路任意时刻的交通状态。

图1为微观交通再现仿真流程图,有以下步骤:

(1) 采集交通数据:

利用分布在路面的线圈采集平均车速、流量、占有率、车头时距等数据信息;

(2) 初始化路网状态:

按照车头时距分布模型,分布车辆到仿真的路网上;

(3) 分配交通出行量:

通过分析路网的历史出行信息计算得到出行量OD 矩阵;

(4) 微观交通再现仿真:

应用跟车模型、换道模型实现仿真;

(5) 评价微观交通再现仿真结果:

分析评价得出预测的仿真结果。

2 车辆生成模型

交通流的输入问题主要由微观交通仿真的最基本的模型,即车辆产生模型来解决[5]。因为在现实的交通流中,车辆的到达是无规律的,表现为随机性和离散性,所以车辆产生模型中的车流量、各车型比例、车辆期望速度范围和路网OD信息等是由用户自定义的,再按照实际的数据库在源头不断地生成新的车辆。车辆生成模型主要有以下内容:

2.1 随机数的产生

为了真实的模拟微观交通仿真模型,必须进行随机抽样,或产生服从一定分布的随机变量。由于任何概率分布函数的值域都在[0,1]之间,应用组合法、逆变法、取舍法、近似法和函数变换法,任取[0,1]之间某一数值作为随机变量的值[6]。所以,在[0,1]上正确地生成符合均匀分布的随机数是产生一切随机变量的基础。要得到正确的随机变量,必须有良好的伪随机数发生器,通常采用线性同余发生器。

Lehmer于1951年提出了线性同余发生器[7],其递推公式为:

其中:m为模数,a为乘数,c为增量,且m、a、c均为非负数;X0为初始值,且为非负数;ui为最后产生的随机数。

2.2 车型随机

在一般微观交通仿真中,车型一般分为大车、普通车(中车)和小车三种类型。其中,大车的车身长度一般大于8m,普通车的车身长度一般介于3m和8m之间,小车的车身长度一般小于3m。本文根据调查所得的分布, 将车辆种类随机的赋予每一辆车辆,大、中、小车比例是通过数据库中读取出来的流量经过一定的分析算法分析计算而得到的。

设p1表示大车所占的百分比,类似的p2表示中车的百分比,p3表示小车的百分比,那么有p1+p2+p3=1,(可以视实际情况加入其它车型)。在车流中,各种车型的出现情况用随机变量X来表示,若出现大车,X=0;若出现中车,X=1;若出现小车,X=2。这样就得到X的概率密度函数如下:

随机变量X的概率分布函数F(x)为:

设有随机数u(x), 0<u(x)<2, 则:

2.3 个性因子随机

通过随机数发生器, 将驾驶员行为参数按某一分布随机地赋给每一个驾驶员。建立地驾驶员的个性模型时,将驾驶员分为保守型、正常型和冒险型。个性因子λ代表每个驾驶员的驾驶行为差异,λ的分布是连续的,如果驾驶员越冒险,λ就越大。大量的研究结果表明,λ一般服从均值为1,方差为0.2的正态分布,即:

λ=1+0.2W (5)

其中:

$W = \sqrt{2 \ln (u_{2}) \sin (2 π u_{1})}$ (6)

式中的u1、u2为0～1之间的随机变量。

2.4 车速随机

以往的研究表明,路网上的车辆速度近似服从正态分布或对数正态分布,然而不能对正态分布函数进行逆变换,故采用函数变换法,当X～N(0,1)时,Y～N(μ,σ2), 表达为:

Y=σX+μ (7)

应用函数变换法后只要产生两个均匀分布的随机函数u1、u2, 就能获得一个服从标准正态分布的随机变量Z, 以及车辆的初始速度v, 其表达式为:

其中,u1、u2表示两个均匀分布的随机数;u表示速度均值;σ表示速度均值方差。

3 OD分配模型

考虑到约束条件,这里研究了OD 矩阵的约束卡尔曼滤波方法[8]。如果该系统不考虑交通流的滞后性,则在k时刻有:

yij(k)=ri(k)aij(k) (9)

yij(k)表示从i进口匝道驶入且从j出口匝道驶出的交通量;ri(k)表示从i进口匝道驶入的交通量;aij(k)表示从i进口匝道驶入并选择从j出口匝道离开的交通量占所有从i进口匝道驶入的交通量的比例,称为匝道选择率。

由路况信息有:

其中,ri表示第i(i=1,2,3,4,5,6)个进口,yj表示第j(j=1,2,3,4,5,6,7)个出口。

这样流入、流出匝道交通量的基础关系就确定了[9]。

下面为约束方程:

其中aij是车辆从第i个入口驶入从第j个出口驶出的概率。假设从采集点能获得上下匝道的交通量,问题就变成了如何由检测到的流入交通量r(k)、流出交通量y(k)来反推OD关系,即匝道选择率A(k),这里应用卡尔曼滤波[10]来求解。

将式(11)转化成下面的形式:

记作:

Y=Ra+E (13)

其中,E被当作由白噪声产生的扰动矩阵来处理。于是原问题的状态空间方程就产生了。首先,假定系统噪声是白噪声序列,其均值为0,且噪声驱动矩阵为单位阵。实际上这也能表征到达率矩阵的随机波动情况。其次,考虑到OD系数诸多的影响因素和复杂的耦合关系,明确的影响因素很难找到,因此可以将控制输入归算到系统噪音中去,并假设系统无控制输入。同样,解析确定系统的状态转移矩阵也是困难的,但是在时间段不长时,两个相邻时间段的到达率矩阵的变化是很小的,基本上可以认为是不变的,因此假定状态转移矩阵也是单位阵。

这样就得到滤波公式:

计算顺序为Pk+1,k⇒Kk+1⇒Pk+1⇒ak+1。其中R1,k和R2,k为白噪声产生的扰动矩阵。

4 车辆初始分布模型

在交通初始分布过程中,首先将交通流量和交通组成导入到每条道路上,然后利用随机函数产生随机数并将车辆随机分布在各个车道上,注意的是在分布的时候必须要保证车辆之间的安全距离。

仿真系统访问的是由线圈来分配的数据库中的数据,车辆的初始化分布利用了相邻两个线圈中的流量信息。读取相邻两个线圈的流量信息,如n1表示经过线圈1的车流量,n2表示经过线圈2的车流量,n表示两个线圈之间的车流量,那么:

n=n1+n2 (15)

于是,我们在两个线圈之间按照线圈间的距离随机分布车流量。

初始化分布的流程如图2所示。

用Webster 法根据道路几何参数大致计算路口的饱和流量S, 通过OD 矩阵得出每条道路的车流量q, 两者之比q/S 即为流量比y( 或称饱和度) , 据此判断采用哪种离散型分布。如果输入的车流量明显小于饱和流量,并且除了模拟区域外其他部分很少有交通信号,也就是说,其它区域多为无信号控制的交叉口,这样车辆到达数的均值和方差基本相等,则选择泊松分布;如果输入的OD矩阵包括高峰期和非高峰期两部分,即有一段时间交通量很大,一段时间交通量很小,就选择负二项分布;还有一种情况,程序模拟路段位于整个路网交通线号的下游,信号周期的前半段交通量大,而后半段交通量小,也适合二项分布;当交通流量很大时,接近或超过饱和流量,这时候车辆自由行驶的机会不多,车辆到达数的方差小于均值,那么就应该用二项分布。泊松分布适用于车流密度不大,车辆间相互影响微小,其他外界干扰因素基本上不存在,即车流是随机的[11]。二项分布适用于车辆比较拥挤、自由行驶机会不多的车流[12]。

因此,本文的车辆初始分布,一般地面道路采用二项分布,高速路采用泊松分布。

地面道路车辆初始分布:

$Ρ_{t} (k) = C_{Ν}^{k} (\frac{λ t}{Ν})^{k} (1 - \frac{λ t}{Ν})^{Ν - k} (k = 0, 1, 2, \dots, n)$ (16)

高速道路车辆初始分布:

$Ρ_{t} (k) = \frac{(λ t)^{k}}{k!} e^{λ t}$ (17)

其中:λ为车辆平均达到率(辆/秒),Pt(k)为在计数间隔t内到达k辆车的概率;t为每个计数间隔持续的时间(秒),n为正整数。

5 实验验证

本系统将实测数据加载到路网上进行仿真,通过仿真结果与实测数据进行比较来验证系统的有效性。选取2010年5月18日7:00-8:00上海市中环路(北翟路-天山西路)的实际数据作为实验数据。图3和图4为7:00-8:00的仿真数据及实测数据对比(线色浅表示实测数据,深色线表示仿真数据)。

可以看出仿真结果中流量数据与实际流量较为吻合,速度有一定的误差,但无论是流量还是速度,其误差都在±5%以内。准确性达到90%以上,满足再现的要求。

本文还对本系统与VISSIM仿真进行了比较(在路尾设置四个采集点,仿真600秒的结果见表1):

为了证明本系统的有效性及各路段最大通行能力值的准确性,针对各条路的最大通行能力进行测试,本文应用VISSIM系统和本系统分别对中环路某路段进行测试,两者的测试结果如图5和图6(采集数据粒度:20秒 ,采集点间距离:210米)所示。

由图5、图6看出,两个系统仿真得到的路段的最大通行能力有少量的差别,车辆的平均瞬时速度也有差别。这是因为本系统仿真环境下,路网上初始时是有分布一些车辆的,这更符合实际交通状况;而在VISSIM不具备此项功能,造成了车辆速度的差异,进而导致采集到的流量存在少量差异。除此之外,本系统还可展示路段的拥堵情况,当某路段上的密度大于某一特定的值时,此路段呈红色,表示此时很拥堵,当该路段上的密度介于某一范围内,此路段呈黄色,表示此时此路段密度已经很大,再加载车辆的话可能会发生拥堵。当此路段畅通时,其呈绿色。

6 结语

本文提出了一个微观交通再现仿真系统,能够有效展示各路段上的交通流量、车辆密度、车辆的行驶速度,真实再现路段上的交通流状况。仿真系统以上海市中环路某一时间段的交通采集数据为基础,再现了过去某个时间段的交通流状况。为了验证本系统的正确性和有效性,并与实测数据进行比较,取得良好的效果;我们还对本系统与VISSIM仿真进行比较,分析了二者的差异,并展示了本系统的一些功能。

摘要：为了再现过去某段时间的交通状况,提出一个微观交通再现仿真系统,主要由车辆生成模型、OD分配模型和车辆初始分布模型组成。仿真系统对车辆仿真进行了再现分析,能够有效展示各路段上的交通流量、车辆密度、车辆的行驶速度,真实再现路段上的交通流状况。选取上海市中环路的实际采集数据进行仿真验证,结果表明微观交通再现仿真系统真实再现了交通流的时空变化。应用该系统能够为交通道路规划与管理提供技术支持,并能对各种交通参数进行比较和评价。

关键词：微观仿真,交通再现,车辆生成模型,OD分配模型,车辆初始分布模型

参考文献

[1]Boyce D,Xiong C.Forecasting travel for very large cities:challengesand opportunities for China[J].Transportmetrica 2007,3(1):1-19.

[2]马云龙,王坚.基于RTI的交通态势实时仿真技术研究[J].系统仿真学报,2008,20(22):6129-6132.

[3]商蕾.城市微观交通仿真及其应用[D].武汉:武汉理工大学,2003.

[4]杨嘉,孙剑.微观交通仿真流程及其应用[J].城市交通,2010,5(8):79-83.

[5]魏丽,孙俊,商蕾.微观交通仿真模型建模及应用[J].武汉理工大学学报:交通科学与工程版,2010,4(34):793-796.

[6]梁欣.基于Agent的交叉口微观仿真系统的设计与实现[D].中南大学,2008.

[7]裴玉龙,张亚平.道路交通系统仿真[M].北京:人民交通出版社,2004.

[8]常云涛,彭国雄,杨晓光.基于进出口匝道流量的高速公路OD矩阵[J].交通运输工程学报,2003,3(4):89-94.

[9]Simon D,Chia T.Kalman filtering with state equality constraints[J].IEEE Transaction on Aerospace and Electronic Systems(S0018-9251),2002,39(1):128-136.

[10]Ennio Cascetta.Dynamic estimators of origin-destination matrices usingtraffic counts[J].Transportation Science(S1526-5447),1993,27(4):363-373.

[11]韩善灵,朱平,林忠钦.路交通噪声评价及预测新方法[J].交通运输工程学报,2005,5(3):111-121.

微观仿真模型篇7

随着我国城市化进程的推进, 城市轨道交通运力大且快捷舒适的特点使其受到越来越多大城市的青睐。截至2014年初, 我国已投入使用的城市轨道交通车站累计超过1 500座。轨道交通车站是为大量乘客提供集散服务的场所, 乘客步行的舒适程度是衡量系统服务质量的重要指标。因此对车站行人设施服务水平进行分级, 并据此在规划设计阶段确定设施规模和尺寸具有重要意义。

针对行人设施服务水平的研究可大致分为21世纪前后2个阶段。20世纪的研究并未对行人设施所处的交通系统进行细分。早在20世纪70年代初, 美国学者Fruin[1]就开始研究行人流运动规律, 他采用行人密度作为评价设施服务水平的指标, 这一方法得到广泛认可和借鉴。随后Tananboriboon[2], Gerill[3]等人针对其所在地区分别提出了行人设施服务水平分级标准。2000年, 美国《道路通行能力手册》[4] (Highway Ca-pacity Manual, HCM) , 将Fruin的分级方法引入手册, 作为步行街、楼梯、人行道、天桥等人行设施规划设计的参考标准。至此, 针对通用步行设施服务水平的研究已经基本完善, 但仍没有针对公共交通系统步行设施服务水平的相关研究。进入21世纪后, 针对不同系统行人运动的研究开始细分, 针对轨道交通系统行人设施服务水平的研究大量开展。美国交通研究委员会发布《公共交通通行能力及服务质量手册》[5] (Transit Capac-ity and Quality of Service Manual, TCQSM) 针对公共交通设施服务水平进行了较为全面的阐述。近年来, 国内学者也对轨道交通车站行人设施服务水平提出众多分级标准[6,7,8,9,10]。现有评价标准在分级依据、阈值确定及分级描述等方面存在差异, 而我国《地铁设计规范》[11]对此又无明确的规定, 因此在我国目前还没有一个统一的服务水平等级划分方法。笔者在总结对比国内外现有标准的基础上, 运用微观仿真方法研究现有标准的适用性, 为车站的规划设计提供参考。

1 服务水平评价指标

轨道交通车站设施分类如图1所示, 笔者以供乘客通行的服务设施为研究对象。行人设施的服务水平划分基于以下2点:行人选择期望步行速度的自由度和绕过走得较慢行人的可能性。为了评估上述2点, 可以选用人均占用空间、步行速度和行人流密度等指标进行服务等级划分。

在行人流指标中, 行人占用空间最能直观体现个体的空间舒适程度;密度可以反应部分区域内的拥挤程度, 且该值容易进行观测和统计;速度可以从另一个方面表现行人运动的舒适度, 根据已有研究成果, 当行人步行速度低于0.7m/s时将不自然地“拖着脚”行走[12];此外, 行人流量可以体现设施的负荷程度, 也可以用来描述行人设施的服务水平。表1给出了利用行人占用空间、行人密度、速度、流量4个指标评价设施服务水平的优缺点比较。微观行人仿真通过行人运动模型实现对行人流的模拟, 是研究交通枢纽内部行人流运动规律的有效工具[13]。通过仿真可以得到实地观测难以统计的行人占用空间等信息, 笔者借助仿真手段, 选取行人占用空间作为服务水平划分指标。

2 服务水平评价标准

2.1 服务水平研究方法

近年来我国学者针对轨道交通系统建立了不同的行人设施服务水平评价标准。为探究国内外评价标准的合理性及适用性, 笔者从研究方法、分级依据、阈值选取等方面对比现有服务水平评价标准的优缺点。对现有评价标准研究方法及特点总结见表2。

在分级依据方面, HCM等标准是根据行人流从自由流向限制流、拥塞流过渡时个体受他人影响和限制的程度划分服务水平等级, 这种分级方式的优点是能够客观地划分行人运动状态, 对于设施通行能力的计算及车站设施设计具有较强参考意义。其缺点在于对行人个体主观感知的考虑不够充分。而张海丽[6]的分级标准充分考虑了行人的主观感受, 采用不同拥挤程度的车站照片对乘客进行访问调查, 并据此确定服务水平分级标准。这种分级方式考虑了行人主观感受, 但由于图片展示数量及感官的局限性, 容易造成较大误差。因此, 建议在较低的服务水平分级上 (如体现通行能力的E级) 依据行人流状态进行划分, 而对较高的服务水平分级上 (如体现自由流状态的A, B级) 可参考行人的主观感知。

现有标准对分级阈值的确定方法主要有观测统计、数学模型推算和问卷调查3种方式。其中观测统计需要采集大量的行人运动视频并准确把握行人流运动状态的变化, 工作量较大, 结果可靠度也较高。数学模型推算法根据行人运动速度-密度函数的数值解析确定不同服务水平等级的阈值, 这种方法简单快捷, 但由于行人运动速密函数本身就存在拟合误差而导致可靠度较低。采用实景照片进行问卷调查的方法工作量适中, 同时考虑到了行人的主观感知, 但会受到照片数量及表现力的局限。

从分级数量上看, 多数研究分为6级, 涵盖了行人流从完全自由状态到拥塞状态的变化过程, 有少部分研究将6级分级中的部分状态合并, 制定了4或5级划分标准。在分级描述上国内研究通常沿用或改进较为成熟的TCQSM方法, 差异较小。

2.2 服务水平分级阈值

2.2.1 通道服务水平分级阈值

行人通道属于通过型设施, 国内外几种分级标准中通道服务水平阈值对比如图2所示。可见TCQSM与张海丽[6]、李洪旭[9]等人的结论较为接近。HCM的分级阈值最高, 因其针对开放道路系统行人设施制定, 其所需活动空间要大于封闭的轨道交通系统。王久亮[7]和王伟涛[10]的分级阈值较低, 因其将TCQSM中所描述的A, B, C三级自由流状态合并为新的A级服务水平, 其A/B, B/C, C/D级阈值分别与TCQSM的C/D, D/E, E/F级阈值相接近。

2.2.2 楼梯服务水平分级阈值

楼梯和通道一样属于通过型设施, 国内外几种分级标准中楼梯服务水平阈值对比如图3 所示。可见, 在楼梯服务水平分级阈值上, 张海丽与HCM, TCQSM等手册较为接近, 而王久亮、王伟涛等人的阈值较低, 其A/B, B/C, C/D级阈值分别与TCQSM的C/D, D/E, E/F级阈值相接近。

2.2.3 等候区服务水平分级阈值

站台及等候区属于排队区域型设施。确定排队和等待区域服务水平最的主要指标是人均可利用空间。除了与舒适感有关外, 人均可利用空间也与环境允许的机动程度有着直接的关系。因此等候区域服务水平的评价应以行人占据空间及其机动性得到满足的程度决定。国内外几种分级标准中等候区服务水平阈值对比如图4 所示。可见, HCM, TCQSM及毕艳祥等[8]在等候区服务水平分级标准上差异甚微, 王久亮[7]的分级阈值较低, 且分级数量较少, 不利于描述车站密度差异较大的情形。

2.3 小结

综上所述, 对于步行设施服务水平分级, 依据行人流运动状态进行划分并通过观测统计确定阈值的方法较为可靠。对于行人自由流状态服务水平的详细划分, 可加入考虑乘客主观感知的修正。分级数量及描述应能够充分体现各分级的差异。因此, TCQSM标准作为目前较为成熟的评价体系对我国具有一定借鉴意义, 未来可补充国内车站观测数据及行人主观感知因素对该标准进行修正。

3 实例分析

3.1 车站概况

北京地铁呼家楼站为地铁6 号线与地铁10号线换乘站。呼家楼站共3层:地下1层为6号线站厅, 分东西2个, 乘客流向简单;地下2层为6号线2个侧式站台与10号线站厅共用, 乘客流线复杂, 为换乘的核心区域;地下3层为10号线分离岛式站台, 乘客流向较简单, 但由于面积较小, 易造成客流拥堵。车站布局及部分尺寸见图5。

3.2 模型构建及参数标定

笔者选用Legion软件作为指标验证的仿真工具。仿真建模过程首先需要在车站设计图的基础上对仿真空间进行简化, 将6 号线、10 号线设计图进行叠加后得到仿真模型的实体框架, 共分3层, 层之间通过28处楼扶梯连接, 见图6。为使模拟效果更加真实, 需对软件默认参数进行重新标定:根据对北京地铁换乘站高峰时段的视频观测和处理, 得到高峰时段乘客在不同设施上的步行速度统计, 步行速度分布情况见图7。

为保证模型真实性, 通过实地调研获取了同一工作日早高峰时段车站各进出站口及站台上下车客流量数据。由于换乘站乘客流线复杂, 难以观测具体路径的OD客流量, 选取部分关键楼梯及通道入口作为客流观测点, 并据此推断各路径的OD客流量。为验证推断得到的OD客流量, 另选部分校验观测点的实际客流与仿真客流量进行对比, 见图8。

3.3 仿真结果及分析

输出仿真时间内车站平均密度分布如图9, 其中换乘通道和候车站台密度较低, 而几处楼梯则密度较高。仿真动态与现场实际观测情形基本一致:换乘通道负荷程度适中, 在列车到达后的短暂时间内有大量行人通过, 此时行人步行速度受到限制, 但极少出现行人间的相互碰撞, 流速较快;尤其在列车到达后易造成拥堵, 此时行人步行速度收到严重限制, 行人间接触和碰撞现象较为普遍;而候车站台则有较大的能力富余, 在有行人排队候车的情况下仍有空间供行人通行。

对仿真输出的行人占用空间进行统计, 按照不同标准划分服务水平, 得到各级服务水平行人百分比分布对比见图10。总体看来, TCQSM与张海丽标准对于通道的服务水平划分较为接近, 以C, D级为主, 符合实际观测情况, 显著高于HCM标准的E级;对于楼梯, 张海丽标准服务水平较高, 以E级为主, 高于实际情况;站台方面, 张海丽标准则较低, 以B, C级为主, 低于实际情况。综合来看, TCQSM标准的可靠性更高, 能够反映车站设施的运行状况。值得注意的是, 采用TCQSM标准时, 处于B级服务水平的行人比例通常小于A, C级, 不符合实际运营中行人占用空间呈正态分布[14]的规律, 这是由于国内外文化差异导致行人心理需求空间不同, 因此TCQSM对于自由状态 (A, B, C级服务水平) 行人流的划分仍有待改进。

4 结束语

微观仿真模型篇8

近年来,球头铣刀在铣削过程中对工件表面形貌及表面粗糙度产生机理的研究吸引了众多学者的关注。通过对已加工表面形貌进行仿真,可以优化切削用量参数,选择适当的刀具,从而保证已加工表面品质[1]。

目前影响已加工表面粗糙度的因素可分成两种[2]:几何因素和物理因素。一般说来,物理因素包括:积屑瘤、鳞刺、振动、切削刃的刃磨品质、工件材料组织的缺陷、切削液的使用情况等;几何因素主要是切削刃与工件相对运动轨迹形成的表面粗糙度,通常与刀具及加工参数有关。高速加工中,积屑瘤和鳞刺几乎不存在,因此刀具几何参数、切削用量等因素将成为影响被加工表面粗糙度的主要因素,这样从理论上进行被加工表面几何形貌仿真具有现实意义[3]。文献[4]用三维数组记录不同刀齿在各个时刻的位置,并在切削过程中更新,得到工件表面上分布点的坐标,给出了动态铣削过程下表面形貌模型;赵小明等[5]针对球头铣刀平面加工时表面微观几何形貌仿真建模进行了研究;阎兵,徐安平等[6]研究了螺旋棒铣刀动态铣削过程下的周铣加工表面形貌,建立了高效的仿真算法。笔者将刀具切削刃划分成切削微元,工件划分为微细网格,同时将加工过程也离散成许多时刻,研究球头铣刀加工表面建模方法。

1 刀具切削轨迹数学模型

在铣削过程中,把刀刃看作一条空间曲线,则切削轨迹就是该曲线旋转和平动合成运动扫略形成的,其形状是一个复杂的空间相交曲面[7]。在仿真表面形貌时,工件表面用三维方格划分,比较刀刃扫略曲面与工件表面网格点的位置关系,曲面上方的网格点被切除,曲面下方的网格点构成工件表面形貌。

1.1 铣削刃数学模型

球头铣刀的刀刃由侧刃部分和球头刃部分构成。球头铣刀的特征主要集中在球形刃部分,加工时一般总是利用球形刃部分,所以本文只研究球形刃部分的切削结果。建立图1 所示的球头铣刀刀具坐标系。

刀刃上任意点P的坐标为[8]:

式中:α——刀刃上P点的位置角;

R——刀具半径;

γ——螺旋角,当γ=0时,即为平面刃。

刀具上任一刀齿位置均可以由特定的一个刀齿旋转得到,因此,引入相位角概念,便可解析各刀齿在加工中的位置。球形刃向uv平面投影,刀刃起点处切线方向与u轴的夹角即为相位角。第i次进给、第j刃的相位角为:

$φ_{i, j} = φ_{i, 1} + \frac{2 π (j - 1)}{f_{z}} - ω t$ (2)

式中:φi,1——第i次进给时第1刃在起始位置的相位角;

fz ——刀齿数;

ω ——刀具角速度;

t ——从第i次进给开始至当前位置所经历的时间。

综上,刀刃上任一点P在刀具坐标系下的坐标值(u,v,w)为:

1.2 刀具的倾斜角度、倾斜方向和进给方式

刀具的倾斜角度和倾斜方向视铣削加工方式而定。在高速铣削过程中,刀具轴线与工件表面较好的夹角关系对于达到最优的表面品质是至关重要的。对平面的铣削加工往往使刀具寿命受到很大的影响,因为在切削刃中心点(刀尖)部位,刀具切削速度为零,有效的容屑空间非常小,使在这一点刀具不是切过工件表面而是划过,这种情况下加工表面品质会不均匀,导致刀具在较短的时间内发生磨损或破损现象。因此经常会给刀具或工件一个小的转角以避免刀尖直接参与切削;同时,也可以有效地避免了曲面加工过程中的干涉现象。倾斜角度改变了刀刃的坐标定位,图2所示顺铣倾斜角度为β时工件坐标系owxyz和刀具坐标系ouvw关系。在这种铣削条件下,刀具坐标系到工件坐标系的转换矩阵为:

球头铣刀走刀方式分两种:一种是刀具完成一次进给后返回,再次进给,称为单向进给;另一种是刀具完成一次进给后不返回,继续进给,称为双向进给。单、双向进给时刀具坐标系原点在工件坐标系下的坐标分别为:

式中:(x0,y0,z0)——第一次进给时道具中心在工件坐标系下的坐标;

fp ——进给行距;

vf ——刀具的进给速度;

Ly ——进给距离,仿真时可取(x0,y0,z0)=(0,0,R)。

1.3 主轴的回转偏心和轴向窜动

主轴误差一般分为两种:主轴的回转偏心和轴向窜动。如果设主轴回转偏心半径为Δd1/2,轴向窜动幅值为Δd2/2,则刀具中心O在刀具坐标系下可用式(6)计算

式中,Δa1,Δa2分别为主轴回转偏心和轴向窜动的初始相位角。

1.4 刀刃的一般表达式

在上述各因素作用下,刀刃上任意点P在工件坐标系下的表达式:

2 表面粗糙度的仿真算法

2.1 三维空间网格划分

设刀具在进给方向和间歇进给方向上的移动距离分别为Lx和Ly,吃刀深度为s。现将工件沿Lx,Ly方向分别用Δx,Δy划分网格,设等分数为kx,ky,则生成(kx+1)×(ky+1)个网格点,用矩阵H=[hi,j]表示网格点的高度。H矩阵的初始值为吃刀深度s。

2.2 仿真算法

当刀具切入工件的时候,对应网格点的值将变化。根据式(7)计算出刀刃上点P的z坐标值,并比较P点坐标与前一次切削保存的对应网格点的高度值H=[hi,j],当z<H时,表示刀刃上点P已切入工件,用P点的z坐标代替H中的对应元素,最后H中保留被加工表面的残留高度值,表面形貌由Matlab软件绘出[9]。具体算法见图3。

2.3 仿真算例

仿真各值的初始值为:球头铣刀半径R=5mm,齿数fz=2,主轴转速n=796r/min,进给量f=40mm/min,进给行距fp=0.4mm,切深s=0.2mm,单向进给。表面形貌仿真如图4所示。

由此,可以得出如下结论:1)刀具在间歇进给交接处表面残余量最大,在保证加工效率的前提下适当减小行距以获得较好的表面。2)主轴转速对粗糙度有一定影响,从仿真结果可以看出,随着转速增加,粗糙度有减小的趋势。

3 结语

在实际形成的加工表面粗糙度中,理论粗糙度仅占实际表面粗糙度中的一部分,原因在于理论仿真模型是从静态条件下几何推算出来的结果,没有考虑切削过程中其他因素对已加工表面生成的影响。现建立的模型预测结果与实际加工十分接近,并且可以揭示不同加工条件对表面粗糙度的影响规律。

参考文献

[1]王素玉.高速铣削加工表面质量的研究[D].济南:山东大学,2006.

[2]袁哲俊.金属切削实验技术[M].北京:机械工业出版社,1987.

[3]张广鹏,徐光月,周红杰,等.铣削表面微观几何形貌仿真方法研究[J].西安理工大学学报,2007,23(3):230-235.

[4]Anotonial A,Savakis C,Bilalis N,et al.Prediction of surface to-pomorphy and roughness in ball-end milling[J].The Interna-tional Jounal of Advanced Manufacturing Technology,2003(21):965-971.

[5]赵晓明,胡德金,赵国伟,等.5坐标数控加工中工件表面形貌的计算机仿真[J].上海交通大学学报,2003,37(5):1-2.

[6]阎兵,徐安平,等.球头铣刀铣削表面形貌建模与仿真[J].计算机辅助设计与图形学学报.

[7]王洪祥,孙涛,董申,等.超精密车削表面微观形貌的几何建模与仿真研究[J].中国机械工程.

[8]Mizugaki Y,Kikkawa K,Terai H,et al.Theoretieal estimation of machined surface profile based on cutting edge movement and tool orientation in ball-nosed end milling,Annals of the CIRP,2003,52(l):49-52.

宏观到微观模型范式及其应用篇9

人类在解决实际问题的时候,往往不是一开始就从粒度最细的层次去分析问题,而是先从宏观出发,粗略地排除一些不必要考虑的因素,锁定一个更窄的问题规模,然后再试图在粒度更细的层次去解决这个问题。宏观到微观算法模型(M2M model)就是一种模仿人类认知思维方式的算法模型。从抽象的意义来说,宏观微观算法思想利用从宏观到微观的过程实现了减治的目的,探讨了模拟人类解决问题从宏观到微观渐进过程的新方法。

M2M算法模型从模仿人类思维方式出发研究人的认知过程。从这个角度来看,M2M模型与粒计算的思想有异曲同工之妙。它们都是一个自顶向下的多层次模型。解决问题时都采取在各抽象层次之间逐步细化的过程。

M2M算法模型具有普适性,是一种指导算法设计的模型,很多经典算法问题和一些具体领域上的应用算法问题,如最近点对问题、凸包问题、TSP问题、聚类问题、寻径问题、碰撞检测问题等都可以利用M2M模型设计出高效的算法。

下面详尽介绍了M2M算法模型及利用M2M算法模型设计的最近邻算法、凸包算法和寻径算法。这些问题都是经典的算法问题。对于最近邻问题有基于平面点集的最优算法[1]、针对最近点对问题的随机算法[2]、基于网格的方法[3],基于四叉树的方法[4]、基于kd树的方法[5]和最新的研究成果,如球形树[6]等。对于凸包算法问题,Ron Graham提出的平面凸包算法[7]是最为经典的方法,被很多研究者作为比较对象。基于分治的凸包算法[8]和输出敏感的凸包算法[9]也是凸包问题的有效解决方法。在实际应用中,经常需要在点集小范围变化的情况下求凸包,动态凸包算法也被广泛研究;而凸包算法的随机性研究[10]和并行性研究[11]也引起研究者的重视。

2. M2M数据结构及其范式

2.1 M2M数据结构

2.2 M2M数据结构范式

基于M2M模型的数据结构可以非常灵活,视乎具体情况和具体需求而变化。但需要满足一些基本的条件:

(1)已知数据点,用O(1)的时间能检索出该点在指定的层所属的分块。

(2)能够用O(1)的时间来把该数据点插入到M2M数据结构中,也能够用O(1)的时间把该数据点从M2M数据结构中删除。

(3)已知某分块的索引,用O(n)的时间能遍历该分块的所有子分块,n为该分块的子分块数。

(4)已知某分块的索引,用O(n)的时间遍历所有属于该分块的数据点,n为属于该分块的数据点数。

(5)已知某分块的索引,用O(1)的时间得到指定层的祖先分块索引。

(6)预处理时间复杂度为O(n),同时支持并行处理。

满足上述条件意味着算法的基本操作,包括建树、查询、添加、删除、更新等操作都达到时间复杂度的平凡下界。

3. M2M数据结构的实现

为了满足上述的基本条件,基于M2M模型的二维空间最近邻算法和凸包算法数据结构如下:

(1)每一层用一个二维数组来保存所有属于该层的分块的索引。由于访问、添加、删除数组元素只需要常数时间,所以满足条件1,2。

(2)每一个分块拥有其子分块的索引列表。

(3)最下层的分块保存属于该分块的所有数据点的列表。如果要遍历任意一层的任意分块所包含的数据点,可以通过广度优先搜索来遍历以该分块作为根节点的树,从而得到所有属于该分块的数据点的索引。算法还采用了额外的一些优化措施,使到这个过程的时间复杂度接近O(n),从而满足条件4。

(4)分块是规整的。可以通过某一分块自身的坐标来换算出其祖先分块的坐标,并通过这个坐标得出该祖先分块的索引,这是在常数时间内完成的,满足条件5。

(5)由于预处理是调用n次插入操作,把n个点插入到数据结构里,而每个插入操作的时间复杂度是O(1),所以预处理的时间复杂度为O(n),满足条件6。

简而言之,基本的M2M数据结构是一棵四叉树[12](在三维的场景中是八叉树),并且树的每一层都与一个横向索引表相关联。这个横向索引表可以是数组也可以用hash表作为存储结构。使用hash技术后,算法的空间复杂度为O(n),与四叉树、KD树等传统数据结构的空间消耗在复杂度上相同。

4. M2M数据结构与常见数据结构的比较

在这里重点的比较对象是层次分解空间数据结构,主要包括BSP树,四叉树,R树与及它们的变体。相较于这些数据结构来说,M2M数据结构:

(1)添加和删除操作是自底向上的,且不必判断与划分面的关系,时间复杂度的期望值为O(1)。

(2)不必保存划分面,节省空间开销。

(3)由于每层都可以利用分块的索引在横向索引表中查找出该分块,所以查询的时间复杂度也为O(1),而且不受树状拓扑结构的不平衡性所影响。

(4)在划分因素比较小的时候可以不保存父分块指向子分块的索引,从而节省内存开销。

(5)由于数据结构的每一层都与一个横向索引相关联,从而可以快速地进行索引搜索。其中,通过索引搜索邻近节点经常被用到。

(6)由于采用规整的分块方式,并且可以取消父分块对子分块的索引表,因而插入、添加操作具有高度的并行性。

(7)由于M2M数据结构的每一层需要维护一个横向索引表,所以内存开销会比其它的树结构要更大一些。尤其当场景属于稀疏场景,而且对场景的分层的最底层粒度比较小的时候。针对这种情况,可以考虑使用哈希表作为较低层的横向索引数据结构。但这样做会增加一定的查询开销。而各种操作的时间复杂度都保持不变。另外,使用哈希表会有损于数据结构的并行性。

简而言之,M2M数据结构涵盖了其它层次分解空间数据结构的操作能力,基本操作的时间复杂度要更低一些,而且具备很好的并行性。此外M2M数据结构还提供了通过横向索引查询邻近分块的操作。

5. M2M算法范式及实验结果

5.1 M2M算法范式

M2M算法一般包括两个阶段,一个是预处理阶段,另一个是解决具体问题的阶段。针对不同的问题具体上有不同的算法,统称之为查询阶段。而更新过程会发生在需要对数据结构进行实时更改的时候。这个过程是针对数据结构进行操作的,所以对于不同的问题,其操作是相同的。

预处理过程:对欧几里得空间点集从上层到下层建立层次表示,从粗到细划分粒度,在每一层把解空间划分为大小均匀的分块。这个过程就是建立M2M数据结构的过程。

更新过程:对已经建立好的数据结构实时进行添加、删除、更新等操作。

查询过程:

(1)从最上层开始,把全局空间作为初始搜索空间。

(2)把当前层搜索空间中每个分块抽象成点,得到一个点集。根据所求解问题,用相应的方法把明显不属于解空间的点从该点集中剔除。再将点集中剩余的点所代表的分块作为粒度更细的下一层的搜索空间。

(3)进入下一层重复2)过程,直到粒度适合的层。

(4)在粒度适合的层的搜索空间中对问题直接求解。

5.2 最近邻算法实验结果

通过实验比较基于M2M模型的最近邻算法和基于KD树数据结构的最近邻算法。其中KD树的代码来自于Sebastian Nowozin[13]。

5.2.1 预处理时间的比较

从图2可以看出,实验结果基本上符合理论分析的结果。在KD树的预处理过程中,由于每次都需要选择好的pivot,需要log(n)的复杂度,所以建树的时间复杂度是n log(n)。基于M2M模型的算法的预处理过程时间复杂度为O(n),所以其曲线接近一条直线。

5.2.2 求最近邻时间的比较

图3是最近邻算法查询阶段耗时的比较,实验结果符合理论分析结果。因为要从树结构里找出目标点所在的分块,基于KD树的求最近邻算法的时间复杂度是近似于log(n),而基于M2M思想的求最近邻算法的时间复杂度近似O(1)。

5.3 凸包算法实验结果

为了更好地研究M2M凸包算法的性能,通过编程实现了M2M凸包算法并且与经典凸包算法进行比较。实验进行的比较对象分别是:Graham scan[14],quick hull[15]和Jarvis march[16]。在实验中随机生成均匀分布的点集,并考察不同算法对不同规模同一点集求凸包的效率。实验环境与最近邻算法相同。图4是实验结果:

图4从上到下的曲线分别是Jarvis march,quick hull,Graham scan和M2M凸包算法这4种算法预处理的耗时。从实验结果可以得到,当点集的规模比较小的时候,Graham scan算法的耗时最少,而M2M凸包算法由于需要预处理,其耗时最多。但随着点集的规模增大,M2M凸包算法的优势渐渐显示出来,当点集规模目到达100万级的时候,M2M凸包算法的耗时大概是Graham scan算法耗时的一半。

6. 结语

M2M模型提供了一个多层次、粒度可选的数据结构,从而可灵活地选择不同的抽象层次去解决不同粒度的问题。通过对M2M算法的理论和实验的分析,可总结出基于M2M模型的算法具有如下共同特性:

(1)预处理共享:算法的预处理过程对大部分问题是相同的。对于一些高级应用,比如模式识别、图形图象处理,往往需要对于相同的图片(点集)作各种处理,而很多处理都可以设计基于M2M模型的相应算法,这些算法可以共享预处理过程。而预处理过程占算法本身大部分的耗时,以M2M凸包算法为例,实验结果表明,预处理时间占据整个算法95%以上的时耗,当多个算法都共享共同的预处理过程时,可以大大地提高整体处理的效率。

(2)高度并行性:M2M算法的预处理过程可以并行执行。此外,很多M2M算法也可以并行执行,可以通过GPU、多CPU、多核等技术来大幅提高M2M算法的效率。

(3)多层结构,粒度可选:M2M数据结构提供了不同粒度的抽象层次,以便在解决具体问题的时候可以选择粒度恰当的层次去解决,而不必每次都关注粒度最细的层次。该算法在宏观到微观的过程中,在粒度较粗的层中仅保留有可能包含解的分块,因此每一层求解后都缩小了解的搜索空间,从而逐步细化,最终求出精确的解。

(4)效率与精确度的互转换:牺牲解的精确度从而缩短算法解决问题的时间。经过简单的调整而成为一个近似算法,可以灵活地实现算法效率和解的精确性互转换。

(5)效率与空间消耗的互转换:宏观-微观算法的层次数目及分块方式可以自定义。一般来说分层越充分,上下层之间的分块数目比越小,算法的空间消耗越大,算法的效率越高,这样就可以灵活地实现算法效率和内存空间之间的互转换。

(6)层次空间分解:M2M数据结构属于一种层次空间分解技术,尤其适用于大规模场景中相关问题的求解。M2M模型兼备了高效性、动态性和并行性等性质,能够很好地解决大规模场景中的相关问题。

摘要：宏观到微观模型源于粒计算的思想。该模型的数据结构用O(n)时间建成,并具备高度的并行性,足够的处理器可使之在O(1)时间内建成(n为点集规模)。由于插入、删除、查询等操作都在常数时间内完成,且不会引起树结构不平衡,因此数据结构具有良好的动态性。此外,M2M模型的数据结构及其预处理过程,能够被所有基于M2M模型的算法所共享,从而大大地提高了需要多种算法共同处理的操作效率。实验结果表明,基于该模型的最近邻算法和凸包算法较之对应的传统算法有很大优势。