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

The generalized close enough traveling salesman problem

Author

Listed:
  • Di Placido, Andrea
  • Archetti, Claudia
  • Cerrone, Carmine
  • Golden, Bruce

Abstract

This paper studies a generalization of the close enough traveling salesman problem referred to as the generalized close enough traveling salesman problem (GCETSP). The canonical problem contains a set of customers, each associated with an area (neighborhood) that is generally circular. In the GCETSP, each customer is associated with a set of disks with different radii. Having multiple disks around the customer allows us to model several real-world applications, in which a higher benefit is gained by more closely approaching each target. A prize is assigned to each disk and is collected if the disk is traversed. The goal is to determine the route that visits each customer and the depot and maximizes the difference between the total collected prize and the route length. The total collected prize is given by the sum of the customer prices’ associated with the innermost disk traversed by the route. We propose a heuristic algorithm and an evolutionary approach, specifically, a genetic algorithm (GA), to solve this problem. We evaluate the GA’s performance on instances generated from benchmark CETSP and TSP instances. We then compare GA solutions with CETSP solutions and solutions obtained through an alternative approach based on pre-selecting intersection points with customers’ disks. The results show that the GA can identify high-quality solutions with a short computing time.

Suggested Citation

  • Di Placido, Andrea & Archetti, Claudia & Cerrone, Carmine & Golden, Bruce, 2023. "The generalized close enough traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 310(3), pages 974-991.
  • Handle: RePEc:eee:ejores:v:310:y:2023:i:3:p:974-991
    DOI: 10.1016/j.ejor.2023.04.010
    as

    Download full text from publisher

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

    File URL: https://libkey.io/10.1016/j.ejor.2023.04.010?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. Yang, Zhao & Xiao, Ming-Qing & Ge, Ya-Wei & Feng, De-Long & Zhang, Lei & Song, Hai-Fang & Tang, Xi-Lang, 2018. "A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods," European Journal of Operational Research, Elsevier, vol. 265(1), pages 65-80.
    2. Michel Gendreau & Gilbert Laporte & Frédéric Semet, 1997. "The Covering Tour Problem," Operations Research, INFORMS, vol. 45(4), pages 568-576, August.
    3. Walton Pereira Coutinho & Roberto Quirino do Nascimento & Artur Alves Pessoa & Anand Subramanian, 2016. "A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 752-765, November.
    4. S. Lin & B. W. Kernighan, 1973. "An Effective Heuristic Algorithm for the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 21(2), pages 498-516, April.
    5. Behnam Behdani & J. Cole Smith, 2014. "An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 415-432, August.
    6. John R. Current & David A. Schilling, 1989. "The Covering Salesman Problem," Transportation Science, INFORMS, vol. 23(3), pages 208-213, August.
    7. Francesco Carrabs & Carmine Cerrone & Raffaele Cerulli & Bruce Golden, 2020. "An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for the Close-Enough Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1030-1048, October.
    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. 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.
    2. Francesco Carrabs & Carmine Cerrone & Raffaele Cerulli & Bruce Golden, 2020. "An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for the Close-Enough Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1030-1048, October.
    3. Wenda Zhang & Jason J. Sauppe & Sheldon H. Jacobson, 2023. "Results for the close-enough traveling salesman problem with a branch-and-bound algorithm," Computational Optimization and Applications, Springer, vol. 85(2), pages 369-407, June.
    4. Keisuke Murakami, 2018. "Iterative Column Generation Algorithm for Generalized Multi-Vehicle Covering Tour Problem," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(04), pages 1-22, August.
    5. Corberán, Ángel & Plana, Isaac & Reula, Miguel & Sanchis, José M., 2021. "On the Distance-Constrained Close Enough Arc Routing Problem," European Journal of Operational Research, Elsevier, vol. 291(1), pages 32-51.
    6. L Vogt & C A Poojari & J E Beasley, 2007. "A tabu search algorithm for the single vehicle routing allocation problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 467-480, April.
    7. Bruce Golden & Zahra Naji-Azimi & S. Raghavan & Majid Salari & Paolo Toth, 2012. "The Generalized Covering Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 24(4), pages 534-553, November.
    8. Liwei Zeng & Sunil Chopra & Karen Smilowitz, 2019. "The Covering Path Problem on a Grid," Transportation Science, INFORMS, vol. 53(6), pages 1656-1672, November.
    9. Stefan Poikonen & Bruce Golden, 2020. "The Mothership and Drone Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 32(2), pages 249-262, April.
    10. Glize, Estèle & Roberti, Roberto & Jozefowiez, Nicolas & Ngueveu, Sandra Ulrich, 2020. "Exact methods for mono-objective and Bi-Objective Multi-Vehicle Covering Tour Problems," European Journal of Operational Research, Elsevier, vol. 283(3), pages 812-824.
    11. Fischer, Vera & Pacheco Paneque, Meritxell & Legrain, Antoine & Bürgy, Reinhard, 2024. "A capacitated multi-vehicle covering tour problem on a road network and its application to waste collection," European Journal of Operational Research, Elsevier, vol. 315(1), pages 338-353.
    12. Leticia Vargas & Nicolas Jozefowiez & Sandra Ulrich Ngueveu, 2017. "A dynamic programming operator for tour location problems applied to the covering tour problem," Journal of Heuristics, Springer, vol. 23(1), pages 53-80, February.
    13. Lamb, John D., 2012. "Variable neighbourhood structures for cycle location problems," European Journal of Operational Research, Elsevier, vol. 223(1), pages 15-26.
    14. Afsaneh Amiri & Majid Salari, 2019. "Time-constrained maximal covering routing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(2), pages 415-468, June.
    15. Christian Burkart & Pamela C. Nolz & Walter J. Gutjahr, 2017. "Modelling beneficiaries’ choice in disaster relief logistics," Annals of Operations Research, Springer, vol. 256(1), pages 41-61, September.
    16. Walton Pereira Coutinho & Roberto Quirino do Nascimento & Artur Alves Pessoa & Anand Subramanian, 2016. "A Branch-and-Bound Algorithm for the Close-Enough Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 752-765, November.
    17. Naji-Azimi, Zahra & Salari, Majid & Toth, Paolo, 2012. "An Integer Linear Programming based heuristic for the Capacitated m-Ring-Star Problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 17-25.
    18. Behnam Behdani & J. Cole Smith, 2014. "An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem," INFORMS Journal on Computing, INFORMS, vol. 26(3), pages 415-432, August.
    19. 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.
    20. J Renaud & F F Boctor & G Laporte, 2004. "Efficient heuristics for Median Cycle Problems," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 179-186, February.

    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:310:y:2023:i:3:p:974-991. 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.