Abstract
Recently much attention has been focused on multilevel programming, a branch of mathematical programming that can be viewed either as a generalization of min-max problems or as a particular class of Stackelberg games with continuous variables. The network design problem with continuous decision variables representing link capacities can be cast into such a framework. We first give a formal description of the problem and then develop various suboptimal procedures to solve it. Worst-case behaviour results concerning the heuristics, as well as numerical results on a small network, are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
H.A. Aashtiani and T.L. Magnanti, “Equilibria on a congested transporation network“,SIAM Journal on Algebraic and Discrete Methods 2 (1981) 213–226.
M. Abdulaal and L.J. LeBlanc, “Continuous equilibrium network design models“,Transportation Research B 13B (1979) 19–32.
J.F. Bard, “An Algorithm for solving the general bilevel programming problem“,Mathematics of Operations Research 8 (1983) 260–272.
J.F. Bard and J.E. Falk, “An explicit solution to the multilevel programming problem“,Computers and Operations Research 9 (1982) 77–100.
D. Bertsekas and E.M. Gafni, “Projection methods for variational inequalities with application to the traffic assignment problem“,Mathematical Programming Study 17 (1982) 139–159.
W.F. Bialas and M.H. Karwan, “On two-level optimization“,IEEE Transactions on Automatic Control AC-27 (1982) 211–214.
J.W. Blankenship and J.E. Falk, “Infinitely constrained optimization problems“,Journal of Optimization Theory and Applications 19 (1976) 261–281.
W. Candler and R.J. Townsley, “A linear two-level programming problem“,Computers and Operations Research 9 (1982) 59–76.
S.C. Dafermos, “Traffic assignment and resource allocation in transportation networks”, Ph.D. Dissertation, Johns Hopkins University (Baltimore, Maryland, 1968).
S.C. Dafermos, “Traffic equilibrium and variational inequalities“,Transportation Science 14 (1980) 42–54.
C. Daganzo, “Stochastic network equilibrium with multiple vehicle types and asymmetric, indefinite link cost Jacobians“,Transportation Science 17 (1983) 282–300.
G.B. Dantzig et al., “Formulating and solving the network design problem by decomposition“,Transportation Research B 13B (1979) 5–18.
R. Dionne and M. Florian, “Exact and approximate algorithms for optimal network design“,Networks 9 (1979) 37–50.
M. Florian, “An improved linear approximation algorithm for the network equilibrium (Packet Switching) problem”,Proceedings of the IEEE Conference on Decision and Control (1977), 812–818.
A. Haurie and P. Marcotte, “On the relationship between Nash and Wardrop equilibrium“,Networks 15 (1985) 295–308.
H.H. Hoang, “A computational approach to the selection of an optimal network“,Management Science 19 (1973) 488–498.
L.J. LeBlanc, “Mathematical programming algorithms for large scale network equilibrium and network design problems”, Ph.D. Dissertation, Northwestern University (Evanston, IL, 1973).
M. Los, “A discrete-convex programming approach to the simultaneous optimization of land-use and transportation“,Transportation Research B 13B (1979) 33–48.
P. Marcotte, “Network optimization with continuous control parameters“,Transportation Science 17 (1983) 181–197.
P. Marcotte, “Design optimal d'un réseau de transport en présence d'effets de congestion”, Ph.D. Thesis, Université de Montréal (Montréal, Canada, 1981).
S. Nguyen, “An algorithm for the traffic assignment problem“,Transportation Science 8 (1974) 203–216.
G. Papavassilopoulos, “Algorithms for leader-follower games”,Proceedings of the 18th Annual Allerton Conference on Communication Control and Computing (1980) 851–859.
G. Papavassilopoulos, “Algorithms for static Stackelberg games with linear costs and polyhedral constraints”,Proceedings of the 21st IEEE Conference on Decisions and Control (1982) 647–652.
M.J. Smith, “The existence, uniqueness and stability of traffic equilibrium“,Transportation Research B 13B (1979) 295–304.
P.A. Steenbrink,Optimization of transportation networks (Wiley, New York, 1974).
H.N. Tan, S.B. Gershwin and M. Athans, “Hybrid optimization in urban traffic networks”, MIT Report DOT-TSC-RSPA-79–7 (1979).
J.G. Wardrop, “Some theoretical aspects of road traffic research“,Proceedings of the Institute of Civil Engineers, Part II 1 (1952) 325–378.
T.L. Magnanti and R.T. Wong, “Network design and transporation planning—Models and algorithms“,Transportation Science 18 (1984) 1–55.
Author information
Authors and Affiliations
Additional information
Research supported by SSHRC-Canada Grant #410-81-0722 and FCAC-Québec grant #83-AS-26.
Rights and permissions
About this article
Cite this article
Marcotte, P. Network design problem with congestion effects: A case of bilevel programming. Mathematical Programming 34, 142–162 (1986). https://doi.org/10.1007/BF01580580
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580580