﻿ 基于Groebner基的Beckmann交通平衡分配模型新解法 A New Method Based on Groebner Bases for Solving the Beckmann Traffic Equilibrium Assignment Model

Dynamical Systems and Control
Vol.05 No.03(2016), Article ID:18026,9 pages
10.12677/DSC.2016.53011

A New Method Based on Groebner Bases for Solving the Beckmann Traffic Equilibrium Assignment Model

Xianpeng Wei1, Qiuyan Zhan2, Lu Chao2

1College of Transportation, Shanghai Maritime University, Shanghai

2College of Art and Science, Shanghai Maritime University, Shanghai

Received: Jun. 26th, 2016; accepted: Jul. 16th, 2016; published: Jul. 20th, 2016

ABSTRACT

Beckmann traffic equilibrium assignment model is the basis of the study of traffic assignment problem. However, at present, the solution of Beckmann traffic equilibrium assignment model is still dependent on the F-W iterative algorithm and intelligent optimization methods, which can’t obtain the exact solution. In order to find the exact solution of the Beckmann traffic equilibrium assignment model, this paper uses the advantage of Groebner bases theory in solving multidimensional polynomial equations, transforms the Beckmann model into a polynomial equation, then introduces the new variables and mapping to make the general polynomial into monomial, and then a method for solving the traffic equilibrium assignment model of Beckmann exactly is given. Finally, an example is given to show the effectiveness of the proposed method.

Keywords:Traffic Engineering, Traffic Equilibrium Assignment, Beckmann, Groebner Bases

1上海海事大学交通运输学院，上海

2上海海事大学文理学院，上海

Beckmann交通平衡分配模型是研究交通分配问题的基础，然而目前该模型的求解主要依赖于F-W迭代算法和智能优化算法，无法求得精确解。为了寻找Beckmann交通平衡分配模型的精确解，本文借助Groebner基理论在求解多维多项式方程方面的优势，将Beckmann模型转化为多项式方程，通过引入新的变量和映射将一般多项式转化为单项式，给出了精确求解Beckmann交通平衡分配模型的方法。最后给出算例验证了该方法的有效性。

1. 引言

Groebner基理论的形成最早是在1927年，F. S. Nlacauly在全体单项式组成的集合中引入全序的概念，研究其理想的不变量。直到1965年B. Buchberger利用除法算法系统地研究了域上多元多项式环的理想生成元问题，才可以解决与理想相关的问题。从此，Groebner基的理论及其应用得到快速发展。2002年中南大学陈小松教授成功将Groebner基理论应用到求解最短路径问题中 [13] ，到2007年陈小松教授指导其学生朱玉莲将Groebner基理论应用到机场停车位优化分配中 [14] 。国外学者Serkan Hoten给出了Groebner基理论求解整数规划问题的方法 [15] 。

2. 问题的转化及Groebner基方法

(1)

(2)

。对于属于的任意表示约化的余式。则

a) 当且仅当时多项式

b) 如果并且，那么

c) 如果每个都是单项式而且，那么也是单项式。

Step1：

Step2：；计算关系序＞的Groebner基；

Step3：置，计算余式

Step4：若那么输出的指数向量，否则无解。

3. Beckmann模型和求解过程

3.1. Beckmann均衡分配模型 [2]

Beckmann均衡分配模型是Wardrop第一原理的数学描述，是研究交通分配问题的基础，具体的模型表达式见式(3)至式(5)。

3.2. 应用Groebner基理论求解过程

3.2.1. 求解思路

Beckmann模型中路段阻抗与路段中交通量有关，所以组成的路径也是不唯一的，然而Groebner基理论处理的是确定多项式的求解。所以假设每一个OD对之间的所有路径都有可能有交通量产生，当达到平衡时，所有被利用的路径具有相等而最小的阻抗，而未被利用的路径与其具有相等或更大的阻抗。

，必有，说明如果从r到s有两条及以上的径路被选中，那么他们行驶时间相等；若，必有，说明如果从r到s的径路流量等于零，那么该径路的行驶时间一

3.2.2. 求解过程

(6)

(7)

(8)

，并采用下列词典序：，就可以得到一个关于理想的Groebner基记为G。取，求关于的约化多项式，记为，如果，那么的指数向量就是所要求的模型解，否则问题无解。

4. 案例分析

4.1. 算例描述

4.2. 求解过程

Figure 1. Schematic diagram of road network

Table 2. Correspondence relation of path-link

(9)

(10)

(11)

(12)

(13)

，由定理2中的算法求得f被G约化的余式的指数向量对应目标函数的解，即。所以平衡后各个路段的流量为：。由计算结果可知，每一个OD对的所有路径中，阻抗较小的路径都分配了流量且行驶时间相等，而阻抗大的路径流量为零，满足Wardrop第一原理，所以Groebner基理论可以用于求解Beckmann模型。与W-F迭代解法和智能优化解法相比，Groebner基理论得到的解是模型的精确解，有更高的精度。然而该方法在面对大规模路网时，由于路径多，目标函数比较复杂，针对目标函数定义特定序的工作量比较大。而对于中小城市路网使用Groebner基理论的方法作交通流量分配更经济。

5. 结论与展望

Groebner基方法在求解非线性多项式方程方面具有优势，可以从任一多项式理想的一组给定生成元有效计算出另一组良好的生成元(称为Groebner基)，且有Hilbert基定理保证得到约化的Groebner基是唯一的，所以求得的解准确可靠。是求解精确解的重要方法。本文结合Groebner基理论将Beckmann模型转化为多项式方程组，给出了精确求解Beckmann模型的新方法，并结合实例验证了该方法的有效性。

A New Method Based on Groebner Bases for Solving the Beckmann Traffic Equilibrium Assignment Model[J]. 动力系统与控制, 2016, 05(03): 96-104. http://dx.doi.org/10.12677/DSC.2016.53011

1. 1. 邵春福. 交通规划原理[M]. 北京: 中国铁道出版社, 2006: 172-180.

2. 2. 刘灿齐. 现代交通规划学[M]. 北京: 人民交通出版社, 2001: 206-244.

3. 3. 董敬欣, 吴建平. 基于神经网络的交通平衡求解算法[J]. 系统仿真学报, 2005, 17(6): 1380-1383.

4. 4. Li, R.M. and Li, W. (2005) The Application of Genetic Algorithm to Dynamic Traffic Assignment. IEEE. Proceedings of Intelligent Vehicles Symposium, Las Vegas, 6-8 June 2005, 827-832.

5. 5. 陆化普, 孙煦, 吴娟. 公交专用道优化设计的双层规划模型[J]. 中国路学报, 2015, 28(2): 88-93.

6. 6. 刘强, 陆化普, 王庆云. 区域综合交通枢纽布局双层规划模型[J]. 东南大学学报(自然科学版), 2010, 40(6): 1359-1362.

7. 7. 徐勋倩, 王亚萍. 用蚂蚁算法处理固定需求交通平衡分配问题[J]. 南通工学院学报: 自然科学版, 2004, 3(2): 24- 27.

8. 8. Mahut, M. (2005) A Heuristic Algorithm for Simulation-Based Dynamic Traffic Assignment. Proceedings of IEEE Intelligent Transportation Systems, Vienna, 13-15 September 2005, 239-244.

9. 9. 王秋平, 刘星明, 魏华. 历史街区慢行交通连续网络设计鲁棒优化模型[J]. 长安大学学报(自然科学版), 2015, 35(5): 112-116.

10. 10. 李宗平, 李冰. 城市交通连续平衡网络设计问题的模拟退火算法[J]. 系统工程, 2004, 22(2): 87-91.

11. 11. 孙杨, 宋瑞, 何世伟, 等. 混合交通网络设计及免疫克隆退火算法求解研究[J]. 交通运输系统工程与信息, 2009, 9(3): 103-108.

12. 12. 王素欣, 高利, 崔小光, 等. 交通分配的粒子群优化算法[J]. 交通运输工程学报, 2007, 7(5): 97-100.

13. 13. 陈小松, 彭丰富. Groebner基理论在最短路径问题中的应用[J]. 中南工业大学学报, 2002, 33(6): 648-650.

14. 14. 朱玉莲. Groebner基理论及其在一些优化问题上的应用[D]: [硕士学位论文]. 长沙: 中南大学, 2007: 15-18.

15. 15. Hoşten, S. and Sturmfels, B. (2005) Integer Programming and Combinatorial Optimization. Springer-Verlag, New York, Berlin, Heidelberg, 267-270.

16. 16. 周梦. 计算机代数与应用[M]. 武汉: 武汉大学出版社, 2002: 205-210.