ALGORITMO GENÉTICO BASEADO EM CHAVES ALEATÓRIAS PARA O ORIENTEERING PROBLEM WITH TIME WINDOWS

Autores

  • Vinícius Almeida Gonçalves
  • Daniel Morais dos Reis
  • Eduardo Habib Bechelane Maia
  • Breno Alves Beirigo
  • Sérgio Ricardo de Souza
  • Anolan Yamilé Milanés Barrientos

DOI:

https://doi.org/10.26512/ripe.v2i10.21730

Palavras-chave:

BRKGA. MultiStart. OPTW. TTDP.

Resumo

O Problema de Planejamento de Rotas Turísticas (TTDP) é um problema computacional que envolve o planejamento de rotas entre pontos de interesse de uma região turística. Ele pode ser modelado como um problema de roteamento bem conhecido, chamado Problema de Orientação com Janelas de Tempo (OPTW), no qual um score e um intervalo de tempo são associados a cada localidade. Este artigo aborda o OPTW ao propor uma comparação entre dois diferentes métodos para solucioná-lo: Biased Random Key Genetic Algorithm (BRKGA) e MultiStart. Ambas técnicas utilizaram a mesma busca local com quatro etapas, baseada nas últimas soluções propostas para este problema. Foram executados experimentos computacionais com as instâncias tradicionais. Os testes mostraram que o método BRKGA atingiu resultados iguais ou melhores que MultiStart em todas as 76 instâncias avaliadas. Além disso, foram encontradas 21 novas melhores soluções para OPTW, em comparação com a literatura atual.

Downloads

Não há dados estatísticos.

Referências

Arulselvan, A., Commander, C.,& Pardalos, P., 2007. A random keys based genetic algorithm for the target visitation problem.Pardalos, P., Murphey, R.,Grundel, D. & Hirsch, M., eds, Advances in Cooperative Control and Optimization, vol. 369 of Lecture Notes in Control and Information Sciences, pp. 389”“397. Springer.

Buriol, L. S.,Resende, M. G. C., Ribeiro, C. C.,&Thorup, M., 2005. A hybrid genetic algorithm for the weight setting problem in OSPF/IS-IS routing. Networks, 46:36”“56.

Buriol, L. S.,Resende, M. G. C.,&Thorup, M., 2007. Survivable IP network design with OSPF routing. Networks, 49:51”“64.

Cura, T., 2014. An artificial bee colony algorithm approach for the team orienteering problem with time windows.Computers & Industrial Engineering, vol. 74, pp. 270”“290.

Gambardella, L. M., Montemanni, R., &Weyland, D., 2012. Coupling ant colony systems with strong local searches.European Journal of Operational Research,vol. 220, n. 3, pp. 831”“843.

Gendreau, M., Laporte, G., &Semet, F., 1998. A tabu search heuristic for the undirected selective travelling salesman problem.European Journal of Operational Research, vol. 106, n. 2-3, pp. 539”“545.

Golden, B. L., Levy, L., & Vohra, R., 1987.The orienteering problem. Naval Research Logitics, vol. 34, n. 3, pp. 307”“318.

Gonçalves, J. F., Mendes, J. J. M.,& Resende, M. G. C., 2005. A hybrid genetic algorithm for the job shop scheduling problem.European Journal of Operational Research, vol. 167, n. 1, pp. 77”“95.

Gonçalves, J. F. &Resende, M. G. C., 2004. An evolutionary algorithm for manufacturing cell formation.Computers and Industrial Engineering, vol. 47, pp. 247”“273.

Gonçalves, J. F., &Resende, M. G. C., 2009. Biased random-key genetic algorithms for combinatorial optimization. To appear in J. of Heuristics, v. 17, n. 5, pp. 487-525.

Goulart, N., Noronha, T. F., de Souza, S. R.,&Dias, L. G. S., 2011. Algoritmo Genético para o Problema de Instalação de Fibras em Redes Óticas. XLIII Simpósio Brasileiro de Pesquisa Operacional, Ubatuba.

Goulart, N., Noronha, T. F., de Souza, S. R.,& Dias, L. G. S., 2011. Biased Random-key Genetic Algorithm for Fiber Installation in Optical Network Optimization. 2011 IEEE Evolutionary Computation,New Orleans, LA, 2011, pp. 2267-2271.

Gunawan, A., Lau, H. C., &Lu, K., 2015a. An iterated local search algorithm for solving the orienteering problem with time windows.In Ochoa, G., Chicano, F., eds,Evolutionary Computation in Combinatorial Optimization, vol. 9026 of Lecture Notes in Computer Science (Springer), pp. 61”“73.

Gunawan, A., Lau, H. C., &Lu, K., 2015b. SAILS: hybrid algorithm for the team orienteering problem with time windows. In Proceedings of the 7th Multidisciplinary International Scheduling Conference (MISTA 2015). Prague, Czech Republic,pp. 276”“295.

Gunawan, A., Lau, H. C., &Lu, K., 2015c. Well-tuned ILS for extended team orienteering problem with time windows.LARC technical report series, SingaporeManagement University.

