Authors: Mladenović, Nenad 
Todosijević, Raca 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Two level General variable neighborhood search for Attractive traveling salesman problem
Journal: Computers and Operations Research
Volume: 52
First page: 341
Last page: 348
Issue Date: 1-Dec-2014
Rank: M21
ISSN: 0305-0548
DOI: 10.1016/j.cor.2013.04.015
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.
Keywords: 2-level GVNS | Demand allocation | Demand attraction | Traveling salesman problem | Variable neighborhood search
Publisher: Elsevier
Project: Mathematical Modelas and Optimization Methods on Large-Scale Systems 

Show full item record


checked on May 17, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.