IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v18y2018i4d10.1007_s11067-018-9415-0.html
   My bibliography  Save this article

An Effective Bilevel Programming Approach for the Evasive Flow Capturing Location Problem

Author

Listed:
  • F. Hooshmand

    (Amirkabir University of Technology)

  • S. A. MirHassani

    (Amirkabir University of Technology)

Abstract

This paper addresses the problem of locating weigh-in-motion (WIM) sensors on a road transportation network to effectively detect and intercept overloaded trucks assuming that truckers quickly find out the locations of WIM facilities, and make an attempt to avoid them by deviating from their predefined shortest paths. We formulate the problem as a bi-level programming (BLP) model and propose two approaches to find its optimal solution: The first approach utilizes the Karush-Kuhn-Tucker (KKT) conditions to provide a single-level reformulation of the BLP model. However, the second one is an exact decomposition-based algorithm that is superior to the KKT-based reformulation in terms of the computational time. The algorithm starts with a relaxed version of the BLP model and adds a family of cuts on the fly, the optimum is obtained within a few iterations. The idea behind our cut generation is novel and it is based on the knowledge of the underlying problem structure. Computational experiments on some randomly generated instances confirm the efficiency of the algorithm.

Suggested Citation

  • 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.
    • Handle: RePEc:kap:netspa:v:18:y:2018:i:4:d:10.1007_s11067-018-9415-0
    DOI: 10.1007/s11067-018-9415-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11067-018-9415-0
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-018-9415-0?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. Xuegang Ban & Henry Liu, 2009. "A Link-Node Discrete-Time Dynamic Second Best Toll Pricing Model with a Relaxation Solution Algorithm," Networks and Spatial Economics, Springer, vol. 9(2), pages 243-267, June.
    2. 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.
    3. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    4. Marković, Nikola & Ryzhov, Ilya O. & Schonfeld, Paul, 2017. "Evasive flow capture: A multi-period stochastic facility location problem with independent demand," European Journal of Operational Research, Elsevier, vol. 257(2), pages 687-703.
    5. Jonathan F. Bard & James T. Moore, 1992. "An algorithm for the discrete bilevel programming problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(3), pages 419-435, April.
    6. 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.
    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. Hooshmand, F. & Mirarabrazi, F. & MirHassani, S.A., 2020. "Efficient Benders decomposition for distance-based critical node detection problem," Omega, Elsevier, vol. 93(C).
    3. Dolores R. Santos-Peñate & Clara M. Campos-Rodríguez & José A. Moreno-Pérez, 2020. "A Kernel Search Matheuristic to Solve The Discrete Leader-Follower Location Problem," Networks and Spatial Economics, Springer, vol. 20(1), pages 73-98, March.
    4. Bogyrbayeva, Aigerim & Kwon, Changhyun, 2021. "Pessimistic evasive flow capturing problems," European Journal of Operational Research, Elsevier, vol. 293(1), pages 133-148.

    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. Tolga H. Seyhan & Lawrence V. Snyder & Ying Zhang, 2018. "A New Heuristic Formulation for a Competitive Maximal Covering Location Problem," Transportation Science, INFORMS, vol. 52(5), pages 1156-1173, October.
    2. Shilei Wang, 2017. "Complex Interactions in Large Government Networks," Networks and Spatial Economics, Springer, vol. 17(4), pages 1213-1229, December.
    3. 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.
    4. Adejuyigbe O. Fajemisin & Laura Climent & Steven D. Prestwich, 2021. "An analytics-based heuristic decomposition of a bilevel multiple-follower cutting stock problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 665-692, September.
    5. 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.
    6. Mofidi, Seyed Shahab & Pazour, Jennifer A., 2019. "When is it beneficial to provide freelance suppliers with choice? A hierarchical approach for peer-to-peer logistics platforms," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 1-23.
    7. 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.
    8. 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.
    9. Milička, P. & Šůcha, P. & Vanhoucke, M. & Maenhout, B., 2022. "The bilevel optimisation of a multi-agent project scheduling and staffing problem," European Journal of Operational Research, Elsevier, vol. 296(1), pages 72-86.
    10. 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.
    11. Rahman Khorramfar & Osman Y. Özaltın & Karl G. Kempf & Reha Uzsoy, 2022. "Managing Product Transitions: A Bilevel Programming Approach," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2828-2844, September.
    12. Fakhry, Ramy & Hassini, Elkafi & Ezzeldin, Mohamed & El-Dakhakhni, Wael, 2022. "Tri-level mixed-binary linear programming: Solution approaches and application in defending critical infrastructure," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1114-1131.
    13. Junlong Zhang & Osman Y. Özaltın, 2021. "Bilevel Integer Programs with Stochastic Right-Hand Sides," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1644-1660, October.
    14. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    15. Andreas Lanz & Gregor Reich & Ole Wilms, 2022. "Adaptive grids for the estimation of dynamic models," Quantitative Marketing and Economics (QME), Springer, vol. 20(2), pages 179-238, June.
    16. Shi, Yi & Deng, Yawen & Wang, Guoan & Xu, Jiuping, 2020. "Stackelberg equilibrium-based eco-economic approach for sustainable development of kitchen waste disposal with subsidy policy: A case study from China," Energy, Elsevier, vol. 196(C).
    17. Lucio Bianco & Massimiliano Caramia & Stefano Giordani & Veronica Piccialli, 2016. "A Game-Theoretic Approach for Regulating Hazmat Transportation," Transportation Science, INFORMS, vol. 50(2), pages 424-438, May.
    18. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    19. Cerulli, Martina & Serra, Domenico & Sorgente, Carmine & Archetti, Claudia & Ljubić, Ivana, 2023. "Mathematical programming formulations for the Collapsed k-Core Problem," European Journal of Operational Research, Elsevier, vol. 311(1), pages 56-72.
    20. Chan Y. Han & Brian J. Lunday & Matthew J. Robbins, 2016. "A Game Theoretic Model for the Optimal Location of Integrated Air Defense System Missile Batteries," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 405-416, August.

    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:18:y:2018:i:4:d:10.1007_s11067-018-9415-0. 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.