第 ２９ 卷 第 １ 期
２０１２ 年 ３ 月
广东工业大学学报
Ｊｏｕｒｎａｌ ｏｆ Ｇｕａｎｇｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ
Ｖｏｌ．２９ Ｎｏ．１
Ｍａｒｃｈ ２０１２
收稿日期： ２０１１－０９－０８
基金项目： 广东省科技计划项目（２００９Ｂ０１０８０００５２）
作者简介： 郭佩珍（１９８７－），女，硕士研究生，主要研究方向为车辆导航路径优化．
基 于 随 机 时 间 的 车 辆 导 航 路 径 规 划 研 究
郭佩珍，胡 刚，傅 惠
（广东工业大学 自动化学院，广东 广州 ５１０００６）
摘要： 根据车辆导航中各路段行车时间具有随机性特点，运用不确定性规划理论建立了行车时间随机的车辆导航
路径随机规划模型，模型以车辆出行中行车时间最短为目标函数．并设计了基于随机模拟的遗传算法求解该模型．
通过数值仿真，证明模型的可行性．
关键词： 车辆导航路径；随机规划模型；期望值；遗传算法；仿真
中图分类号： Ｕ４９５ 文献标志码： Ａ 文章编号： １００７－７１６２（２０１２）０１－００３５－０４
Ｒｅｓｅａｒｃｈ ｏｎ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｗｉｔｈ Ｒａｎｄｏｍ Ｔｉｍｅ ｆｏｒ Ｖｅｈｉｃｌｅ Ｎａｖｉｇａｔｉｏｎ
Ｇｕｏ Ｐｅｉ－ｚｈｅｎ， Ｈｕ Ｇａｎｇ， Ｆｕ Ｈｕｉ
（Ｆａｃｕｌｔｙ ｏｆ Ａｕｔｏｍａｔｉｏｎ， Ｇｕａｎｇｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｇｕａｎｇｚｈｏｕ ５１０００６， Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ： Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｒａｎｄｏｍｎｅｓｓ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｖｅｈｉｃｌｅ ｎａｖｉｇａｔｉｏｎ， ｉｔ ｓｅｔｓ ｕｐ ｔｈｅ ｓｔｏｃｈａｓｔｉｃ ｐｒｏ－
ｇｒａｍｍｉｎｇ ｍｏｄｅｌ ｗｉｔｈ ｔｈｅ ｓｈｏｒｔｅｓｔ ｔｒａｖｅｌ ｔｉｍｅ ｆｏｒ ｔａｒｇｅｔ ｆｕｎｃｔｉｏｎ ｉｎ ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｆ ｖｅｈｉｃｌｅ ｎａｖｉｇａｔｉｏｎ．
Ｔｈｅ ｄｅｓｉｇｎ ｏｆ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｗａｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｓｔｏｃｈａｓｔｉｃ ｓｉｍｕｌａｔｉｏｎ ｔｏ ｏｂｔａｉｎ ｔｈｅ ｍｏｄｅｌ．Ｔｈｅ ｓｉｍｕ－
ｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｐｒｏｖｅ ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ｍｏｄｅｌ．
Ｋｅｙ ｗｏｒｄｓ： ｖｅｈｉｃｌｅ ｎａｖｉｇａｔｉｏｎ ｐａｔｈ； ｓｔｏｃｈａｓｔｉｃ ｐｒｏｇｒａｍｍｉｎｇ ｍｏｄｅｌ； ｅｘｐｅｃｔａｔｉｏｎｓ； ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；
ｓｉｍｕｌａｔｉｏｎ
车辆导航系统是智能交通系统的重要组成部
分，随着计算机、通讯技术以及 ＧＩＳ （ 地理信息系
统）、ＧＰＳ（全球定位系统） 等技术的迅速发展，车辆
导航系统的研究也获得了长足的进展
［１］
．最优路径
规划按某种策略，如时间最少或路径最短等，为驾驶
员实时准确地选定一条最优的行车路径，并显示在
计算机屏幕的电子地图上，是车辆导航系统的核心
技术之一，是其它各种功能应用的基础
［２］
．
目前，投入市场应用的成熟车辆导航系统大多
基于静态的路径规划，在过去的几十年里，静态导航
最短路径问题，已经取得了很大的成就，提出了很多
算法
［３－５］
，这些算法主要集中在如何改善算法的效率
上．然而面对存在众多不稳定因素的交通现实，尤其
是发生交通事故和交通堵塞时，算法结果并不理想．
因为在静态路径规划中，交通路网中的路网阻抗是
恒定的，不随时间变化的．很明显与实际交通路网不
相符，如路段中的行车时间、行车速度、行车费用等
应该是动态变化的，且这种变化具有不确定性．
本文拟考虑车辆导航中行车时间变化的不确定
性，应用随机规划方法，建立基于随机时间的车辆导
航随机规划期望值模型，并在此基础上设计出基于
随机模拟的遗传算法，对模型进行求解．
１ 模型及算法
１．１ 车辆导航路径随机规划模型建立
在现有的复杂的交通网络中，影响车辆行车时
间的因素很多，天气、交通事故等随机因素的影响，
导致出行车辆的行车时间产生不确定性的变化．近
年来，学者们对行车时间预测、规律统计等方面都作
了大量的研究．行程时间预测方法有历史趋势方法、
非参数回归方法、时间序列、神经网络方法、Ｆｕｚｚｙ 回
归法、交叉技术法、随机排队理论法和宏观延误法
等，但这些模型算法复杂，操作难度大
［６］
．在行车时
间规律统计方面，朱彦等
［７］
采用统计分析方法得出
使用正态分布和对数正态分布模型来描述同一路段
相同时段的行程时间是比较合适的．
资源评论
