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

Francesco Carrabs (), Carmine Cerrone (), Raffaele Cerulli () and Bruce Golden ()
Additional contact information
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

INFORMS Journal on Computing, 2020, vol. 32, issue 4, 1030-1048

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.

Keywords: close-enough, traveling salesman problem; neighborhoods; carousel greedy; drones (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://doi.org/10.1287/ijoc.2020.0962 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:32:y:4:i:2020:p:1030-1048

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().