IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v31y2019i1p171-192.html
   My bibliography  Save this article

Exact Approaches for Network Design Problems with Relays

Author

Listed:
  • Markus Leitner

    (Department of Statistics and Operations Research, University of Vienna, 1010 Vienna, Austria)

  • Ivana Ljubić

    (ESSEC Business School of Paris, 95021 Cergy-Pontoise, France)

  • Martin Riedler

    (Institute of Logic and Computation, TU Wien, 1040 Vienna, Austria)

  • Mario Ruthmair

    (Department of Statistics and Operations Research, University of Vienna, 1010 Vienna, Austria)

Abstract

In this article we consider the network design problem with relays (NDPR), which gives answers to some important strategic design questions in telecommunication network design. Given a family of origin-destination pairs and a set of existing links these questions are as follows: (1) What are the optimal locations for signal regeneration devices (relays) and how many of them are needed? (2) Could the available infrastructure be enhanced by installing additional links in order to reduce the travel distance and therefore reduce the number of necessary relays? In contrast to previous work on the NDPR, which mainly focused on heuristic approaches, we discuss exact methods based on different mixed-integer linear programming formulations for the problem. We develop branch-and-price and branch-price-and-cut algorithms that build upon models with an exponential number of variables (and constraints). In an extensive computational study, we analyze the performance of these approaches for instances that reflect different real-world settings. Finally, we also point out the relevance of the NDPR in the context of electric mobility.

