西安公路交通大学学报
Journal of Xi'an Highway University
2001 Vol.21 No.1 P.64-67

车辆导航系统基于GIS的动态K最短路递推解法

晏克非　 苏永云　 黄翔　 覃煜　 朱培康　

摘　要：在对车辆导航系统的路径引导信息进行供需分析的基础上，提炼出了对系统设计具有重要意义的动态K最短路问题，建立了路段动态行程时间计算模型，提出了将其融入最短路算法中并结合GIS技术的动态最短路改进A*算法，并设计了通过替换动态最短路的部分路段以搜索动态K最短路的合理前趋替换算法。
关键词：车辆导航系统；GIS；动态K最短路；改进A*算法；合理前趋替换算法
分类号：U491.2　文献标识码：A
文章编号：1007-4112(2001)01-0064-04

Algorithm for Dynamic K Shortest-Pathsin Vehicle Navigation Sytem Based on GIS

YAN Ke-fei（Department of Road and Traffic Engineering, Tongji University, Shanghai 200092, China）　
SU Yong-yun（Department of Road and Traffic Engineering, Tongji University, Shanghai 200092, China）　
HUANG Xiang（Department of Road and Traffic Engineering, Tongji University, Shanghai 200092, China）　
QIN Yu（Department of Road and Traffic Engineering, Tongji University, Shanghai 200092, China）　
ZHU Pei-kang（Department of Road and Traffic Engineering, Tongji University, Shanghai 200092, China）　

Abstract：The supply and demand of the route guidance information in vehicle navigation system are analyzed. The problem of dynamic K shortest paths is derived and the model for estimating dynamic traveling time on segment is deduced. At last the improved A* algorithm for dynamic shortest path and reasonable predecessor replaced algorithm for dynamic K shortest patehs based on GIS is put forward.
Keywords：vehicle navigation system;GIS；dynamic K shortes-paths;improved A* algorithm;reasonable predecessor replaced algorithm
基金项目：国家自然科学基金资助项目(59978035)
作者简介：晏克非(1943-)，男，湖南浏阳人，同济大学教授，博士生导师
作者单位：晏克非（同济大学　道路与交通工程系，上海　200092）　
　　　　　苏永云（同济大学　道路与交通工程系，上海　200092）　
　　　　　黄翔（同济大学　道路与交通工程系，上海　200092）　
　　　　　覃煜（同济大学　道路与交通工程系，上海　200092）　
　　　　　朱培康（同济大学　道路与交通工程系，上海　200092）　

参考文献：

［1］赵亦林，谭国真.车辆定位与导航系统［M］.北京：电子工业出版社，1999.
［2］杨兆升.城市交通流诱导系统理论与模型［M］.北京：人民交通出版社，2000.
［3］DAVID E Boyce. Route guidance systems for improving urban travel and location choice［J］.Transportation Research,1998,22A(4):275—281.
［4］贺国光，徐岩宇.车辆线路引导系统的行程时间预测模型研究［J］.中国公路学报，1998，11(3)：79—86.
［5］李作敏，黄中祥.VRGS中车辆引导比例研究——MLP优化模型描述［J］.中国公路学报，1999，12(4)：96—100.
［6］BERTSIMAS D J, SIMCHI-LEVI D. A new generation of vehicle routing research:algorithms,addressing uncertainty［J］.Operations Res,1996,44(2):286—304.
［7］FU L,RILETT L R.Expected shortest paths in dynamic and stochastic traffic networks［J］.Transpn Res-B,1998,32(7):499—516.
［8］WEYMANN J,FARGES J L,HENRY J J.Dynamic route guidance with queue and flow-dependent travel time［J］.Transpn Res-C,1994,2(3):165—183.
［9］杜端甫.运筹图论(图、网络理论中的运筹问题)［M］.北京：北京航天航空大学出版社，1990.

收稿日期：2000年7月7日

出版日期：2001年1月1日