Solution Algorithm for a New Bi-Level Discrete Network Design Problem
Abstract
A new discrete network design problem (DNDP) was pro-posed in this paper, where the variables can be a series of integers rather than just 0-1. The new DNDP can determine both capacity improvement grades of reconstruction roads and locations and capacity grades of newly added roads, and thus complies with the practical projects where road capacity can only be some discrete levels corresponding to the number of lanes of roads. This paper designed a solution algorithm combining branch-and-bound with Hooke-Jeeves algorithm, where feasible integer solutions are recorded in searching the process of Hooke-Jeeves algorithm, lend -ing itself to determine the upper bound of the upper-level problem. The thresholds for branch cutting and ending were set for earlier convergence. Numerical examples are given to demonstrate the efficiency of the proposed algorithm.References
Yang, H., Bell, M.G.H. : Models and algorithms for road network design: a review and some new developments, Transport Reviews, Vol. 18, No. 3, 1998, pp. 257-278
Chen, M.Y., Alfa, A.S. : A network design algorithm using a stochastic incremental traffic assignment approach, Transportation Science, Vol. 25, No. 3, 1991, pp. 214-224
Davis, G.A.: Exact local solution of the continuous network design problem via stochastic user equilibrium assignment, Transportation Research Part B, Vol. 28, No. 1, 1994, pp. 61-75
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. Transportation Research Part B, Vol. 42, No. 10, 2008, pp. 843–860
Chiou, S.W.: Bilevel programming for the continuous transport network design problem , Transportation Research Part B, Vol. 39, No.4, 2005, pp. 361–383
Meng, Q., Yang, H., Bell, M.G.H. : An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem, Transportation Research Part B, Vol. 35, No. 1, 2001, pp. 83–105
Sumalee, A., Watling, D.P., Nakayama, S.: Reliable network design problem: case with uncertain demand and total travel time reliability , Transportation Re -search Record, Vol. 1964, 2006, pp. 81–90
Wong, S.C., Yang, H.: Reserve capacity of a signal-controlled road network , Transportation Research Part B, Vol. 31, No.5, 1997, pp. 397–402
Friesz, T.L. , Harker, P.T.: Properties of the iterative optimization-equilibrium algorithm , Civil Engineering Systems, Vol. 2, No.3, 1985, pp. 142-154
Suwansirikul, C. , Friesz, T.L. , Tobin, R.L. : Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problems, Transportation Science, Vol. 21, No. 4, 1987, pp. 254–263
Marcotte, P., Marquis, G. : Efficient implementation of heuristic for the continuous network design problems, Annals of Operation Research, Vol. 34, No.1, 1992, pp. 163-176.
Magnanti, T.L., Wong, R.T.: Network design and transportation planning: models and algorithms, Transportation Science, Vol. 18, No.1, 1984, pp. 1-55
Dantzig, G.B., Maier, S.F., Lansdowne, Z.F. : Application of decomposition to transportation network analysis, Control Analysis Corporation, Palo Alto, California, Technical Report No. 1, March 1976
Boyce, D.E. : Urban transportation network equilibrium and design models: Recent achievements and future prospectives, Environment and Planning Part A, Vol. 16, No. 1, 1984, pp. 1445–1474
Connors, R.D. , Sumalee, A., Watling, D.P.: Sensitivity analysis of the variable demand probit stochastic user equilibrium with multiple user-classes, Transportation Research Part B, Vol. 41, No. 6, 2007, pp. 593–615
Abdulaal, M. , Leblanc, L.J. : Continuous equilibrium network design models , Transportation Research Part B, Vol. 13, No. 1, 1979, pp. 19–32
Gao, Z., Wu, J., Sun, H.: Solution algorithm for the bi level discrete network design problem, Transportation Research Part B, Vol. 39, No. 6, 2005, pp. 479–495
Leblanc, L.J.: An algorithm for the discrete network design problem , Transportation Science, Vol. 9, No. 3, 1975, pp. 183–199
Poorzahedy, H. , Turnquist, M.A. : Approximate algorithms for the discrete network design problem , Transportation Research Part B, Vol. 16, No. 1, 1982, pp. 45–55
Hamid, F., Mohammad, M.S.: A single-level mixed integer linear formulation for a bi-level discrete network design problem , Transportation Research Part E, Vol. 47, No. 5, 2011, pp. 623–640
Wang, D.Z.W. , Lo, H.K.: Global optimum of the linearized network design problem with equilibrium flows , Transportation Research Part B, Vol. 44, No.4, 2010, pp. 482–492
Luathep, P. , Sumalee, A., Lam, W.H.K., Li, Z., Lo, H.K.: Global optimization method for mixed transportation
network design problem: A mixed-integer linear programming approach , Transportation Research Part B, Vol. 45, No. 5, 2011, pp. 808-827
Sheffi, Y.: Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods , Prentice-Hall, Englewood Cliffs, NJ, USA, 1985
Mokhtar, S.B. , Shetty, C.M.: Nonlinear Programming: Theory and Algorithms , John Wiley & Sons, Inc., New York, 1979
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
