IDEAS home Printed from https://ideas.repec.org/a/taf/uiiexx/v44y2012i8p681-694.html
   My bibliography  Save this article

The flowtime network construction problem

Author

Listed:
  • Igor Averbakh
  • Jordi Pereira

Abstract

Given a network whose edges need to be constructed, the problem is to find a construction schedule that minimizes the total recovery time of the vertices, where the recovery time of a vertex is the time when the vertex becomes connected to a special vertex (depot) that is the initial location of the construction crew. The construction speed is constant and is assumed to be incomparably slower than the travel speed of the construction crew in the already constructed part of the network. In this article, this new problem is introduced, its complexity is discussed, mixed-integer linear programming formulations are developed, fast and simple heuristics are proposed, and an exact branch-and-bound algorithm is presented which is based on specially designed lower bounds and dominance tests that exploit the problem’s combinatorial structure. The results of extensive computational experiments are also presented. Connections between the problem and the Traveling Repairman Problem, also known as the Delivery Man Problem, and applications in emergency restoration operations are discussed.

Suggested Citation

  • Igor Averbakh & Jordi Pereira, 2012. "The flowtime network construction problem," IISE Transactions, Taylor & Francis Journals, vol. 44(8), pages 681-694.
    • Handle: RePEc:taf:uiiexx:v:44:y:2012:i:8:p:681-694
    DOI: 10.1080/0740817X.2011.636792
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/0740817X.2011.636792
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/0740817X.2011.636792?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.

    Citations

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


    Cited by:

    1. Hongtan Sun & Thomas C. Sharkey, 2017. "Approximation guarantees of algorithms for fractional optimization problems arising in dispatching rules for INDS problems," Journal of Global Optimization, Springer, vol. 68(3), pages 623-640, July.
    2. Francis Bloch & Bhaskar Dutta & Marcin Dziubi´nski, 2024. "Strategic hiding and exploration in networks," Working Papers 112, Ashoka University, Department of Economics.
    3. Aybike Ulusan & Ozlem Ergun, 2018. "Restoration of services in disrupted infrastructure systems: A network science approach," PLOS ONE, Public Library of Science, vol. 13(2), pages 1-28, February.
    4. Ni, Ni & Howell, Brendan J. & Sharkey, Thomas C., 2018. "Modeling the impact of unmet demand in supply chain resiliency planning," Omega, Elsevier, vol. 81(C), pages 1-16.
    5. Sanci, Ece & Daskin, Mark S., 2019. "Integrating location and network restoration decisions in relief networks under uncertainty," European Journal of Operational Research, Elsevier, vol. 279(2), pages 335-350.
    6. Garrett, Richard A. & Sharkey, Thomas C. & Grabowski, Martha & Wallace, William A., 2017. "Dynamic resource allocation to support oil spill response planning for energy exploration in the Arctic," European Journal of Operational Research, Elsevier, vol. 257(1), pages 272-286.
    7. Felix Happach & Lisa Hellerstein & Thomas Lidbetter, 2022. "A General Framework for Approximating Min Sum Ordering Problems," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1437-1452, May.
    8. Canbilen Sütiçen, Tuğçe & Batun, Sakine & Çelik, Melih, 2023. "Integrated reinforcement and repair of interdependent infrastructure networks under disaster-related uncertainties," European Journal of Operational Research, Elsevier, vol. 308(1), pages 369-384.
    9. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    10. Melih Çelik & Özlem Ergun & Pınar Keskinocak, 2015. "The Post-Disaster Debris Clearance Problem Under Incomplete Information," Operations Research, INFORMS, vol. 63(1), pages 65-85, February.
    11. Igor Averbakh & Jordi Pereira, 2018. "Lateness Minimization in Pairwise Connectivity Restoration Problems," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 522-538, August.
    12. Iloglu, Suzan & Albert, Laura A., 2018. "An integrated network design and scheduling problem for network recovery and emergency response," Operations Research Perspectives, Elsevier, vol. 5(C), pages 218-231.
    13. Baxter, Matthew & Elgindy, Tarek & Ernst, Andreas T. & Kalinowski, Thomas & Savelsbergh, Martin W.P., 2014. "Incremental network design with shortest paths," European Journal of Operational Research, Elsevier, vol. 238(3), pages 675-684.
    14. Nihal Berktaş & Bahar Yetiş Kara & Oya Ekin Karaşan, 2016. "Solution methodologies for debris removal in disaster response," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(3), pages 403-445, September.
    15. Sharkey, Thomas C. & Cavdaroglu, Burak & Nguyen, Huy & Holman, Jonathan & Mitchell, John E. & Wallace, William A., 2015. "Interdependent network restoration: On the value of information-sharing," European Journal of Operational Research, Elsevier, vol. 244(1), pages 309-321.
    16. Garay-Sianca, Aniela & Nurre Pinkley, Sarah G., 2021. "Interdependent integrated network design and scheduling problems with movement of machines," European Journal of Operational Research, Elsevier, vol. 289(1), pages 297-327.
    17. Tianyu Wang & Igor Averbakh, 2022. "Network construction/restoration problems: cycles and complexity," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 51-73, August.
    18. Averbakh, Igor & Pereira, Jordi, 2015. "Network construction problems with due dates," European Journal of Operational Research, Elsevier, vol. 244(3), pages 715-729.

    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:taf:uiiexx:v:44:y:2012:i:8:p:681-694. 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.

    We have no bibliographic references for this item. You can help adding them by using 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 Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/uiie .

    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.