城市交通流量估计的运筹学方法

doi:10.15960/j.cnki.issn.1007-6093.2023.02.002

摘要/Abstract

摘要：

随着社会经济的发展和人类生产方式的进步, 交通管理系统为运筹学提供一系列研究课题。运筹学方法在交通网络建模领域有着广泛应用, 其在智能交通管理系统中亦占有重要位置。充分应用运筹学的各个分支方法去解决交通系统中存在的问题, 可有效保障生活中交通的高效、有序运行。本文首先介绍交通问题中一些基本概念和交通流量问题的若干基本模型, 然后从线性规划、整数规划、动态规划、图论、统计方法、启发式方法和机器学习七个方面综述现有的相关研究成果。最后, 探讨了交通流量模型及相关问题的发展方向, 提出其尚需研究和解决的问题, 以期为交通运输管理者与研究者提供更多参考。

关键词: 流量估计与预测, 规划论, 图论, 统计学, 机器学习

Abstract:

With the development of the social economy and the progress of human production mode, the traffic management system provides a series of subjects for operations research. The operational research methods are widely applied in the field of traffic network modeling, and they also occupy some important positions in the intelligent traffic management system. To solve the problems existing in the traffic system, we can make full use of various branches of operations research, which can effectively ensure the efficiency and orderliness of transportation in real life. In this paper, we first introduce several solution models for solving traffic flow estimation problems and then review the existing research from seven aspects: linear programming, integer programming, dynamic programming, graph theory, statistical, heuristic approach, and machine learning method. Finally, to provide more references for transportation managers and researchers, we discuss the development directions and related problems for traffic flow estimation models and propose the potential problems that need to be further investigated and solved.

Key words: traffic estimation and prediction, programming theory, graph theory, statistics, machine learning

中图分类号:

O221.2

邵虎, 卓越, 刘鹏杰, 邵枫. 城市交通流量估计的运筹学方法[J]. 运筹学学报, 2023, 27(2): 27-48.

Hu SHAO, Yue ZHUO, Pengjie LIU, Feng SHAO. Operational research methods for urban traffic flow estimation[J]. Operations Research Transactions, 2023, 27(2): 27-48.

图/表 4

图1

表1

表2

表3

参考文献 95

