交通网络平衡配流问题的研究
|
摘要
网络配流问题是交通工程领域中的重大理论问题，更是水资源领
域、通信领域中的重要研究内容。在智能交通系统中，无论进行交通规
划还是进行路径选择，交通配流都是核心问题。交通配流已引起大量专
家学者的广泛注意。在前人研究的基础上，本文在平衡配流方面主要做
了以下一些工作：
在静态平衡配流理论中，构建了完全基于路段的变分不等式模型，
即目标函数和约束条件不含有路径参数。由于该模型是完全基于路段
的，从而克服了基于路径方法必须进行路径穷举的缺陷。该模型是与
Wolfe用户平衡条件是等价的，即：对任意起止点对，所有被选用的路
径上的旅行时间是最小的，而未被选用的路径上的旅行时间都大于或等
于被选用路径上的旅行时间。提出了最优路径选择算法用以求解该变分
不等式模型并为交通网络中的群体车辆进行路径诱导。经试验结果，表
明本文的模型和算法是正确和有效的。
在动态平衡配流理论中，给出了用于动态路径选择的基于路段的变
分不等式模型。该模型满足动态用户最优条件，即：任意起止点对间，
同一时间段出发的所有用户到达目的地时所经历的时间是相等的，并且
是最小的。使用嵌套对角线算法求解该变分不等式模型。提出了群体车
辆的动态路径选择算法用于为交通网络中的每个车辆寻找最优行驶路
径。
针对交通需求矩阵不易获得的问题，本文给出了用于交通预测的极
大熵模型，这样根据获得的路段上交通量数据和历史交通需求矩阵数
据，可以预测得到现在的交通需求矩阵。使用牛顿法求解该极大熵模型，
提出了一些非常有效的数据结构及算法，包括稀疏矩阵的存储与使用以
及逆阵的求解等。最后用算例说明极大熵模型求得的O-D矩阵的可靠
性和求解算法及数据结构的有效性。
Network flow assignment is a significant theorical problem and an important research subject in the field of the communication and water resource. In the intelligent transportation system, traffic flow assignment is the core of the traffic regulation and path choice problems. It has attracted many researchers. Based on the others' research in traffic flow assignment, we do some work as follows:
In the theory of static traffic flow assignment, we formulate a completely link-based variational inequality (VI) model, whose objective function and constraint conditions do not have the path variables. Since the model is completely link-based, we need not enumerate all the paths to evaluate this model. This model is equivalent to the user equilibrium (UE) condition, that is, for each origin-destination pair, the travel time on all the used paths is equal and minimal; the travel time on the unused paths is greater than or equal to the minimal travel time. We present an optimal path choice algorithm to solve the VI model and determine an optimal path for each vehicle in the traffic network. An example is given to show that the model and the algorithm are right and effective.
In the theory of dynamic flow assignment, we present a link-based VI model for the dynamic path choice. This model satisfies the dynamic user optimal condition, i.e., for each Origin-Destination pair, the path travel time experienced by travelers departing during the same interval is equal and minimal. We present the nested diagonalization method. We then put up a dynamic path choice algorithm to determine an optimal path for each vehicle in the traffic network.
Since the traffic demand matrix is difficult to obtain, we present a discrete time-dependent maximum entropy (ME) approach to estimate the origin-destination trip matrices in transit network. The Newton method is applied to solve this optimization model of ME model. Then some efficient algorithms and data structures are put up, including the storage and application of the sparse matrix and the evaluation of the reverse matrix. An example is given to show that the origin-destination trip matrices which is gained by the ME model has a high reliability and the data structures and algorithms are very efficient.
域、通信领域中的重要研究内容。在智能交通系统中，无论进行交通规
划还是进行路径选择，交通配流都是核心问题。交通配流已引起大量专
家学者的广泛注意。在前人研究的基础上，本文在平衡配流方面主要做
了以下一些工作：
在静态平衡配流理论中，构建了完全基于路段的变分不等式模型，
即目标函数和约束条件不含有路径参数。由于该模型是完全基于路段
的，从而克服了基于路径方法必须进行路径穷举的缺陷。该模型是与
Wolfe用户平衡条件是等价的，即：对任意起止点对，所有被选用的路
径上的旅行时间是最小的，而未被选用的路径上的旅行时间都大于或等
于被选用路径上的旅行时间。提出了最优路径选择算法用以求解该变分
不等式模型并为交通网络中的群体车辆进行路径诱导。经试验结果，表
明本文的模型和算法是正确和有效的。
在动态平衡配流理论中，给出了用于动态路径选择的基于路段的变
分不等式模型。该模型满足动态用户最优条件，即：任意起止点对间，
同一时间段出发的所有用户到达目的地时所经历的时间是相等的，并且
是最小的。使用嵌套对角线算法求解该变分不等式模型。提出了群体车
辆的动态路径选择算法用于为交通网络中的每个车辆寻找最优行驶路
径。
针对交通需求矩阵不易获得的问题，本文给出了用于交通预测的极
大熵模型，这样根据获得的路段上交通量数据和历史交通需求矩阵数
据，可以预测得到现在的交通需求矩阵。使用牛顿法求解该极大熵模型，
提出了一些非常有效的数据结构及算法，包括稀疏矩阵的存储与使用以
及逆阵的求解等。最后用算例说明极大熵模型求得的O-D矩阵的可靠
性和求解算法及数据结构的有效性。
Network flow assignment is a significant theorical problem and an important research subject in the field of the communication and water resource. In the intelligent transportation system, traffic flow assignment is the core of the traffic regulation and path choice problems. It has attracted many researchers. Based on the others' research in traffic flow assignment, we do some work as follows:
In the theory of static traffic flow assignment, we formulate a completely link-based variational inequality (VI) model, whose objective function and constraint conditions do not have the path variables. Since the model is completely link-based, we need not enumerate all the paths to evaluate this model. This model is equivalent to the user equilibrium (UE) condition, that is, for each origin-destination pair, the travel time on all the used paths is equal and minimal; the travel time on the unused paths is greater than or equal to the minimal travel time. We present an optimal path choice algorithm to solve the VI model and determine an optimal path for each vehicle in the traffic network. An example is given to show that the model and the algorithm are right and effective.
In the theory of dynamic flow assignment, we present a link-based VI model for the dynamic path choice. This model satisfies the dynamic user optimal condition, i.e., for each Origin-Destination pair, the path travel time experienced by travelers departing during the same interval is equal and minimal. We present the nested diagonalization method. We then put up a dynamic path choice algorithm to determine an optimal path for each vehicle in the traffic network.
Since the traffic demand matrix is difficult to obtain, we present a discrete time-dependent maximum entropy (ME) approach to estimate the origin-destination trip matrices in transit network. The Newton method is applied to solve this optimization model of ME model. Then some efficient algorithms and data structures are put up, including the storage and application of the sparse matrix and the evaluation of the reverse matrix. An example is given to show that the origin-destination trip matrices which is gained by the ME model has a high reliability and the data structures and algorithms are very efficient.
引文
[1] [美]赵亦林 著，谭国真 译．车辆定位与导航系统．电子工业出版社，1999
[2] T.H.Cormen. C.E.Leiserson, and R.L.Rivest. Introduction to Algorithms,Cambridge, MA: MIT Press; New York: McGraw-Hill, 1990
[3] D．金德勒雷 G．斯当帕克亚．变分不等式方程及其应用．科学出版社．1991
[4] Mei-Shiang Chang Huey-Kuo Chen. A fuzzy user-optimal route choice problem using a link-based fuzzy variational inequality formulation.Fuzzy Sets and Systems 114. 2000, 339-345
[5] Takashi Akamatsu. Decomposition of Path Choice Entropy in General Transport Networks. Transportation Science, Vol 31. No.4. November 1997
[6] 陈宝林．最优化理论与算法．清华大学出版社．1989
[7] S.Dafermos, Traffic equilibrium and variational inequalities,Transportation Science, 14,1980, 42-54
[8] A.Nagurney, Network Economics: A Variational Inequality Approach,Kluwer Academic Publishers, Dordrecht, The Netherlands, 1993
[9] 黄海军．城市交通网络平衡分析理论与实践，人民交通出版社，19921SBN7-03-002057-x
[10] 谭国真等．最短路径算法的设计、分析与评价，大连理工大学计算机系研究报告．1999
[11] Huey-Kuo Chen & Che-Fu Hsueh, A Model and an Algorithm For The Dynamic User-Optimal Route Choice Problem, Transportation Research B Vol.32 No. 3 pp219-234, 1998
[12] Der-Horng Lee. Formulation and Solution of a Dynamic User-Optimal Route Choice Model On a Large-Scale Traffic Network. Ph.D. thesis of University of Illinois at Chicago, 1996
[13] JiFeng Wu, A Real-Time Origin-Destination Matrix Updationg Algorithm For On-Line Applications, Transportation Research B Volume 31 No.5, pp381-396,1997
[14] Xiaoyan Zhang and Mike J. Maher.The Evaluation and Application of A Fully Disaggregate Method For Trip Matrix Estimation With Platoon Dispersion, Transpn Res.-B Vol. 32. No4, pp.261-276,1998
[15] 刘法胜，夏尊铨．大连理工大学数学系博士学位论文，网络配流问题的模型分析与应用，BL 571，1999
[16] S.C. Wong and C.O. Tong. Estimation Of Time-Dependent Origin-Destination Matrices For Transit Networks, Transpn Res.-B, 1996.11 Vol.32.No. 1.pp 35-48
[17] Templeman A.B. & Li Xingsi.A Maximum Entropy Approach To Constrained Non-Linear Programming, Engineering Optimization,1987.12 No.3, 191 205
[18] 毛保华 曾回欣 袁振州．交通规划模型及其应用 中国铁道出版社1999．3
[2] T.H.Cormen. C.E.Leiserson, and R.L.Rivest. Introduction to Algorithms,Cambridge, MA: MIT Press; New York: McGraw-Hill, 1990
[3] D．金德勒雷 G．斯当帕克亚．变分不等式方程及其应用．科学出版社．1991
[4] Mei-Shiang Chang Huey-Kuo Chen. A fuzzy user-optimal route choice problem using a link-based fuzzy variational inequality formulation.Fuzzy Sets and Systems 114. 2000, 339-345
[5] Takashi Akamatsu. Decomposition of Path Choice Entropy in General Transport Networks. Transportation Science, Vol 31. No.4. November 1997
[6] 陈宝林．最优化理论与算法．清华大学出版社．1989
[7] S.Dafermos, Traffic equilibrium and variational inequalities,Transportation Science, 14,1980, 42-54
[8] A.Nagurney, Network Economics: A Variational Inequality Approach,Kluwer Academic Publishers, Dordrecht, The Netherlands, 1993
[9] 黄海军．城市交通网络平衡分析理论与实践，人民交通出版社，19921SBN7-03-002057-x
[10] 谭国真等．最短路径算法的设计、分析与评价，大连理工大学计算机系研究报告．1999
[11] Huey-Kuo Chen & Che-Fu Hsueh, A Model and an Algorithm For The Dynamic User-Optimal Route Choice Problem, Transportation Research B Vol.32 No. 3 pp219-234, 1998
[12] Der-Horng Lee. Formulation and Solution of a Dynamic User-Optimal Route Choice Model On a Large-Scale Traffic Network. Ph.D. thesis of University of Illinois at Chicago, 1996
[13] JiFeng Wu, A Real-Time Origin-Destination Matrix Updationg Algorithm For On-Line Applications, Transportation Research B Volume 31 No.5, pp381-396,1997
[14] Xiaoyan Zhang and Mike J. Maher.The Evaluation and Application of A Fully Disaggregate Method For Trip Matrix Estimation With Platoon Dispersion, Transpn Res.-B Vol. 32. No4, pp.261-276,1998
[15] 刘法胜，夏尊铨．大连理工大学数学系博士学位论文，网络配流问题的模型分析与应用，BL 571，1999
[16] S.C. Wong and C.O. Tong. Estimation Of Time-Dependent Origin-Destination Matrices For Transit Networks, Transpn Res.-B, 1996.11 Vol.32.No. 1.pp 35-48
[17] Templeman A.B. & Li Xingsi.A Maximum Entropy Approach To Constrained Non-Linear Programming, Engineering Optimization,1987.12 No.3, 191 205
[18] 毛保华 曾回欣 袁振州．交通规划模型及其应用 中国铁道出版社1999．3
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |