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

双准则最短路径问题旨在寻找路网两节点间所含路段总权重最小化的路径,其中路段权重需综合考虑如时间、金钱在内的两种准则。考虑出行者的异质性假设,研究中通常采用一个连续分布刻画同一起讫点(origin-destination,OD)出行者的时间价值。尽管将连续分布均等离散化并将每个分段近似成单一值后可以使用如Dijkstra算法等标准最短路径算法求解,但较少离散类别下这种近似处理致使部分出行者的路径选择被错误刻画,而过多的离散类别又会大大降低算法效率。因此,研究者们致力于精确求解连续双准则最短路径问题。但现有研究在算法的网络拓扑解释方面仍有欠缺,对不同算法性能的比较也较为缺乏。本文详细分析了连续双准则最短路径问题的三种求解算法,首先阐述了基于OD对和基于起点两类双准则最短路径算法的原理以及实现步骤,进一步分析基于起点的“转轴”加速策略。通过一系列数值实验分析测试算法性能,结果表明,基于起点的算法配合“转轴”加速策略在不同规模的测试网络中均展现出较高的计算效率,而基于OD对的算法在大型网络中表现较差。此外,本文还在网络规模、收费路段数量、收费尺度、需求水平等维度全面测试了三种算法,并分析不同要素对算法性能的影响。结果显示,收费增加和网络拥挤均会在一定程度上降低三种算法的求解效率。本研究不仅有助于加深对双准则路径选择行为的理解,还为解决多用户多准则网络均衡、多目标网络优化等复杂优化问题奠定了基础。