1	沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25 (1): 1- 16.
2	汪光焘. 中国城市交通问题、对策与理论需求[J]. 城市交通, 2016, 14 (6): 1- 9.
3	胡运权. 运筹学基础及应用[M]. 哈尔滨: 哈尔滨工业大学出版社, 1998.
4	吴祈宗, 侯福均. 运筹学与最优化方法[M]. 北京: 机械工业出版社, 2013.
5	黄海军. 城市交通网络平衡分析: 理论与实践[M]. 北京: 人民交通出版社, 1994.
6	程琳. 城市交通网络流理论[M]. 南京: 东南大学出版社, 2010.
7	Yang H , Zhou J . Optimal traffic counting locations for origin-destination matrix estimation[J]. Transportation Research Part B, 1998, 32 (2): 109- 126. doi: 10.1016/S0191-2615(97)00016-7
8	Cipriani E, Fusco G, Gori S. Optimal location of traffic count sections[C]//Traffic and Transportation Studies, Universita di Roma Tre, Dipartimento di Scienza dell'ingegneria Civile, 2004.
9	Ehlert A , Bell M G H , Gross S . The optimization of traffic count locations in road networks[J]. Transportation Research Part B, 2006, 40 (6): 460- 479. doi: 10.1016/j.trb.2005.06.001
10	Castillo E , Rivas A , Jiménez P , et al. Observability in traffic networks: Plate scanning added by counting information[J]. Transportation, 2012, 39 (6): 1301- 1333. doi: 10.1007/s11116-012-9390-0
11	Castillo E , Nogal M , Rivas A , et al. Observability of traffic networks: Optimal location of counting and scanning devices[J]. Transportmetrica B: Transport Dynamics, 2013, 1 (1): 68- 102. doi: 10.1080/21680566.2013.780987
12	Minguez R , Sánchez-Cambronero S , Castillo E , et al. Optimal traffic plate scanning location for OD trip matrix and route estimation in road networks[J]. Transportation Research Part B, 2010, 44 (2): 282- 298. doi: 10.1016/j.trb.2009.07.008
13	Yang H , Iida Y , Sasaki T . An analysis of the reliability of an origin-destination trip matrix estimated from traffic counts[J]. Transportation Research Part B, 1991, 25 (5): 351- 363. doi: 10.1016/0191-2615(91)90028-H
14	Bierlaire M . The total demand scale: A new measure of quality for static and dynamic origin-destination trip tables[J]. Transportation Research Part B, 2002, 36 (9): 837- 850. doi: 10.1016/S0191-2615(01)00036-4
15	Chen A , Chootinan P , Recker W W . Examining the quality of synthetic origin-destination trip table estimated by path flow estimator[J]. Journal of Transportation Engineering, 2005, 131 (7): 506- 513. doi: 10.1061/(ASCE)0733-947X(2005)131:7(506)
16	Gan L , Yang H , Wong S C . Traffic counting location and error bound in origin-destination matrix estimation problems[J]. Journal of Transportation Engineering, 2005, 131 (7): 524- 534. doi: 10.1061/(ASCE)0733-947X(2005)131:7(524)
17	Van Zuylen H J , Willumsen L G . The most likely trip matrix estimated from traffic counts[J]. Transportation Research Part B, 1980, 14 (3): 281- 293. doi: 10.1016/0191-2615(80)90008-9
18	Zhou X , List G F . An information-theoretic sensor location model for traffic origin-destination demand estimation applications[J]. Transportation Science, 2010, 44 (2): 254- 273. doi: 10.1287/trsc.1100.0319
19	Simonelli F , Marzano V , Papola A , et al. A network sensor location procedure accounting for o-d matrix estimate variability[J]. Transportation Research Part B, 2012, 46 (10): 1624- 1638. doi: 10.1016/j.trb.2012.08.007
20	Viti F, Corman F. A novel approach to the sensor location problem for measuring the observed network flow variability[C]//Proceedings of the 5th International Symposium of Traffic Network Reliability, 2012.
21	Cascetta E , Inaudi D , Marquis G . Dynamic estimators of origin-destination matrices using traffic counts[J]. Transportation Science, 1993, 27 (4): 363- 373. doi: 10.1287/trsc.27.4.363
22	伍建国, 王峰. 城市道路交通数据采集系统检测器优化布点研究[J]. 公路交通科技, 2004, 21 (2): 88- 98.
23	Castillo E , Conejo A J , Pruneda R E , et al. Observability in linear systems of equations and inequalities: Applications[J]. Computers and Operations Research, 2007, 34 (6): 1708- 1720. doi: 10.1016/j.cor.2005.05.035
24	Castillo E , Conejo A J , Menéndez J M , et al. The observability problem in traffic network models[J]. Computer-Aided Civil and Infrastructure Engineering, 2008, 23 (3): 208- 222. doi: 10.1111/j.1467-8667.2008.00531.x
25	Castillo E , Jiménez P , Menéndez J M , et al. The observability problem in traffic models: Algebraic and topological methods[J]. IEEE Transactions on Intelligent Transportation Systems, 2008, 9 (2): 275- 287. doi: 10.1109/TITS.2008.922929
26	Castillo E , Gallego I , Sanchez-Cambronero S , et al. Matrix tools for general observability analysis in traffic networks[J]. IEEE Transportations on Intelligent Transportation Systems, 2010, 11 (4): 799- 813. doi: 10.1109/TITS.2010.2050768
27	Hu S R , Peeta S , Chu C H . Identification of vehicle sensor locations for link-based network traffic applications[J]. Transportation Research Part B, 2009, 43 (8-9): 873- 894. doi: 10.1016/j.trb.2009.02.008
28	王殿海, 徐程, 祁宏生, 等. 基于路段流量相关性的检测器优化布设[J]. 华南理工大学学报, 2011, 39 (3): 107- 113.
29	Ng M W . Synergistic sensor location for link flow inference without path enumeration: A node-based approach[J]. Transportation Research Part B, 2012, 46 (6): 781- 788. doi: 10.1016/j.trb.2012.02.001
30	Ng M W . Partial link flow observability in the presence of initial sensors: Solution without path enumeration[J]. Transportation Research Part E, 2013, 51, 62- 66. doi: 10.1016/j.tre.2012.12.002
31	何胜学, 孙晶晶. 解决路网检测器布局问题的树形结合方法[J]. 交通运输系统工程与信息, 2016, 16 (5): 58- 63.
32	李翠杰. 交通流量多阶段估计方法与应用[D]. 徐州: 中国矿业大学, 2020.
33	朱宁, 马寿峰, 贾宁. 考虑故障因素的交通检测器布设优化问题研究[J]. 系统工程理论与实践, 2014, 34 (4): 997- 1002.
34	Wang N , Gentili M , Mirchandani P . Model to locate sensors for estimation of static origin-destination volumes given prior flow information[J]. Transportation Research Record, 2012, 2283 (1): 67- 73. doi: 10.3141/2283-07
35	Xu X D , Lo H K , Chen A , et al. Robust network sensor location for complete link flow observability under uncertainty[J]. Transportation Research Part B, 2016, 88, 1- 20.
36	Merchant D K , Nemhauser G L . Optimality conditions for a dynamic traffic assignment model[J]. Transportation Science, 1978, 12 (3): 200- 207. doi: 10.1287/trsc.12.3.200
37	Friesz T L , Luque J , Tobin R L . Dynamic network traffic assignment considered as a continuous time optimal control problem[J]. Operations Research, 1989, 37 (6): 893- 901. doi: 10.1287/opre.37.6.893
38	Jayakrishnan R , Tsai W K , Chen A . A dynamic traffic assignment model with traffic-flow relationships[J]. Transportation Research Part C, 1995, 3 (1): 51- 72. doi: 10.1016/0968-090X(94)00015-W
39	Carey M , Subrahmanian E . An approach to modelling time-varying flows on congested networks[J]. Transportation Research Part B, 2000, 34 (3): 157- 183. doi: 10.1016/S0191-2615(99)00019-3
40	Szeto W Y , Lo H K . Dynamic traffic assignment: Properties and extensions[J]. Transportmetrica, 2006, 2 (1): 31- 52. doi: 10.1080/18128600608685654
41	王衡. 城市道路交通定点检测器优化布设研究[D]. 上海: 同济大学, 2008.
42	Ban X , Herring R , Margulici J D , et al. Optimal sensor placement for freeway travel time estimation[J]. Transportation and Traffic Theory, 2009, 697- 722.
43	Gu X Z, Jia X D. On a traffic control problem[C]//Symposium on Parallel Architectures. IEEE, 2005.
44	Bianco L , Confessore G , Gentili M . Combinatorial aspects of the sensor location problem[J]. Annals of Operations Research, 2006, 144 (1): 201- 234. doi: 10.1007/s10479-006-0016-9
45	Morrison D R , Martonosi S E . Characteristics of optimal solutions to the sensor location problem[J]. Annals of Operations Research, 2015, 226, 463- 478. doi: 10.1007/s10479-014-1638-y
46	Morrison D R, Martonosi S E. Where are all the cars? Characteristics of optimal solutions to the sensor location problem[C]//INFORMS Annual Meeting, 2008.
47	林培群, 徐建闽. 基于图论的路网交通检测器之布点[J]. 控制理论与应用, 2010, 27 (12): 1605- 1611.
48	王彦杰, 李文勇. 基于图论的交通检测器新型布设方法[J]. 西部交通科技, 2010, 4, 92- 95.
49	张墨逸, 曹洁, 牛建强, 等. 基于图论与矩阵论的交通检测器布设新方法[J]. 公路交通科技, 2012, 29 (11): 130- 134.
50	He S X . A graphical approach to identify sensor locations for link flow inference[J]. Transportation Research Part B, 2013, 51 (4): 65- 76.
51	孙超, 程琳, 栾鑫, 等. 基于网络拓扑的子网络OD需求估计[J]. 东南大学学报(自然科学版), 2017, 47 (6): 1248- 1252.
52	付相君. 基于路网拓扑结构的相关路段流量预测研究[D]. 重庆: 重庆交通大学, 2020.
53	叶秀秀, 马晓凤, 钟鸣, 等. 基于局部路网空间结构特征的无检测器路段交通流预测方法[J]. 交通信息与安全, 2021, 39 (2): 137- 144.
54	Maher M J . Inferences on trip matrices from observations on link volumes: A Bayesian statistical approach[J]. Transportation Research Part B, 1983, 17 (6): 435- 447. doi: 10.1016/0191-2615(83)90030-9
55	Castillo E , Jiménez P , Menéndez J M , et al. A Bayesian method for estimating traffic flows based on plate scanning[J]. Transportation, 2013, 40 (1): 173- 201. doi: 10.1007/s11116-012-9443-4
56	Castillo E , Menéndez J M , Sanchez-Cambronero S . Traffic estimation and optimal counting location with path enumeration using Bayesian networks[J]. Computer-Aided Civil and Infrastructure Engineering, 2008, 23 (3): 189- 207. doi: 10.1111/j.1467-8667.2008.00526.x
57	Shao H , Lam W H K , Tam M L . A reliability-based stochastic traffic assignment model for network with multiple user classes under uncertainty in demand[J]. Networks and Spatial Economics, 2006, 6 (3): 173- 204.
58	Shao H, Lam W H K, Meng Q, et al. A demand driven travel time reliability-based traffic assignment problem[C]//Transportation Research Board Meeting, 2006.
59	Lam W H K , Shao H , Sumalee A . Modeling impacts of adverse weather conditions on a road network with uncertainties in demand and supply[J]. Transportation Research Part B, 2008, 42 (10): 890- 910. doi: 10.1016/j.trb.2008.02.004
60	Chen A , Yang H , Lo H K , et al. Capacity reliability of a road network: An assessment methodology and numerical results[J]. Transportation Research Part B, 2002, 36 (3): 225- 252. doi: 10.1016/S0191-2615(00)00048-5
61	Zhou Z , Chen A . Comparative analysis of three user equilibrium models under stochastic demand[J]. Journal of Advanced Transportation, 2008, 42 (3): 239- 263. doi: 10.1002/atr.5670420304
62	Nakayama S, Takayama J. Traffic network equilibrium model for uncertain demands[C]//Proceedings of the 82nd Transportation Research Board Annual Meeting, 2003.
63	Clark S D , Watling D P . Modeling network travel time reliability under stochastic demand[J]. Transportation Research Part B, 2005, 39 (2): 119- 140. doi: 10.1016/j.trb.2003.10.006
64	Castillo E , Menéndez J M , Jiménez P . Trip matrix and path flow reconstruction and estimation based on plate scanning and link observations[J]. Transportation Research Part B, 2008, 42 (5): 455- 481. doi: 10.1016/j.trb.2007.09.004
65	Shao H , Lam W H K , Sumalee A , et al. Estimation of mean and covariance of peak hour origin-destination from day-to-day traffic counts[J]. Transportation Research Part B, 2014, 68, 52- 75. doi: 10.1016/j.trb.2014.06.002
66	Shao H , Lam W H K , Sumalee A , et al. Estimation of mean and covariance of stochastic multi-class OD demands from classified traffic counts[J]. Transportation Research Part C, 2015, 59, 192- 211.
67	沈良. 不确定条件下的交通网络最优路径搜索算法及其应用[D]. 徐州: 中国矿业大学, 2019.
68	Lo H P , Zhang N , Lam W H K . Estimation of an origin-destination matrix with random link choice proportions: A statistical approach[J]. Transportation Research Part B, 1996, 30 (4): 309- 324. doi: 10.1016/0191-2615(95)00036-4
69	姜桂艳, 张若旗, 周志强. 城市主干道检测器分布于交通流量预测研究[J]. ITS通讯, 2002, 11 (1): 22- 26.
70	杨晓光, 刘斌, 张晔. 城市道路网络OD估计模型及算法研究[J]. 同济大学学报, 2011, 39 (9): 1292- 1296.
71	Lam W H K , Lo H P . Accuracy of OD estimates from traffic counts[J]. Traffic Engineering and Control, 1990, 31 (6): 358- 367.
72	Cipriani E, Fusco G, Gori S, et al. Heuristic methods for the optimal location of road traffic monitoring[C]//2006 IEEE Intelligent Transportation Systems Conference, 2006: 1072-1077.
73	Bianco L , Confessore G , Reverberi P . A network based model for traffic sensor location with implications on O/D matrix estimates[J]. Transportation Science, 2001, 35 (1): 50- 60. doi: 10.1287/trsc.35.1.50.10140
74	Bianco L, Cerulli R, Gentili M. New resolution approaches for the sensor location problem[C]//Proceedings of Tristan Ⅵ Symposium, 2007.
75	Confessore G , Dell'Olmo P , Gentili M . Experimental evaluation of approximation and heuristic algorithms for the dominating paths problem[J]. Computers and Operations Research, 2005, 32 (9): 2383- 2405. doi: 10.1016/j.cor.2004.03.008
76	邢文博. 基于车牌识别数据的城市路网OD估计及分析研究[D]. 成都: 西南交通大学, 2020.
77	于德新, 杨兆升, 刘雪杰. 基于DTA的OD估计方法的交通检测器优化布置模型研究[J]. 公路交通科技, 2006, 23 (12): 111- 117.
78	杜长飞. 基于OD估计的路网交通检测器优化布设研究[D]. 北京: 北京交通大学, 2012.
79	Lo H K. A dynamic traffic assignment formulation that encapsulates the cell-transmission model[C]//14th International Symposium on Transportation and Traffic Theory Transportation Research Institute, 1999.
80	Lo H K , Szeto W Y . A cell-based dynamic traffic assignment model: Formulation and properties[J]. Mathematical and Computer Modelling, 2002, 35 (7-8): 849- 865. doi: 10.1016/S0895-7177(02)00055-9
81	Celikoglu H B . A dynamic network loading model for traffic dynamics modeling[J]. IEEE Transactions on Intelligent Transportation Systems, 2007, 8 (4): 575- 583. doi: 10.1109/TITS.2007.903051
82	裴玉龙, 刘博航, 徐慧智. 一种交通量检测设备布设方法的研究[J]. 公路交通科技, 2007, 24 (11): 100- 104.
83	刘政威. 考虑交通事件检测的固定型交通检测器布设方法研究[D]. 南京: 东南大学, 2011.
84	Ke J T , Zheng H Y , Yang H , et al. Short-term forecasting of passenger demand under on-demand ride services: A spatio-temporal deep learning approach[J]. Transportation Research Part C, 2017, 85, 591- 608. doi: 10.1016/j.trc.2017.10.016
85	Bogaertsa T , Masegosa A D , Angarita-Zapata J S , et al. A graph CNN-LSTM neural network for short and long-term traffic forecasting based on trajectory data[J]. Transportation Research Part C, 2020, 112, 62- 77. doi: 10.1016/j.trc.2020.01.010
86	周常胜. Hadoop环境下基于SVR的短时交通流预测[D]. 大连: 大连理工大学, 2015.
87	罗文慧, 董宝田, 王泽胜. 基于CNN-SVR混合深度学习模型的短时交通流预测[J]. 交通运输系统工程与信息, 2017, 17 (5): 68- 74.
88	何雨桧. 基于车牌识别数据的信号交叉口交通参数获取方法及应用[D]. 成都: 西南交通大学, 2020.
89	Ma T , Antoniou C , Toledo T . Hybrid machine learning algorithm and statistical time series model for network-wide traffic forecast[J]. Transportation Research Part C, 2020, 111, 352- 372. doi: 10.1016/j.trc.2019.12.022
90	李曙光, 巨永峰, 姬建岗. 多模式路径流量估计模型与算法[J]. 交通运输工程学报, 2009, 9 (1): 87- 91.
91	张涛, 陈先, 谢美萍, 等. 基于k近邻非参数回归的短时交通流预测方法[J]. 系统工程理论与实践, 2010, 30 (2): 376- 384.
92	吴芳超. 交通事件检测算法适应性分析及检测器布设方法研究[D]. 西安: 长安大学, 2013.
93	阮树斌, 王福建, 马东方, 等. 基于车牌识别数据的机动车出行轨迹提取算法[J]. 浙江大学学报(工学版), 2018, 52 (5): 836- 844.
94	Liu Z Y , Liu Y , Meng Q , et al. A tailored machine learning approach for urban transport network flow estimation[J]. Transportation Research Part C, 2019, 108, 130- 150. doi: 10.1016/j.trc.2019.09.006
95	孙超, 宋茂灿, 陈志超, 等. 观测路径出行时间下随机网络交通需求估计[J]. 中国公路学报, 2021, 34 (3): 206- 215.

	流量可观测问题	流量估计问题	流量预测问题
