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

doi:10.16182/j.issn1004731x.joss.23-0779

摘要/Abstract

摘要：

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

关键词: 路径优化, 动态环境, 协同进化, 涟漪扩散算法：不确定性

Abstract:

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 re-optimization 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.

Key words: path optimization, co-evolutionary, dynamic environment, ripple-spreading algorithm, uncertainty

中图分类号:

TP391.1

解鑫,胡小兵,周航 . 动态路网环境下的路径优化算法研究[J]. 系统仿真学报, 2024, 36(8): 1969-1981.

Xie Xin,Hu Xiaobing,Zhou Hang . Research on Path Optimization Algorithm in Dynamic Routing Environment[J]. Journal of System Simulation, 2024, 36(8): 1969-1981.

图/表 11

图1

图2

图3

图4

表1

表2

表3

表4

图5

图6

图7

参考文献 20

1	Sapundzhi F I, Popstoilov M S. Optimization Algorithms for Finding the Shortest Paths[J]. Bulgarian Chemical Communications, 2018, 50(SB): 115-120.
2	张渝彬, 徐飞. 城市生鲜冷链物流配送中心选址与路径优化问题研究现状分析[J]. 中国储运, 2022(10): 97-98.
3	Adzhar Noraziah, Yusof Yuhani, Muhammad Azrin Ahmad. A Review on Autonomous Mobile Robot Path Planning Algorithms[J]. Advances in Science, Technology and Engineering Systems Journal, 2020, 5(3): 236-240.
4	陈晓明, 李引珍, 沈强, 等. 基于双层复杂网络的城市交通网络协同优化方法[J]. 计算机应用, 2019, 39(10): 3079-3087.
	Chen Xiaoming, Li Yinzhen, Shen Qiang, et al. Urban Traffic Networks Collaborative Optimization Method Based on Two-layered Complex Networks[J]. Journal of Computer Applications, 2019, 39(10): 3079-3087.
5	Teleweck P E, Chandrasekaran B. Path Planning Algorithms and Their Use in Robotic Navigation Systems[J]. Journal of Physics: Conference Series, 2019, 1207(1): 012018.
6	Ju Chunyu, Luo Qinghua, Yan Xiaozhen. Path Planning Using an Improved A-star Algorithm[C]//2020 11th International Conference on Prognostics and System Health Management (PHM-2020 Jinan). Piscataway: IEEE, 2020: 23-26.
7	Javaid M A. Understanding Dijkstra's Algorithm[J]. SSRN Electronic Journal, 2013.
8	李全勇, 李波, 张瑞, 等. 基于改进Dijkstra算法的AGV路径规划研究[J]. 机械工程与自动化, 2021(1): 23-25, 28.
	Li Quanyong, Li Bo, Zhang Rui, et al. Research on AGV Path Planning Based on Improved Dijkstra Algorithm[J]. Mechanical Engineering & Automation, 2021(1): 23-25, 28.
9	Goyal Abhishek, Mogha Prateek, Luthra Rishabh, et al. Path Finding: A^*or Dijkstra's?[J]. International Journal in IT and Engineering, 2014, 2(1): 1-15.
10	Kim Sungkwan, Jin Hojun, Seo Minah, et al. Optimal Path Planning of Automated Guided Vehicle Using Dijkstra Algorithm Under Dynamic Conditions[C]//2019 7th International Conference on Robot Intelligence Technology and Applications (RiTA). Piscataway: IEEE, 2019: 231-236.
11	刘建美, 马寿峰, 马帅奇. 基于改进的Dijkstra算法的动态最短路计算方法[J]. 系统工程理论与实践, 2011, 31(6): 1153-1157.
	Liu Jianmei, Ma Shoufeng, Ma Shuaiqi. Computation Method of the Dynamic Shortest Path Based on Improved-Dijkstra Algorithm[J]. Systems Engineering-Theory & Practice, 2011, 31(6): 1153-1157.
