IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0264584.html

A novel approach to the Orienteering Problem based on the Harmony Search algorithm

Author

Listed:
  • Krzysztof Szwarc
  • Urszula Boryczka

Abstract

This article presents a new approach to designing a Harmony Search (HS) algorithm, adapted to solve Orienteering Problem (OP) instances. OP is a significant N P-hard problem that has considerable practical application, requiring the development of an effective method for determining its solutions. The proposed HS has demonstrated its effectiveness through determined optimum results for each task from the six most popular benchmarks; a marginal number approximated the best results, with the average error below 0.01%. The article details the application of this described algorithm, comparing its results with those of state-of-the-art methods, indicating the significant efficiency of the proposed approach.

Suggested Citation

  • Krzysztof Szwarc & Urszula Boryczka, 2022. "A novel approach to the Orienteering Problem based on the Harmony Search algorithm," PLOS ONE, Public Library of Science, vol. 17(2), pages 1-21, February.
    • Handle: RePEc:plo:pone00:0264584
    DOI: 10.1371/journal.pone.0264584
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0264584
    Download Restriction: no
    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0264584&type=printable
    Download Restriction: no
    File URL: https://libkey.io/10.1371/journal.pone.0264584?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. Thibaut Vidal & Nelson Maculan & Luiz Satoru Ochi & Puca Huachi Vaz Penna, 2016. "Large Neighborhoods with Implicit Customer Selection for Vehicle Routing Problems with Profits," Transportation Science, INFORMS, vol. 50(2), pages 720-734, May.
    2. Chao, I-Ming & Golden, Bruce L. & Wasil, Edward A., 1996. "A fast and effective heuristic for the orienteering problem," European Journal of Operational Research, Elsevier, vol. 88(3), pages 475-489, February.
    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. Dang, Duc-Cuong & Guibadj, Rym Nesrine & Moukrim, Aziz, 2013. "An effective PSO-inspired algorithm for the team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 332-344.
    2. Luo, Zhixing & Cheang, Brenda & Lim, Andrew & Zhu, Wenbin, 2013. "An adaptive ejection pool with toggle-rule diversification approach for the capacitated team orienteering problem," European Journal of Operational Research, Elsevier, vol. 229(3), pages 673-682.
    3. Azi, Nabila & Gendreau, Michel & Potvin, Jean-Yves, 2010. "An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles," European Journal of Operational Research, Elsevier, vol. 202(3), pages 756-763, May.
    4. Toni Pacheco & Rafael Martinelli & Anand Subramanian & Túlio A. M. Toffolo & Thibaut Vidal, 2023. "Exponential-Size Neighborhoods for the Pickup-and-Delivery Traveling Salesman Problem," Transportation Science, INFORMS, vol. 57(2), pages 463-481, March.
    5. Dominique Feillet & Pierre Dejax & Michel Gendreau, 2005. "Traveling Salesman Problems with Profits," Transportation Science, INFORMS, vol. 39(2), pages 188-205, May.
    6. Matthew Henchey & Scott Rosen, 2021. "Emerging approaches to support dynamic mission planning: survey and recommendations for future research," The Journal of Defense Modeling and Simulation, , vol. 18(4), pages 453-468, October.
    7. Ruiz-Meza, José & Montoya-Torres, Jairo R., 2022. "A systematic literature review for the tourist trip design problem: Extensions, solution techniques and future research lines," Operations Research Perspectives, Elsevier, vol. 9(C).
    8. Divsalar, A. & Vansteenwegen, P. & Cattrysse, D., 2013. "A variable neighborhood search method for the orienteering problem with hotel selection," International Journal of Production Economics, Elsevier, vol. 145(1), pages 150-160.
    9. Archetti, C. & Coelho, L.C. & Speranza, M.G. & Vansteenwegen, P., 2026. "Beyond fifty years of vehicle routing: Insights into the history and the future," European Journal of Operational Research, Elsevier, vol. 330(2), pages 355-372.
    10. Fabian Akkerman & Martijn Mes, 2025. "Distance approximation to support customer selection in vehicle routing problems," Annals of Operations Research, Springer, vol. 350(1), pages 269-297, July.
    11. 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.
    12. Gulcin Dinc Yalcin & Hilal Malta & Seher Saylik, 2023. "A new mathematical model and a heuristic algorithm for the tourist trip design problem under new constraints: a real-world application," OPSEARCH, Springer;Operational Research Society of India, vol. 60(4), pages 1703-1730, December.
    13. Dontas, Michael & Sideris, Georgios & Manousakis, Eleftherios G. & Zachariadis, Emmanouil E., 2023. "An adaptive memory matheuristic for the set orienteering problem," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1010-1023.
    14. Fleckenstein, David & Klein, Robert & Steinhardt, Claudius, 2023. "Recent advances in integrating demand management and vehicle routing: A methodological review," European Journal of Operational Research, Elsevier, vol. 306(2), pages 499-518.
    15. Wouter Souffriau & Pieter Vansteenwegen & Greet Vanden Berghe & Dirk Van Oudheusden, 2013. "The Multiconstraint Team Orienteering Problem with Multiple Time Windows," Transportation Science, INFORMS, vol. 47(1), pages 53-63, February.
    16. Samita Kedkaew & Warisa Nakkiew & Parida Jewpanya & Wasawat Nakkiew, 2024. "A Novel Tourist Trip Design Problem with Stochastic Travel Times and Partial Charging for Battery Electric Vehicles," Mathematics, MDPI, vol. 12(18), pages 1-19, September.
    17. Yibo Dang & Manjeet Singh & Theodore T. Allen, 2021. "Network Mode Optimization for the DHL Supply Chain," Interfaces, INFORMS, vol. 51(3), pages 179-199, May.
    18. Verbeeck, C. & Vansteenwegen, P. & Aghezzaf, E.-H., 2016. "Solving the stochastic time-dependent orienteering problem with time windows," European Journal of Operational Research, Elsevier, vol. 255(3), pages 699-718.
    19. Shiri, Davood & Akbari, Vahid & Hassanzadeh, Ali, 2024. "The Capacitated Team Orienteering Problem: An online optimization framework with predictions of unknown accuracy," Transportation Research Part B: Methodological, Elsevier, vol. 185(C).
    20. Ann Campbell & Michel Gendreau & Barrett Thomas, 2011. "The orienteering problem with stochastic travel and service times," Annals of Operations Research, Springer, vol. 186(1), pages 61-81, June.

    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:plo:pone00:0264584. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.