交通双层规划问题:统一数学模型及其算法

摘要/Abstract

摘要： 主要讨论基于用户平衡原则的交通网络优化问题。这些问题大致上可以分为二大类:一类是涉及到确定性用户平衡原则；另一类是考虑随机性用户平衡原则。众所周知，运筹学中的双层规划模型能够完美地刻画这些问题，但是所建立的双层优化模型往拄属于不可微优化问题的范畴，这就给设计有效的算法带来了很大困难.此文首先从模型和算法的角度总结了有关这类问题已有的研究成果，接着介绍有关这方面的最新的研究进展，即如何把用户基于平衡原则下的交通网络优化问题的双层规划模型统一地转换为一个连续可微的单层最优化问题，并设计统一的算法。作为统一的算法方面的研究，我们可以看到增广的拉格朗日方法可以用来解上述的第一类问题，而基于灵敏度的分析的序列二次规划方法完全有能力解上述的第二类问题。

关键词: 交通双层规划问题, 最优化问题, 用户平衡原则, 统一数学模型, 统一算法

Abstract: This paper is concerned with a class of transport bilevel programming problems investigated by analytical analysis approaches. It begins with a state-of-art review on transport bilevel programming problems taking into account behavior of network users’ routing choice. These problems in reality can be classifies into two major categories: transport bilevel programming problems with deterministic user equilibrium constraints and transport bilevel programming problems with stochastic user equilibrium constraints. It is well recognized that the bilevel programming model or mathematical program with equilibrium constraints as unified modeling approach can perfectly characterize these two categories of problems. Nevertheless, induced bilevel programming models for the former category usually belong to a subject of nondifferentiable optimization problems, whereas that for the latter category becomes the continuously differentiable optimization problems. It should be pointed out that designing an efficient solution method for a nondifferentiable optimization problem is not an easy task. This study thus introduces the recent unified modeling approach for the problems in the preceding category, which aims at transforming a bilevel programming model into a single level continuously differentiable optimization problem. As unified algorithms, it can be seen that the augmented Lagrangian method and sequential quadratic programming method based on the sensitivity analysis for the stochastic user equilibrium problem are capable of solving any problem in the first and second categories. Finally, three examples are provided to demonstrate the unified continuously differentiable optimization approach.

Key words: transportation bilevel programming problems, optimization problems, user equilibrium principle, unified Models, unified algorithms

孟强,李德宏. 交通双层规划问题:统一数学模型及其算法[J]. 交通运输系统工程与信息, 2005, 5(4): 120-140 .

MENG Qiang, LI De-hong. Transport Bilevel Programming Problems: Unified Models and Algorithms[J]. Journal of Transportation Systems Engineering and Information Technology, 2005, 5(4): 120-140 .

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract17317.shtml

http://www.tseit.org.cn/CN/Y2005/V5/I4/120

参考文献

