522. A Block Coordinate Descent enhanced metaheuristic for the Euclidean Traveling Salesman Problem with Polygonal Neighborhoods
Invited abstract in session MC-35: Nonlinear Optimization Algorithms and Applications: 2, stream Continuous and mixed-integer nonlinear programming: theory and algorithms.
Monday, 12:30-14:00Room: Michael Sadler LG15
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 with Neighborhoods (TSPN) is a generalization of the well-known Traveling Salesman Problem. In the TSPN, given a finite set of regions of the Euclidean space, the goal is to find an order of these regions and a visit point in each region so that the length of a tour that visits them only once and returns to the starting point is minimized. Most of the literature on the TSPN focuses on the case where the regions are disks. In this work, we focus on the case where the regions are given by arbitrary (nonconvex) polygons. Considering the Euclidean distance, the problem can be modeled as a mixed-integer quadratically constrained programming problem. We propose an Iterated Local Search (ILS) metaheuristic to find solutions to large instances of the problem. The proposed ILS combines a block coordinate descent method to determine the visit points with different neighborhood structures widely used in the TSP literature to generate the permutations. Numerical experiments illustrate the performance of the proposed method.
Keywords
- Programming, Mixed-Integer
- Vehicle Routing
- Metaheuristics
Status: accepted
Back to the list of papers