Two level General variable neighborhood search for Attractive traveling salesman problem

Abstract

Attractive traveling salesman problem (AtTSP) consists of finding maximal profit tour starting and ending at a given depot after visiting some of the facilities. Total length of the tour must not exceed the given maximum distance. Each facility achieves profit from the customers, based on the distance between the facility and customers as well as on the attractiveness of that facility. Total profit of a tour is equal to a sum of profits of all visited facilities. In this paper, we develop a new variant of Variable neighborhood search, called 2-level General variable neighborhood search (2-GVNS) for solving AtTSP. At the second level, we use General variable neighborhood search in the local search lor building neighboring solution and checking its feasibility. Our 2-GVNS heuristic outperforms tabu search heuristic, the only one proposed in the literature so far, in terms of precision and running times. In addition, 2-GVNS finds all optimal known solutions obtained by Branch and cut algorithm and offers several new best known solutions.