IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0192454.html
   My bibliography  Save this article

An outer approximation method for the road network design problem

Author

Listed:
  • Saeed Asadi Bagloee
  • Majid Sarvi

Abstract

Best investment in the road infrastructure or the network design is perceived as a fundamental and benchmark problem in transportation. Given a set of candidate road projects with associated costs, finding the best subset with respect to a limited budget is known as a bilevel Discrete Network Design Problem (DNDP) of NP-hard computationally complexity. We engage with the complexity with a hybrid exact-heuristic methodology based on a two-stage relaxation as follows: (i) the bilevel feature is relaxed to a single-level problem by taking the network performance function of the upper level into the user equilibrium traffic assignment problem (UE-TAP) in the lower level as a constraint. It results in a mixed-integer nonlinear programming (MINLP) problem which is then solved using the Outer Approximation (OA) algorithm (ii) we further relax the multi-commodity UE-TAP to a single-commodity MILP problem, that is, the multiple OD pairs are aggregated to a single OD pair. This methodology has two main advantages: (i) the method is proven to be highly efficient to solve the DNDP for a large-sized network of Winnipeg, Canada. The results suggest that within a limited number of iterations (as termination criterion), global optimum solutions are quickly reached in most of the cases; otherwise, good solutions (close to global optimum solutions) are found in early iterations. Comparative analysis of the networks of Gao and Sioux-Falls shows that for such a non-exact method the global optimum solutions are found in fewer iterations than those found in some analytically exact algorithms in the literature. (ii) Integration of the objective function among the constraints provides a commensurate capability to tackle the multi-objective (or multi-criteria) DNDP as well.

Suggested Citation

  • Saeed Asadi Bagloee & Majid Sarvi, 2018. "An outer approximation method for the road network design problem," PLOS ONE, Public Library of Science, vol. 13(3), pages 1-28, March.
    • Handle: RePEc:plo:pone00:0192454
    DOI: 10.1371/journal.pone.0192454
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0192454
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0192454&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0192454?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
    ---><---

    References listed on IDEAS

    as
    1. Larry J. Leblanc, 1975. "An Algorithm for the Discrete Network Design Problem," Transportation Science, INFORMS, vol. 9(3), pages 183-199, August.
    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. Teodorović Dušan & Nikolić Miloš, 2023. "Work Zone Scheduling Problem in the Urban Traffic Networks," Economic Themes, Sciendo, vol. 61(1), pages 1-18, March.

    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. Wei, Chong & Asakura, Yasuo & Iryo, Takamasa, 2014. "Formulating the within-day dynamic stochastic traffic assignment problem from a Bayesian perspective," Transportation Research Part B: Methodological, Elsevier, vol. 59(C), pages 45-57.
    2. Ahipaşaoğlu, Selin Damla & Meskarian, Rudabeh & Magnanti, Thomas L. & Natarajan, Karthik, 2015. "Beyond normality: A cross moment-stochastic user equilibrium model," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 333-354.
    3. 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.
    4. Lim, Yongtaek & Heydecker, Benjamin, 2005. "Dynamic departure time and stochastic user equilibrium assignment," Transportation Research Part B: Methodological, Elsevier, vol. 39(2), pages 97-118, February.
    5. Ospina, Juan P. & Duque, Juan C. & Botero-Fernández, Verónica & Montoya, Alejandro, 2022. "The maximal covering bicycle network design problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 159(C), pages 222-236.
    6. Maher, Mike, 1998. "Algorithms for logit-based stochastic user equilibrium assignment," Transportation Research Part B: Methodological, Elsevier, vol. 32(8), pages 539-549, November.
    7. 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.
    8. David Watling, 2002. "A Second Order Stochastic Network Equilibrium Model, II: Solution Method and Numerical Experiments," Transportation Science, INFORMS, vol. 36(2), pages 167-183, May.
    9. 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.
    10. 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.
    11. Liu, Haoxiang & Wang, David Z.W., 2017. "Locating multiple types of charging facilities for battery electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 30-55.
    12. 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.
    13. 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.
    14. Jiayang Li & Zhaoran Wang & Yu Marco Nie, 2023. "Wardrop Equilibrium Can Be Boundedly Rational: A New Behavioral Theory of Route Choice," Papers 2304.02500, arXiv.org, revised Feb 2024.
    15. P.Delle Site & André de Palma & Samarth Ghoslya, 2024. "Matching and fair pricing of socially optimal, stable and financially sustainable ride-sharing in congestible networks," THEMA Working Papers 2024-06, THEMA (THéorie Economique, Modélisation et Applications), Université de Cergy-Pontoise.
    16. 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.
    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. Hadi Karimi & Bahador Ghadirifaraz & Seyed Nader Shetab Boushehri & Seyyed-Mohammadreza Hosseininasab & Narges Rafiei, 2022. "Reducing traffic congestion and increasing sustainability in special urban areas through one-way traffic reconfiguration," Transportation, Springer, vol. 49(1), pages 37-60, February.
    19. Liu, Haoxiang & Szeto, W.Y. & Long, Jiancheng, 2019. "Bike network design problem with a path-size logit-based equilibrium constraint: Formulation, global optimization, and matheuristic," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 284-307.
    20. D E Boyce, 1984. "Urban Transportation Network-Equilibrium and Design Models: Recent Achievements and Future Prospects," Environment and Planning A, , vol. 16(11), pages 1445-1474, November.

    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:plo:pone00:0192454. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.