双准则最短路径问题的算法实现与对比分析  

Algorithm implementation and comparative analysis of the bi-criteria shortest path problem

作　　者：李辉 谢军 王倩妮 陈心宇 LI Hui;XIE Jun;WANG Qianni;CHEN Xinyu(School of Transportation and Logistics,Southwest Jiaotong University,Chengdu 610031,China;Department of Civil and Environmental Engineering,Northwestern University,Illinois 60208,USA)

机构地区：[1]西南交通大学,交通运输与物流学院,成都611756 [2]西北大学(埃文斯顿),土木与环境工程系,伊利诺伊州60208

出　　处：《交通运输工程与信息学报》2024年第4期96-112,共17页Journal of Transportation Engineering and Information

基　　金：国家自然科学基金面上项目(72371205)。

摘　　要：双准则最短路径问题旨在寻找路网两节点间所含路段总权重最小化的路径,其中路段权重需综合考虑如时间、金钱在内的两种准则。考虑出行者的异质性假设,研究中通常采用一个连续分布刻画同一起讫点(origin-destination,OD)出行者的时间价值。尽管将连续分布均等离散化并将每个分段近似成单一值后可以使用如Dijkstra算法等标准最短路径算法求解,但较少离散类别下这种近似处理致使部分出行者的路径选择被错误刻画,而过多的离散类别又会大大降低算法效率。因此,研究者们致力于精确求解连续双准则最短路径问题。但现有研究在算法的网络拓扑解释方面仍有欠缺,对不同算法性能的比较也较为缺乏。本文详细分析了连续双准则最短路径问题的三种求解算法,首先阐述了基于OD对和基于起点两类双准则最短路径算法的原理以及实现步骤,进一步分析基于起点的“转轴”加速策略。通过一系列数值实验分析测试算法性能,结果表明,基于起点的算法配合“转轴”加速策略在不同规模的测试网络中均展现出较高的计算效率,而基于OD对的算法在大型网络中表现较差。此外,本文还在网络规模、收费路段数量、收费尺度、需求水平等维度全面测试了三种算法,并分析不同要素对算法性能的影响。结果显示,收费增加和网络拥挤均会在一定程度上降低三种算法的求解效率。本研究不仅有助于加深对双准则路径选择行为的理解,还为解决多用户多准则网络均衡、多目标网络优化等复杂优化问题奠定了基础。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.Although 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 approximation in fewer discrete classes misrepresents the path choices of some travelers,whereas too many discrete 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 interpretation of the algorithmic steps in terms of network topology and fail to conduct thorough comparisons 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 effects 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 efficiencies of the three algorithms.This research not only enhances the analysis of path-choice behavior under bi-criteria settings but also lays the foundation for addressing optimization prob

关 键 词：城市交通 双准则最短路径问题 连续分布 路径选择 用户异质性 

分 类 号：U121[交通运输工程] U116.2