The continuous network design problem is formulated as a mathematical program with complementarity constraints (MPCC) and a Gauss–Seidel decomposition scheme is presented for the solution of the MPCC model. The model has an upper level as a nonlinear programming problem and the lower level as a nonlinear complementarity problem. With the application of the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level nonlinear programming problem. To solve the single-level problem, a decomposition scheme that can resolve the possible dimensionality problem (i.e., a large number of defining variables) is developed. The decomposition scheme is tested, and promising results are shown for well-known test problems.
Get full access to this article
View all access options for this article.
References
1.
LeBlancL., and BoyceD. E.. A Bilevel Programming Algorithm for Exact Solution of the Network Design Problem with User-Optimal Flows.Transportation Research, Vol. 20B, 1986, pp. 259–265.
2.
MorlokE. K.Development and Application of a Highway Network Design Model.FHWA, U.S. Department of Transportation, 1973.
3.
TanH.-N., GershwinS. B., and AthanaM.. Hybrid Optimization in Urban Traffic Networks. Report DOT-TSC-RSPA-79-7. Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, 1979.
4.
MarcotteP.Network Optimization with Continuous Control Parameters.Transportation Science, Vol. 17, 1983, pp. 181–197.
5.
SuwansirikulC., FrieszT. L., and TobinR. L.. Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem.Transportation Science, Vol. 21, 1987, pp. 254–263.
6.
FrieszT. L.Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints.Transportation Science, Vol. 26, 1992, pp. 18–26.
7.
YangH.Sensitivity Analysis for the Elastic Demand Network Equilibrium Problem with Applications.Transportation Research, Vol. 31B, 1997, pp. 55–70.
8.
YangH., and BellM. G. H.. Transport Bilevel Programming Problems: Recent Methodological Advances.Transportation Research, Vol. 35B, 2001, pp. 1–4.
9.
OutrataJ., KocvaraM., and ZoweJ.. Nonsmooth Approach to Optimization Problems with Equilibrium Constraints.Kluwer Academic Publishers, 1998.
10.
LuoZ.-Q., PangJ. S., and RalphD.. Mathematical Programs with Equilibrium Constraints.Cambridge University PressCambridge, United Kingdom,1996.
11.
MengQ., YangH., and BellM. G. H.. An Equivalent Continuously Differentiable Model and a Locally Convergent Algorithm for the Continuous Network Design Problem.Transportation Research, Vol. 35B, 2001, pp. 83–105.
12.
MarcotteP., and ZhuD. L.. Exact and Inexact Penalty Methods for the Generalized Bilevel Programming Problem.Mathematical Programming, Vol. 74, 1996, pp. 141–157.
13.
PatrikssonM., and RockafellarR. T.. A Mathematical Model and Descent Algorithm for Bilevel Traffic Management.Transportation Science, Vol. 36, 2002, pp. 271–291.
14.
BanX. G., LiuX. H., and FerrisM. C.. A General MPCC Model and Its Solution Algorithm for Continuous Network Design Problem.Mathematical and Computer Modeling, Vol. 43, No. 5–6, 2006, pp. 493–505.
15.
ScheelH., and ScholteS.. Mathematical Programs with Complementarity Constraints: Stationarity, Optimality, and Sensitivity.Mathematics of Operations Research, Vol. 22, No. 1, 2000, pp. 1–22.
16.
AnitescuM.On Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs. Preprint ANL/MCS-P864-1200. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill., 2000.
17.
AnitescuM.Global Convergence of an Elastic Mode Approach for a Class of Mathematical Programs with Complementarity Constraints. Preprint ANL/MCS–P1143–0404. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Ill.,2004.
18.
FletcherR., and LeyfferS.. Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs.Optimization Methods and Software, Vol. 19, No. 1, 2004, pp. 15–40.
19.
HuX., and RalphD.. A Note on Sensitivity of Value Functions of Mathematical Programs with Complementarity Constraints.Mathematical Programming, Vol. 93, No. 2, 2002, pp. 265–279.
20.
JiangH., and RalphD.. Smooth SQP Methods for Mathematical Programs with Nonlinear Complementarity Constraints.Society for Industrial Applied Mathematics Journal of Optimization, Vol. 10, No. 3, 2000, pp. 779–808.
21.
JiangH., and RalphD.. Extension of Quasi-Newton Methods to Mathematical Programs with Complementarity Constraints.Computational Optimization and Applications, Vol. 25, No. 1–3, 2003, pp. 123–150.
22.
FerrisM. C., DirkseS. P., and MeerausA.. Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimization. Numerical Analysis Group Research Report NA-02/11. Oxford University Computing Laboratory, Oxford University,Oxford, United Kingdom, 2002.
23.
FerrisM. C., DirkseS. P., and MeerausA.. Mathematical Programs with Equilibrium Constraints: Automatic Reformulation and Solution via Constrained Optimization. In Frontiers in Applied General Equilibrium Modeling (KehoeT. J., SrinivasanT. N., and WhalleyJ., eds.), Cambridge University Press, Cambridge, United Kingdom, 2004.
24.
BrookeA., KendrickD., and MeerausA.. GAMS, a User's Guide.GAMS Development Corporation, 1998.
25.
RalphD., and WrightS. J.. Some Properties of Regularization and Penalization Schemes for MPECs.Optimization Methods and Software, Vol. 19, 2004, pp. 527–556.
26.
BanX. G.Quasi-Variational Inequality Formulations and Solution Approaches for Dynamic User Equilibria. Ph.D. thesis. University of Wisconsin, Madison, 2005.
27.
OrtegaJ. M., and RheinboldtW. C.. Iterative Solution of Nonlinear Equations in Several Variables.Academic Press, New York, 1970.
28.
ZadehN.A Note on the Cyclic Coordinate Ascent Method.Management Science, Vol. 16, 1969–1970, pp. 642–644.
29.
BertsekasD. P., and TsitsiklisJ. N.. Parallel and Distributed Computation: Numerical Methods.Prentice-Hall, London, 1997.
30.
BoyceD. E., Ralevic-DekicB., and Bar-GeraH.. Convergence of Traffic Assignment: How Much Is Enough?Journal of Transportation Engineering, ASCE, Vol. 130, No. 1, 2004, pp. 49–55.
31.
LeBlancL.An Algorithm for the Discrete Network Design Problem.Transportation Science, Vol. 9, 1975, pp. 183–199.
32.
MurtaghB. A., and SaundersM. A.. The Implementation of a Lagrangian-Based Algorithm for Sparse Nonlinear Constraints.SOL Technical Report. Stanford University, Stanford, California, 1981.
33.
AbdulaalM., and LeBlancL. J.. Continuous Equilibrium Network Design Models.Transportation Research, Vol. 13B, 1979, pp. 19–32.
