动态路网环境下的路径优化算法研究

Research on Path Optimization Algorithm in Dynamic Routing Environment

为解决真实动态路网环境下,静态路径优化(static path optimization,SPO)方法和传统动态路径优化(dynamic path optimization,DPO)方法由于频繁实时优化计算,规划路径过程中容易出现绕路、折返、计算复杂度高等问题,提出基于涟漪扩散算法(ripple-spreading algorithm,RSA)的重启协同进化路径优化(restart co-evolutionary path optimization,RCEPO)方法。将路径优化过程与路网环境的动态变化过程相结合,提升了路径优化效果。仅当路网环境的动态变化超出预测范围时才进行路径的重新优化计算,降低了计算复杂度。实验结果表明:在动态路网环境下,该方法的实际行进轨迹长度和行进时间相较于传统DPO方法分别缩短了17%和12%。有效解决了真实动态路网环境下路径优化问题。并且通过机器狗实验,验证了该方法的实用性和有效性。

In a real dynamic routing environment,static path optimization(SPO)and traditional dynamic path optimization(DPO)tend to encounter issues such as detours,reversals and high computational complexity due to frequent real-time optimization calculation.To address these problems,a novel restart co-evolutionary path optimization(RCEPO)method based on the ripple-spreading algorithm(RSA)is proposed.This method integrates the path optimization process with the dynamic changes of the routing network environment to enhance the effectiveness of path optimization.Moreover,the path reoptimization calculation is performed only when the dynamic changes in the routing environment exceed the predicted range,thereby reducing computational complexity.Experimental results demonstrate that the actual travel path length and the actual travel time of this method are shortened by 17%and 12%,respectively,compared with the traditional DPO method under the dynamic routing network environment.It can effectively solve the path optimization problem under the real dynamic routing network environment.The feasibility and effectiveness of this approach are validated through experiments conducted with a robot dog.