IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v13y2013i1p67-106.html
   My bibliography  Save this article

A Branch and Bound Algorithm for Bi-level Discrete Network Design Problem

Author

Listed:
  • Hamid Farvaresh
  • Mohammad Sepehri

Abstract

Discrete network design problem (DNDP) is generally formulated as a bi-level programming. Because of non-convexity of bi-level formulation of DNDP which stems from the equilibrium conditions, finding global optimal solutions are very demanding. In this paper, a new branch and bound algorithm being able to find exact solution of the problem is presented. A lower bound for the upper-level objective and its computation method are developed. Numerical experiments show that our algorithm is superior to previous algorithms in terms of both computation time and solution quality. The conducted experiments indicate that in most cases the first incumbent solution which is obtained within a few seconds is superior to the final solution of some of previous algorithms. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • 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.
    • Handle: RePEc:kap:netspa:v:13:y:2013:i:1:p:67-106
    DOI: 10.1007/s11067-012-9173-3
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11067-012-9173-3
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-012-9173-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. 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.
    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. Karakostas, George & Kim, Taeyon & Viglas, Anastasios & Xia, Hao, 2011. "On the degradation of performance for traffic networks with oblivious users," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 364-371, February.
    4. Hossain Poorzahedy & Farhad Abulghasemi, 2005. "Application of Ant System to network design problem," Transportation, Springer, vol. 32(3), pages 251-273, May.
    5. Byung Kim & Wonkyu Kim, 2006. "An equilibrium network design model with a social cost function for multimodal networks," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 40(3), pages 473-491, August.
    6. Kaj Holmberg & Johan Hellstrand, 1998. "Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound," Operations Research, INFORMS, vol. 46(2), pages 247-259, April.
    7. 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.
    8. LeBlanc, Larry J. & Boyce, David E., 1986. "A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows," Transportation Research Part B: Methodological, Elsevier, vol. 20(3), pages 259-265, June.
    9. Nie, Yu (Marco), 2010. "A class of bush-based algorithms for the traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 44(1), pages 73-89, January.
    10. 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.
    11. 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.
    12. Lihui Zhang & Siriphong Lawphongpanich & Yafeng Yin, 2009. "An Active-set Algorithm for Discrete Network Design Problems," Springer Books, in: William H. K. Lam & S. C. Wong & Hong K. Lo (ed.), Transportation and Traffic Theory 2009: Golden Jubilee, chapter 0, pages 283-300, Springer.
    13. 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.
    14. Hillel Bar-Gera, 2002. "Origin-Based Algorithm for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 36(4), pages 398-417, November.
    15. 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.
    16. Larry J. Leblanc, 1975. "An Algorithm for the Discrete Network Design Problem," Transportation Science, INFORMS, vol. 9(3), pages 183-199, August.
    17. Terry L. Friesz & Hsun-Jung Cho & Nihal J. Mehta & Roger L. Tobin & G. Anandalingam, 1992. "A Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints," Transportation Science, INFORMS, vol. 26(1), pages 18-26, February.
    18. Farvaresh, Hamid & Sepehri, Mohammad Mehdi, 2011. "A single-level mixed integer linear formulation for a bi-level discrete network design problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(5), pages 623-640, September.
    19. Byung Chung & Tao Yao & Chi Xie & Andreas Thorsen, 2011. "Robust Optimization Model for a Dynamic Network Design Problem Under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 11(2), pages 371-389, June.
    20. 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.
    21. Wang, David Z.W. & Lo, Hong K., 2010. "Global optimum of the linearized network design problem with equilibrium flows," Transportation Research Part B: Methodological, Elsevier, vol. 44(4), pages 482-492, May.
    22. 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)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhou, Guanyu & Dong, Qianyu & Zhao, Yuming & Wang, Han & Jian, Linni & Jia, Youwei, 2023. "Bilevel optimization approach to fast charging station planning in electrified transportation networks," Applied Energy, Elsevier, vol. 350(C).
    2. F. Hooshmand & S. A. MirHassani, 2018. "An Effective Bilevel Programming Approach for the Evasive Flow Capturing Location Problem," Networks and Spatial Economics, Springer, vol. 18(4), pages 909-935, December.
    3. 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.
    4. W. Szeto & Y. Jiang & D. Wang & A. Sumalee, 2015. "A Sustainable Road Network Design Problem with Land Use Transportation Interaction over Time," Networks and Spatial Economics, Springer, vol. 15(3), pages 791-822, September.
    5. Ghavamifar, Ali & Makui, Ahmad & Taleizadeh, Ata Allah, 2018. "Designing a resilient competitive supply chain network under disruption risks: A real-world application," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 87-109.
    6. Rashidi, Eghbal & Parsafard, Mohsen & Medal, Hugh & Li, Xiaopeng, 2016. "Optimal traffic calming: A mixed-integer bi-level programming model for locating sidewalks and crosswalks in a multimodal transportation network to maximize pedestrians’ safety and network usability," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 91(C), pages 33-50.
    7. Tan, Zhijia & Yang, Hai & Tan, Wei & Li, Zhichun, 2016. "Pareto-improving transportation network design and ownership regimes," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 292-309.
    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. Gokalp, Can & Patil, Priyadarshan N. & Boyles, Stephen D., 2021. "Post-disaster recovery sequencing strategy for road networks," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 228-245.
    10. Wang, Guangmin & Gao, Ziyou & Xu, Meng, 2019. "Integrating link-based discrete credit charging scheme into discrete network design problem," European Journal of Operational Research, Elsevier, vol. 272(1), pages 176-187.
    11. Hosseininasab, Seyyed-Mohammadreza & Shetab-Boushehri, Seyyed-Nader, 2015. "Integration of selecting and scheduling urban road construction projects as a time-dependent discrete network design problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 762-771.
    12. Lili Du & Srinivas Peeta, 2014. "A Stochastic Optimization Model to Reduce Expected Post-Disaster Response Time Through Pre-Disaster Investment Decisions," Networks and Spatial Economics, Springer, vol. 14(2), pages 271-295, June.
    13. Arash Kaviani & Russell G. Thompson & Abbas Rajabifard & Majid Sarvi, 2020. "A model for multi-class road network recovery scheduling of regional road networks," Transportation, Springer, vol. 47(1), pages 109-143, February.
    14. Qiang Zhang & Shi Qiang Liu & Andrea D’Ariano, 2023. "Bi-objective bi-level optimization for integrating lane-level closure and reversal in redesigning transportation networks," Operational Research, Springer, vol. 23(2), pages 1-51, June.
    15. Shilei Wang, 2017. "Complex Interactions in Large Government Networks," Networks and Spatial Economics, Springer, vol. 17(4), pages 1213-1229, December.
    16. Inbal Haas & Shlomo Bekhor, 2017. "An Alternative Approach for Solving the Environmentally-Oriented Discrete Network Design Problem," Networks and Spatial Economics, Springer, vol. 17(3), pages 963-988, September.
    17. Pirmin Fontaine & Stefan Minner, 2017. "A dynamic discrete network design problem for maintenance planning in traffic networks," Annals of Operations Research, Springer, vol. 253(2), pages 757-772, June.

    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. 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.
    3. Wang, David Z.W. & Liu, Haoxiang & Szeto, W.Y., 2015. "A novel discrete network design problem formulation and its global optimization solution algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 79(C), pages 213-230.
    4. 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.
    5. 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.
    6. Hong Zheng & Xiaozheng He & Yongfu Li & Srinivas Peeta, 2017. "Traffic Equilibrium and Charging Facility Locations for Electric Vehicles," Networks and Spatial Economics, Springer, vol. 17(2), pages 435-457, June.
    7. 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.
    8. 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.
    9. 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.
    10. Karimi Dehnavi, Hadi & Rezvan, Mohammad Taghi & Shirmohammadli, Abdolmatin & Vallée, Dirk, 2013. "A solution for urban road selection and construction problem using simulation and goal programming—Case study of the city of Isfahan," Transport Policy, Elsevier, vol. 29(C), pages 46-53.
    11. 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.
    12. 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.
    13. Fontaine, Pirmin & Minner, Stefan, 2014. "Benders Decomposition for Discrete–Continuous Linear Bilevel Problems with application to traffic network design," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 163-172.
    14. Arash Kaviani & Russell G. Thompson & Abbas Rajabifard & Majid Sarvi, 2020. "A model for multi-class road network recovery scheduling of regional road networks," Transportation, Springer, vol. 47(1), pages 109-143, February.
    15. Wei Huang & Guangming Xu & Hong K. Lo, 2020. "Pareto-Optimal Sustainable Transportation Network Design under Spatial Queuing," Networks and Spatial Economics, Springer, vol. 20(3), pages 637-673, September.
    16. Hosseininasab, Seyyed-Mohammadreza & Shetab-Boushehri, Seyyed-Nader, 2015. "Integration of selecting and scheduling urban road construction projects as a time-dependent discrete network design problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 762-771.
    17. 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.
    18. Pirmin Fontaine & Stefan Minner, 2017. "A dynamic discrete network design problem for maintenance planning in traffic networks," Annals of Operations Research, Springer, vol. 253(2), pages 757-772, June.
    19. Bastiaan Possel & Luc J. J. Wismans & Eric C. Berkum & Michiel C. J. Bliemer, 2018. "The multi-objective network design problem using minimizing externalities as objectives: comparison of a genetic algorithm and simulated annealing framework," Transportation, Springer, vol. 45(2), pages 545-572, March.
    20. Liu, Jiangtao & Zhou, Xuesong, 2016. "Capacitated transit service network design with boundedly rational agents," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 225-250.

    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:kap:netspa:v:13:y:2013:i:1:p:67-106. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.