Gunawan, A., Lau, H. C., &Lu, K., 2015d. The latest best known solutions for the TeamOrienteering Problem with Time Windows (TOPTW)benchmark instances. Disponível em http://research.larc.smu.edu.sg/downloads/OPLib/Publications/SupplementTOPTW.pdf. Acesso em 15 de junho de 2016.

Gunawan, A., Lau, H. C.,&Vansteenwegen, P., 2016. Orienteering Problem: A survey of recent variants, solution approaches and applications.European Journal of Operational Research, vol. 255, n.2, pp.315”“332.

Hu, Q.,& Lim, A., 2014. An iterative three-component heuristic for the team orienteering problem with time windows.European Journal of Operational Research, vol. 232, n. 2, pp. 276”“286.

Kantor, M. G., &Rosenwein, M. B., 1992. The Orienteering Problem with Time Windows.The Journal of the Operational Research Society, vol. 43, n. 6, pp. 629”“635.

Labadie, N., Mansini, R., Melechovsk`y, J., WolflerCalvo, R., 2011. Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics, vol. 17, n. 6, pp. 729”“753.

Labadie, N., Mansini, R., Melechovský, J., &WolflerCalvo, R., 2012. The team orienteering problem with time windows: an LP-based granular variable neighborhood search. European Journal of Operational Research, vol. 220, n. 1, pp. 15”“27.

Lin, S. W., Yu,& V. F., 2012. A simulated annealing heuristic for the team orienteering problem with time windows.European Journal of Operational Research, vol. 217, n. 1, pp. 94”“107.

Malve, S., &Uzsoy, R., 2007. A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, v. 34, p. 3016”“3028.

Noronha, T. F.,Resende, M. G. C., &Ribeiro, C. C., 2010. A biased random-key genetic algorithm for routing and wavelength assignment.Journal of Global Optimization, vol. 50, n. 3, pp. 503-518.

Reis, R.,Ritt, M.,Buriol, L. S., &Resende, M. G. C., 2011. A biased random-key genetic algorithm for ospf and deft routing to minimize network congestion. International Transactions in Operational Research, vol. 18, pp. 401”“423.

Samanlioglu, F., Ferrell, W. G.Jr.,&Kurz, M. E., 2008. A memetic random-key genetic algorithm for a symmetric multi-objective traveling salesman problem. Computers & Industrial Engineering, v. 55, n. 2, p. 439”“449.

Snydera, L. V., &Daskin, M. S., 2006. A random-key genetic algorithm for the generalized traveling salesman problem. European Journal of Operational Research, vol. 174, pp. 38”“53.

Souffriau, W., Vansteenwegen, P., VandenBerghe, G., & Van Oudheusden, D.,2013. The multiconstraint team orienteering problem with multiple time windows.Transportation Science, vol. 47, n. 1, pp. 53”“63.

Spears, W.,de Jong, K., 1991. On the virtues of parameterized uniform crossover.Proceedings of the Fourth International Conference on Genetic Algorithms, p. 230”“236, San Mateo.

The Orienteering Problem: Test Instances, 2011. Disponível em http://www.mech.kuleuven.be/en/cib/op. Acessado em 15 de junho de 2016.

Toso, Rodrigo F., Resende, Mauricio G. C., 2015. A C++ Application Programming Interface for Biased Random-Key Genetic Algorithms. Optimization Methods and Software, vol. 30, n. 1, pp. 81-93.

Tsiligirides, T., 1984.Heuristic methods applied to orienteering.Journal of the Operational Research Society, vol. 35, n. 9, pp. 797”“809.

Vansteenwegen, P., Souffriau, W., &Van Oudheusden, D., 2011.The Orienteering Problem: a Survey.European Journal of Operational Research, vol. 209, n. 1, pp. 1”“10.

Vansteenwegen, P., Souffriau, W., VandenBerghe, G., & Van Oudheusden, D.,2009. Iterated local search for the team orienteering problem with time windows.Computers & Operations Research, vol. 36, n. 12, pp. 3281”“3290.

Vansteenwegen, P., &Van Oudheusden, D., 2007.The mobile tourist guide: An OR opportunity.Operational Research Insight, vol. 20, n. 3, pp. 21”“27.

Downloads

Publicado

2017-01-25

Como Citar

Gonçalves, V. A., Reis, D. M. dos, Maia, E. H. B., Beirigo, B. A., Souza, S. R. de, & Barrientos, A. Y. M. (2017). ALGORITMO GENÉTICO BASEADO EM CHAVES ALEATÓRIAS PARA O ORIENTEERING PROBLEM WITH TIME WINDOWS. Revista Interdisciplinar De Pesquisa Em Engenharia, 2(10), 90–104. https://doi.org/10.26512/ripe.v2i10.21730

Edição

v. 2 n. 10 (2016): COMPUTATIONAL INTELLIGENCE TECHNIQUES FOR OPTMIZATION AND DATA MODELING (II)

Seção

Artigos

Licença

Autores que publicam nesta revista concordam com os seguintes termos:

Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, sendo o trabalho simultaneamente licenciado sob a Creative Commons Attribution License o que permite o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial nesta revista.

Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.

Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado.