考虑禁行路线路网的最优路径求解  

Solution to Optimal Path in Road Network with Restricted Routes

作　　者：潘福全[1] 陆键[1] 王丰元[2] 项乔君[1] 

机构地区：[1]东南大学,南京210096 [2]青岛理工大学,青岛266033

出　　处：《交通与计算机》2006年第3期5-8,共4页Computer and Communications

基　　金：国家十五科技攻关项目资助(批准号:2002BA404-A01);山东省教育厅中青年学术骨干基金资助(批准号:A2002-107)

摘　　要：为了解决含有禁行路线路网中的最优路径求解问题,研究了含有禁行路线路网的特点,建立了数学模型。通过路网转化法把含有禁行路线的路网转化为不含禁行路线的路网,降低了最优路径求解的难度。采用邻接结点关系矩阵和邻接结点权矩阵表达路网中结点和路段的拓扑关系,减少了路网的存储空间。用动态邻接结点关系矩阵和邻接结点权矩阵对经典的D ijkstra算法进行了改进,节省了计算机存储空间、提高了计算效率,并给出了基本算法。将所研究的路网转化方法和改进的D ijkstra算法应用于所研发的车辆诱导系统软件,并进行了实际测试,测试结果表明,应用该方法能够在含有禁行路线的路网中求解最优路径,且运算效率较高。In order to solve the optimal path in road network with restricted routes, this paper analyzed the characteristics of road network with restricted routes, and constructed its mathematic model. The road network with restricted routes was translated into the road network without restricted routes according to the studied method, which reduced the complexity of the optimal path solution. The topological relationship of nodes and road sections in road network was expressed By adjacent node relation matrix and adjacent node weight matrix, which saved the storage space. The traditional Dijkstra algorithm was optimized with dynamic adjacent node relation matrix and adjacent node weight matrix, which reduced the storage space and improved the calculation efficiency, and the corresponding algorithm was given. A vehicle guidance system was developed with the optimized Dijkstra algorithm to find the optimal path in the restricted road network. Test results indicated that the method for transforming road network and optimized Dijkstra algorithm was efficient in calculating the optimal path in the road network with restricted routes.

关 键 词：智能交通系统 车辆诱导系统 路网 禁行路线 最优路径 

分 类 号：U491.1[交通运输工程—交通运输规划与管理]