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

摘要

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.