线性规划	代数性质^{[22, 24, 25, 26, 27, 28]}
	矩阵变换^{[29, 30, 31, 32]}
整数规划	随机规划^[33]
	二元整数规划^[35]
图论方法	图的多种类型^{[44, 45, 46]}	子网络拓扑^[51]	网络拓扑^{[52, 53]}
统计方法	贝叶斯估计^[56]	贝叶斯估计^{[54, 55]}
		正态分布^{[57, 58, 59, 60, 61]}
		方差、协方差^{[62, 63, 64, 65, 66, 67]}
启发式方法	启发式算法^{[71, 73, 74, 75]}
	遗传算法^{[77, 78]}
机器学习		神经网络^{[79, 80, 82, 83, 84, 85]}
		向量机^{[86, 87, 88]}
		数据分析^{[93, 94]}	$ K $近邻^[91]

作者	使用方法	解决的问题
Castillo E	代数技术、矩阵变换	流量可观测问题^{[23, 24, 25, 26]}
	贝叶斯统计	流量估计问题^{[55, 56]}
Bianco L	图论、启发式算法	流量可观测问题^{[44, 73, 74]}
Ng M W	矩阵变换	流量可观测问题^{[29, 30]}
Shao H	正态分布、方差、协方差	流量估计问题^{[57, 58, 65, 66]}
Lo H K	神经网络	流量可观测、估计问题^{[79, 80]}
Lam W H K	正态分布、启发式算法	流量可观测、估计问题^{[59, 71]}

