A Variable Neighborhood Search Heuristic for the Traveling Salesman Problem with Hotel Selection
Marques Sousa$^{1}$, Luiz Satoru Ochi$^{1}$, Igor Machado Coelho$^{2}$, Luciana Brugiolo Gonçalves$^{3}$
$^{1}$Universidade Federal Fluminense. Niterói, RJ Brazil,
$^{2}$Universidade do Estado do Rio de Janeiro. Rio de Janeiro, RJ Brazil,
$^{3}$Universidade Federal de Juiz de Fora. Juiz de Fora, MG Brazil
email: msousa@ic.uff.br, luiz.satoru@gmail.com, igor.machado@gmail.com, lbrugiolo@ice.ufjf.br

Schedule:Wed 21st@11:15, Room: A

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.

BibTex

@InProceedings{CLEI-2015:145054,
	author 		= {Marques Sousa and Luiz Satoru Ochi and Igor Machado Coelho and Luciana Brugiolo Gonçalves},
	title 		= {A Variable Neighborhood Search Heuristic for the Traveling Salesman Problem with Hotel Selection},
	booktitle 	= {2015 XLI Latin American Computing Conference (CLEI)},
	pages 		= {362--373},
	year 		= {2015},
	editor 		= {Hector Cancela and Alex Cuadros-Vargas and Ernesto Cuadros-Vargas},
	address 	= {Arequipa-Peru},
	month 		= {October},
	organization 	= {CLEI},
	publisher 	= {CLEI},
	url 		= {http://clei.org/clei2015/145054},
	isbn 		= {978-1-4673-9143-6},
	}