zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A globally convergent algorithm for transportation continuous network design problem. (English) Zbl 1175.90061
Summary: The Continuous Network Design Problem (CNDP) is characterized by a bilevel programming model, in which the upper level problem is generally to minimize the total system cost under limited expenditure, while at the lower level the network users make choices with regard to route conditions following the user equilibrium principle. In this paper, the bilevel programming model for CNDP is transformed into a single level convex programming problem by virtue of an optimal-value function tool and the relationship between System Optimum (SO) and User Equilibrium (UE). By exploring the inherent nature of the CNDP, the optimal-value function for the lower level user equilibrium problem is proved to be continuously differentiable and its derivative in link capacity enhancement can be obtained efficiently by implementing user equilibrium assignment subroutine. However, the reaction (or response) function between the upper and lower level problem is implicit and its gradient is difficult to obtain. Although, here we approximately express the gradient with the difference concept at each iteration, based on the Method of Successive Averages (MSA), we propose a globally convergent algorithm to solve the single level convex programming problem. Comparing with widely used heuristic algorithms, such as Sensitivity Analysis Based (SAB) method, the proposed algorithm needs not strong hypothesis conditions and complex computation for the inverse matrix. Finally, a numerical example is presented to compare the proposed method with some existing algorithms.

90B10Network models, deterministic (optimization)
90B06Transportation, logistics
90C90Applications of mathematical programming
Full Text: DOI
[1] Abdulaal M, LeBlanc LJ (1979) Continuous equilibrium network design models. Transp Res B 13:19--32 · Zbl 0398.90042 · doi:10.1016/0191-2615(79)90004-3
[2] Boyce DE (1984) Urban transportation network equilibrium and design models: recent achievements and future prospectives. Environ Plan A 16:1445--1474 · doi:10.1068/a161445
[3] Chiou SW (1999) Optimization of area traffic control for equilibrium network flows. Transp Sci 33:279--289 · Zbl 1004.90014 · doi:10.1287/trsc.33.3.279
[4] Cho HJ (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
[5] Cree ND, Maher MJ (1998) The continuous equilibrium optimal network design problem: a genetic approach. In: Transportation networks: recent methodological advances. Elsevier, Netherlands, pp 163--174
[6] Dafermos S (1980) Traffic equilibria and variational inequalities. Transp Sci 14:42--54 · doi:10.1287/trsc.14.1.42
[7] Dafermos S, Nagurney A (1984) Sensitivity analysis for the asymmetric network equilibrium problem. Math Program 28:174--184 · Zbl 0535.90038 · doi:10.1007/BF02612357
[8] Friesz TL (1981) An equivalent optimization problem with combined multiclass distribution assignment and modal split which obviates symmetry restriction. Transp Res B 15:361--369 · doi:10.1016/0191-2615(81)90020-5
[9] Friesz TL (1985) Transportation network equilibrium, design and aggregation: key developments and research opportunities. Transp Res A 19:413--427 · doi:10.1016/0191-2607(85)90041-X
[10] Friesz TL, Harker PT (1985) Properties of the iterative optimization equilibrium algorithm. Civ Eng Syst 2:142--154 · doi:10.1080/02630258508970398
[11] Friesz TL et al (1990) Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. Math Program 48:265--284 · Zbl 0723.90070
[12] Friesz TL et al (1993) The multiobjective equilibrium network design problem revisited: a simulated annealing approach. Eur J Oper Res 65:44--57 · Zbl 0772.90043 · doi:10.1016/0377-2217(93)90143-B
[13] Gao ZY, Song YF (2002) A reserve capacity model of optimal signal control with user-equilibrium route choice. Transp Res B 36:313--323 · doi:10.1016/S0191-2615(01)00005-4
[14] Gao ZY, Song YF Si BF (2000) Urban transportation continuous equilibrium network design problem: theory and method. China Railway Press, Beijing
[15] Gao ZY, Wu JJ, Sun HJ (2005) Solution algorithm for the bi-level discrete network design problem. Transport Res B 39:479--495 · doi:10.1016/j.trb.2004.06.004
[16] Kim TJ (1990) Advanced transport and spatial systems models: applications to Korea. Springer, New York
[17] Kim TJ, Suh S (1988) Toward developing a national transportation planning model: a bilevel programming approach for Korea. Ann Reg Sci XXSPED:65--80 · doi:10.1007/BF01952844
[18] Luo ZQ, Pang JS, Ralph D (1996) Mathematical programs with equilibrium constraints. Cambridge University Press, Cambridge
[19] Magnanti TL, Wong RT (1984) Network design and transportation planning: models and algorithms. Transp Sci 18:1--55 · doi:10.1287/trsc.18.1.1
[20] Mangasarian OL, Rosen JB (1964) Inequalities for stochastic nonlinear programming problems. Oper Res 12:143--154 · Zbl 0132.13806 · doi:10.1287/opre.12.1.143
[21] Marcotte P (1983) Network optimization with continuous control parameters. Transp Sci 17:181--197 · doi:10.1287/trsc.17.2.181
[22] Marcotte P (1986) Network design problem with congestion effects: a case of bi-level programming. Math Program 34:142--162 · Zbl 0604.90053 · doi:10.1007/BF01580580
[23] Marcotte P, Marquis G (1992) Efficient implementation of heuristics for the continuous network design problem. Ann Oper Res 34:163--176 · Zbl 0756.90037 · doi:10.1007/BF02098178
[24] Marcotte P, Zhu DL (1996) Exact and inexact penalty methods for the generalized bilevel programming problems. Math Program 74:141--157 · Zbl 0855.90120
[25] Meng Q, Yang H, Bell MGH (2001) An equivalent continuously differentiable model and a locally convergent algorithm for the continuous networks design problem. Transp Res B 35:83--105 · doi:10.1016/S0191-2615(00)00016-3
[26] Patriksson M (1994) The traffic assignment problem models and methods. VSB BV, Netherlands
[27] Powell WB, Sheffi Y (1982) The convergence of equilibrium algorithms with predetermined step size. Transp Sci 6:5--55
[28] Rockafellar RT (1970) Convex analysis. Princeton University Press, Princeton · Zbl 0193.18401
[29] Sheffi Y (1985) Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice--Hall, Englewood Cliffs
[30] Shimizu K, Ishizuka Y, Bard JF (1997) Nondifferentiable and two-level mathematical programming. Kluwer Academic, Massachusetts · Zbl 0878.90088
[31] Suwansirikul C, Friesz TL, Tobin RL (1987) Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem. Transp Sci 21:254--263 · Zbl 0638.90097 · doi:10.1287/trsc.21.4.254
[32] Tan HN, Gershwin SB, Athans M (1979) Hybrid optimization in urban traffic networks. Report No. DOT-TSC-RSPA-79-7. Laboratory for Information and Decision System, MIT, Cambridge, MA
[33] Tobin RL, Friesz TL (1988) Sensitivity analysis for equilibrium network flows. Transp Sci 22:242--250 · Zbl 0665.90031 · doi:10.1287/trsc.22.4.242
[34] Wong SC, Yang H (1997) Reserve capacity of a signal-controlled road network. Transp Res Part B 31:397--402 · doi:10.1016/S0191-2615(97)00002-7
[35] Yang H (1995) Sensitivity analysis for queuing equilibrium network flow and its application to traffic control. Math Comput Model 22:247--258 · Zbl 0838.90041
[36] Yang H (1997) Sensitivity analysis for the elastic demand network equilibrium problem with applications. Transp Res B 31:55--70 · doi:10.1016/S0191-2615(96)00015-X
[37] Yang H, Bell MGH (1998) Models and algorithm for road network design: a review and some new developments. Transp Rev 18(3):257--278 · doi:10.1080/01441649808717016
[38] Yang H, Yagar S (1994) Traffic assignment and traffic control in general freeway-arterial corridor systems. Transp Res B 28:463--486 · doi:10.1016/0191-2615(94)90015-9
[39] Yang H, Meng Q, Liu GS (2004) The generalized transportation network optimization problem: models and algorithms. Working Paper, The Hong Kong University of Science and Technology