IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v45y1999i3p330-345.html
   My bibliography  Save this article

Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search

Author

Listed:
  • Jiefeng Xu

    (Delta Technology, Inc., 1001 International Boulevard, Atlanta, Georgia 30354-1801)

  • Steve Y. Chiu

    (GTE Laboratories, Inc., 40 Sylvan Road, Waltham, Massachusetts 02254)

  • Fred Glover

    (Graduate School of Business, University of Colorado at Boulder, Boulder, Colorado 80309-0419)

Abstract

One of the private line network design problems in the telecommunications industry is to interconnect a set of customer locations through a ring of end offices so as to minimize the total tariff cost and provide reliability. We develop a Tabu Search method for the problem that incorporates long term memory, probabilistic move selections, hierarchical move evaluation, candidate list strategies and an elite solution recovery strategy. Computational results for test data show that the Tabu Search heuristic finds optimal solutions for all test problems that can be solved exactly by a branch-and-cut algorithm, while running about three orders of magnitude faster than the exact algorithm. In addition, for larger size problems that cannot be solved exactly, the tabu search algorithm outperforms the best local search heuristic currently available. The performance gap favoring Tabu Search increases significantly for more difficult problem instances.

Suggested Citation

  • Jiefeng Xu & Steve Y. Chiu & Fred Glover, 1999. "Optimizing a Ring-Based Private Line Telecommunication Network Using Tabu Search," Management Science, INFORMS, vol. 45(3), pages 330-345, March.
    • Handle: RePEc:inm:ormnsc:v:45:y:1999:i:3:p:330-345
    DOI: 10.1287/mnsc.45.3.330
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/mnsc.45.3.330
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.45.3.330?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. Laporte, Gilbert, 1992. "The traveling salesman problem: An overview of exact and approximate algorithms," European Journal of Operational Research, Elsevier, vol. 59(2), pages 231-247, June.
    2. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka, 1994. "On tabu search for the location of interacting hub facilities," European Journal of Operational Research, Elsevier, vol. 73(3), pages 502-509, March.
    3. Manuel Laguna, 1994. "Clustering for the Design of SONET Rings in Interoffice Telecommunications," Management Science, INFORMS, vol. 40(11), pages 1533-1541, November.
    4. Jiefeng Xu & James P. Kelly, 1996. "A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem," Transportation Science, INFORMS, vol. 30(4), pages 379-393, November.
    5. Manuel Laguna & Fred Glover, 1993. "Bandwidth Packing: A Tabu Search Approach," Management Science, INFORMS, vol. 39(4), pages 492-500, April.
    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. Russell, Robert A. & Chiang, Wen-Chyuan, 2006. "Scatter search for the vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 169(2), pages 606-622, March.
    2. Contreras, Ivan & Fernández, Elena, 2012. "General network design: A unified view of combined location and network design problems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 680-697.
    3. Labbe, Martine & Laporte, Gilbert & Rodriguez Martin, Inmaculada & Gonzalez, Juan Jose Salazar, 2005. "Locating median cycles in networks," European Journal of Operational Research, Elsevier, vol. 160(2), pages 457-470, January.
    4. Glock, Katharina & Meyer, Anne, 2023. "Spatial coverage in routing and path planning problems," European Journal of Operational Research, Elsevier, vol. 305(1), pages 1-20.
    5. Alfandari, Laurent & Ljubić, Ivana & De Melo da Silva, Marcos, 2022. "A tailored Benders decomposition approach for last-mile delivery with autonomous robots," European Journal of Operational Research, Elsevier, vol. 299(2), pages 510-525.
    6. Baldacci, R. & Dell'Amico, M., 2010. "Heuristic algorithms for the multi-depot ring-star problem," European Journal of Operational Research, Elsevier, vol. 203(1), pages 270-281, May.
    7. 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. Kafle, Nabin & Zou, Bo & Lin, Jane, 2017. "Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 62-82.
    2. Chu, Chao-Hsien & Premkumar, G. & Chou, Hsinghua, 2000. "Digital data networks design using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 127(1), pages 140-158, November.
    3. Manuel Laguna, 1998. "Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty," Management Science, INFORMS, vol. 44(11-Part-2), pages 101-110, November.
    4. Sudip Bhattacharjee & Hong Zhang & R. Ramesh & Dee H. Andrews, 2007. "A Decomposition and Guided Simulation Methodology for Large-Scale System Design: A Study in QoS-Capable Intranets with Fixed and Mobile Components," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 429-442, August.
    5. Marianov, Vladimir & Serra, Daniel & ReVelle, Charles, 1999. "Location of hubs in a competitive environment," European Journal of Operational Research, Elsevier, vol. 114(2), pages 363-371, April.
    6. Skorin-Kapov, Darko & Skorin-Kapov, Jadranka, 2005. "Threshold based discounting networks: The cost allocation provided by the nucleolus," European Journal of Operational Research, Elsevier, vol. 166(1), pages 154-159, October.
    7. 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.
    8. Dhyani, Sneha & Jayaswal, Sachin & Sinha, Ankur & Vidyarthi, Navneet, 2019. "Alternate Second Order Conic Programming Reformulations for Hub Location with Capacity Selection under Demand," IIMA Working Papers WP 2018-12-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    9. Vidyarthi, Navneet & Jayaswal, Sachin & Chetty, Vikranth Babu Tirumala, 2013. "Exact Solution to Bandwidth Packing Problem with Queuing Delays," IIMA Working Papers WP2013-11-04, Indian Institute of Management Ahmedabad, Research and Publication Department.
    10. Niels Agatz & Paul Bouman & Marie Schmidt, 2018. "Optimization Approaches for the Traveling Salesman Problem with Drone," Transportation Science, INFORMS, vol. 52(4), pages 965-981, August.
    11. Сластников С.А., 2014. "Применение Метаэвристических Алгоритмов Для Задачи Маршрутизации Транспорта," Журнал Экономика и математические методы (ЭММ), Центральный Экономико-Математический Институт (ЦЭМИ), vol. 50(1), pages 117-126, январь.
    12. A. T. Ernst & M. Krishnamoorthy, 1998. "An Exact Solution Approach Based on Shortest-Paths for p -Hub Median Problems," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 149-162, May.
    13. Kusum Deep & Hadush Mebrahtu & Atulya K. Nagar, 2018. "Novel GA for metropolitan stations of Indian railways when modelled as a TSP," International Journal of System Assurance Engineering and Management, Springer;The Society for Reliability, Engineering Quality and Operations Management (SREQOM),India, and Division of Operation and Maintenance, Lulea University of Technology, Sweden, vol. 9(3), pages 639-645, June.
    14. Müller, R.J. & Gui, H. & Vohra, R., 2004. "Dominant strategy mechanisms with multidimensional types," Research Memorandum 046, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    15. Ricardo Saraiva de Camargo & Gilberto de Miranda & Henrique Pacca L. Luna, 2009. "Benders Decomposition for Hub Location Problems with Economies of Scale," Transportation Science, INFORMS, vol. 43(1), pages 86-97, February.
    16. Schuijbroek, J. & Hampshire, R.C. & van Hoeve, W.-J., 2017. "Inventory rebalancing and vehicle routing in bike sharing systems," European Journal of Operational Research, Elsevier, vol. 257(3), pages 992-1004.
    17. Tang, Lixin & Liu, Jiyin & Rong, Aiying & Yang, Zihou, 2000. "A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex," European Journal of Operational Research, Elsevier, vol. 124(2), pages 267-282, July.
    18. Castellano, Davide & Gallo, Mosè & Grassi, Andrea & Santillo, Liberatina C., 2019. "The effect of GHG emissions on production, inventory replenishment and routing decisions in a single vendor-multiple buyers supply chain," International Journal of Production Economics, Elsevier, vol. 218(C), pages 30-42.
    19. Gagliardi, Jean-Philippe & Ruiz, Angel & Renaud, Jacques, 2008. "Space allocation and stock replenishment synchronization in a distribution center," International Journal of Production Economics, Elsevier, vol. 115(1), pages 19-27, September.
    20. Vaithyanathan, Shivakumar & Burke, Laura I. & Magent, Michael A., 1996. "Massively parallel analog tabu search using neural networks applied to simple plant location problems," European Journal of Operational Research, Elsevier, vol. 93(2), pages 317-330, September.

    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:ormnsc:v:45:y:1999:i:3:p:330-345. 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.