An Adaptive Heuristic Approach to Compute Upper and Lower Bounds for The Close-Enough Traveling Salesman Problem
Autor: | Carmine Cerrone, Francesco Carrabs, Bruce L. Golden, Raffaele Cerulli |
---|---|
Jazyk: | angličtina |
Rok vydání: | 2020 |
Předmět: |
Mathematical optimization
021103 operations research carousel greedy Heuristic (computer science) Computer science Node (networking) 0211 other engineering and technologies General Engineering traveling salesman problem 02 engineering and technology Travelling salesman problem Upper and lower bounds close-enough drones close-enough traveling salesman problem neighborhoods carousel greedy drones 0202 electrical engineering electronic engineering information engineering Euclidean traveling salesman problem 020201 artificial intelligence & image processing neighborhoods Carousel greedy Close-enough Drones Neighborhoods Traveling salesman problem |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |