总第２７５期 计算机与数字工程 Ｖｏ１．４０ Ｎｏ．９ ２０１２年第９期 Ｃｏｍｐｕｔｅｒ＆Ｄｉｇｉｔａｌ Ｅｎｇｉｎｅｅｒｉｎｇ ２４ 基于Ｒ树索引的智能交通系统的算法研究 王植 （西安航空职业技术学院西安７１００８９） 摘要 由于道路交通矛盾的现象已经日益严重，利用智能交通系统解决交通问题已成为普遍共识。文章重点讨论了地理信息系统技术 和全球定位系统技术等相关技术，并利用改进的Ｒ树索引完成了智能交通系统的核心不确定范围查询算法，分析与实现了智能交通系统。 关键词地理信息系统；全球定位系统；Ｒ树索引；智能交通系统；不确定范围查询 中图分类号ＴＰ３０１．６ Ｉｎｔｅｌｌｉｇｅｎｔ ＴｒａｎｓｐＯｒｔａｔｉ０ｎ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ ｔｈｅ Ｒ Ｔｒｅｅ Ｉｎｄｅｘ ＷＡＮＧＺｈｉ （Ａｅｒｏｎａｕｔｉｃａ１ Ｐｏｌｙｔｅｃｈｎｉｃ Ｉｎｓｔｉｔｕｔｅ，Ｘｉ’ａｎ ７１００８９） Ａｂｓｔｒａｃｔ Ｄｕｅ ｔｏ ｒｏａｄ ｔｒａｆｆｉｃ ｃｏｎｔｒａｄｉｃｔｉｏｎ ｐｈｅｎｏｍｅｎｏｎ ｈａｓ ｂｅｃｏｍｅ ｉｎｃｒｅａｓｉｎｇｌｙ ｓｅｒｉｏｕｓ，ｕｓｉｎｇ ｉｎｔｅｌｌｉｇｅｎｔ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｓｙｓｔｅｍ ｔｏ ｓｏｌｖｅ ｔｈｅ ｔｒａｆｆｉｃ ｐｒｏｂｌｅｍ ｈａｓ ｂｅｃｏｍｅ ａ ｇｅｎｅｒａｌ ｃｏｎｓｅｎｓｕｓ．Ｔｈｉｓ ｐａｐｅｒ ｆｏｃｕｓｅｓ ｏｎ ｔｈｅ ｄｉｓｃｕｓｓｉｏｎ ｏｆ ｔｈｅ ｇｅｏｇｒａｐｈｉｃ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ（ＧＩＳ） ｔｅｃｈｎｏｌｏｇｙ ａｎｄ ｇｌｏｂａｌ ｐｏｓｉｔｉｏｎｉｎｇ ｓｙｓｔｅｍ（ＧＰＳ）ｔｅｃｈｎｏｌｏｇｙ，ａｎｄ ｕｓｉｎｇ ｉｍｐｒｏｖｅｄ Ｒ ｔｒｅｅ ｉｎｄｅｘ ｆｉｎｉｓｈｅｄ ｔｈｅ ｃｏｒｅ ｔｏ ｉｎｔｅｌｌｉｇｅｎｔ ｔｒａｆｆｉｃ ｓｙｓｔｅｍ ｕｎｃｅｒｔａｉｎｔｙ ｒａｎｇｅ ｑｕｅｒｙ ａｌｇｏｒｉｔｈｍ，ａｎａｌｙｓｉｓ ａｎｄ ｉｍｐｌｅｍｅｎｔａｔｉｏｎ ｏｆ ｉｎｔｅｌｌｉｇｅｎｔ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｓｙｓｔｅｍ Ｋｅｙ Ｗｏｒｄｓ ＧＩＳ，ＧＰＳ，Ｒ ｔｒｅｅ ｉｎｄｅｘ，ｉｎｔｅｌｌｉｇｅｎｔ ｔｒａｆｆｉｃ ｓｙｓｔｅｍ，ｕｎｃｅｒｔａｉｎｔｙ ｒａｎｇｅ ｑｕｅｒｙ Ｃｌａｓｓ Ｎｕｍｂｅｒ ＴＰ３Ｏ１．６ １ 引言 并为社会提供舒适、便利的交通环境。近几十年来，智能交 通系统逐渐成为解决交通堵塞等发展瓶颈问题的途径之 随着经济的高速发展和城市规模的日益扩大，道路交 一，其重要性和必要性正在社会发展中凸显出来。智能交 通矛盾的现象已经日益严重，利用智能交通系统解决交通 通系统的出现大大促进了解决此类问题，其不仅能够记录 问题已成为普遍共识。智能交通系统主要基于地理信息系 交通信息以提高解决交通问题的效率，而且能够有效地利 统（ＧＩＳ），在ＧＩＳ中被广泛应用的轨迹数据库管理的研究开 用现有交通设施、减少交通负荷和环境污染、保证交通安 始于上世纪８Ｏ年代。不确定范围查询作为轨迹数据库管 全、提高运输效率。 理的重要内容这两年有着较为深入的研究，对智能交通系 统的开发意义重大。 ３系统结构分析与实现 ２智能交通系统相关内容以及研究意义 智能交通系统由两大部分构成的：公共交通管理系统 和出行者系统。公共交通系统主要包括路段车辆查询、路 目前从军用技术脱胎的全球定位系统、红外传感技术、 段车辆速度查询以及交通预测。出行者系统主要包括交通 机器成像技术等已成为智能交通系统研究的重要技术。在 概况信息查询、交通诱导以及路段推荐。路段数据以及车 这样的背景下，智能交通系统成为解决现代社会诸多交通 辆数据需要设计好索引再存储以加快查询速度。数据库设 的一个全新并有无限前景的发展领域。结合计算机技术、 计完成后，就可将图中各路段信息以及车辆信息录入到数 通信、信息科学等学科知识，智能交通系统是一个在应用方 据库中。数据库建好后，定时对数据库进行维护更新。索 面的产物。在技术层面可将智能交通系统分层次，包括高 引的构建主要使用Ｒ树索引结构［１ ］以及ＴＰＲ＊树索 级智能交通系统、模式化智能交通系统、初级智能交通系 引ｌ５］，这样做的好处是可以提升查询速度以提高整个系统 统、以监控为主的交通工程。其中高级智能交通系统对人 的性能。 工智能要求很高。模式化智能交通系统需要用到系统识别 ３．１ 系统功能描述和划分 以及模式识别。初级只能运输系所需技术包括计算机相关 根据系统总模块图可知，系统主要包括公共交通管理 技术、信息技术、数学应用、地理信息处理以及通信技术。 系统和出行者系统，而出行者系统所需的信息主要由公共 以监控为主的交通工程要求较低，仅需要交通工程的基本 交通管理系统提供，因此首先要将公共交通管理系统设计 设施、电子设备、传感器以及数据采集软件和监控软件。 好。公共交通管理系统主要包括路段车辆查询、路段车辆 智能交通系统能有效地缓解交通堵塞，减少交通事故 速度查询以及交通预测，其中之所以将路段车辆速度查询 ＊收稿日期：２０１２年３月１ Ｅｌ，修回日期：２０１２年４月２７日 作者简介：王植，男，硕士研究生，讲师，研究方向：信息处理，数据挖掘。 ２０１２年第９期 计算机与数字工程 ２５ 从路段车辆查询中单独提取出来，是因为路段车辆速度查 询并非直接从车辆信息中提取出速度信息，而是系统根据 车辆坐标以及时间信息计算出，因此路段车辆查询必须在 管理员选择此功能时才会进行计算，否则耗用资源太多。 圭塑 ！ 垫塑卜 坐堡竺垫ｈ ｌ坐坚堑垫Ｉ Ｉ＜ ． 磊丽 竺苎奎 笪望墨竺 出行者系统 路段车辆查询 交通概况信息查洵 路段车辆速度查洵 路径诱导 交通预测 路段推荐 图１系统体系结构图 １）公共交通管理模块 公共交通管理系统登录后系统根据公共交通管理系统 管理员选择的功能从数据库中使用索引结构查找到相关的 数据然后进行相应的处理，处理完毕后，将结果显示在系统 界面。在管理员使用功能完毕并退出系统后，系统将会清 空所使用功能中用到的数据。公共交通管理系统使用流程 图如图２所示。 ［ ．＝ ｉ堕 选择功能 路段车辆查询Ｉ ｌ路段车辆速度汁算ｌ ｌ 交通预测 输入查洵条件Ｉ ｌ输入查询条件ｌ ｌ输入预测时间 提交 ——Ｔ一 查看结果 否 结束 图２公共交通管理系统使用流程图 ２）出行者系统模块 出行者系统使用者系统根据出行者系统使用者选择的 功能从数据库中使用索引结构查找到相关的数据然后进行 相应的处理，处理完毕后，将结果显示在系统界面。在使用 者使用功能完毕并退出系统后，系统将会清空所使用功能 中用到的数据。出行者系统使用流程图如图３所示。 ３．２ 路段以及车辆定位 定位在本文研究中占有十分重要的比重。首先各路段 的定位可通过ｇｏｏｇｌｅ提供的地图来实现，由于ｇｏｏｇｌｅ地图 已经使用ＧＰＳ技术对各路段进行了坐标转换［。 ］，因此本 文可直接进行使用。在本文研究的课题里，车辆的定位主 要依靠ＧＰＳ定位装置，最后通过坐标转换计算车辆城建坐 标。由于本文研究中无法实现通过ＧＰＳ对路段所有车辆 进行定位，因此车辆的坐标数据通过工具在一定范围内随 即生成。 ３．３移动轨迹 对于本文所研究路网空间中的车辆，一般可以认为其 运动在二维空 ］中，虽然这会造成一点偏差，但在可接 受范围内。在某一时刻，定义车辆的轨迹某一点信息为（ｔ， ， ），其中 代表车辆的城建横坐标，Ｙ代表车辆的城建 纵坐标。令￡一 （ ）一（口 （ ），口Ｙ（ ）），ｔＥ Ｊ，Ｊ为时间间隔， ａ（￡）为时间ｔ的一个函数，它可以以时间ｔ为参数推导出车 辆的 以及Ｙ坐标，即是Ｒ—Ｒ２，Ｒ代表时间间隔，Ｒ２代表 二维空间，那么 Ｔ一｛（ｔ，口 （￡），ｄ ｙ（ ））ＥＲ×Ｒ２ＩｔＥ Ｊ｝ 即是车辆在时间间隔Ｒ内的一段轨迹。 图３ 出行者系统使用流程图 ３．４路段推荐功能 路段推荐功能主要是针对一些出行者用户的特殊需求 来设计的。系统会让出行者系统使用者选择功能，主要包 括： １）最短距离； ２）最省时间； ３）最不拥堵。 选择最短距离时，路段推荐的结果根据交通诱导得出 的路段序列即可得到。 选择最省时间时，则需要用到公共交通管理系统的交 通预测功能。 本文中最不拥堵功能的实现则比较简单，主要是根据 当前路段的下一路口所连接的路段中挑选，根据公共交通 管理系统中的预测功能即可得到路段中车辆最少的路段。 ３．５路段车辆查询 路段车辆查询的实现比较简单，主要通过查询车辆所 在位置是否在某路段范围内，即可得到结果集。同样，路段 车辆速度查询的实现相对也比较简单。首先从数据库读入 相关路段以及路口信息后，即可建立Ｒ树索引。在Ｒ树叶 子结点中，选择一个合适的叶子结点并将路段的不确定矩 形框插入之。对于Ｒ树合适的评价标准是插入下一个路段 的不确定矩形框后，ＭＢＲ面积增加最少。如果这个叶子结 点还能容纳不确定矩形框，则直接插入；否则，将该叶子结 点分裂成两个叶子结点，且这两个叶子结点包含要输人的 矩形框和原来含有的矩形框。分裂时，使得这两个叶子结 点对应的矩形区域之和最小。分裂之后，从叶子结点向根 结点进行调整。如此直至将路段的矩形框都插入到Ｒ树 中。路段的Ｒ树结构如图４所示。 Ｒ树插入算法的基本思想：找到合适的叶子结点，插入 ２６ 王植：基于Ｒ树索引的智能交通系统的算法研究 第４Ｏ卷 之，若需分裂，则由下至上调整ＭＢＲ值。算法如下 图４路段的Ｒ树结构 １）选择一个合适的叶子结点Ｌ以容纳需插入项Ｅ； ２）若Ｌ中还能容纳Ｅ，则加人之；否则分裂该结点成 两个结点Ｌ和ｆ Ｌ，它们包含Ｅ和Ｌ中原有的所有项； ３）调整以Ｌ和ＬＬ为根的子树； ４）若结点分裂向上传播导致根结点的分裂，则生成新 的根结点。 开始 选择一个合适的叶子结 ｌ 点以放置新项Ｅ。合适的评价 从数据库中获取数据 标准是插入Ｅ后的结点ＭＢＲ Ｊ 为路段建立Ｒ树索引， 面积增加度最少。分裂结点 为车辆建立ＴＰＲ＊树索引 Ｉ 的原则是：使分裂后的两个结 汁算查询路段的坐标范围 点ＭＢＲ面积和最小。在为路 段建立Ｒ树索引后，即可进行 车辆查询，车辆查询流程图如 图５所示。 查询结果集 如图５所示，系统从数据 ｌ 结束 库中获取数据以后，为路段建 立Ｒ树索引，并为车辆建立 图５车辆查询流程图 ＴＰＲ＊索引。在公共交通管 理系统使用者输入查询路段以后，即计算查询路段在地图 中的坐标范围，然后在索引中查找在此范围内的车辆，查找 完毕以后，即可得到结果集。 ３．６路段车辆速度的查询 在车辆查询的基础上，通过两次车辆查询即可计算车 辆速度以完成车辆速度的查询。系统从数据库中获取数据 以后，为路段建立Ｒ树索引，并为车辆建立ＴＰＲ＊索引。 在公共交通管理系统使用者输入查询路段以后，即计算查 询路段在地图中的坐标范围，然后在索引中查找在此范围 内的车辆，查找完毕以后，即可得到结果集，得到此结果集 后，即可查询结果集中的车辆在上一时刻的坐标，并通过计 算得到其速度。注意，第一步数据需在Ｍｙｓｑｌ数据中一次 性取出，然后建立索引，这样做的目的是加快查询速度，如 果一次一次地从数据库取出数据，则速度较慢。 ４结语 本系统很好地实现了基于ｃ／ｓ模式的智能交通系统的 研究，研究主要针对智能交通系统的关键技术索引结构、速 度估算及系统实现展开。文章中既详细叙述了根据实际项 目需求所设计的实时性强、精度高、应用方便的关键技术算 法，也对相关领域的研究背景、有关知识及实现时的具体操 作进行了介绍。 智能交通系统中的公共交通管理系统和智能交通系统 仍然集成在一起，今后可以讲两系统分开，并实现通信的功 能。与欧美的成熟智能交通系统软件相比，功能仍比较稀 少，这些不足之处今后将不断补充和完善，使系统能更趋完 善。对于本系统，数据库的建设还不很合理和规范，仍需要 改进。车辆的索引结构并没有真正能够合理的使用，今后 可以进一步研究以加快查询速度。在建立轨迹模型的过程 中，改进了轨迹模型，加入了其他的轨迹信息，方便查询实 现。在查询阶段，使用了改进的ＭＢＲ，并分为两步查询，减 少了查询对象并减少了系统开销。由于本文的设备限制， 所研究的地图数据比较少，今后可以进～步扩展。 参考文献 ［１］李洪涛，许国昌，薛鸿印．ＧＰＳ应用程序设计［Ｍ］．北京：科学出 版社，１９９９． Ｉ Ｉ Ｈｏｎｇｔａｏ，ＸＵ Ｇｕｏｃｈａｎｇ，ＸＵＥ Ｈｏｎｇｙｉｎ，ＧＰＳ ａｐｐｌｉｃａｔｉｏｎ ｄｅｓｉｇｎ，Ｓｃｉｅｎｃｅ Ｐｒｅｓｓ，１９９９． Ｅ２］［美］赵亦林著，谭国真译．车辆定位与导航系统［Ｍ］．北京：电子 工业出版社，１９９９． ＺＨＡＯ Ｙｉｌｉｎ，ＴＡＮ Ｇｕｏｚｈｅｎ，ＶｅＮｃｌｅ ｌｏｃａｔｉｏｎ ａｎｄ ｎａｖｉｇａｔｉｏｎ ｓｙｓｔｅｍ ［Ｍ］．Ｂｅｉｊｉｎｇ：Ｐｕｂｌｉｓｈｉｎｇ Ｈｏｕｓｅ ｏｆ ｅｌｅｃｔｒｏｎｉｃｓ ｉｎｄｕｓｔｒｙ，１９９９． ［３］张可．车辆导航系统关键技术的研究［Ｉ）］．北京工业大学，２００１． ＺＨＡＮＧ Ｋｅ．Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ｋｅｙ ｔｅｃｈｎｏｌｏｇｙ ｏｆ ｖｅｈｉｃｌｅ ｎａｖｉｇａ ｔｉｏｎ ｓｙｓｔｅｍ［Ｄ］．Ｄｏｃｔｏｒａｌ Ｄｉｓｓｅｒｔａｔｉｏｎ ｏｆ Ｂｅｉｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，２００１． ［４］刘允才．智能交通系统在我国的发展趋势＿Ｊ］．交通流与颗粒 流，２００４，５：１５５—１６８． Ｉ ＩＵ Ｙｕｎｃａｉ．Ｉｎｔｅｌｌｉｇｅｎｔ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｓｙｓｔｅｍ ｉｔｓ ｄｅｖｅｌｏｐｍｅｎｔ ｔｒｅｎｄ ｉｎ Ｃｈｉｎａ，Ｔｒａｆｆｉｃ ａｎｄ ｇｒａｎｕｌａｒ ｆｌｏｗ，２００４，５：１５５—１６８． ［５］关旭．智能交通系统中地理信息系统的研究［Ｄ］．上海交通大 学，２００５． ＧＵＡＮ Ｘｕ．Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍ ｉｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ［Ｄ＿．Ｓｈａｎｇｈａｉ Ｊｉａｏ Ｔｏｎｇ Ｕｎｉ— ｖｅｒｓｉｔｙ，２００５． ［６］刘文闳，熊伟，吴烨，等．空间索引并行批量加载算法研究［Ｊ］． 现代电子技术，２０１ｌ（２２）． ＬＩＵ Ｗｅｎｈｏｎｇ，ＸＩ（）ＮＧ Ｗｅｉ，ＷＵ Ｙｅ，ｅｔ ａ１．Ｓｐａｔｉａｌ ｉｎｄｅｘ ａｌｇｏ— ｒｉｔｈｍ ｏｆ ｐａｒａｌｌｅｌ ｂａｔｃｈ ｌｏａｄｉｎｇ［Ｊ］．Ｍｏｄｅｒｎ ｅｌｅｃｔｒｏｎｉｃ ｔｅｃｈｎｏｌｏ ｇＹ，２０１１（２２）． ［７］肖金城，王恩泉，胡特或．三维地理信息应急指挥系统设计［Ｊ］． 测绘科学，２０１２（２）． ＸＩＡＯ Ｊｉｎｃｈｅｎｇ，ＷＡＮＧ ＥｎＱｕａｎ，ＨＵ ＴｅＹｕ．Ｔｈｒｅｅ－ｄｉｍｅｎ ｓｉｏｎａｌ ｇｅｏｇｒａｐｈｉｃ ｉｎｆｏｒｍａｔｉｏｎ ｅｍｅｒｇｅｎｃｙ ｃｏｍｍａｎｄ ｓｙｓｔｅｍ ｄｅ— ｓｉｇｎＥＪ］．Ｓｃｉｅｎｃｅ ｏｆ Ｓｕｒｖｅｙｉｎｇ ａｎｄ ｍａｐｐｉｎｇ，２０１２（２）． ［８］过志峰，王字翔，杨崇俊．空间数据索引与查询技术研究及其应 用［Ｊ］．计算机工程与应用，２００２，３８（２３）：１７６—１７８． ＧＵＯ Ｚｈｉｆｅｎｇ，ＷＡＮＧ Ｙｕｃｈｏｎｇ，ＹＡＮＧ ＣｈｏｎＮｕｎ．Ｓｐａｔｉａｌ ｄａ— ｔａ ｉｎｄｅｘ ａｎｄ ｑｕｅｒｙ ｔｅｃｈｎｏｌｏｇｙ ｒｅｓｅａｒｃｈ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ，２００２，３８（２３）：１７６— １７８． ［９］肖予钦，张巨，景宁，等．基于Ｒ树的方向关系查询处理［Ｊ］．软 件学报，２０４，１５（１）：１０３—１１１． ＸＩＡＯ Ｚｉｑｉｎ，ＺＨＡＮＧ Ｊｕ，ＪＩＮＧ Ｎｉｎｇ，ｅｔ ａ１．Ｂａｓｅｄ ｏｎ ｔｈｅ Ｒ ｔｒｅｅ ｄｉｒｅｃｔｉｏｎ ｒｅｌａｔｉｏｎ ｑｕｅｒｙ ｐｒｏｃｅｓｓｉｎｇ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ ｓｏｆｔｗａｒｅ， ２００４，１５（１）：１０３一ｌ１１． Ｅｌ０］胡志勇．空间数据库索引技术研究［Ｄ］．武汉大学，２００１． ＨＵ Ｚｈｉｙｏｎｇ．Ｓｐａｔｉａｌ ｄａｔａｂａｓｅ ｉｎｄｅｘ ｔｅｃｈｎｏｌｏｇｙ ｒｅｓｅａｒｃｈＥＤ］． Ｗｕｈａｎ Ｕｎｉｖｅｒｓｉｔｙ，２００１．