Suggested Citation

  • Markus Leitner & Ivana Ljubić & Martin Riedler & Mario Ruthmair, 2019. "Exact Approaches for Network Design Problems with Relays," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 171-192, February.
    • Handle: RePEc:inm:orijoc:v:31:y:2019:i:1:p:171-192
    DOI: 10.1287/ijoc.2018.0820
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0820
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2018.0820?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. Capar, Ismail & Kuby, Michael & Leon, V. Jorge & Tsai, Yu-Jiun, 2013. "An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations," European Journal of Operational Research, Elsevier, vol. 227(1), pages 142-151.
    2. Abilio Lucena & Nelson Maculan & Luidi Simonetti, 2010. "Reformulations and solution algorithms for the maximum leaf spanning tree problem," Computational Management Science, Springer, vol. 7(3), pages 289-311, July.
    3. Yiyong Xiao & Abdullah Konak, 2017. "A variable neighborhood search for the network design problem with relays," Journal of Heuristics, Springer, vol. 23(2), pages 137-164, June.
    4. Konak, Abdullah, 2012. "Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation," European Journal of Operational Research, Elsevier, vol. 218(3), pages 829-837.
    5. James F. Campbell & Morton E. O'Kelly, 2012. "Twenty-Five Years of Hub Location Research," Transportation Science, INFORMS, vol. 46(2), pages 153-169, May.
    6. Si Chen & Ivana Ljubić & S. Raghavan, 2015. "The Generalized Regenerator Location Problem," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 204-220, May.
    7. Li, Xiangyong & Aneja, Y.P. & Huo, Jiazhen, 2012. "Using branch-and-price approach to solve the directed network design problem with relays," Omega, Elsevier, vol. 40(5), pages 672-679.
    8. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    9. S. Raghavan & Daliborka Stanojević, 2011. "Branch and Price for WDM Optical Networks with No Bifurcation of Flow," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 56-74, February.
    10. Cabral, Edgar Alberto & Erkut, Erhan & Laporte, Gilbert & Patterson, Raymond A., 2007. "The network design problem with relays," European Journal of Operational Research, Elsevier, vol. 180(2), pages 834-844, July.
    11. Samuel Pelletier & Ola Jabali & Gilbert Laporte, 2016. "50th Anniversary Invited Article—Goods Distribution with Electric Vehicles: Review and Research Perspectives," Transportation Science, INFORMS, vol. 50(1), pages 3-22, February.
    12. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    13. Yıldız, Barış & Arslan, Okan & Karaşan, Oya Ekin, 2016. "A branch and price approach for routing and refueling station location model," European Journal of Operational Research, Elsevier, vol. 248(3), pages 815-826.
    14. Bernard Gendron & Abilio Lucena & Alexandre Salles da Cunha & Luidi Simonetti, 2014. "Benders Decomposition, Branch-and-Cut, and Hybrid Algorithms for the Minimum Connected Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 645-657, November.
    15. Halit Üster & Panitan Kewcharoenwong, 2011. "Strategic Design and Analysis of a Relay Network in Truckload Transportation," Transportation Science, INFORMS, vol. 45(4), pages 505-523, November.
    16. C S Sung & S H Song, 2003. "Branch-and-price algorithm for a combined problem of virtual path establishment and traffic packet routing in a layered communication network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(1), pages 72-82, January.
    17. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    18. Santini, Alberto & Plum, Christian E.M. & Ropke, Stefan, 2018. "A branch-and-price approach to the feeder network design problem," European Journal of Operational Research, Elsevier, vol. 264(2), pages 607-622.
    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. Kınay, Ömer Burak & Gzara, Fatma & Alumur, Sibel A., 2021. "Full cover charging station location problem with routing," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 1-22.
    2. S. Raghavan & Rui Zhang, 2022. "Rapid Influence Maximization on Social Networks: The Positive Influence Dominating Set Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1345-1365, May.
    3. Kewcharoenwong, Panitan & Li, Qiaofeng & Üster, Halit, 2023. "Lagrangean relaxation algorithms for fixed-charge capacitated relay network design," Omega, Elsevier, vol. 121(C).
    4. Xu, Min & Meng, Qiang, 2020. "Optimal deployment of charging stations considering path deviation and nonlinear elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 135(C), pages 120-142.

    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. Kewcharoenwong, Panitan & Li, Qiaofeng & Üster, Halit, 2023. "Lagrangean relaxation algorithms for fixed-charge capacitated relay network design," Omega, Elsevier, vol. 121(C).
    2. Yiyong Xiao & Abdullah Konak, 2017. "A variable neighborhood search for the network design problem with relays," Journal of Heuristics, Springer, vol. 23(2), pages 137-164, June.
    3. Barış Yıldız & Oya Ekin Karaşan, 2017. "Regenerator Location Problem in Flexible Optical Networks," Operations Research, INFORMS, vol. 65(3), pages 595-620, June.
    4. Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Regenerator Location Problem and survivable extensions: A hub covering location perspective," Transportation Research Part B: Methodological, Elsevier, vol. 71(C), pages 32-55.
    5. Arslan, Okan & Karaşan, Oya Ekin, 2016. "A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 670-695.
    6. Leitner, Markus & Ljubić, Ivana & Riedler, Martin & Ruthmair, Mario, 2020. "Exact approaches for the directed network design problem with relays," Omega, Elsevier, vol. 91(C).
    7. Xu, Min & Meng, Qiang, 2020. "Optimal deployment of charging stations considering path deviation and nonlinear elastic demand," Transportation Research Part B: Methodological, Elsevier, vol. 135(C), pages 120-142.
    8. Xu, Min & Meng, Qiang, 2019. "Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 23-49.
    9. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    10. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    11. Yıldız, Barış & Arslan, Okan & Karaşan, Oya Ekin, 2016. "A branch and price approach for routing and refueling station location model," European Journal of Operational Research, Elsevier, vol. 248(3), pages 815-826.
    12. Yıldız, Barış & Olcaytu, Evren & Şen, Ahmet, 2019. "The urban recharging infrastructure design problem with stochastic demands and capacitated charging stations," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 22-44.
    13. Zu-Jun Ma & Fei Yang & Ying Dai & Zuo-Jun Max Shen, 2021. "The Migratory Beekeeping Routing Problem: Model and an Exact Algorithm," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 319-335, January.
    14. Shen, Zuo-Jun Max & Feng, Bo & Mao, Chao & Ran, Lun, 2019. "Optimization models for electric vehicle service operations: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 462-477.
    15. Jie, Wanchen & Yang, Jun & Zhang, Min & Huang, Yongxi, 2019. "The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology," European Journal of Operational Research, Elsevier, vol. 272(3), pages 879-904.
    16. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    17. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    18. Wang, Mengtong & Miao, Lixin & Zhang, Canrong, 2021. "A branch-and-price algorithm for a green location routing problem with multi-type charging infrastructure," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    19. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    20. Li, Xiangyong & Lin, Shaochong & Tian, Peng & Aneja, Y.P., 2017. "Models and column generation approach for the resource-constrained minimum cost path problem with relays," Omega, Elsevier, vol. 66(PA), pages 79-90.

    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:inm:orijoc:v:31:y:2019:i:1:p:171-192. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.