中文

Operations Research Transactions >

2023 , Vol. 27 >Issue 2: 1 - 26

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.02.001

A systematic review of researches and applications of bi-level programming in the context of urban transport

Expand
  • 1. Beijing Municipal Institute of City Planning and Design, Beijing 100045, China
    2. Beijing Chengyuan Digital Technology Co. Ltd, Beijing 100045, China

Received date: 2023-04-13

  Online published: 2023-06-13

Fold

Abstract

Bi-level programming is a typical NP-Hard problem. It is a nonconvex optimization problem with upper and lower hierarchical structure and contains optimization problems in constraint conditions. This paper systematically reviews the researches and applications of bi-level programming in the context of urban transport, focusing on transportation network design problem and OD estimation/adjustment problem. Firstly, the domestic and international research topics and evolution progress are summarized by bibliometrics. Secondly, it takes pioneering research as the clue to look back upon important researches, the first systematic review paper, the first doctoral dissertation, the first Transportation Research Part-B's issue, and the first review paper in Chinese are introduced. Thirdly, the recent development of network design problems including road, transit and multi-modal, and the static and dynamic OD estimation problems are expounded. Fourthly, some general solutions are concluded, and the trends of solutions are discussed, the relationship between bi-level programming and MPEC is expressed. Finally, it points out three opportunities and challenges in the future should be addressed, including exploring and revealing of smart transportation, the optimization of modeling architecture, and building a computing platform to share and interact.

Key words： bi-level programming; network design problem; OD estimation/adjust -ment; user equilibrium; MPEC; model and algorithm

Cite this article

He WEI, Haofei LIU, Dandan XU, Xuehua HAN, Liang WANG, Xiaodong ZHANG . A systematic review of researches and applications of bi-level programming in the context of urban transport[J]. Operations Research Transactions, 2023 , 27(2) : 1 -26 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.02.001

References

