IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v39y2005i6p479-495.html
   My bibliography  Save this article

Solution algorithm for the bi-level discrete network design problem

Author

Listed:
  • Gao, Ziyou
  • Wu, Jianjun
  • Sun, Huijun

Abstract

The discrete network design problem deals with the selection of link additions to an existing road network, with given demand from each origin to each destination. The objective is to make an optimal investment decision in order to minimize the total travel cost in the network, while accounting for the route choice behaviors of network users. Because of the computational difficulties experienced with the solution algorithm of nonlinear bi-level mixed integer programming with a large number of 0-1 variables, the discrete network design problem has been recognized as one of the most difficult yet challenging problems in transport. In this paper, at first a traditional bi-level programming model for the discrete network design problem is introduced, and then a new solution algorithm is proposed by using the support function concept to express the relationship between improvement flows and the new additional links in the existing urban network. Finally, the applications of the new algorithm are illustrated with two numerical examples. Numerical results indicate that the proposed algorithm would be efficient in practice.

Suggested Citation

  • Gao, Ziyou & Wu, Jianjun & Sun, Huijun, 2005. "Solution algorithm for the bi-level discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 39(6), pages 479-495, July.
    • Handle: RePEc:eee:transb:v:39:y:2005:i:6:p:479-495
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(04)00099-2
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Wong, S. C. & Yang, Hai, 1997. "Reserve capacity of a signal-controlled road network," Transportation Research Part B: Methodological, Elsevier, vol. 31(5), pages 397-402, October.
    2. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    3. Abdulaal, Mustafa & LeBlanc, Larry J., 1979. "Continuous equilibrium network design models," Transportation Research Part B: Methodological, Elsevier, vol. 13(1), pages 19-32, March.
    4. Gao, Ziyou & Sun, Huijun & Shan, Lian Long, 2004. "A continuous equilibrium network design model and algorithm for transit systems," Transportation Research Part B: Methodological, Elsevier, vol. 38(3), pages 235-250, March.
    5. D E Boyce & A Farhi & R Weischedel, 1973. "Optimal Network Problem: A Branch-and-Bound Algorithm," Environment and Planning A, , vol. 5(4), pages 519-533, August.
    6. Suh-Wen Chiou, 1999. "Optimization of Area Traffic Control for Equilibrium Network Flows," Transportation Science, INFORMS, vol. 33(3), pages 279-289, August.
    7. Mingyuan Chen & Attahiru Sule Alfa, 1991. "A Network Design Algorithm Using a Stochastic Incremental Traffic Assignment Approach," Transportation Science, INFORMS, vol. 25(3), pages 215-224, August.
    8. Ben-Ayed, Omar & Boyce, David E. & Blair, Charles E., 1988. "A general bilevel linear programming formulation of the network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 22(4), pages 311-318, August.
    9. Poorzahedy, Hossain & Turnquist, Mark A., 1982. "Approximate algorithms for the discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 16(1), pages 45-55, February.
    10. Yang, Hai & Yagar, Sam, 1994. "Traffic assignment and traffic control in general freeway-arterial corridor systems," Transportation Research Part B: Methodological, Elsevier, vol. 28(6), pages 463-486, December.
    11. Larry J. Leblanc, 1975. "An Algorithm for the Discrete Network Design Problem," Transportation Science, INFORMS, vol. 9(3), pages 183-199, August.
    12. Dantzig, George B. & Harvey, Roy P. & Lansdowne, Zachary F. & Robinson, David W. & Maier, Steven F., 1979. "Formulating and solving the network design problem by decomposition," Transportation Research Part B: Methodological, Elsevier, vol. 13(1), pages 5-17, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y. & Rashidi, Hannaneh, 2013. "A review of urban transportation network design problems," European Journal of Operational Research, Elsevier, vol. 229(2), pages 281-302.
    2. Gallo, Mariano & D'Acierno, Luca & Montella, Bruno, 2010. "A meta-heuristic approach for solving the Urban Network Design Problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 144-157, February.
    3. Elnaz Miandoabchi & Reza Farahani & W. Szeto, 2012. "Bi-objective bimodal urban road network design using hybrid metaheuristics," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 20(4), pages 583-621, December.
    4. Elnaz Miandoabchi & Reza Farahani & Wout Dullaert & W. Szeto, 2012. "Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks," Networks and Spatial Economics, Springer, vol. 12(3), pages 441-480, September.
    5. Meng, Q. & Yang, H. & Bell, M. G. H., 2001. "An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 35(1), pages 83-105, January.
    6. Poorzahedy, Hossain & Rouhani, Omid M., 2007. "Hybrid meta-heuristic algorithms for solving network design problem," European Journal of Operational Research, Elsevier, vol. 182(2), pages 578-596, October.
    7. Hamid Farvaresh & Mohammad Sepehri, 2013. "A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem," Networks and Spatial Economics, Springer, vol. 13(1), pages 67-106, March.
    8. Wang, Shuaian & Meng, Qiang & Yang, Hai, 2013. "Global optimization methods for the discrete network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 50(C), pages 42-60.
    9. Dung-Ying Lin & Ampol Karoonsoontawong & S. Waller, 2011. "A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem," Networks and Spatial Economics, Springer, vol. 11(1), pages 101-126, March.
    10. Giulio Cantarella & Antonino Vitetta, 2006. "The multi-criteria road network design problem in an urban area," Transportation, Springer, vol. 33(6), pages 567-588, November.
    11. Khooban, Zohreh & Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y., 2015. "Mixed network design using hybrid scatter search," European Journal of Operational Research, Elsevier, vol. 247(3), pages 699-710.
    12. Hosseininasab, Seyyed-Mohammadreza & Shetab-Boushehri, Seyyed-Nader & Hejazi, Seyed Reza & Karimi, Hadi, 2018. "A multi-objective integrated model for selecting, scheduling, and budgeting road construction projects," European Journal of Operational Research, Elsevier, vol. 271(1), pages 262-277.
    13. Luathep, Paramet & Sumalee, Agachai & Lam, William H.K. & Li, Zhi-Chun & Lo, Hong K., 2011. "Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach," Transportation Research Part B: Methodological, Elsevier, vol. 45(5), pages 808-827, June.
    14. Hua Wang & Xiaoning Zhang, 2017. "Game theoretical transportation network design among multiple regions," Annals of Operations Research, Springer, vol. 249(1), pages 97-117, February.
    15. Ukkusuri, Satish V. & Patil, Gopal, 2009. "Multi-period transportation network design under demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 625-642, July.
    16. Di, Zhen & Yang, Lixing & Qi, Jianguo & Gao, Ziyou, 2018. "Transportation network design for maximizing flow-based accessibility," Transportation Research Part B: Methodological, Elsevier, vol. 110(C), pages 209-238.
    17. Josefsson, Magnus & Patriksson, Michael, 2007. "Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design," Transportation Research Part B: Methodological, Elsevier, vol. 41(1), pages 4-31, January.
    18. Joseph Y. J. Chow & Amelia C. Regan, 2011. "Real Option Pricing of Network Design Investments," Transportation Science, INFORMS, vol. 45(1), pages 50-63, February.
    19. Solanki, Rajendra S. & Gorti, Jyothi K. & Southworth, Frank, 1998. "Using decomposition in large-scale highway network design with a quasi-optimization heuristic," Transportation Research Part B: Methodological, Elsevier, vol. 32(2), pages 127-140, February.
    20. Di, Xuan & Ma, Rui & Liu, Henry X. & Ban, Xuegang (Jeff), 2018. "A link-node reformulation of ridesharing user equilibrium with network design," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 230-255.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:39:y:2005:i:6:p:479-495. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.