UM ALGORITMO MEMÉTICO HÍBRIDO APLICADO AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELA DE TEMPO

UM ALGORITMO MEMÉTICO HÍBRIDO APLICADO AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELA DE TEMPO

Stehling, Thiago Muniz; Souza, Sérgio Ricardo de; Filho, Moacir Felizardo de França

Artigo Completo:

Este artigo apresenta um Algoritmo Memético Híbrido para a solução do Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). A hibridização está caracterizada na combinação entre PFIH e GRASP, utilizada para gerar a população inicial do algoritmo proposto. O meme inserido no processo evolutivo visa não somente alcançar bons resultados, mas economizar tempo de execução. Para os experimentos computacionais, as 56 instâncias de Solomon foram utilizadas. Os resultados obtidos são comparados com os melhores resultados conhecidos na literatura e com algoritmos similares ao proposto neste trabalho. Uma análise empírica, uma avaliação do tempo de execução e uma análise estatística foram realizadas. Os resultados indicam que o algoritmo alcançou resultados melhores em um tempo de execução razoável, considerando a inserção do meme.

Este artigo apresenta um Algoritmo Memético Híbrido para a solução do Problema de Roteamento de Veículos com Janela de Tempo (PRVJT). A hibridização está caracterizada na combinação entre PFIH e GRASP, utilizada para gerar a população inicial do algoritmo proposto. O meme inserido no processo evolutivo visa não somente alcançar bons resultados, mas economizar tempo de execução. Para os experimentos computacionais, as 56 instâncias de Solomon foram utilizadas. Os resultados obtidos são comparados com os melhores resultados conhecidos na literatura e com algoritmos similares ao proposto neste trabalho. Uma análise empírica, uma avaliação do tempo de execução e uma análise estatística foram realizadas. Os resultados indicam que o algoritmo alcançou resultados melhores em um tempo de execução razoável, considerando a inserção do meme.

Palavras-chave:

DOI: 10.5151/marine-spolm2015-140440

Referências bibliográficas

• [1] Cordeau, J. F.; Desaulniers, G.; Desrosiers, J. e Solomon, M. M. (2001). The vrp with time windows. Toth, P. e Vigo, D., editors, The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, p. 157–194. SIAM, Philadelphia, EUA.
• [2] Gendreau, M. e Tarantilis, C. D. (2010). Solving large-scale vehicle routing problems with time windows: The state-of-the-art. Technical Report CIRRELT-2010-04, CIRRELT.
• [3] Feo, T. A. e Resende, M. G. C. (1995). Greedy randomized adaptive search. Journal of Global Optimization, v. 3, p. 109–133.
• [4] Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, v. 35, n. 2, p. 254–265.
• [5] Stehling, T. M.; Souza, S. R.; França Filho, M. F. e Silva, M. A. L. (2014). Um algoritmo genético híbrido para a solução do problema de roteamento de veículos com janela de tempo. Proceedings of the XXXV Iberian Latin-American Congress on Computational Methods in Engineering (CILAMCE 2014), Nov 2014.
• [6] Moscato, P. (1989). On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Toward Memetic Algorithms, California Inst. Technol., Pasadena, CA, Tech. Rep. Caltech Concurrent Comput. Prog. Rep. 826, 1989.
• [7] Krasnogor, N. e Smith, J. (2005). A tutorial for competent memetic algorithms: Model, taxonomy, and design issues. IEEE Trans. Evol. Comput., vol. 9, no. 5, pp. 474–488, Oct. 2005.
• [8] Moscato, P. e Cotta, C. (2003). A gentle introduction to memetic algorithms, in: F. Glover and G. A. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer, Boston, pp. 105–144.
• [9] Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.
• [10] Ong, Y. S.; Lim, M. H.; Zhu, N. e Wong, K. W. (2006). Classification of adaptive memetic algorithms: A comparative study. IEEE Trans. Syst., Man, Cybern. Part B, vol. 36, no. 1, pp. 141–152, 2006.
• [11] Berger, J. e Barkaoui, M. (2002). A memetic algorithm for the vehicle routing problem with time windows. In Proceedings of the 7th International Command and Control Research and Technology Symposium, 2002.
• [12] Vidal, T.; Crainic, T.; Gendreau, M. e Prins, C. (2011). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Tech. Rep. 2011-61, CIRRELT 2011.
• [13] Cruz-Chávez, M. A.; Díaz-Parra, O.; Juárez-Romero, D. e Martínez-Rangel, M. G. (2008). Memetic Algorithm base on a Constraint Satisfaction Technique for VRPTW. L. Rutkowski et al. (Eds.). Artificial Intelligence and Soft Computing – ICAISC 2008.
• [14] Nalepa, J. e Czech, Z. J. (2014). A Parallel Memetic Algorithm to Solve the Vehicle Routing Problem with Time Windows. arXiv preprint arXiv:1402.6942. 27 Feb 2014.
• [15] Ombuki, B.; Ross, B. J. e Hanshar, F. (2006). Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence, v. 1, n. 24, p. 17–30.
• [16] Montgomery, D. e Runger, G. (2009). Applied statistics and probability for engineers. Wiley, 4nd edição.

Como citar:

Stehling, Thiago Muniz; Souza, Sérgio Ricardo de; Filho, Moacir Felizardo de França; "UM ALGORITMO MEMÉTICO HÍBRIDO APLICADO AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM JANELA DE TEMPO", p-317-328. In: Anais do XVIII Simpósio de Pesquisa Operacinal & Logística da Marinha. São Paulo: Blucher, 2016.
ISSN 21756295, DOI 10.5151/marine-spolm2015-140440