Solution Algorithm for a New Bi-Level Discrete Network Design Problem

  • Qun Chen
  • Haibo Chen
Keywords: discrete network design problem, integer programming, branch-and-bound algorithm

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

How to Cite
1.
Chen Q, Chen H. Solution Algorithm for a New Bi-Level Discrete Network Design Problem. Promet [Internet]. 1 [cited 2024Jun.12];25(6):513-24. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/1424
Section
Articles