IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v40y2020i2d10.1007_s10878-020-00576-2.html
   My bibliography  Save this article

The band collocation problem

Author

Listed:
  • Hakan Kutucu

    (Karabuk University)

  • Arif Gursoy

    (Ege University)

  • Mehmet Kurt

    (Bahcesehir University)

  • Urfat Nuriyev

    (Ege University
    Institute of Control Systems of Azerbaijan National Academy of Sciences)

Abstract

In order to reduce costs in the telecommunication sector, many mathematical models have been developed. Over time, these models either fall out out of use or are revised according to new technological developments. The Bandpass Problem (BP) is an optimization problem introduced in 2004 to reduce hardware costs in communication networks. However, over time, technological advances in fiber-optic networks have caused the BP to lose functionality and usability. Major changes should be made to the model to make the BP functional again. It is necessary to define the problem after having made these changes as a new problem, not as a revised problem. In this paper, we first review the BP. We then discuss the notion that the BP has become unusable due to technological developments. We introduce a new problem called the Band Collocation Problem (BCP), which fixes the issues in the BP. We also develop several mathematical models of the BCP. Furthermore, we prove that the BCP is NP-hard. In order to encourage further research, we develop a Library of Band Collocation Problems. Finally, we present heuristic and meta-heuristic methods to solve the BCP and compare the computational results.

Suggested Citation

  • Hakan Kutucu & Arif Gursoy & Mehmet Kurt & Urfat Nuriyev, 2020. "The band collocation problem," Journal of Combinatorial Optimization, Springer, vol. 40(2), pages 454-481, August.
    • Handle: RePEc:spr:jcomop:v:40:y:2020:i:2:d:10.1007_s10878-020-00576-2
    DOI: 10.1007/s10878-020-00576-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00576-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-020-00576-2?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. Guohui Lin, 2011. "On the Bandpass problem," Journal of Combinatorial Optimization, Springer, vol. 22(1), pages 71-77, July.
    2. G. A. Croes, 1958. "A Method for Solving Traveling-Salesman Problems," Operations Research, INFORMS, vol. 6(6), pages 791-812, December.
    3. Djangir A. Babayev & George I. Bell & Urfat G. Nuriyev, 2009. "The bandpass problem: combinatorial optimization and library of problems," Journal of Combinatorial Optimization, Springer, vol. 18(2), pages 151-172, August.
    4. Hakan Kutucu & Arif Gursoy & Mehmet Kurt & Urfat Nuriyev, 0. "The band collocation problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-28.
    Full references (including those not matched with items on IDEAS)

    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. Hakan Kutucu & Arif Gursoy & Mehmet Kurt & Urfat Nuriyev, 0. "The band collocation problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-28.
    2. Liqin Huang & Weitian Tong & Randy Goebel & Tian Liu & Guohui Lin, 2015. "A 0.5358-approximation for Bandpass-2," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 612-626, October.
    3. Jesús Sánchez-Oro & Manuel Laguna & Rafael Martí & Abraham Duarte, 2016. "Scatter search for the bandpass problem," Journal of Global Optimization, Springer, vol. 66(4), pages 769-790, December.
    4. Ahmed Kheiri & Alina G. Dragomir & David Mueller & Joaquim Gromicho & Caroline Jagtenberg & Jelke J. Hoorn, 2019. "Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(5), pages 561-595, December.
    5. Tarantilis, C. D. & Diakoulaki, D. & Kiranoudis, C. T., 2004. "Combination of geographical information system and efficient routing algorithms for real life distribution operations," European Journal of Operational Research, Elsevier, vol. 152(2), pages 437-453, January.
    6. R Torres-Velázquez & V Estivill-Castro, 2004. "Local search for Hamiltonian Path with applications to clustering visitation paths," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(7), pages 737-748, July.
    7. 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.
    8. Nair, D.J. & Grzybowska, H. & Fu, Y. & Dixit, V.V., 2018. "Scheduling and routing models for food rescue and delivery operations," Socio-Economic Planning Sciences, Elsevier, vol. 63(C), pages 18-32.
    9. Pan-Li Zhang & Xiao-Bo Sun & Ji-Quan Wang & Hao-Hao Song & Jin-Ling Bei & Hong-Yu Zhang, 2022. "The Discrete Carnivorous Plant Algorithm with Similarity Elimination Applied to the Traveling Salesman Problem," Mathematics, MDPI, vol. 10(18), pages 1-34, September.
    10. Arthur Charpentier & Romuald Élie & Carl Remlinger, 2023. "Reinforcement Learning in Economics and Finance," Computational Economics, Springer;Society for Computational Economics, vol. 62(1), pages 425-462, June.
    11. Ozgur, C. O. & Brown, J. R., 1995. "A two-stage traveling salesman procedure for the single machine sequence-dependent scheduling problem," Omega, Elsevier, vol. 23(2), pages 205-219, April.
    12. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    13. CASTRO, Marco & SÖRENSEN, Kenneth & VANSTEENWEGEN, Pieter & GOOS, Peter, 2012. "A simple GRASP+VND for the travelling salesperson problem with hotel selection," Working Papers 2012024, University of Antwerp, Faculty of Business and Economics.
    14. Guohui Lin, 2011. "On the Bandpass problem," Journal of Combinatorial Optimization, Springer, vol. 22(1), pages 71-77, July.
    15. Eric Bonabeau & Florian Henaux & Sylvain Gu'erin & Dominique Snyers & Pascale Kuntz & Guy Theraulaz, 1998. "Routing in Telecommunications Networks with ``Smart'' Ant-Like Agents," Working Papers 98-01-003, Santa Fe Institute.
    16. Dimitris Bertsimas & Patrick Jaillet, & Sébastien Martin, 2019. "Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications," Operations Research, INFORMS, vol. 67(1), pages 143-162, January.
    17. Alain Hertz & Gilbert Laporte & Pierrette Nanchen Hugo, 1999. "Improvement Procedures for the Undirected Rural Postman Problem," INFORMS Journal on Computing, INFORMS, vol. 11(1), pages 53-62, February.
    18. Zachariadis, Emmanouil E. & Tarantilis, Christos D. & Kiranoudis, Christos T., 2009. "A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints," European Journal of Operational Research, Elsevier, vol. 195(3), pages 729-743, June.
    19. Z P Fan & Y Chen & J Ma & S Zeng, 2011. "Erratum: A hybrid genetic algorithmic approach to the maximally diverse grouping problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(7), pages 1423-1430, July.
    20. Krzysztof Ostrowski & Joanna Karbowska-Chilinska & Jolanta Koszelew & Pawel Zabielski, 2017. "Evolution-inspired local improvement algorithm solving orienteering problem," Annals of Operations Research, Springer, vol. 253(1), pages 519-543, June.

    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:spr:jcomop:v:40:y:2020:i:2:d:10.1007_s10878-020-00576-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.