基于路径的Logit型随机用户均衡模型求解算法研究

发布时间：2018-08-31 12:27

【摘要】：Logit型随机用户均衡模型由于具有结构简单,可解释性强等特点,在交通规划中有着广泛的应用,一直是人们研究的热点。本文运用非线性规划理论,以城市交通网络为背景,研究基于路径的Logit型随机用户均衡模型的求解算法。梯度投影算法是目前求解该模型最有效的算法。为了更高效地求解Logit型随机用户均衡模型,本文提出了4种新算法,具体的研究内容和取得的结果如下：(1)提出了双层部分线性化算法。该算法包括内外两层迭代：外层迭代运用二阶形式的部分线性化算法,生成一个线性约束条件下的熵最大问题；内层迭代运用一阶形式的部分线性化算法近似求解该子问题。根据内外层迭代子问题的不同特点,选取不同的步长准则,可有效提高算法的计算效率。(2)提出了对偶算法。该算法将Logit型随机用户均衡模型转化为其对偶问题,再应用变尺度最速上升算法进行求解。(3)提出了改进的截断牛顿算法。该算法通过不精确求解既约牛顿方程得出搜索方向,再运用Armijo准则,生成迭代步长。在迭代过程中,既约变量是可以动态变化的。(4)指出传统的Steihaug-Toint算法并不适合求解基于路径的Logit型随机用户均衡模型,并提出了一种改进的信赖域牛顿算法。该算法的搜索方向与试探步长是一先一后确定的,而不是同时确定的,因此能够克服传统Steihaug-Toint算法的缺点。本文详细论证了新算法的收敛性和收敛速度,并将4种新算法分别同梯度投影算法进行对比。计算结果表明,4种新算法各有特点,但均能在某些方面优于梯度投影算法。因此,本文为Logit型随机用户均衡模型的求解提供了新的思路与途径,研究结果具有一定理论价值和实践意义。
[Abstract]:Because of its simple structure and strong interpretability, Logit stochastic user equilibrium model has been widely used in traffic planning and has been a hot research topic. In this paper, using nonlinear programming theory and taking urban traffic network as the background, we study the algorithm of solving Logit stochastic user equilibrium model based on path. Gradient projection algorithm is the most effective algorithm to solve this model. In order to solve the stochastic user equilibrium model of Logit type more efficiently, four new algorithms are proposed in this paper. The specific research contents and the results obtained are as follows: (1) A bilevel partial linearization algorithm is proposed. The algorithm consists of two layers: the outer iteration uses a second-order partial linearization algorithm to generate a maximum entropy problem under linear constraints, and the inner iteration uses a first-order partial linearization algorithm to approximate solve the sub-problem. According to the different characteristics of the inner and outer layer iterative subproblems, different step size criteria can effectively improve the computational efficiency of the algorithm. (2) A dual algorithm is proposed. The algorithm transforms the Logit stochastic user equilibrium model into its dual problem, and then uses the variable scale steepest rise algorithm to solve the problem. (3) an improved truncated Newton algorithm is proposed. The search direction is obtained by solving the irreducible Newton equation inaccurately, and the iterative step size is generated by using the Armijo criterion. In the iterative process, the reduced variables can change dynamically. (4) it is pointed out that the traditional Steihaug-Toint algorithm is not suitable for solving the path-based Logit stochastic user equilibrium model, and an improved trust region Newton algorithm is proposed. The search direction and the trial step size of the algorithm are determined one by one, not at the same time, so it can overcome the shortcomings of the traditional Steihaug-Toint algorithm. In this paper, the convergence and convergence rate of the new algorithm are discussed in detail, and the four new algorithms are compared with the gradient projection algorithm. The results show that the four new algorithms have their own characteristics, but all of them are superior to the gradient projection algorithm in some aspects. Therefore, this paper provides a new idea and approach for the solution of Logit stochastic user equilibrium model, and the research results have certain theoretical value and practical significance.
【学位授予单位】：东南大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：U491.12

【相似文献】