IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v303y2022i1p1-13.html
   My bibliography  Save this article

A taxonomy of multilayer network design and a survey of transportation and telecommunication applications

Author

Listed:
  • Crainic, Teodor Gabriel
  • Gendron, Bernard
  • Akhavan Kazemzadeh, Mohammad Rahim

Abstract

Multilayer network design represents an important problem class when interwoven design decisions must be simultaneously considered. Examples of such cases are the selection of trains and blocks in freight rail transportation and the selection of physical and logical paths in telecommunications. Each set of those design variables are then defined on a particular network making up a layer with its own nodes, which can represent or not the same physical or conceptual locations, potential arcs, with fixed selection cost and with or without limited capacities, and, possibly, multicommodity demands, which need to be routed within the layer by selecting/opening the appropriate arcs. The particular characteristic and challenge of multilayer network design consists in the various design and flow-connectivity requirements linking the decisions on different layers. Thus, for example, to select a light path, all the links making up the supporting physical path must be installed. Similarly, to select a transportation service, all the supporting resources must be selected together with their feasible working paths in the corresponding layers. We propose the first classification and a state-of-the-art survey of multilayer network design problems. The survey focuses on applications in transportation and telecommunications, as well as on solution methods. We also propose a general modeling framework which encompasses the models in the literature.

