基于弧长均值和方差的集装箱站场排队网络最短路问题研究

集装箱站场排队网络属于随机的动态服务系统,顾客从网络的起点进入一直到终点离开该系统的时间长短则反映集装箱站场的服务水平.为使顾客在这一过程花费的时间最短,根据稳态条件下的排队系统理论,结合多准则最短路问题,提出了一种基于弧长均值和方差的双准则最短路算法,并通过算例证明了该算法的可行性.文中提到的方法还适用于寻找随机路径问题中从起点到终点的最短路.

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

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