540. A heuristic method for the close enough traveling salesman problem
Invited abstract in session ME-19: Vehicle Routing, cluster Combinatorial Optimization.
Monday, 16:15-17:45Room: FENH105
Authors (first author is the speaker)
| 1. | Ernesto G. Birgin
|
| Dept. of Computer Science, University of Sao Paulo | |
| 2. | Paula C. R. Ertel
|
| University of São Paulo |
Abstract
The traveling salesman problem is one of the most studied combinatorial optimization problems. Given n cities and their pairs of distances, one seeks to find a tour of minimum distance passing through all cities. In the Close Enough TSP variant, it is unnecessary to pass exactly through each city, but through one neighborhood of each city. This problem can be modeled as a continuous optimization problem with integer variables. In this paper, we present a heuristic method to find solutions of the Close Enough TSP, including a constructive heuristic, a local search based on the 2-opt movement and a continuous optimization method of the coordinate block search; for a given permutation, it tries to find a point to be visited in the neighborhood of each city, to minimize the tour length for the given permutation. Numerical experiments illustrate the performance of the proposed method.
Keywords
- Programming, Nonlinear
- Combinatorial Optimization
- Routing
Status: accepted
Back to the list of papers