Suggested Citation

  • Crainic, Teodor Gabriel & Gendron, Bernard & Akhavan Kazemzadeh, Mohammad Rahim, 2022. "A taxonomy of multilayer network design and a survey of transportation and telecommunication applications," European Journal of Operational Research, Elsevier, vol. 303(1), pages 1-13.
  • Handle: RePEc:eee:ejores:v:303:y:2022:i:1:p:1-13
    DOI: 10.1016/j.ejor.2021.12.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721010821
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2021.12.028?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. Anantaram Balakrishnan & Thomas L. Magnanti & Prakash Mirchandani, 1994. "A Dual-Based Algorithm for Multi-Level Network Design," Management Science, INFORMS, vol. 40(5), pages 567-581, May.
    2. Jean-François Cordeau & Federico Pasin & Marius Solomon, 2006. "An integrated model for logistics network design," Annals of Operations Research, Springer, vol. 144(1), pages 59-82, April.
    3. Teodor Gabriel Crainic & Bernard Gendron, 2021. "Exact Methods for Fixed-Charge Network Design," Springer Books, in: Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron (ed.), Network Design with Applications to Transportation and Logistics, chapter 0, pages 29-89, Springer.
    4. Andersen, Jardar & Crainic, Teodor Gabriel & Christiansen, Marielle, 2009. "Service network design with management and coordination of multiple fleets," European Journal of Operational Research, Elsevier, vol. 193(2), pages 377-389, March.
    5. Jean-François Cordeau & Goran Stojković & François Soumis & Jacques Desrosiers, 2001. "Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling," Transportation Science, INFORMS, vol. 35(4), pages 375-388, November.
    6. Teodor Gabriel Crainic & Mike Hewitt & Michel Toulouse & Duc Minh Vu, 2018. "Scheduled service network design with resource acquisition and management," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 277-309, September.
    7. Obreque, Carlos & Donoso, Macarena & Gutiérrez, Gabriel & Marianov, Vladimir, 2010. "A branch and cut algorithm for the hierarchical network design problem," European Journal of Operational Research, Elsevier, vol. 200(1), pages 28-35, January.
    8. Teodor Gabriel Crainic & Michel Gendreau, 2021. "Heuristics and Metaheuristics for Fixed-Charge Network Design," Springer Books, in: Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron (ed.), Network Design with Applications to Transportation and Logistics, chapter 0, pages 91-138, Springer.
    9. Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron, 2021. "Fixed-Charge Network Design Problems," Springer Books, in: Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron (ed.), Network Design with Applications to Transportation and Logistics, chapter 0, pages 15-28, Springer.
    10. Knippel, Arnaud & Lardeux, Benoit, 2007. "The multi-layered network design problem," European Journal of Operational Research, Elsevier, vol. 183(1), pages 87-99, November.
    11. Hewitt, Mike & Crainic, Teodor Gabriel & Nowak, Maciek & Rei, Walter, 2019. "Scheduled service network design with resource acquisition and management under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 324-343.
    12. Mervat Chouman & Teodor Gabriel Crainic, 2021. "Freight Railroad Service Network Design," Springer Books, in: Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron (ed.), Network Design with Applications to Transportation and Logistics, chapter 0, pages 383-426, Springer.
    13. Endong Zhu & Teodor Gabriel Crainic & Michel Gendreau, 2014. "Scheduled Service Network Design for Freight Rail Transportation," Operations Research, INFORMS, vol. 62(2), pages 383-400, April.
    14. 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.
    15. Costa, Alysson M. & França, Paulo M. & Lyra Filho, Christiano, 2011. "Two-level network design with intermediate facilities: An application to electrical distribution systems," Omega, Elsevier, vol. 39(1), pages 3-13, January.
    16. Amy Mainville Cohn & Cynthia Barnhart, 2003. "Improving Crew Scheduling by Incorporating Key Maintenance Routing Decisions," Operations Research, INFORMS, vol. 51(3), pages 387-396, June.
    17. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    18. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    19. Daeki Kim & Cynthia Barnhart & Keith Ware & Gregory Reinhardt, 1999. "Multimodal Express Package Delivery: A Service Network Design Application," Transportation Science, INFORMS, vol. 33(4), pages 391-407, November.
    20. Michael Berliner Pedersen & Teodor Gabriel Crainic & Oli B. G. Madsen, 2009. "Models and Tabu Search Metaheuristics for Service Network Design with Asset-Balance Requirements," Transportation Science, INFORMS, vol. 43(2), pages 158-177, May.
    21. Geir Dahl & Alexander Martin & Mechthild Stoer, 1999. "Routing Through Virtual Paths in Layered Telecommunication Networks," Operations Research, INFORMS, vol. 47(5), pages 693-702, October.
    22. Jardar Andersen & Marielle Christiansen & Teodor Gabriel Crainic & Roar Grønhaug, 2011. "Branch and Price for Service Network Design with Asset Management Constraints," Transportation Science, INFORMS, vol. 45(1), pages 33-49, February.
    23. Sara Mattia, 2012. "Solving survivable two-layer network design problems by metric inequalities," Computational Optimization and Applications, Springer, vol. 51(2), pages 809-834, March.
    24. Lin, Cheng-Chang, 2010. "The integrated secondary route network design model in the hierarchical hub-and-spoke network for dual express services," International Journal of Production Economics, Elsevier, vol. 123(1), pages 20-30, January.
    25. Teodor Gabriel Crainic & Mike Hewitt, 2021. "Service Network Design," Springer Books, in: Teodor Gabriel Crainic & Michel Gendreau & Bernard Gendron (ed.), Network Design with Applications to Transportation and Logistics, chapter 0, pages 347-382, Springer.
    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. Eskandarzadeh, Saman & Fahimnia, Behnam, 2024. "Containerised parcel delivery: Modelling and performance evaluation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 186(C).
    2. Dukkanci, Okan & Campbell, James F. & Kara, Bahar Y., 2024. "Facility location decisions for drone delivery: A literature review," European Journal of Operational Research, Elsevier, vol. 316(2), pages 397-418.

    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. Li, Xiangyong & Ding, Yi & Pan, Kai & Jiang, Dapei & Aneja, Y.P., 2020. "Single-path service network design problem with resource constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    2. Hewitt, Mike & Lehuédé, Fabien, 2023. "New formulations for the Scheduled Service Network Design Problem," Transportation Research Part B: Methodological, Elsevier, vol. 172(C), pages 117-133.
    3. Dayarian, Iman & Rocco, Adolfo & Erera, Alan & Savelsbergh, Martin, 2022. "Operations design for high-velocity intra-city package service," Transportation Research Part B: Methodological, Elsevier, vol. 161(C), pages 150-168.
    4. Belieres, Simon & Hewitt, Mike, 2024. "Hedging against uncertainty in transportation network design through flexible scheduling," Omega, Elsevier, vol. 126(C).
    5. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.
    6. Wang, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.
    7. Li, Xiangyong & Wei, Kai & Aneja, Y.P. & Tian, Peng, 2017. "Design-balanced capacitated multicommodity network design with heterogeneous assets," Omega, Elsevier, vol. 67(C), pages 145-159.
    8. Satici, Ozgur & Dayarian, Iman, 2024. "Tactical and operational planning of express intra-city package services," Omega, Elsevier, vol. 122(C).
    9. Wang, Zujian & Qi, Mingyao & Cheng, Chun & Zhang, Canrong, 2019. "A hybrid algorithm for large-scale service network design considering a heterogeneous fleet," European Journal of Operational Research, Elsevier, vol. 276(2), pages 483-494.
    10. Bilegan, Ioana C. & Crainic, Teodor Gabriel & Wang, Yunfei, 2022. "Scheduled service network design with revenue management considerations and an intermodal barge transportation illustration," European Journal of Operational Research, Elsevier, vol. 300(1), pages 164-177.
    11. Li, Xiangyong & Wei, Kai & Guo, Zhaoxia & Wang, Wei & Aneja, Y.P., 2021. "An exact approach for the service network design problem with heterogeneous resource constraints," Omega, Elsevier, vol. 102(C).
    12. Mervat Chouman & Teodor Gabriel Crainic, 2015. "Cutting-Plane Matheuristic for Service Network Design with Design-Balanced Requirements," Transportation Science, INFORMS, vol. 49(1), pages 99-113, February.
    13. Hewitt, Mike & Crainic, Teodor Gabriel & Nowak, Maciek & Rei, Walter, 2019. "Scheduled service network design with resource acquisition and management under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 324-343.
    14. Zhang, X. & Liu, X., 2022. "A two-stage robust model for express service network design with surging demand," European Journal of Operational Research, Elsevier, vol. 299(1), pages 154-167.
    15. Bai, Ruibin & Wallace, Stein W. & Li, Jingpeng & Chong, Alain Yee-Loong, 2014. "Stochastic service network design with rerouting," Transportation Research Part B: Methodological, Elsevier, vol. 60(C), pages 50-65.
    16. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2017. "Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design," Transportation Science, INFORMS, vol. 51(2), pages 650-667, May.
    17. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    18. Naoto Katayama, 2020. "MIP neighborhood search heuristics for a service network design problem with design-balanced requirements," Journal of Heuristics, Springer, vol. 26(4), pages 475-502, August.
    19. Eskandarzadeh, Saman & Fahimnia, Behnam, 2024. "Containerised parcel delivery: Modelling and performance evaluation," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 186(C).
    20. Greening, Lacy M. & Dahan, Mathieu & Erera, Alan L., 2023. "Lead-Time-Constrained Middle-Mile Consolidation Network Design with Fixed Origins and Destinations," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).

    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:eee:ejores:v:303:y:2022:i:1:p:1-13. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.