基于可靠性的随机交通网络约束最优路径问题

Constrained shortest path problem in stochastic traffic network based on reliability

为了仿真交通网络中资源约束条件下的路径选择行为,建立了随机交通网络约束最优路径问题数学模型并进行求解.采用期望-方差为路径目标函数,将约束最优路径问题建模为混合非线性整数约束优化问题,构造基于线性规划的分支定界算法以求解该问题.针对Sioux Falls网络展开数值试验,将无资源约束和不同资源约束条件下的交通网络最优路径计算结果进行比较分析.试验结果表明:无资源约束和有资源约束条件下交通网络中相同起迄点之间的最优值和最优路径是不同的;在不同资源上限的约束条件下,相同起迄点之间的最优值和最优路径也是不同的,约束上限值与最优值成反比例关系.交通网络中资源约束条件对最优路径的选择具有重大影响.

To simulate the behavior of the path choice under the resource constraints in the traffic network,the mathematical model of the constrained shortest path problem in the stochastic traffic network is established and solved.The mean-variance is defined as the objective function of the path.The constrained shortest path problem is modeled as a nonlinear mixed integer constrained optimization problem and solved by the proposed branch-and-bound algorithm based on linear programming.Numerical experiments in the Sioux Falls network are carried out,and the calculation results of the constrained shortest path without resource constraint and with different resource constraints are compared and analyzed.The experimental results show that the optimal values and the shortest paths obtained without resource constraints and with resource constraints are different.The optimal values and the shortest paths obtained with different resource constraints are also different,and the upper value of the resource constraints is in inverse proportion to the optimal value.The resource constraints have a great influence on the choice of the optimal path in the traffic network.