12	Kadry Seifedine, Alferov Gennady, Fedorov Viktor, et al. Path Optimization for D-star Algorithm Modification[J]. AIP Conference Proceedings, 2022, 2425(1): 080002.
13	Segato Alice, Marco Di Marzo, Zucchelli Sara, et al. Inverse Reinforcement Learning Intra-operative Path Planning for Steerable Needle[J]. IEEE Transactions on Biomedical Engineering, 2022, 69(6): 1995-2005.
14	Chen Biyu, H K Lam William, Sumalee Agachai, et al. Reliable Shortest Path Problems in Stochastic Time-dependent Networks[J]. Journal of Intelligent Transportation Systems, 2014, 18(2): 177-189.
15	Yamín Daniel, Medaglia Andrés L, Prakash A A. Exact Bidirectional Algorithm for the Least Expected Travel-time Path Problem on Stochastic and Time-dependent Networks[J]. Computers & Operations Research, 2022, 141: 105671.
16	Arun Prakash A. Algorithms for Most Reliable Routes on Stochastic and Time-dependent Networks[J]. Transportation Research Part B: Methodological, 2020, 138: 202-220.
17	López David, Lozano Angélica. Shortest Hyperpaths in a Multimodal Hypergraph with Real-time Information on some Transit Lines[J]. Transportation Research Part A: Policy and Practice, 2020, 137: 541-559.
18	Hu Xiaobing, Wang Ming, Leeson M S, et al. Deterministic Agent-based Path Optimization by Mimicking the Spreading of Ripples[J]. Evolutionary Computation, 2016, 24(2): 319-346.
19	Hu Xiaobing, Zhang Mingkong, Zhang Qi, et al. Co-evolutionary Path Optimization by Ripple-spreading Algorithm[J]. Transportation Research Part B: Methodological, 2017, 106: 411-432.
20	Zhang Jing, Wu Jun, Shen Xiao, et al. Autonomous Land Vehicle Path Planning Algorithm Based on Improved Heuristic Function of A-star[J]. International Journal of Advanced Robotic Systems, 2021, 18(5): 17298814211042730.

N_o	指标	DPO	CEPO	NRCEPO	RCEPO
100	CT/s	1.955	0.018	0.017	0.031
	PL/m	156.32	135.20	137.24	137.55
	TT/s	30.21	25.66	28.29	26.20
	σTT	1.90	1.55	1.81	1.57
225	CT/s	2.78	0.06	0.06	0.15
	PL/m	261.19	220.43	221.43	223.57
	TT/s	42.86	35.40	40.58	37.55
	σTT	1.99	1.58	1.82	1.59
400	CT/s	12.19	0.15	0.14	0.43
	PL/m	350.46	278.66	282.99	279.60
	TT/s	56.25	46.95	50.13	48.13
	σTT	2.19	1.66	1.98	1.71
900	CT/s	122.30	0.48	0.51	1.59
	PL/m	485.13	400.15	412.14	411.23
	TT/s	78.25	72.64	76.45	73.22
	σTT	2.50	1.82	2.21	1.88

N_o	指标	DPO	CEPO	NRCEPO	RCEPO
100	CT/s	2.010	0.015	0.015	0.032
	PL/m	149.65	135.25	139.32	136.28
	TT/s	29.65	25.01	27.32	26.05
	σTT	1.90	1.52	1.79	1.55
225	CT/s	2.52	0.05	0.06	0.13
	PL/m	266.53	219.43	225.43	222.57
	TT/s	41.95	34.31	39.28	36.98
	σTT	2.01	1.58	1.80	1.62
400	CT/s	13.52	0.16	0.16	0.39
	PL/m	362.26	278.62	285.68	280.60
	TT/s	57.62	46.02	51.23	48.44
	σTT	2.15	1.65	2.00	1.70
900	CT/s	119.10	0.52	0.55	1.72
	PL/m	490.10	411.12	420.15	415.12
	TT/s	80.01	73.15	78.88	75.22
	σTT	2.42	1.82	2.30	1.86

N_o	指标	DPO	CEPO	NRCEPO	RCEPO
100	CT/s	1.898	0.014	0.016	0.029
	PL/m	142.26	125.26	126.26	128.68
	TT/s	28.33	23.21	26.22	25.19
	σTT	1.81	1.49	1.77	1.52
