Research on Path Optimization Algorithm in Dynamic Routing Environment

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

Abstract

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

CLC Number:

TP391.1

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.

Figures/Tables 11

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Table 2

Table 3

Table 4

Fig. 5

Fig. 6

Fig. 7

References 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]	Bao Zhe, Li Wei, Zhang Xiaofang, An Zongyuan, Xu Ye. Study on Robust Chance Constrained Optimization of Multi-energy Supply System Based on Wind and Solar Power Combined Output Simulation [J]. Journal of System Simulation, 2024, 36(8): 1895-1913.
[2]	Huang Zhifeng, Liu Yuanhua. UAV Path Planning Based on Improved Harris Hawk Algorithm and B-spline Curve [J]. Journal of System Simulation, 2024, 36(7): 1509-1524.
[3]	Shui Jijun, Peng Daogang, Song Yankan, Zhou Qiang. Optimal Scheduling Strategy of Virtual Power Plant with Carbon Emission and Carbon Penalty Considering Uncertainty of Wind Power and Photovoltaic Power [J]. Journal of System Simulation, 2024, 36(2): 305-319.
[4]	Li Zhang, Mingling He, Qiushuang Yin, Ning Li, Le'an Yu. Research on Period Emergency Supply Distribution Optimization Under Uncertainty [J]. Journal of System Simulation, 2023, 35(8): 1669-1680.
[5]	Hailan Yang, Yongqiang Qi, Baolei Wu, Dan Rong, Miaoying Hong, Jun Wang. Path Planning of Mobile Robots Based on Memristor Reinforcement Learning in Dynamic Environment [J]. Journal of System Simulation, 2023, 35(7): 1619-1633.
[6]	Yaqian Fan, Songyuan Yu, Fang Fang. Two-Stage Distributed Robust Optimal Dispatching for a Combined Heat and Power Virtual Power Plant [J]. Journal of System Simulation, 2023, 35(5): 1046-1058.
[7]	Zhaopeng Liu, Xinhai Xu, Bowen Yuan, Jinlu Zhang. A Multi-resolution Simulation Modeling Method [J]. Journal of System Simulation, 2023, 35(1): 202-211.
[8]	Wanjie Hu, Jianjun Dong, Rui Ren, Zhilong Chen. Layout Planning of Metro-based Underground Logistics System Network Considering Fuzzy Uncertainties [J]. Journal of System Simulation, 2022, 34(8): 1725-1740.
[9]	Jiangtao Liang, Huiqin Wang. Study on Building Fire Evacuation Path Planning Based on Improved Ant Colony Algorithm [J]. Journal of System Simulation, 2022, 34(5): 1044-1053.
[10]	Nie Kai, Zeng Kejun, Meng Qinghai. Uncertainty Simulation Method Based on Deep Bayesian Networks Learning [J]. Journal of System Simulation, 2022, 34(1): 79-85.
[11]	Dai Xuezhi, Xiong Weili. Active Learning Intelligent Soft Sensor based on Probability Selection [J]. Journal of System Simulation, 2021, 33(6): 1350-1357.
[12]	Meng Yangkai, Wang Zheng, Fan Jiali. Scheduling Optimization Research Based on Tabu Algorithm for Uncertainty Carrier Aircraft Support [J]. Journal of System Simulation, 2021, 33(10): 2363-2371.
[13]	Fan Shuangnan, Chen Jiming, Gao Weimin, Wang Zengfeng. Dynamic Vehicle Distribution Path Optimization Based on Improved Intelligent Water Drop Algorithm [J]. Journal of System Simulation, 2020, 32(9): 1808-1817.
[14]	Wei Le, Li Xijin. Dynamic Environmental and Economic Dispatching of Wind Farm Based on Multi-objective [J]. Journal of System Simulation, 2020, 32(9): 1825-1830.
[15]	Shao Lulu, Han Jihong, Niu Kan, Liu Xiaohu, Shao Fang. Research on Failure Modes Analysis Based on Weighted Evidence Theory [J]. Journal of System Simulation, 2020, 32(5): 782-791.