BDD 数据建模的路径规划算法

摘要：

针对道路交通状态高动态性和不确定性的路径规划问题，提出一种基于 BDD 建模的启发式初始路径规划、增量重规划算法与 A*搜索算法。首先利用基于 BDD 的启发式搜索进行全局规划，求解路网中车辆的最优路径集。基于 BDD 的启发式搜索利用 BDD 这一紧凑的数据结构来表示迁移状态空间，又通过启发信息进一步压缩搜索空间的大小；当路网信息发生变化时，按不同拥堵状况分类进行 BDD 迁移关系的修改，并进行增量重规划，重新获得当前状态至目标状态的最优路径集。仿真实验结果表明：基于 BDD 的启发式搜索和增量重规划，在求解路网信息动态不确定性下的车辆路径规划问题上具有高效性和实用性，避免了交通路网长时间陷入拥堵状态。

关键词：动态不确定环境、车辆路径规划、基于 BDD 的启发式搜索、增量重规划

分类号：TP491

资助基金：国际合作重大专项2010DFB90460;国家自然科学基金项目61363077;江西省青年科学基金项目20122BAB211037．

在线出版日期：2015-05-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：67-72