考虑鲁棒成本与绝对后悔的最短路径问题研究

为克服鲁棒偏差方法在处理区间路网时所求鲁棒最短路径的保守性问题,通过分析鲁棒成本的定义以及鲁棒最短路径过于保守的原因,结合算例分析提出了绝对后悔值的概念,并以鲁棒成本和绝对后悔值为目标函数建立了区间路网的多目标最短路径模型;根据最短路径模型的特点设计了分离路径决策变量与连续变量的Benders分解算法,同时基于传统有效路径的判断依据重新定义了符合该最短路径模型的有效路径,并在分解后的主问题模型中引入了有效路径约束以加快算法收敛速度;利用MATLAB生成了一个包含29个节点、70条双向通行路段的区间路网对模型与算法进行仿真测试。结果表明:考虑鲁棒成本和绝对后悔值的最短路径模型能在区间路网中找到不保守,且同时兼具鲁棒性的最短路径,能够有效克服鲁棒偏差方法的缺陷。

基于Benders分解的鲁棒最短路算法

为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型。通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型。在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解。并在一个仿真网络中对本研究方法进行了验证分析。研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解。

区间阻抗下基于可接受度的鲁棒最短路

为了研究鲁棒最短路问题,引入了可接受程度系数,同时提出了鲁棒有效路径的概念。在此基础上建立了区间阻抗下基于可接受度的鲁棒最短路模型,然后根据模型设计出一种基于鲁棒有效路径的深度优先算法进行求解,并对算法判定条件的相关定理给予了证明。最后通过一个算例对本研究所提出的模型及算法进行了验证,结果有效合理。

健壮性通信网络的抗毁性

以全连通网络为参考标准,以最短路径数为评价指标,建立健壮性通信网络的抗毁性模型,利用MATLAB提出一种新的计算最短路径数的方法,通过实例进行计算,得出网络的抗毁性。研究发现,拓扑结构越对称,健壮性通信网络的抗毁性越好。

区间不确定阻抗下的可靠最短路径

将最短路径问题与区间分析方法结合起来,采用区间值衡量路段阻抗,并将阻抗下界值作为路段非延误状态下的阻抗,阻抗上界值与下界值的差作为路段阻抗的最大延误,建立了区间不确定阻抗下的可靠最短路径模型。将阻抗的上界值、下界值以及二者之差作为参数,采用超星算法,求解可靠最短路径模型,得到超路径集合和多条可靠最短路径。通过求解可靠最短路径的实例,验证了本研究所提出的模型及其算法的合理性和有效性。

基于区间交叉熵的鲁棒最短路模型和算法研究

由于交通需求是区间数,路段阻抗也必然是区间数,这导致区间阻抗下的鲁棒最短路成为研究的核心问题。文章运用行为经济学的参照系理论,分别用下界与上界为阻抗,计算得到区间最短路,以此为参照,考虑最坏情形,构造鲁棒有效路径的两个判断标准,得到有效路径集合;运用交叉熵理论,计算有效路径与参照区间最短路的交叉熵,构建基于最小交叉熵的鲁棒最短路模型。

区间阻抗下的鲁棒最短路算法

交通需求一旦发生变化,交通路网中的路段阻抗也会呈现显著的不确定性,而现行的最短路求解方法缺乏鲁棒性。为了增强最短路方法的鲁棒性,引入区间型数据的路网阻抗,同时结合鲁棒离散优化与情景分析法,给出鲁棒成本的定义。建立了区间阻抗下的鲁棒最短路模型,接下来基于模型设计了分支定界算法,并就算法的判定条件给出3个定理,最后对一个大型路网进行了仿真测试。结果表明:相对于现行的最短路方法,该方法求解得到的最短路径具有更强的鲁棒性,且求解结果准确高效。