1 黄正海, 林贵华, 修乃华. 变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展[J]. 运筹学学报, 2014, 18 (1): 113- 133.
2 宋一凡, 高自友. 求解连续平衡网络设计问题近似解的启发式算法[J]. 北方交通大学学报, 1998, 22 (6): 19- 24.
3 Bracken J , McGill J T . Mathematical programs with optimization problems in the constraints[J]. Operations Research, 1973, 21 (1): 37- 44.
4 Candler W, Norton R. Multilevel programming[R]. Technical Report 20, World Bank Development Research Center, 1977.
5 Von Stackelberg H . Market Structure and Equilibrium[M]. Berlin: Springer Science & Business Media, 2010.
6 LeBlanc L J . An algorithm for the discrete network design problem[J]. Transportation Science, 1975, 9 (3): 183- 199.
7 Abdulaal M , LeBlanc L J . Continuous equilibrium network design models[J]. Transportation Research Part B: Methodological, 1979, 13 (1): 19- 32.
8 Powell M J . An efficient method for finding the minimum of a function of several variables without using derivatives[J]. The Computer Journal, 1964, 7 (2): 155- 162.
9 Hooke R , Jeeves T A . Direct search solution of numerical and statistical problems[J]. Journal of the Association for Computing Machinery, 1961, 8 (2): 212- 229.
10 LeBlanc L J , Boyce D E . A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows[J]. Transportation Research Part B: Methodological, 1986, 20 (3): 259- 265.
11 Bard J F , Falk J E . An explicit solution to the multi-level programming problem[J]. Computers & Operations Research, 1982, 9 (1): 77- 100.
12 Bard J F . An algorithm for solving the general bilevel programming problem[J]. Mathematic of Operations Research, 1983, 8 (2): 260- 272.
13 Migdalas A . Bilevel programming in traffic planning: models, methods and challenge[J]. Journal of Global Optimization, 1995, 7 (4): 381- 405.
14 Wardrop J G . Some theoretical aspects of road traffic research[J]. Proceedings of the Institution of Civil Engineers, 1952, 1 (3): 325- 362.
15 Chen Y. Bilevel programming problems: analysis, algorithms and applications[D]. Montreal: Université de Montréal, 1994.
16 Chen Y , Florian M . The nonlinear bilevel programming problem: formulations, regularity and optimality conditions[J]. Optimization: A Journal of Mathematical Programming and Operations Research, 1995, 32 (3): 193- 209.
17 Florian M , Chen Y . A coordinate descent method for the bi-level o-d matrix adjustment problem[J]. International Transactions in Operational Research, 1995, 2 (2): 165- 179.
18 Meng Q. Bilevel transportation modeling and optimization[D]. Hong Kong: Hong Kong University of Science and Technology, 2000.
19 Meng Q , Yang H , Bell M G H . An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem[J]. Transportation Research Part B: Methodological, 2001, 35 (1): 83- 105.
20 Meng Q , Yang H . Benefit distribution and equity in road network design[J]. Transportation Research Part B: Methodological, 2002, 36 (1): 19- 35.
21 Yang H , Meng Q . Highway pricing and capacity choice in a road network under a build-operate-transfer scheme[J]. Transportation Research Part A: Policy and Practice, 2000, 34 (3): 207- 222.
22 Meng Q , Yang H , Wong S C . A combined land-use and transport model for work trips[J]. Environment and Planning B: Planning and Design, 2000, 27 (1): 93- 103.
23 Yang H , Meng Q , Bell M G H . Simultaneous estimation of the origin-destination matrices and travel-cost coefficient for congested networks in a stochastic user equilibrium[J]. Transportation Science, 2001, 35 (2): 107- 123.
24 Meng Q , Lee D H , Yang H , et al. Transportation network optimization problems with stochastic user equilibrium constraints[J]. Transportation Research Record: Journal of the Transportation Research Board, 2004, 1882, 113- 119.
25 孟强, 李德宏. 交通双层规划问题: 统一数学模型及其算法[J]. 交通运输系统工程与信息, 2005, 5 (4): 120- 140.
26 Yang H , Bell M G H . Transport bilevel programming problems: recent methodological advances[J]. Transportation Research Part B: Methodological, 2001, 35 (1): 1- 4.
27 Yang H , Bell M G H . Models and algorithms for road network design: a review and some new developments[J]. Transport Reviews, 1998, 18 (3): 257- 278.
28 Friesz T L , Shah S . An overview of nontraditional formulations of static and dynamic equilibrium network design[J]. Transportation Research Part B: Methodological, 2001, 35 (1): 5- 21.
29 Maher M J , Zhang X Y , Vliet D . A bi-level programming approach for trip matrix estimation and traffic control problems with stochastic user equilibrium link flows[J]. Transportation Research Part B: Methodological, 2001, 35 (1): 23- 40.
30 Clegg J , Smith M , Xiang Y L , et al. Bilevel programming applied to optimising urban transportation[J]. Transportation Research Part B: Methodological, 2001, 35 (1): 41- 70.
31 Clegg J , Smith M J . Cone projection versus half-space projection for the bilevel optimization of transportation networks[J]. Transportation Research Part B: Methodological, 2001, 35 (1): 71- 82.
32 高自友, 张好智, 孙会君. 城市交通网络设计问题中双层规划模型、方法及应用[J]. 交通运输系统工程与信息, 2004, 4 (1): 35- 44.
33 Gao Z Y , Song Y F . A reserve capacity model of optimal signal control with user-equilibrium route choice[J]. Transportation Research Part B: Methodological, 2002, 36 (4): 313- 323.
34 Gao Z Y , Sun H J , Shan L L . A continuous equilibrium network design model and algorithm for transit systems[J]. Transportation Research Part B: Methodological, 2004, 38 (3): 235- 250.
35 Gao Z Y , Wu J J , Sun H Z . Solution algorithm for the bi-level discrete network design problem[J]. Transportation Research Part B: Methodological, 2005, 39 (6): 479- 495.
36 Farahani R Z , Miandoabchi E , Szeto W Y , et al. A review of urban transportation network design problems[J]. European Journal of Operational Research, 2013, 229 (1): 228- 302.
37 Zhao L J , Xu X , Gao H , et al. A bi-level model for GHG emission charge based on a continuous distribution of travelers' value of time (VOT)[J]. Transportation Research Part D: Transport and Environment, 2016, 47, 371- 382.
38 Jiang Y , Szeto W Y . Time-dependent transportation network design that considers health cost[J]. Transportmetrica A: Transport Science, 2015, 11 (1): 74- 101.
39 Zhang X , Waller S T . Implications of link-based equity objectives on transportation network design problem[J]. Transportation, 2019, 46 (5): 1559- 1589.
40 Li Z C , Ge X Y . Traffic signal timing problems with environmental and equity considerations[J]. Journal of Advanced Transportation, 2014, 48 (8): 1066- 1086.
41 Madadi B , Nes R , Snelder M , et al. Multi-stage optimal design of road networks for automated vehicles with elastic multi-class demand[J]. Computers and Operations Research, 2021, 136, 105483.
42 龙建成, 郭嘉琪. 动态交通分配问题研究回顾与展望[J]. 交通运输系统工程与信息, 2021, 21 (5): 125- 138.
43 Lin B L , Liu C , Wang H J , et al. Modeling the railway network design problem: a novel approach to considering carbon emissions reduction[J]. Transportation Research Part D: Transport and Environment, 2017, 56, 95- 109.
44 Liu T , Ceder A . Integrated public transport timetable synchronization and vehicle scheduling with demand assignment: a bi-objective bi-level model using deficit function approach[J]. Transportation Research Part B: Methodological, 2018, 117B, 935- 955.
45 Cancela H , Mauttone A , Urquhart M E . Mathematical programming formulations for transit network design[J]. Transportation Research Part B: Methodological, 2015, 77, 17- 37.
46 Yu B , Kong L , Sun Y , et al. A bi-level programming for bus lane network design[J]. Transportation Research Part C: Emerging Technologies, 2015, 55 (6): 310- 327.
47 Wang J P , Liu T L , Huang H J . Tradable od-based travel permits for bi-modal traffic management with heterogeneous users[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 118, 589- 605.
48 Zhao J , Yu J , Xia X M , et al. Exclusive bus lane network design: a perspective from intersection operational dynamics[J]. Networks and Spatial Economics, 2019, 19 (4): 1143- 1171.
49 Yu Y , Machemehl R B , Xie C . Demand-responsive transit circulator service network design[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 76, 160- 175.
50 Yang H , Yagar S . Traffic assignment and traffic control in general freeway-arterial corridor systems[J]. Transportation Research Part B: Methodological, 1994, 28 (6): 463- 486.
51 彭显玥, 王昊. 交通分配与信号控制组合优化研究综述[J]. 交通运输工程与信息学报, 2023, 21 (1): 1- 18.
52 Barnhart C , Johnson E L , Nemhauser G L , et al. Branch-and-price: column generation for solving huge integer programs[J]. Operations Research, 1998, 46 (3): 316- 329.
53 Erlander S , Nguyen S , Stewart N F . On the calibration of the combined distribution-assignment model[J]. Transportation Research Part B: Methodological, 1979, 13 (3): 259- 267.
54 Florian M , Nguyen S , Ferland J . On the combined distribution-assignment of traffic[J]. Transportation Science, 1975, 9 (1): 43- 53.
55 Nguyen S. Estimating an O-D matrix from network data: a network equilibrium approach[R]. Université de Montreal, Montréal, Canada, 1977.
56 Boyce D E , Janson B N . A discrete transportation network design problem with combined trip distribution and assignment[J]. Transportation Research Part B: Methodological, 1980, 14 (1-2): 147- 154.
57 Fisk C S , Boyce D E . A note on trip matrix estimation from link traffic count data[J]. Transportation Research Part B: Methodological, 1983, 17 (3): 245- 250.
58 楊海, 佐佐木綱. ネットワーク均衡に基づく観測リンクフローからのOD交通量推計法に関する検討[J]. 土木計画学研究論文集, 1991, 9, 29- 36.
59 Yang H , Iida Y , Sasaki T . The equilibrium-based origin-destination matrix estimation problem[J]. Transportation Research Part B: Methodological, 1994, 28 (1): 23- 33.
60 Yang H , Ssaki T , Iida Y , et al. Estimation of origin-destimation matrices from link traffic counts on congested networks[J]. Transportation Research Part B: Methodological, 1992, 26 (6): 417- 434.
61 楊海, 朝仓康夫, 飯田恭敬, 等. 交通混雑を考慮した観測リンク交通量からのOD交通量推計モデル[J]. 土木学会論文集, 1991, 440, 117- 124.
62 Yang H . Heuristic algorithms for the bilevel origin-destination matrix estimation problem[J]. Transportation Research Part B: Methodological, 1995, 29 (4): 231- 242.
63 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: Methodological, 1991, 25 (5): 351- 363.
64 Castillo E , Grande Z , Calvino A , et al. A state-of-the-art review of the sensor location, flow observability, estimation, and prediction problems in traffic networks[J]. Journal of Sensors, 2015, 903563
65 Owais M . Traffic sensor location problem: three decades of research[J]. Expert Systems with Applications, 2022, 1, 118134.
66 Drissi-Kaitouni O, Lundgren J T. Bilevel origin-destination matrix estimation using a descent approach[R]. Linkoping, Sweden: Linkoping Institute of Technology, 1992.
67 Spiess H. A gradient approach for the O-D matrix adjustment problem[R]. Montreal, Canada: Universite de Montreal, 1990.
68 Lundgren J T , Peterson A . A Heuristic for the bilevel origin-destination-matrix estimation problem[J]. Transportation Research Part B: Methodological, 2008, 42 (4): 339- 354.
69 Menon A K , Cai C , Wang W H , et al. Fine-grained od estimation with automated zoning and sparsity regularization[J]. Transportation Research Part B: Methodological, 2015, 80, 150- 172.
70 Wang J X , Lu S , Liu H S , et al. Transportation origin-destination estimation with quasi-sparsity[J]. Transportation Science, 2023, 57 (2): 289- 312.
71 Maher M J . Inferences on trip matrices from observations on link volumes: a Bayesian statistical approach[J]. Transportation Research Part B: Methodological, 1983, 17 (6): 435- 447.
72 Hazelton M L . Estimation of origin-destination matrices from link flows on uncongested networks[J]. Transportation Research Part B: Methodological, 2000, 34 (7): 549- 566.
73 Shao H , Lam W H K , Sumalee A , et al. Estimation of mean and covariance of peak hour origin-destination demands from day-to-day traffic counts[J]. Transportation Research Part B: Methodological, 2014, 68, 52- 75.
74 焦朋朋, 陆化普, 杨姗姗. 动态OD反推理论中的关键问题研究[J]. 公路交通科技, 2004, 21 (12): 93- 95.93-95 102
75 Ashok K. Estimation and prediction of time-dependent origin-destination flows[D]. Cambridge: Massachusetts Institute of Technology, 1996.
76 Tavana H. Internally-consistent estimation of dynamic network origin-destination flow from intelligent transportation systems data using bi-level optimization[D]. Austin: The University of Texas at Austin, 2001.
77 Zhou X S , Taylor J . DTALite: a queue-based mesoscopic traffic simulator for fast model evaluation and calibration[J]. Cogent Engineering, 2014, 1 (1): 961345.
78 Zhou X S. Dynamic origin-destination demand estimation and prediction for off-line and on-line dynamic traffic assignment operation[D]. City of College Park: University of Maryland, 2004.
79 Bert M. Urban origin-destination matrix estimation methodology[D]. Lausanne: école Polytechnique Fédérale de Lausanne, 2009.
80 Chi H. An improved framework for dynamic origin-destination (o-d) matrix estimation[D]. Miami: Florida International University, 2010.
81 Nie Y , Zhang H M . A variational inequality formulation for inferring dynamic origin-destination travel demands[J]. Transportation Research Part B: Methodology, 2008, 42 (7-8): 635- 662.
82 Ros-Roca X , Montero L , Barcelo J , et al. A practical approach to assignment-free dynamic origin-destination matrix estimation problem[J]. Transportation Research Part C: Emerging Technologies, 2022, 134, 103477.
83 Bard J F . Practical Bilevel Optimization Algorithms and Applications[M]. Dordrecht: Kluwer Academic Publishers, 1998.
84 Dempe S . Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints[J]. Optimization: A Journal of Mathematical Programming and Operations Research, 2003, 52 (3): 333- 359.
85 Colson B , Marcotte P , Savard G . An overview of bilevel optimization[J]. Annals of Operations Research, 2007, 153 (1): 235- 256.
86 王广民, 万仲平, 王先甲. 二(双) 层规划综述[J]. 数学进展, 2007, 36 (5): 513- 529.
87 Dempe S , Zemkoho A . Bilevel Optimization: Advances and Next Challenges[M]. Springer, 2020.
88 孙小玲, 李端. 整数规划新进展[J]. 运筹学学报, 2014, 18 (1): 39- 68.
89 戴彧虹, 刘新为. 线性与非线性规划算法与理论[J]. 运筹学学报, 2014, 18 (1): 69- 92.
90 刘明明, 崔春风, 童小娇, 戴彧虹. 混合整数非线性规划的算法软件及最新进展[J]. 中国科学: 数学, 2016, 46 (1): 1- 20.
91 刘佳, 王先甲. 系统工程优化决策理论及其发展战略[J]. 系统工程理论与实践, 2020, 40 (8): 1945- 1960.
92 Kleinert T , Labbe M , Ljubic I , et al. A survey of mixed-integer programming techniques in bilevel optimization[J]. EURO Journal on Computational Optimization, 2021, 9, 100007.
93 Talbi E G . Metaheuristics for Bi-level Optimization[M]. Berlin: Springer, 2013.
94 Sinha A , Malo P , Deb K . A review on bilevel optimization: from classical to evolutionary approaches and applications[J]. IEEE Transactions on Evolutionary Computation, 2017, 22 (2): 276- 295.
95 Friesz T L , Tobin R L , Cho H J , et al. Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints[J]. Mathematical Programming, 1990, 48 (1-3): 265- 284.
96 Ban J X , Liu H X , Ferris M C , et al. A general MPCC model and its solution algorithm for continuous network design problem[J]. Mathematical and Computer Modelling, 2006, 43 (5-6): 493- 505.
97 Patriksson M . On the applicability and solution of bilevel optimization models in transportation science: a study on the existence, stability and computation of optimal solutions to stochastic mathematical programs with equilibrium constraints[J]. Transportation Research Part B: Methodological, 2008, 42 (10): 843- 860.
98 Li Q , Liao F . Incorporating vehicle self-relocations and traveler activity chains in a bi-level model of optimal deployment of shared autonomous vehicles[J]. Transportation Research Part B: Methodological, 2020, 140, 151- 175.
99 Xi H , Aussel D , Liu W , et al. Single-leader multi-follower games for the regulation of two-sided mobility-as-a-service markets[J]. European Journal of Operational Research, 2023,
100 Bao Z , Xie C . Optimal station locations for en-route charging of electric vehicles in congested intercity networks: A new problem formulation and exact and approximate partitioning algorithms[J]. Transportation Research Part C: Emerging Technologies, 2021, 133, 103447.
101 Wang J , Wang W , Ren G , et al. Worst-case traffic assignment model for mixed traffic flow of human-driven vehicles and connected and autonomous vehicles by factoring in the uncertain link capacity[J]. Transportation Research Part C: Emerging Technologies, 2022, 140, 103703.
102 Adler N , Brudner A , Proost S . A review of transport market modeling using game-theoretic principles[J]. European Journal of Operational Research, 2021, 291 (3): 808- 829.
103 王坤峰, 苟超, 段艳杰, 等. 生成式对抗网络GAN的研究进展与展望[J]. 自动化学报, 2017, 43 (3): 321- 332.
104 王龙, 黄锋. 多智能体博弈、学习与控制[J]. 自动化学报, 2023, 49 (3): 580- 613.
105 张毅, 裴华鑫, 姚丹亚. 车路协同环境下车辆群体协同决策研究综述[J]. 交通运输工程学报, 2022, 22 (3): 1- 18.
106 Sherali H D , Soyster A L , Murphy F H . Stackelberg-Nash-Cournot equilibria: Characterizations and computations[J]. Operations Research, 1983, 31 (2): 253- 276.
107 Sherali H D , Sivanandan R , Hobeika A . A linear programming approach for synthesizing origin-destination trip tables from link traffic volumes[J]. Transportation Research Part B: Methodological, 1994, 28 (3): 213- 233.
108 Bell M G H , Shield C M , Busch F , et al. A stochastic user equilibrium path flow estimator[J]. Transportation Research Part C: Emerging Technologies, 1997, 5 (3-4): 197- 210.
109 Sherali H D , Park T Y . Estimation of dynamic origin-destination trip tables for a general network[J]. Transportation Research Part B: Methodological, 2001, 35 (3): 217- 235.
110 Nie Y , Zhang H M , Recker W W . Inferring origin-destination trip matrices with a decoupled GLS path flow estimator[J]. Transportation Research Part B: Methodological, 2005, 39 (6): 497- 518.
111 Lu C C , Zhou X S , Zhang K L . Dynamic origin-destination demand flow estimation under congested traffic conditions[J]. Transportation Research Part C: Emerging Technologies, 2013, 34, 16- 37.
112 Tong L , Zhou X S , Mill H J . Transportation network design for maximizing space-time accessibility[J]. Transportation Research Part B: Methodological, 2015, 81 (2): 555- 576.
113 Liu J T , Zhou X S . Capacitated transit service network design with boundedly rational agents[J]. Transportation Research Part B: Methodological, 2016, 93 (A): 225- 250.
114 Qu Y C , Zhou X S . Large-scale dynamic transportation network simulation: a space-time-event parallel computing approach[J]. Transportation Research Part C: Emerging Technologies, 2017, 75, 1- 16.
115 Li P F , Zhou X S . Recasting and optimizing intersection automation as a connected-and-automated-vehicle (CAV) scheduling problem: a sequential branch-and-bound search approach in phase-time-traffic hypernetwork[J]. Transportation Research Part B: Methodological, 2017, 105, 479- 506.
116 Wu X , Guo J F , Xian K , et al. Hierarchical travel demand estimation using multiple data sources: a forward and backward propagation algorithmic framework on a layered computational graph[J]. Transportation Research Part C: Emerging Technologies, 2018, 96, 321- 346.
117 Yao Y , Zhu X N , Dong H Y , et al. ADMM-based problem decomposition scheme for vehicle routing problem with time windows[J]. Transportation Research Part B: Methodological, 2019, 129, 156- 174.
118 Wu X , Lu J W , Wu S N , et al. Synchronizing time-dependent transportation services: reformulation and solution algorithm using quadratic assignment problem[J]. Transportation Research Part B: Methodological, 2021, 152, 140- 179.
119 LeBlanc L J , Morlok E K , Pierskalla W P . An efficient approach to solving the road network equilibrium traffic assignment problem[J]. Transportation Research, 1975, 9 (5): 309- 318.
120 Frank M , Wolfe P . An algorithm for quadratic programming[J]. Naval Research Logistics Quarterly, 1956, 3 (1-2): 95- 110.
121 Fisk C S . Game theory and transportation systems modelling[J]. Transportation Research Part B: Methodological, 1984, 18 (4-5): 301- 313.
122 Nash J . Non-cooperative games[J]. Annals of Mathematics, 1951, 54 (2): 286- 295.
123 Smith M J . The existence, uniqueness and stability of traffic equilibria[J]. Transportation Research Part B: Methodological, 1979, 13 (4): 295- 304.
124 Zukhovitskii S I , Poliak R A , Primak M E . Concave multiperson games: numerical methods[J]. Ekonomika I Matematicheskie Metody, 1971, 6, 10- 30.
Options
Outlines

/

〈 〉