Computer Engineering and Applications ›› 2022, Vol. 58 ›› Issue (8): 297-306.DOI: 10.3778/j.issn.1002-8331.2009-0380

• Engineering and Applications • Previous Articles     Next Articles

Many-to-Many Path Planning Method for Material Distribution Under Dynamic Disaster Environment

HU Xiaobing, MENG Xiangzhi   

  1. 1.College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
    2.Sino-European Institute of Aviation Engineering, Civil Aviation University of China, Tianjin 300300, China
  • Online:2022-04-15 Published:2022-04-15

动态灾害环境下多对多物资配送路径规划方法

胡小兵,孟相至   

  1. 1.中国民航大学 电子信息与自动化学院,天津 300300
    2.中国民航大学 中欧航空工程师学院,天津 300300

Abstract: Under the dynamic disaster environment, the route planning problem of many-to-many materials distribution has great practical significance. It needs to deal with the change of road network environment with time while planning the path, find the optimal correspondence between different materials reserve sites and residential areas, and guarantee the timeliness and success rate of solution. The current static plan optimization(SPO) and dynamic path optimization(DPO) method is difficult to ensure the theoretical optimality of the solution effect in the dynamic disaster environment, and may even lead to the failure of some residential areas to obtain the distribution of materials in time. By modifying the method of co-evolutionary path optimization(CEPO) based on ripple spreading algorithm(RSA), it extended to solve the many-to-many problem in the dynamic disaster environment, so as to obtain the theoretical optimal solution of the many-to-many path optimization problem in the dynamic environment through a single off-line operation. The feasibility and superiority of the method are verified by experiments.

Key words: path planning, co-evolutionary path optimization(CEPO), ripple spreading algorithm(RSA), typhoon dynamic environment

摘要: 动态灾害环境下多对多物资配送路径规划问题具有重大的现实意义,它需要在路径规划的同时应对路网环境随时间的变化,并找到不同应急物资储备点、配送点之间的最佳对应关系,同时保证求解的时效性和成功率。目前的静态预案规划方法(SPO)和动态路径规划方法(DPO)难以确保动态灾害环境下求解效果的理论最优性,甚至可能导致部分配送点不能及时获得应急物质的配送。通过对基于涟漪扩散算法(RSA)的协同进化路径优化(CEPO)方法的修改将其扩展到动态灾害环境下多对多问题的求解,实现通过一次离线运算得到动态灾害环境下多对多路径优化问题的理论最优解。并通过实验验证了该方法的可行性和优越性。

关键词: 路径规划, 协同进化路径优化方法(CEPO), 涟漪扩散算法(RSA), 台风动态环境