中文摘要：

为解决现有微观交通仿真系统中,由于采用基于链表的方法处理近邻查询导致的查询效率和可扩展性不高的问题,提出了一种基于B＋树的近邻查询算法。该算法借鉴了数据库中近邻查询算法的思想并结合了链表结构的优点,在叶子节点维护了其存储的数据单元（即车辆）关系的索引结构,以达到快速查询车辆所在车道的前后车的目的。同时,在假设车辆随机分布的前提下,构建了一个数学模型,根据道路的属性和道路中车辆的数量,计算查询目标车辆的邻近车辆所需的最短平均查询长度,并通过此最短查询长度推导算法参数的最优值。理论分析和对比仿真实验显示,衡量该算法的主要指标：即仿真每个车辆的平均时间消耗,在三类常见的交通参数设置（正常的、较拥堵的和拥堵的）下较链表和B＋树分别降低了64.2%和12.8%。仿真结果表明该算法具有良好的可扩展性,更适用于大规模微观交通仿真系统。

英文摘要：

Since methods based on linked list in existing microscopic traffic simulation systems are not efficient and scalable to process Nearest Neighbor （NN） queries.a variation of B ＋ tree based method was proposed to resolve these problems. This method combined ideas from NN queries in database with advantages of linked list. By maintaining indices of nearby vehicles of each vehicle in the local lane, the performance of NN queries in that lane could be largely improved. Under the assumption of randomly distribution of vehicles, a mathematical model was also proposed to optimize the parameter setting according to multiple parameters for lanes and the amount of vehicles. This model calculated the minimized average query length of each NN query to optimize the parameter setting. The results of theoretical analysis and simulations showed that in common traffic conditions including sparse, normal and congestion, the main indicator, namely the average simulation time cost of each vehicle, could be reduced by 64.2% and 12.8% compared with linked list and B ＋ tree respectively. The results prove that the proposed method is suitable for larges-cale microscopic traffic simulation systems.