A dynamic ripple-spreading algorithm for solving mean–variance of shortest path model in uncertain random networks. (February 2023)

• Record Type: Journal Article
• Authors: Jie, Ke-Wei; Liu, San-Yang; Sun, Xiao-Jun; Xu, Yun-Cheng
• Is Part Of: Chaos, solitons and fractals. Volume 167(2023)
• Publication Date: 2023-02
• Subjects: Shortest path problem -- Mean–variance -- Dynamic ripple-spreading algorithm -- Hybrid prediction algorithm -- Pareto optimal path; Chaotic behavior in systems -- Periodicals; Solitons -- Periodicals; Fractals -- Periodicals; Chaotic behavior in systems; Fractals; Solitons; Periodicals; 003.7
• DOI: 10.1016/j.chaos.2022.113081
• Languages: English
• ISSNs: 0960-0779

Abstract

Abstract: Combinatorial optimization involves more and more evaluation indicators, and some parameters cannot be accurately described. This paper considers a shortest path problem where arc costs include both uncertainty and randomness, and the decision-maker wishes to minimize both the expected cost and the variance of this cost. Firstly, a mean–variance model for the shortest path problem with uncertain arc cost and random arc cost is proposed, and the equivalent deterministic model of the model is deduced. Secondly, we develop a dynamic ripple spreading algorithm ( DRSA ) to solve the model, based on the ripple spreading patterns on the natural water surface. Then, the ripple spreading speed of the algorithm is simulated and predicted by hybrid prediction algorithm ( HPA ) on the basis of obtaining real urban traffic data, and it is verified by theoretical proof that DRSA can find the Pareto optimal path from the source node to the destination node within a single run. Finally, the proposed mean–variance shortest path problem model and DRSA are verified by numerical experiments. Highlights: A mean–variance model for the shortest path problem with uncertain arc cost and random arc cost is proposed. A dynamic ripple spreading algorithm ( DRSA ) is proposed to solve the problem. The ripple spreading speed of DRSA is simulated and predicted by hybrid prediction algorithm on the basis of obtaining real urban traffic data. The complexity of dynamic algorithm is analyzed. Experimental results demonstrate the superiority of our proposed approach.