问题种类	求解方法	优缺点对比
流量可观测问题	线性规划	优点: 多使用代数性质求解, 借助矩阵工具, 方法简单
		缺点: 结果不精确, 只能得到一个大概的上下界
	整数规划	优点: 可考虑多种路况, 能较好得使用路径流量等多源信息, 减小求解误差
		缺点: 需要一些先验条件, 对源数据精确度要求高
	图论法	优点: 充分考虑交通网络的拓扑情况
		缺点: 结果不精确, 只能得到一个大概的上下界
	启发式算法	优点: 针对NP难问题, 得到结果较为精确
		缺点: 在一些特殊情况下不适用, 求解速度较慢
	遗传算法	优点: 使用网络中多种流量信息, 保证模型在大型网络上的可行性
		缺点: 收敛速度慢, 控制变量多, 编码较为复杂
流量估计问题	贝叶斯估计	优点: 多用于估计OD矩阵, 使用先验流量信息, 可最大化减小方差
		缺点: 需要先验概率, 属性之间相互独立的假设往往不成立
	最小二乘法	优点: 对网络中路径流量和OD信息进行很好的估计
		缺点: 对一些情况不适用, 局限性较大
	正态分布	优点: 对路段或路径的出行时间、流量的方差和协方差等信息都有很好的研究
		缺点: 结果不精确
流量预测问题	神经网络	优点: 能更好的捕捉时空特征和解释变量之间的相关性, 可对网络上动态流量较好的预测
		缺点: 计算代价高, 需要大量参数
	支持向量机方法	优点: 代替神经网络在后处理中的作用, 提高预测准确性
		缺点: 对大规模数据难以计算

[1]	张慧灵, 徐洋, 徐姿. 分块凸-非凹极小极大问题的交替近端梯度算法[J]. 运筹学学报, 2022, 26(4): 64-74.
[2]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[3]	张家普, CHATTERJEE Subhojyoti, 王凤. 应用图论分析与最优化理论来数据挖掘大规模水牛普里昂蛋白结构数据[J]. 运筹学学报, 2017, 21(2): 73-83.
[4]	陈征, 高岩. 控制系统生存核的逼近算法[J]. 运筹学学报, 2013, 17(4): 24-32.