IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y4i2020p1030-1048.html
   My bibliography  Save this article

An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for the Close-Enough Traveling Salesman Problem

Author

Listed:
  • Francesco Carrabs

    (Department of Mathematics, University of Salerno, 84084 Fisciano, Italy;)

  • Carmine Cerrone

    (Department of Economics and Business Studies, University of Genova, 16126 Genova, Italy;)

  • Raffaele Cerulli

    (Department of Mathematics, University of Salerno, 84084 Fisciano, Italy;)

  • Bruce Golden

    (Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742)

Abstract

This paper addresses the close-enough traveling salesman problem, a variant of the Euclidean traveling salesman problem, in which the traveler visits a node if it passes through the neighborhood set of that node. We apply an effective strategy to discretize the neighborhoods of the nodes and the carousel greedy algorithm to appropriately select the neighborhoods that, step by step, are added to the partial solution until a feasible solution is generated. Our heuristic, based on these ingredients, is able to compute tight upper and lower bounds on the optimal solution relatively quickly. The computational results, carried out on benchmark instances, show that our heuristic often finds the optimal solution, on the instances where it is known, and in general, the upper bounds are more accurate than those from other algorithms available in the literature. Summary of Contribution: In this paper, we focus on the close-enough traveling salesman problem. This is a problem that has attracted research attention over the last 10 years; it has numerous real-world applications. For instance, consider the task of meter reading for utility companies. Homes and businesses have meters that measure the usage of gas, water, and electricity. Each meter transmits signals that can be read by a meter reader vehicle via radio-frequency identification (RFID) technology if the distance between the meter and the reader is less than r units. Each meter plays the role of a target point and the neighborhood is a disc of radius r centered at each target point. Now, suppose the meter reader vehicle is a drone and the goal is to visit each disc while minimizing the amount of energy expended by the drone. To solve this problem, we develop a metaheuristic approach, called ( lb/ub ) Alg , which computes both upper and lower bounds on the optimal solution value. This metaheuristic uses an innovative discretization scheme and the Carousel Greedy algorithm to obtain high-quality solutions. On benchmark instances where the optimal solution is known, ( lb/ub ) Alg obtains this solution 83% of the time. Over the remaining 17% of these instances, the deviation from the optimality is 0.05%, on average. On the instances with the highest overlap ratio, ( lb/ub ) Alg does especially well.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:orijoc:v:32:y:4:i:2020:p:1030-1048
    DOI: 10.1287/ijoc.2020.0962
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2020.0962
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2020.0962?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. 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. 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.
    5. John R. Current & David A. Schilling, 1989. "The Covering Salesman Problem," Transportation Science, INFORMS, vol. 23(3), pages 208-213, August.
    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. 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. 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.
    3. Yuan, Yuan & Cattaruzza, Diego & Ogier, Maxime & Semet, Frédéric & Vigo, Daniele, 2021. "A column generation based heuristic for the generalized vehicle routing problem with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    4. Archetti, C. & Carrabs, F. & Cerulli, R. & Laureana, F., 2024. "A new formulation and a branch-and-cut algorithm for the set orienteering problem," European Journal of Operational Research, Elsevier, vol. 314(2), pages 446-465.
    5. 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.
    6. Carrabs, Francesco, 2021. "A biased random-key genetic algorithm for the set orienteering problem," European Journal of Operational Research, Elsevier, vol. 292(3), pages 830-854.

    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. 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.
    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. 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.
    5. Liwei Zeng & Sunil Chopra & Karen Smilowitz, 2019. "The Covering Path Problem on a Grid," Transportation Science, INFORMS, vol. 53(6), pages 1656-1672, November.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Lei, Chao & Lin, Wei-Hua & Miao, Lixin, 2014. "A multicut L-shaped based algorithm to solve a stochastic programming model for the mobile facility routing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 699-710.
    12. 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.
    13. 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.
    14. 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.
    15. Eduardo Álvarez-Miranda & Markus Sinnl, 2020. "A branch-and-cut algorithm for the maximum covering cycle problem," Annals of Operations Research, Springer, vol. 284(2), pages 487-499, January.
    16. Allahyari, Somayeh & Salari, Majid & Vigo, Daniele, 2015. "A hybrid metaheuristic algorithm for the multi-depot covering tour vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 242(3), pages 756-768.
    17. Elfe Buluc & Meltem Peker & Bahar Y. Kara & Manoj Dora, 2022. "Covering vehicle routing problem: application for mobile child friendly spaces for refugees," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 461-484, June.
    18. Agatz, N.A.H. & Bouman, P.C. & Schmidt, M.E., 2016. "Optimization Approaches for the Traveling Salesman Problem with Drone," ERIM Report Series Research in Management ERS-2015-011-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    19. Katharina Glock & Anne Meyer, 2020. "Mission Planning for Emergency Rapid Mapping with Drones," Transportation Science, INFORMS, vol. 54(2), pages 534-560, March.
    20. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).

    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:orijoc:v:32:y:4:i:2020:p:1030-1048. 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.