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

doi:10.3778/j.issn.1002-8331.2009-0380

Abstract

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）, 台风动态环境

HU Xiaobing, MENG Xiangzhi. Many-to-Many Path Planning Method for Material Distribution Under Dynamic Disaster Environment[J]. Computer Engineering and Applications, 2022, 58(8): 297-306.

胡小兵, 孟相至. 动态灾害环境下多对多物资配送路径规划方法[J]. 计算机工程与应用, 2022, 58(8): 297-306.

References

[1] 史培军，王季薇，张钢锋，等.透视中国自然灾害区域分异规律与区划研究[J].地理研究，2017，36（8）：1401-1414.
SHI P J，WANG J W，ZHANG G F，et al.Perspective on the regional differentiation of natural disasters in China and research on regionalization[J].Geographical Research，2017，36（8）：1401-1414.
[2] JI S，YANG L.An extension of dynamic programming algorithm in robotic path planning[C]//International Conference on Computer Science and Service System，2012：1709-1712.
[3] NAYL T，MOHAMMED M Q，MUHAMED S Q，et al.Obstacles avoidance for an articulated robot using modified smooth path planning[C]//International Conference on Control and Automation，2017：185-189.
[4] DIB O，MANIER M，CAMINADA A，et al.Memetic algorithm for computing shortest paths in multimodal transportation networks[J].Transportation Research Procedia，2015：745-755.
[5] SHAO S，PENG Y，HE C，et al.Efficient path planning for UAV formation via comprehensively improved particle swarm optimization[J].ISA Transactions，2020，97：415-430.
[6] 马炫，刘栋，胡家鑫.求解必经点[k]条最优路径问题的粒子群优化算法[J].计算机工程与应用，2019，55（20）：89-94.
MA X，LIU D，HU J X.Particle swarm optimization algorithm for solving [k] optimal path problems[J].Computer Engineering and Applications，2019，55（20）：89-94.
[7] QU H，XING K，ALEXANDER T.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing，2013：509-517.
[8] XIONG C，CHEN D，LU D，et al.Path planning of multiple autonomous marine vehicles for adaptive sampling using Voronoi-based ant colony optimization[J].Robotics and Autonomous Systems，2019：90-103.
[9] XU H，SOARES C G.Vector field path following for surface marine vessel and parameter identification based on LS-SVM[J].Ocean Engineering，2016：151-161.
[10] 程志，张志安，李金芝，等.改进人工势场法的移动机器人路径规划[J].计算机工程与应用，2019，55（23）：29-34.
CHENG Z，ZHANG Z A，LI J Z，et al.Mobile robot path planning based on improved artificial potential field method[J].Computer Engineering and Applications，2019，55（23）：29-34.
[11] HU X，ZHANG M，ZHANG Q，et al.Co-evolutionary path optimization by ripple-spreading algorithm[J].Transportation Research Part B-Methodological，2017：411-432.
[12] TAOKA S，TAKAFUJI D，IGUCHI T，et al.Performance comparison of algorithms for the dynamic shortest path problem[J].IEICE Transactions on Fundamentals of Electronics，Communications and Computer Sciences，2007，90（4）：847-856.
[13] BAUER R，WAGNER D.Batch dynamic single-source shortest-path algorithms：an experimental study[C]//International Symposium on Experimental Algorithms.Berlin，Heidelberg：Springer，2009：51-62.
[14] 张明空，胡小兵，王静爱.考虑火灾动态扩散过程的高层建筑疏散路径研究[J].中国安全科学学报，2019，29（3）：32-38.
ZHANG M K，HU X B，WANG J A.Research on the evacuation path of high-rise buildings considering the dynamic fire diffusion process[J].Chinese Safety Science Journal，2019，29（3）：32-38.
[15] HU X B，WANG M，LEESON M S，et al.Deterministic agent-based path optimization by mimicking the spreading of ripples[J].Evolutionary computation，2016，24（2）：319-346.
[16] 郑桥.浙江近海典型台风浪和寒潮浪的精细化数值模拟[D].杭州：浙江大学，2019.
ZHENG Q.Refined numerical simulation of typical typhoon waves and cold waves in the coastal waters of Zhejiang[D].Hangzhou：Zhejiang University，2019.
[17] 丁琪，贺亚茹，符瑜.基于突发事件下的海南食品应急物流储备管理对策研究[J].物流科技，2018，41（1）：42-43.
DING Q，HE Y R，FU Y.Research on the countermeasures of Hainan food emergency logistics reserve management based on emergencies[J].Logistics Technology，2018，41（1）：42-43.
[18] 刘大伟.基于全路径模型的台风极值风速预测[D].合肥：合肥工业大学，2019.
LIU D W.Typhoon extreme wind speed prediction based on full path model[D].Hefei：Hefei University of Technology，2019.
[19] 薛霖.我国沿海台风大风及其风工程参数特性研究[D].北京：中国气象科学研究院，2018.
XUE L.Study on the characteristics of typhoon and wind engineering parameters along the coast of my country[D].Beijing：Chinese Academy of Meteorological Sciences，2018.
[20] 刘煜麟.基于经验参数模型的台风数值模拟及其基本设计风速推算[D].成都：西南交通大学，2017.
LIU Y L.Numerical simulation of typhoon based on empirical parameter model and calculation of basic design wind speed[D].Chengdu：Southwest Jiaotong University，2017.