一种求解交通网络中最短路径问题的人工蜂群算法

王 玉, 申铉京, 周昱洲， 林鸿斌

(1. 吉林大学 计算机科学与技术学院, 长春 130012； 2. 吉林大学 软件学院， 长春 130012)

随着智能交通系统的应用越来越广泛, 车辆路径规划作为智能交通系统的一项基本功能, 因而得到越来越多的关注. 目前, 对于静态交通网络的车辆路径规划研究已有很多结果： 张波良等[1]对静态路网中的各算法进行了比较; TNR算法[2]用表查找完全替代了Dijkstra搜索, 使其加速比达100多万; 文献[3]进一步将TNR算法与边标记法相结合, 加速比提升至300多万. 但实际交通网络总在不断变化, 而忽视路网环境的变化很可能使车辆陷入交通拥挤的状态中, 因此, 在静态交通网络中获取的最短路径通常不能很好地满足人们出行的需求, 动态网络下的路径规划更具有实际意义. 交通路网中各条道路的通行时间是不断变化的, 即满足网络中弧的行走时间是时间的函数这一特性. 故交通网络是一个时间依赖网络(简称TDN网络). 谭国真等[4]将TDN网络分为先进先出(FIFO)型与非FIFO型, 并证明在FIFO型网络中可采用Dijkstra算法求解, 而非FIFO网络则不可行; 王海梅[5]通过对路网进行分析认为, 当路径寻优的对象为机动车辆时, 道路交通网络具有FIFO网络的特性.

本文针对在TDN网络中求解最短路径问题, 提出一种基于人工蜂群算法的解决方案, 相比于遗传算法[6], 该算法具有控制参数少、 易实现的特点. 同时, 根据FIFO网络的特性对算法中的路径选择策略进行改进, 进一步提升算法的执行效率.

1 问题描述……

登录APP查看全文

猜你喜欢

策略

基于“选—练—评”一体化的二轮复习策略

教学考试(高考化学)(2021年2期)2021-05-30 06:15:52

例谈未知角三角函数值的求解策略

中学生数理化(高中版.高考理化)(2020年2期)2020-04-21 05:32:50

我说你做讲策略

小学生作文(低年级适用)(2019年9期)2019-10-08 08:37:10

“我说你做”讲策略

小学生作文(低年级适用)(2018年9期)2018-10-08 02:29:48

高中数学复习的具体策略

数学大世界(2018年1期)2018-04-12 05:39:14

“唱反调”的策略

幸福(2017年18期)2018-01-03 06:34:53

价格调整 讲策略求互动

中国卫生(2016年8期)2016-11-12 13:26:50

2016年理财策略——少折腾

金色年华(2016年1期)2016-02-28 01:38:19

Passage Four

时代英语·高三(2014年5期)2014-08-26 02:49:51