[1] Abdulaal, M. and LeBlanc, L. J. (1979) Continuous equilibrium network design models. Transportation Research, 13B,19-32.
[2] Akamatsu, T.(1997) Decomposition of path choices entropy in general transportation networks. Transportation Science, 81, 349-362.
[3] Akamatsu, T. and Miyawaki, O. (1995) Maximum network capacity problem under the transportation equilibrium assignment. Infrastructure Planning Review, 12, 719-729 In Japanese).
[4] Asakura, Y. (1992) Maximum capacity of road network constrained by user equilibrium conditions. Paper presented at the 24th Annual Conference of the UTSG.
[5] Bard, J. F. (1998) Practical Bilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, Dordrecht, the Netherlands.
[6] Bell, M. G. H. (1995) Alternative to dial’s logit as signment algorithm. Transportation Research, 29B, 287-295.
[7] Bell, M. G. H. and lida, Y. (1997) Transportation Network Analysis.} John Wiley & Sons Ltd.
[8] Bergendrorff, P.，Hearn, D. W. and Ramanda, M.V . (1997) Congestion Toll Pricing of Traffic Networks, in Network Optimization, Lecture Notes in Economics and Mathematical Systems 450, P. M. Pardslos, D. W. Heard and W. W. Hager (eds), pp. 52-71.
[9] Berkseaks, D. P. (1982) Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York.
[10] Bertsekas, D.，Nonlinear Programming. Athena Scientific (1999).
[11] Boggs, P. T. and Tolle, J. W. (1995) Sequential quadratic programming. Acts Numerica,1-51.
[12] Chen, Y. (1992) Bilevel Programming Problems: Analysis, Algorithms and Applications. Ph. D. Dissertation, University de Montreal, Montreal, Canada.
[13] Chian, S- W (1999) Optimization of area traffic control for equilibrium network flows. Transportation Science, 33, 279-289.
[14] Cho, H.-J.，Smith, T. E. and Fries, T. L. (2000) A reduction method for local sensitivity analysis of network equilibrium are flows. Transportation Research, 34B, 31-51.
[15] Cho, H-J. (1988) Sensitivity Analysis of Equilibrium Network Flows and Its Application to the Development of Solution Methods for Equilibrium Network Design Problems. PhD dissertation, University of Pennsylvania, Philadelphia.
[16] Clark, S. D. and Waiting, D. P. (2002) Sensitivity analysis of the probit-based stochastic user equilibrium assignment model. Transportation Research, 36B, 617-635.
[17] Daganzo, C. F. (1979) Multinomial Probit: the Theory and Its Application to Demand Forecasting. Academic Press, New York.
[18] Dagans, C. F. (1982) Unconstrained extremal formulation of some transportation equilibrium problems. Transportation Science, 16, 332-361.
[19] Davis, G. A. (1994) Exact local solution of the continuous network design problem via stochastic user equilibrium assignment. Transportation Research, 28B, 61-75.
[20] Dempe, S. (2002) Foundation of Bilevel Programming. Klumer Academic Publishers, Dordrecht, the Netherlands.
[21] Dial, R. B. (1971) A probabilistic multipath traffic assignment model. Which obviates the need of path enumeration . Transportation Science, 5,83-111.
[22] Dial,R .B . (2002) Minimal-revenue congestion pricing: part II: an efficient algorithm for the general case. Transportation Research,34B, 645-665 .
[23] Ferrari, P.(1995) Road pricing and network equilibrium. Transportation Research, 29B,357-372.
[24] Fisk, C. S. (1980) Some developments in equilibrium traffic assignment methodology. Transportation Research, 11B, 253-274.
[25] Fisk, C. S. (1984) Optimal signal controls on congested networks. Proceedings of the Ninth International Symposium on Transportation and Traffic Theory, VNU Science Press, Delft, the Netherlands, pp. 197-216.
[26] Fisk, C. S. (1989) Trip matrix estimation from link traffic counts: the congested network case. Transportation Research, 17B, 245-250.
[27] Florian, M. and Hearn, D. (1995)Network Equilibrium Models and Algorithms. Handbooks in Operations Research and Management Science Vol. 8: Network Routing, Ball, M. O.，Magnanti, T. L. ， Monma , C. L. and Nemhauser, G. L. (eds), Elsevier Science B. V.、pp.485-542.
[28] Fries.,T. L.，Anandalingam, G.，Mehts, N. J.， Nam, K. , Shah, S. J. and Tobin, R. L. (1993) The multiobjective equilibrium network design problem revisited: a simulated annealing approach. European Journal of Operational Research, 65, 44-57.
[29] Fukushima, M. (1992) Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Mathematical Programming, 53, 99-110.
[30] Gang, Z. Y. and Song, Y. F. (2002) A reserved capacity model of optimal signal control with user equ ilibrium route choice. Transportation Research, 36B, 313-323.
[31] Ga rtner, N. H.，Gershwin. S. B..Little, J. D. c. and Ross, P. (1980) Pilot study of computer-based urban traffic management. Transportation Research, 14B, 203-217.
[32] Gauvin, J. and Dubeau, F. (1982) Differentiable properties of the marginal function in mathematical. programming. Mathematical Programming Study. 19, 101-119.
[33] Huang, H.-J., Wang, S. and Belt, M. G. H. (2001) A bi-level formulation and quasi-newton algorithm for stochastic equilibrium network design problem with elastic demand [J]. Journal of Systems Science and Complexity, 14, 40-53.
[34] Iida, Y.，Hasegawa, T.，Asakura, Y. and Sho, C. F. (1989) A formulation of on-ramp traffic control system with route guidance for urban expressway. IFAC/IFFIP/IFORS/-Six International Conference on Control in Transportation System, Frances, Pairs, July, pp229-236.
[35] LeBlanc, L. J. (1975) An algorithm for discrete network design problem, Transportation Science9, 183-199.
[36] Leurent, L.(1998) Sensitivity and error analysis of the dual criteria traffic assignment model. Transportation Research. 32B. 189-204.
[37] Lim, A. C. (2002)Transportation Network Design Problems; An MPEC Approach. Department of Mathematical Science, Johns Hopkins University.
[38] Liu, S. and Fricker, J. D. (1996) Estimation of a trip table and the parameter in a stochastic network. Transportation Research. 30A. 87-305.
[39] Luo, Z. Q.，Pang, J. S. and Ralph. D. (1996) Mathematical Programs with Equilibrium Constraints. Cambridge University Press.
[40] Maher, M. 1.，Zhang. X. Y. and Van VIiet, D. (2001) A bi-level programming approach for trip matrix estimation and traffic control problems with stochastic user equilibrium link flows. Transportation Research. 35B. 23-40.
[41] Marcotte. P. (1986) Network design problem with congestion effects; a case of bilevel programming. Mathematical Programming, 34. 142-162.
[42] Marcotte. P. and Marquis, G. (1992) Efficient implementation of heuristics for the continuous network design problem. Annals of Operations Research, 34, 163-176.
[43] Meng, Q. (2000) Bilevel Transportation Modeling and Optimization. Ph.D. Dissertation, Department of Civil Engineering. Hong Kong University of Science & Technology.
[44] Meng, Q. and Yang, H. (2002.) A unified continuously differentiable approach for the transportation network optimization problems with user equilibrium constraints. Transportation Science (Submitted).
[45] Meng, Q. and Yang, H. (2002b) Benefit distribution and equity in road network design.Transportation Research 36B, 19-35.
[46] Meng, Q. and Yang, H. (2004) A unified continuously differentiable approach for the transportation network optimization problems. The CD-ROM of the 10th World Conference on Transportation Research, July 4-8, 2004, Istanbul. Turkey.
[47] Meng, Q.. Lee, D. H. and Chen, R. L. (2004a) Simultaneous estimating O-D matrix and calibrating link travel cost functions from traffic counts. Proceedings of the 8th International Conference on the Application of Advanced Technology in Transportation, 26-28 May, 2004 Beijing, China, pp. 56-60.
[48] Meng, Q ，Lee, D.-H.，Yang, H, and Huang, H. -J. (2004b) Transportation network optimization problems with stochastic user equilibrium constraints[J]. Journal of Transportation Research Record}(in press).
[49] Meng, Q., Wong, S. C. and Yang, H. (2000) A combined land-use and transportation model for work trips. Environment and Planning B.27,93-103.
[50] Meng, Q.，Yang, H. and Bell. M. G. H. (2001) An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transportation Research,35B, 83-105.
[51] Migdalas, A. (1995) Bilevel programming in traffic planning: models, methods and challenge[J]. Journal of Global Optimization, 7,381-405.
[52] Nguyen, S. (1977) Estimating an O-D Matrix from Network Data: A Network Equilibrium Approach: Publication 87, Centre de recherche sur les Transportation, University de Montreal, Canada.
[53] Nguyen, S. (1984) Estimating Origin-Destination matrices from observed flow, In Transportation Planning Models. Florian, M. (Ed), pp.363-380.
[54] Outrata, J. V. (1997) On a special class of mathematical programs with equilibrium constraints. Lecture Notes in Economics and Mathematical System, 452, Springer-Verlag, Berlin, pp. 246-260.
[55] Outrata. J. V.，Kocvara, M. and Zowe. J.(1998) Non-smooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Application and Numerical Results. Kluwer Academic Pubbsbers, Dordrecht, the Netherlands.
[56] Patriksson, M.(1994) The Traffic Assignment Problems, Models and Methods. VSP. Utrecht. the Netherlands.
[57] Patriksson. M. (2004)Sensitivity analysis of traffic equilibria. Transportation Science 38, 258-28l.
[58] Patriksson, M. and Rockafellar, R. T. (2002) A mathematical model and descent algorithm for bilevel traffic management. Transportation Science, 36, 271-291.
[59] Patriksson, M. and Rockafellar, R. T. (2003) Sensitivity analysis of variational inequalities over aggregated polyhedra with applications to traffic equilibria. Transportation Science, 37, 56-68.
[60] Qiu, Y. and Magnanti, T. L. (1989) Sensitivity analysis for variational inequalities defined on polyhedral sets. Mathematics of Operations Research, 14, 410-432.
[61] Schittkowski, K. (2003) Personal Web Site of Schittkowski www.uni-bayreuth.de/departments/math/～kschittkowski/. Accessed 12 August 2003.
[62] Sheffi, Y. (1985) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Englewood Cliffs, NJ: Prentice-Hall.
[63] Shimizu, K.，Ishizuka, Y. and Bard, J. F. (1997) Nondifferentiable and Two-level Mathematical Programming. Klumer Academic Publishers Boston.
[64] Suwansirikul, C.，Friesz, T. I.and Tobin, R. L. (1987) Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem. Transportation Science, 21, 254-263.
[65] Tam, M. L. and Lam. W. H. K(2000) Maximum car ownership under constraints of road capacity and parking space. Transportation Research. 34A, 145-170.
[66] Tan. H,，Gershwin, S. and Athans M. (1979) Hybrid Optimization in Urban Traffic Networks.MIT Report DOT-TSC-RSPA-79-7.
[67] Tobin, R. L. and Fries, T. L. (1988) Sensitivity analysis for equilibrium network flows Transportation Science, 22, 242-250.
[68] Wong S. C. and Yang H. (1997) Reserve capacity of a signal-controlled road network, Transportation Research, 31B, 397-402.
[69] Xu G. and Lam W. H. K. an d Chan, K. S.(2002) An integrated approach for trip matrix estimation and network calibration[J]. Journal of Transportation Engineering. 130, 231-244.
[70] Yang. H.(1991)Estimating Origin-Destination Matrices From Traffic Counts in Congested Networks. Doctoral Dissertation, Kyoto University, Japan.
[71] Yang, H. and Bell,M . G.H.(1997) Traffic restraint, road pricing and network equilibrium Transportation Research, 31B, 303-314.
[72] Yang,H .and Latn,W. H. K. (1996) Optimal Road Tolls under Conditions of Queuing and Congestion. Transportation Research, 30A, 319-332.
[73] Yang, H. and Meng, Q. (2000) Highway pricing and capacity choice in a road network under a build-operate-transfer scheme. Transportation Research, 34A,207-222.
[74] Yang, H. and Yagar, S. (1994) Traffic assignment and traffic control in general freewayarterial corridor systems. Transportation Research, 28B, 463-486.
[75] Yang, H. and Yagar, S. (1995) Traffic assignment and signal control in saturated road network, Transportation Research, 29A, 125-139.
[76] Yang,R. and Zhang, X. Z. (2002) Multiclass network toll design problem with social and spatial equity constraints[J]. Journal of Transportation Engineering, ASCE, 128, 420-428.
[77] Yang, H.，Bell, M. G. H. and Meng, Q. (2000) Modeling the capacity and level of service of urban transportation networks. Transportation Research, 34B, 255-275.
[78] Yang, H.，Meng, Q. and Bell, M. G. H. (2001) Simultaneous estimation origin-destination matrices and travel-cost coefficient in congested stochastic networks. Transportation Science, 35, 107-123.
[79] Yang, H.，Meng, Q. and Liu G. S. (2005) Reformulating and solving a class of transportation network optimization problems with user equilibrium constraints. The IFORS Triennial 2005 Conference, 11-15 July 2005, Hilton Hawaii Village, Hawaii, United States. (Submitted).
[80] Yen, N. D. (1995) Lipschitz continuity of solutions of variational inequalities with a parametric polyhedral constraint. Mathematics of Operations Research}, 20, 695-708.
[81] Yin, Y. (2000) Genetic-algorithm-baaed approach for bilevel programming models. ASCE Journal of Transportation Engineering, 126, 115-120.
[82] Ying, J. Q. and Miyagi, T. (2001) Sensitivity analysis for stochastic user equilibrium network flows-a dualapproach. Transportation Science, 35, 24-133.
[83] Zhang, X. N. (2003) OptimalR oad Pricing in Transportation Networks. Ph. D. Dissertation, Department of Civil Engineering, Hong Kong University of Science & Technology.
[84] Zhang, Y.-F. (1994) Parameter Estimation for Combined Models Of Urban Travel Choices Consistent with Equilibrium Travel Costs. Ph. D. Dissertation, Department of Civil Engineering, University of Illinois at Chicago.