225	CT/s	2.01	0.05	0.05	0.11
	PL/m	232.91	216.43	220.43	219.59
	TT/s	39.61	33.15	36.58	34.42
	σTT	1.91	1.60	1.82	1.65
400	CT/s	10.95	0.12	0.15	0.35
	PL/m	332.15	256.20	274.33	258.36
	TT/s	54.26	42.31	46.08	43.22
	σTT	2.05	1.60	1.88	1.64
900	CT/s	110.32	0.47	0.45	1.53
	PL/m	477.15	380.22	400.15	390.15
	TT/s	76.35	70.36	75.74	71.36
	σTT	2.36	1.77	2.20	1.79

N_o	指标	DPO	CEPO	NRCEPO	RCEPO
100	CT/s	2.515	0.021	0.029	0.044
	PL/m	172.16	146.15	150.87	146.95
	TT/s	39.26	28.99	35.15	30.11
	σTT	1.97	1.58	1.88	1.62
225	CT/s	4.01	0.10	0.15	0.23
	PL/m	301.91	250.43	257.43	255.59
	TT/s	45.61	39.15	42.58	40.42
	σTT	2.11	1.65	1.99	1.72
400	CT/s	19.11	0.39	0.36	0.68
	PL/m	420.27	301.25	325.78	304.52
	TT/s	69.77	50.12	58.14	52.91
	σTT	2.45	1.79	2.15	1.88
900	CT/s	180.15	0.55	0.61	2.61
	PL/m	561.15	448.15	480.68	450.14
	TT/s	90.19	77.15	81.66	79.77
	σTT	2.81	1.77	2.30	1.89

[1]	黄志锋, 刘媛华. 基于改进哈里斯鹰和B-spline曲线的无人机路径规划研究[J]. 系统仿真学报, 2024, 36(7): 1509-1524.
[2]	王育洁, 游晓明, 刘升. 结合评估奖惩机制和邻域动态退化的协同蚁群算法[J]. 系统仿真学报, 2024, 36(6): 1475-1492.
[3]	万远鹏, 梁承姬, 王思洪, 王钰. 考虑订单替换的冷链配送-库存联合优化与仿真[J]. 系统仿真学报, 2024, 36(3): 578-594.
[4]	杨海兰, 祁永强, 吴保磊, 荣丹, 洪妙英, 王军. 动态环境下基于忆阻强化学习的移动机器人路径规划[J]. 系统仿真学报, 2023, 35(7): 1619-1633.
[5]	张腾飞, 胡蓉, 钱斌, 吕阳. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.
[6]	王旭, 季伟东, 周国辉. 基于协同博弈粒子群算法的故障指示器配置优化[J]. 系统仿真学报, 2023, 35(6): 1278-1289.
[7]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[8]	范双南, 陈纪铭, 高为民, 王增凤. 基于改进智能水滴算法的动态车辆配送路径优化[J]. 系统仿真学报, 2020, 32(9): 1808-1817.
[9]	魏乐, 李希金. 基于多目标的含风电场动态环境经济调度[J]. 系统仿真学报, 2020, 32(9): 1825-1830.
[10]	谌海云, 陈华胄, 刘强. 基于改进人工势场法的多无人机三维编队路径规划[J]. 系统仿真学报, 2020, 32(3): 414-420.
[11]	陈智勇, 刘昊. 基于信息素算法的校园物联网多路传输优化[J]. 系统仿真学报, 2019, 31(8): 1719-1726.
[12]	王恒, 徐亚星, 王振锋, 周天鹏, 田德春. 基于道路状况的生鲜农产品配送路径优化[J]. 系统仿真学报, 2019, 31(1): 126-135.
[13]	陈晖, 马亚平. 基于多级协同MOEA/D的联合火力打击目标分配方法[J]. 系统仿真学报, 2018, 30(8): 2942-2949.
[14]	周非, 刘文楠. 动态节点定位过程中锚节点的自适应移动方案[J]. 系统仿真学报, 2018, 30(5): 1885-1892.
[15]	戴月明, 王明慧, 王春, 王艳. 骨干双粒子群算法求解柔性作业车间调度问题[J]. 系统仿真学报, 2017, 29(6): 1268-1276.