时相关车辆路径规划问题的改进A~*算法
来源期刊:控制工程2012年第5期
论文作者:张翼 唐国金 陈磊
文章页码:750 - 1508
关键词:时相关车辆路径问题;启发式算法;威胁;时相关启发函数;
摘 要:时相关车辆路径问题是研究时变路网环境下的车辆路径优化问题。首先,分别采用阶跃函数和分段连续函数描述不同路径上的跨时段行驶速度和威胁度,将路径时间指标和路径威胁指标表示成时相关函数;其次,为提高搜索效率,对传统A*算法进行改进,在启发函数中增加了最短路径中当前结点的父结点信息,构造了包含里程指标、时间指标和威胁指标的时相关启发函数;最后,构造了包含100个结点、190条路径的车辆机动保障路网模型,通过仿真验证了该算法的有效性。
张翼,唐国金,陈磊
国防科技大学航天与材料工程学院
摘 要:时相关车辆路径问题是研究时变路网环境下的车辆路径优化问题。首先,分别采用阶跃函数和分段连续函数描述不同路径上的跨时段行驶速度和威胁度,将路径时间指标和路径威胁指标表示成时相关函数;其次,为提高搜索效率,对传统A*算法进行改进,在启发函数中增加了最短路径中当前结点的父结点信息,构造了包含里程指标、时间指标和威胁指标的时相关启发函数;最后,构造了包含100个结点、190条路径的车辆机动保障路网模型,通过仿真验证了该算法的有效性。
关键词:时相关车辆路径问题;启发式算法;威胁;时相关启发函数;