Title | ||
---|---|---|
A variable neighborhood search heuristic for the traveling salesman problem with hotel selection |
Abstract | ||
---|---|---|
This work deals with the Traveling Salesman Problem with Hotel Selection (TSPHS), a variant of the classic Traveling Salesman Problem (TSP). In the TSPHS, a set of hotels can be visited in strategic points of the route, dividing it in a minimum number of trips. Each trip must not exceed a given time limit, minimizing also the total time traveled. The TSPHS is NP-Hard, being a generalization of the TSP, so the main approaches in literature are based in Mathematical Programming and Metaheuristics. The metaheuristics are generic heuristics capable of escaping from local optima, usually obtaining good quality solutions in low computational time. It is developed a heuristic based on Variable Neighborhood Search, compared with the best algorithms in literature using classic instances. Computational results indicate that the proposed algorithm finds solutions with fewer trips in low computational time, with a traveled total time comparable to the best known solutions. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/CLEI.2015.7360046 | 2015 Latin American Computing Conference (CLEI) |
Keywords | Field | DocType |
Traveling Salesman Problem with Hotel Selection,Variable Neighborhood Search,Metaheuristics | Traveling purchaser problem,Bottleneck traveling salesman problem,Mathematical optimization,Variable neighborhood search,Combinatorial optimization,Travelling salesman problem,2-opt,Local search (optimization),Mathematics,Metaheuristic | Conference |
ISSN | Citations | PageRank |
2381-1609 | 2 | 0.40 |
References | Authors | |
19 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marques M. Sousa | 1 | 2 | 0.40 |
Luiz Satoru Ochi | 2 | 474 | 34.62 |
I. M. Coelho | 3 | 58 | 12.95 |
Luciana Brugiolo Gonçalves | 4 | 5 | 2.14 |