交通运输工程与信息学报2024，Vol.22Issue(4)：96-112,17.DOI:10.19961/j.cnki.1672-4747.2024.04.026
双准则最短路径问题的算法实现与对比分析
Algorithm implementation and comparative analysis of the bi-criteria shortest path problem
摘要
Abstract
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.关键词
城市交通/双准则最短路径问题/连续分布/路径选择/用户异质性Key words
urban traffic/bicriteria shortest path problem/continuous distribution/route choice/user heterogeneity分类
交通工程引用本文复制引用
李辉,谢军,王倩妮,陈心宇..双准则最短路径问题的算法实现与对比分析[J].交通运输工程与信息学报,2024,22(4):96-112,17.基金项目
国家自然科学基金面上项目(72371205) （72371205）
