基于支撑树法的高速公路多路径识别问题研究.pdf

维普资讯 AFFI 基于支撑树法的高速公路多路径识别问题研究 口 丛浩哲 ，姜 杰 (山东科技大学 交通信息研究所，青岛 266510) 摘 要：随着高速公路的不断建设，开始出现环路，路网密度不断增大，由此产生两点之间车辆 行驶的多路径识别问题，是高速公路联网收费及管理中迫切需要解决的问题。通过深度优先搜索算法 搜索出需要在交通网络中添加标识站的路段，把交通网络网状结构图转化为支撑树树状结构图，从而 实现多路径的识别。 关键词：高速公路i标识站；支撑树；多路径识别 中图分类号：U412 文献标识码：A 文章编号：1671—3400(2007)07—0080—03 Study0fExpresswayMulti-pathRecognitionProblem Based 0n ~，__pannl●ngr。1●一ree CONGHao—Zhe．JIANGJ,ie (TrafficInformationInstituteofShandongUniversityofScienceAndTechnology,Qingdao，266510，China) Abstract：W iththeconstructionofexpressway，thenetworkdensityenlargescontinuouslywithappearingcirculra roads． Becauseofthesereasons，theproblem ofvehicles’drivingmulti-pathrecognitionistheurgentproblem intheon·linetolland managementofexpressway．Serachtheroadsegmentsinthetransportationnetworkwhichraeneededtobeincreasedwith identificationstationsthroughthemehtodofadepthfirstserach，andconvertthenetstructurediagram ofhtetransportation networktothetree·stylesrtucturediagrma ofspanningrtee．W iththis，themethodcancarryouttheproblem ofmulti—path recognition． Keywords：Expressway；Identificationstation；Spanningrtee；M ulti—pathrecognition 段设立标识，获取车辆行驶的标识信息，就可以根据出 0 引言 1：3信息、入1：3信息、标识信息 (可能有多个)识别出任 随着高速公路联网收费网络规模的扩大，两点之间 意车辆的准确行驶路径。在给定的网络中，如何通过添 车辆行驶的多路径识别问题成为联网收费及网络费用清 加一定数量标识站对两顶点之间多路径进行识别是本文 分模式中迫切需要解决的问题 。在封闭式的收费系统 研究的主要问题。 环境下，车辆通过路网时，已经具备了两项信息——出 1 理论依据 口信息和入 口信息。对于路径识别来说，路径是由出口、 入 口、路段信息共同组成，只要三种信息齐全，路径就 引用图论中的一些定理 ： 可以唯一确定。因此，只需要在路网中会产生歧义的路 定义图G是一个三元组，记作G=(G)， G)妒