Algorithm implementation and comparative analysis of the bi-criteria shortest path problem
The continuous bi-criteria shortest path(BSP)problem aims to find a path between two nodes in a road network such that the sum of the weights(e.g.,time and money)of its constituent links is minimized.Based on the heterogeneity of travelers,a continuous distribution is commonly used to characterize the value of time for travelers from the same origin-destination(OD)pair.Al-though discretizing continuous distributions uniformly and approximating each segment as a single value enable the use of classic shortest-path algorithms such as Dijkstra's algorithm,this approxima-tion in fewer discrete classes misrepresents the path choices of some travelers,whereas too many dis-crete classes greatly reduce algorithmic efficiency.Therefore,researchers have attempted to design exact algorithms to solve the continuous BSP problem.However,existing studies lack a full interpre-tation of the algorithmic steps in terms of network topology and fail to conduct thorough compari-sons of algorithmic performance.This study conducts a detailed analysis of three algorithms to solve the continuous BSP problem.First,we explain OD-and origin-based continuous BSP algorithms.We then analyze the"pivot"acceleration strategy for origin-based algorithms.The performances of the algorithms are compared and analyzed through a series of numerical experiments.The results show that the two origin-based algorithms,when combined with the"pivot"acceleration strategy,exhibit higher computational efficiency in networks of different scales,whereas the OD-based algorithm has difficulty dealing with large-scale networks.The study fully tested the three algorithms under the ef-fects of different network sizes,numbers of toll links,toll scales,and demand levels.The results show that a greater number of tolled links and toll values and more network congestion reduce the ef-ficiencies of the three algorithms.This research not only enhances the analysis of path-choice behav-ior under bi-criteria settings but also lays the foundation for addressing optimization problems such as multi-class multi-criteria network equilibrium and multi-objective network optimization.
国家科技期刊平台
NSTL
万方数据
