A new approach for the traveling salesperson problem with hotel selection

EURO Journal on Transportation and Logistics

卷:10

Luiz Satoru Ochi¹  Gustavo Silva Semaan²  Augusto Pizano Vieira Beltrão³  José André de Moura Brito³  Nelson Maculan⁴  Augusto César Fadel⁵ 

[1] Corresponding author.;

[2] Escola Nacional de Ciências Estatísticas (ENCE/IBGE), R. André Cavalcanti, 106 - Centro, 20231-050, Rio de Janeiro, (RJ), Brazil;

[3] Instituto de Computação, Universidade Federal Fluminense (IC/UFF), Av. Gal. Milton Tavares de Souza, s/n - São Domingos, 24210-310, Niterói, (RJ), Brazil;

[4] Instituto do Noroeste Fluminense de Educação Superior, Universidade Federal Fluminense (INFES/UFF), Estr. João Jasbick, s/n - Dezessete, 28470-000, Santo Antônio de Pádua, (RJ), Brazil;

[5] Universidade Federal do Rio de Janeiro (COPPE/UFRJ), Rua Horácio Macedo, Bloco G, 2030 - 101 - Cidade Universitária da Universidade Federal do Rio de Janeiro, 21941-450, Rio de Janeiro, (RJ), Brazil;

关键词: Metaheuristics;    BRKGA;    TSP;    Combinatorial optimization;    Hotel selection;   

DOI  :  

来源: DOAJ

【 摘 要 】

The Traveling Salesperson Problem with Hotel Selection (TSPHS) corresponds to a variant of the classic Traveling Salesman Problem (TSP) where the salesperson must establish a route in order to visit and attend all customers and return to the point of origin. At the end of each working day, if they had not attended all customers, the salesperson must go to a hotel (and stay there overnight). The objective of TSPHS is to first minimize the number of trips and then to minimize the total time spent. The present work proposes a new heuristic algorithm called BRKGA-LS, that combines characteristics and procedures of well-established metaheuristics and methods of vehicle routing problems. Based on computational experiments, carried out with 131 instances of the literature, the global optimum was achieved in about 90% of the cases where it is known (86 out of 95 instances), and the algorithm was able to improve the results of the literature in 11 of all 36 instances. Additionally, a hypothesis test was performed to validate the results and the good performance of the BRKGA-LS in comparison to other algorithms in the literature. Therefore, the proposed algorithm is a promising alternative for solving the problem addressed.

【 授权许可】

Unknown