HEURÍSTICA HÍBRIDA APLICADA AO PROBLEMA DO CAIXEIRO VIAJANTE COM SELEÇÃO DE HOTÉIS

HEURÍSTICA HÍBRIDA APLICADA AO PROBLEMA DO CAIXEIRO VIAJANTE COM SELEÇÃO DE HOTÉIS

Beltrão, Augusto Pizano Vieira; Ochi, Luiz Satoru; Brito, José André de Moura

Artigo Completo:

O Problema do Caixeiro Viajante com Seleção de Hotéis (TSPHS) é uma variante do conhecido Problema do Caixeiro Viajante. A resolução do TSPHS corresponde a determinar uma rota na qual um vendedor visita todos os clientes e retorna para localização inicial. Ao final de cada jornada de trabalho (dada por um limite de tempo), o vendedor deve visitar algum hotel para descansar. O objetivo é minimizar o número de viagens necessárias para completar a rota. Neste trabalho, é proposto um algoritmo heurístico, inspirado no BRKGA, que foi combinado com métodos construtivos e procedimentos de busca local. Experimentos conduzidos mostram que o algoritmo proposto é capaz de produzir resultados competitivos frente aos da literatura. Além disso, foram encontradas soluções melhores que as da literatura em 7 das 131 instâncias da literatura.

O Problema do Caixeiro Viajante com Seleção de Hotéis (TSPHS) é uma variante do conhecido Problema do Caixeiro Viajante. A resolução do TSPHS corresponde a determinar uma rota na qual um vendedor visita todos os clientes e retorna para localização inicial. Ao final de cada jornada de trabalho (dada por um limite de tempo), o vendedor deve visitar algum hotel para descansar. O objetivo é minimizar o número de viagens necessárias para completar a rota. Neste trabalho, é proposto um algoritmo heurístico, inspirado no BRKGA, que foi combinado com métodos construtivos e procedimentos de busca local. Experimentos conduzidos mostram que o algoritmo proposto é capaz de produzir resultados competitivos frente aos da literatura. Além disso, foram encontradas soluções melhores que as da literatura em 7 das 131 instâncias da literatura.

Palavras-chave:

DOI: 10.5151/spolm2019-102

Referências bibliográficas

• [1] AHUJA, Ravindra K.; MAGNANTI, Thomas L.; ORLIN, James B. Network flows. 1988. APPLEGATE, David L. et al. The traveling salesman problem: a computational study. Princeton university press, 2006. BEKTAS, Tolga. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, v. 34, n. 3, p. 209-219, 2006. CASTRO, Marco et al. A fast metaheuristic for the travelling salesperson problem with hotel selection. 4OR, v. 13, n. 1, p. 15-34, 2015. CASTRO, Marco et al. A memetic algorithm for the travelling salesperson problem with hotel selection. Computers & Operations Research, v. 40, n. 7, p. 1716-1728, 2013. CORDEAU, Jean-François; GENDREAU, Michel; LAPORTE, Gilbert. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks: An International Journal, v. 30, n. 2, p. 105-119, 1997. CORDEAU, Jean-François; LAPORTE, Gilbert; MERCIER, Anne. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational research society, v. 52, n. 8, p. 928-936, 2001. CROES, Georges A. A method for solving traveling-salesman problems. Operations research, v. 6, n. 6, p. 791-812, 1958. FEO, Thomas A.; RESENDE, Mauricio GC. Greedy randomized adaptive search procedures. Journal of global optimization, v. 6, n. 2, p. 109-133, 1995. GLOVER, Fred. Tabu search—part I. ORSA Journal on computing, v. 1, n. 3, p. 190-206, 1989. GLOVER, Fred. Tabu search—part II. ORSA Journal on computing, v. 2, n. 1, p. 4-32, 1990. GONÇALVES, José Fernando; RESENDE, Mauricio GC. Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, v. 17, n. 5, p. 487- 525, 2011. HANSEN, Pierre; MLADENOVIĆ, Nenad; PÉREZ, José A. Moreno. Variable neighbourhood search: methods and applications. Annals of Operations Research, v. 175, n. 1, p. 367-407, 2010. HOLLAND, John H. Genetic algorithms. Scientific american, v. 267, n. 1, p. 66-73, 1992. LIN, Shen. Computer solutions of the traveling salesman problem. Bell System Technical Journal, v. 44, n. 10, p. 2245-2269, 1965. LIN, Shen; KERNIGHAN, Brian W. An effective heuristic algorithm for the travelingsalesman problem. Operations research, v. 21, n. 2, p. 498-516, 1973. LU, Yongliang; BENLIC, Una; WU, Qinghua. A hybrid dynamic programming and memetic algorithm to the traveling salesman problem with hotel selection. Computers & Operations Research, v. 90, p. 193-207, 2018. MLADENOVIĆ, Nenad; HANSEN, Pierre. Variable neighborhood search. Computers & operations research, v. 24, n. 11, p. 1097-1100, 1997. OR, I. Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking. PhD thesis (Department of Industrial Engineering and Management Science, Northwestern University), 1976. PRINS, Christian. A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, v. 31, n. 12, p. 1985-2002, 2004. SOUSA, Marques M.; GONÇALVES, Luciana Brugiolo. Comparação de abordagens heurísticas baseadas em algoritmo memético para o problema do caixeiro viajante com seleção de hotéis. In: Proc. XLVI Simpósio Brasileiro de Pesquisa Operacional. 2014. p. 1543-1554. SOUSA, Marques M. et al. A variable neighborhood search heuristic for the traveling salesman problem with hotel selection. In: 2015 Latin American Computing Conference (CLEI). IEEE, 2015. p. 1-12. SOUSA, Marques Moreira; OCHI, Luiz Satoru; DE LIMA MARTINS, Simone. An Efficient Heuristic to the Traveling Salesperson Problem with Hotel Selection. In: International Workshop on Hybrid Metaheuristics. Springer, Cham, 2019. p. 31-45. SOLOMON, Marius M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, v. 35, n. 2, p. 254-265, 1987. TOTH, Paolo; VIGO, Daniele (Ed.). The vehicle routing problem. Society for Industrial and Applied Mathematics, 2002. VANSTEENWEGEN, Pieter; SOUFFRIAU, Wouter; SÖRENSEN, Kenneth. The travelling salesperson problem with hotel selection. Journal of the Operational Research Society, v. 63, n. 2, p. 207-217, 2012.

Como citar:

Beltrão, Augusto Pizano Vieira; Ochi, Luiz Satoru; Brito, José André de Moura; "HEURÍSTICA HÍBRIDA APLICADA AO PROBLEMA DO CAIXEIRO VIAJANTE COM SELEÇÃO DE HOTÉIS", p-1390-1405. In: Anais do XIX Simpósio de Pesquisa Operacional & Logística da Marinha. São Paulo: Blucher, 2020.
ISSN 21756295, DOI 10.5151/spolm2019-102