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

Shortest Path Problem Considering Robust Cost and Absolute Regret

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

In order to overcome the conservativeness problem of the robust shortest path obtained by the robust deviation method when dealing with the interval road network,the concept of absolute regret value was proposed by combing with the case study through analyzing the definition of robust cost and the reasons why the robust shortest path was too conservative.And the multi-objective shortest path model of the interval road network was established with the robust cost and absolute regret value as the objective function.According to the characteristics of the shortest path model,the Benders decomposition algorithm that separated the path decision variable and the continuous variable was designed,meanwhile,the effective path conforming to the proposed shortest path model was redefined on the basis of the judgment criteria of the traditional effective path.Furhthermore,the effective path constraint was introduced into the decomposed main problem model to accelerate the convergence speed of the algorithm.MATLAB was used to generate an interval road network with 29 nodes and 70 two-way traffic sections,and the proposed model and algorithm were simulated and tested.The results show that the shortest path model considering the robust cost and absolute regret value can find the shortest path that is not conservative and is robust at the same time in the interval road network and can effectively overcome the shortcomings of the robust deviation method.