IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v48y2000i5p745-760.html
   My bibliography  Save this article

Topological Design of Two-Level Telecommunication Networks with Modular Switches

Author

Listed:
  • Steven Chamberland

    (CRT and Department of Electrical Engineering, École de Technologie Supérieure, 1100, Notre-Dame Ouest, Montréal (Québec), Canada H3C 1K3)

  • Brunilde Sansò

    (GERAD and Department of Electrical Engineering and Computer Engineering, École Polytechnique de Montréal, C.P. 6079 Succ. Centre-Ville, Montréal (Québec), Canada H3C 3A7)

  • Odile Marcotte

    (GERAD and Department of Computer Science, Université du Québec à Montréal, C.P. 8888 Succ. Centre-Ville, Montréal, (Québec), Canada H3C 3P8)

Abstract

In this article we propose a mixed 0-1 linear programming model for the topological network design problem with modular switches such as the ones that will be used in asynchronous transfer mode (ATM) frame relay and other broadband networks. The model includes the location of switches, their configuration with respect to ports and multiplexers, the design of an access network with a star topology, and a backbone network with a fixed topology (ring or tree). To obtain a solution, we propose a greedy heuristic that provides a good starting solution, and a tabu search heuristic to improve the solution. Finally, we present an example of the application of the heuristics and results for a set of randomly generated problems with up to 500 users and 30 potential switch sites. For the hundreds of problems generated, the tabu algorithm produced solutions that were, on average, within 1.5% of the optimal solution, and in the worst case within 4.95% of the optimal solution.

Suggested Citation

  • Steven Chamberland & Brunilde Sansò & Odile Marcotte, 2000. "Topological Design of Two-Level Telecommunication Networks with Modular Switches," Operations Research, INFORMS, vol. 48(5), pages 745-760, October.
    • Handle: RePEc:inm:oropre:v:48:y:2000:i:5:p:745-760
    DOI: 10.1287/opre.48.5.745.12412
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.48.5.745.12412
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.48.5.745.12412?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. Fred Glover, 1989. "Tabu Search---Part I," INFORMS Journal on Computing, INFORMS, vol. 1(3), pages 190-206, August.
    2. Jeffery L. Kennington & Zhiming Wang, 1991. "An Empirical Analysis of the Dense Assignment Problem: Sequential and Parallel Implementations," INFORMS Journal on Computing, INFORMS, vol. 3(4), pages 299-306, November.
    3. 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.
    4. Volgenant, A., 1989. "A Lagrangean approach to the degree-constrained minimum spanning tree problem," European Journal of Operational Research, Elsevier, vol. 39(3), pages 325-331, April.
    5. Youngho Lee & Steve Y. Chiu & Jennifer Ryan, 1996. "A Branch and Cut Algorithm for a Steiner Tree-Star Problem," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 194-201, August.
    6. Fred Glover, 1990. "Tabu Search—Part II," INFORMS Journal on Computing, INFORMS, vol. 2(1), pages 4-32, February.
    7. Michel Gendreau & Alain Hertz & Gilbert Laporte, 1992. "New Insertion and Postoptimization Procedures for the Traveling Salesman Problem," Operations Research, INFORMS, vol. 40(6), pages 1086-1094, December.
    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. Steven Chamberland & Brunilde Sansò, 2001. "On the Design Problem of Multitechnology Networks," INFORMS Journal on Computing, INFORMS, vol. 13(3), pages 245-256, August.
    2. C S Sung & S H Song, 2003. "Integrated service network design for a cross-docking supply chain network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(12), pages 1283-1295, December.
    3. E A Cabral & E Erkut & G Laporte & R A Patterson, 2008. "Wide area telecommunication network design: application to the Alberta SuperNet," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(11), pages 1460-1470, November.
    4. Balakrishnan, Anantaram & Banciu, Mihai & Glowacka, Karolina & Mirchandani, Prakash, 2013. "Hierarchical approach for survivable network design," European Journal of Operational Research, Elsevier, vol. 225(2), pages 223-235.

    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. Olli Bräysy & Michel Gendreau, 2005. "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation Science, INFORMS, vol. 39(1), pages 119-139, February.
    2. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar & Mohammad Hassan Sharifitabar, 2015. "A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 48-58, February.
    3. Mohammad Javad Feizollahi & Igor Averbakh, 2014. "The Robust (Minmax Regret) Quadratic Assignment Problem with Interval Flows," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 321-335, May.
    4. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    5. Cazzaro, Davide & Fischetti, Martina & Fischetti, Matteo, 2020. "Heuristic algorithms for the Wind Farm Cable Routing problem," Applied Energy, Elsevier, vol. 278(C).
    6. Huang, Yeran & Yang, Lixing & Tang, Tao & Gao, Ziyou & Cao, Fang, 2017. "Joint train scheduling optimization with service quality and energy efficiency in urban rail transit networks," Energy, Elsevier, vol. 138(C), pages 1124-1147.
    7. B Dengiz & C Alabas-Uslu & O Dengiz, 2009. "Optimization of manufacturing systems using a neural network metamodel with a new training approach," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(9), pages 1191-1197, September.
    8. S-W Lin & K-C Ying, 2008. "A hybrid approach for single-machine tardiness problems with sequence-dependent setup times," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(8), pages 1109-1119, August.
    9. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.
    10. Abdmouleh, Zeineb & Gastli, Adel & Ben-Brahim, Lazhar & Haouari, Mohamed & Al-Emadi, Nasser Ahmed, 2017. "Review of optimization techniques applied for the integration of distributed generation from renewable energy sources," Renewable Energy, Elsevier, vol. 113(C), pages 266-280.
    11. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    12. Chris S. K. Leung & Henry Y. K. Lau, 2018. "Multiobjective Simulation-Based Optimization Based on Artificial Immune Systems for a Distribution Center," Journal of Optimization, Hindawi, vol. 2018, pages 1-15, May.
    13. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, August.
    14. Andaryan, Abdullah Zareh & Mousighichi, Kasra & Ghaffarinasab, Nader, 2024. "A heuristic approach to the stochastic capacitated single allocation hub location problem with Bernoulli demands," European Journal of Operational Research, Elsevier, vol. 312(3), pages 954-968.
    15. Panta Lučić & Dušan Teodorović, 2007. "Metaheuristics approach to the aircrew rostering problem," Annals of Operations Research, Springer, vol. 155(1), pages 311-338, November.
    16. Haluk Yapicioglu, 2018. "Multiperiod Multi Traveling Salesmen Problem Considering Time Window Constraints with an Application to a Real World Case," Networks and Spatial Economics, Springer, vol. 18(4), pages 773-801, December.
    17. Daniel O’Malley & Velimir V Vesselinov & Boian S Alexandrov & Ludmil B Alexandrov, 2018. "Nonnegative/Binary matrix factorization with a D-Wave quantum annealer," PLOS ONE, Public Library of Science, vol. 13(12), pages 1-12, December.
    18. Marco Antonio Boschetti & Vittorio Maniezzo, 2022. "Matheuristics: using mathematics for heuristic design," 4OR, Springer, vol. 20(2), pages 173-208, June.
    19. C-H Lan & C-C Chen, 2007. "Optimal purchase of two-itemized drugs for a disease," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 309-316, March.
    20. G Lulli & U Pietropaoli & N Ricciardi, 2011. "Service network design for freight railway transportation: the Italian case," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2107-2119, December.

    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:oropre:v:48:y:2000:i:5:p:745-760. 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.