Operador de cruzamento baseado em partições aplicado no problema de roteamento de veículos
Resumo
Este artigo propõe uma modificação do operador de cruzamento Generation Partition Crossover 2 (GPX2) que é uma adaptação do operador de cruzamento Partition Crossover (PX). Os operadores GPX2 e PX foram inicialmente validados apenas no Problema do Caixeiro Viajante. Diante disto, a proposta deste trabalho consiste na adaptação do operador GPX2 ao Problema de Roteamento de Veículos. O GPX2 utiliza o conceito de Ghost nodes e uma função fitness que considera penalização de soluções infactíveis do Problema de Roteamento de Veículos. O método é validado comparando o desempenho do GPX2 com o operador Order Crossover que é bastante utilizado em Problemas de Roteamento de Veículos.
Palavras-chave:
Cruzamento baseado em partições, algoritmo genético, roteamento de veículos
Referências
Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., and Semet, F. (2002). A guide to vehicle routing heuristics. Journal of the Operational Research Society, 53(5):512– 522.
Geetha, S., Poonthalir, G., and Vanathi, P. (2009). Improved k-means algorithm for capacitated clustering problem. INFOCOMP, 8(4).
Nagata, Y. (2007). Edge assembly crossover for the capacitated vehicle routing problem. In Proceedings of the 7th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP’07, pages 142–153, Berlin, Heidelberg. SpringerVerlag.
Perez-Wohlfeil, E., Chicano, F., and Alba, E. (2018). An Intelligent Data Analysis of the Structure of NP Problems for Efficient Solution: The Vehicle Routing Case. pages 368–378.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12):1985–2002.
Puljic, K. and Manger, R. (2013). Comparison of eight evolutionary crossover operators for the vehicle routing problem. Mathematical Communications, 18(2):359–375.
Rodrigues, P. R. A. (2008). Introdução aos sistemas de transporte no Brasil e à logı́stica internacional. Edições Aduaneiras.
Sanches, D., Whitley, D., and Tinós, R. (2017). Building a better heuristic for the travling salesman problem. In Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’17, pages 329–336, New York, New York, USA. ACM Press.
Tinós, R., Whitley, D., and Ochoa, G. (2019). A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling Between Local Optima. Evolutionary Computation, pages 1–31.
Tlili, T., Chicano, F., Krichen, S., and Alba, E. (2015). Evolutionary Algorithm Based on Partition Crossover (EAPX) for the Vehicle Routing Problem. In 2015 International Conference on Intelligent Networking and Collaborative Systems, pages 169–175. IEEE.
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., and Subramanian, A. (2017). New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, 257(3):845–858.
Vigo, D. and Toth, P. (2014). Vehicle Routing; Problems, Methods, and Applications. MOS-SIAM Series on Optimization, page 467.
Whitley, D., Hains, D., and Howe, A. (2009). Tunneling between optima. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation - GECCO ’09, page 915, New York, New York, USA. ACM Press.
Geetha, S., Poonthalir, G., and Vanathi, P. (2009). Improved k-means algorithm for capacitated clustering problem. INFOCOMP, 8(4).
Nagata, Y. (2007). Edge assembly crossover for the capacitated vehicle routing problem. In Proceedings of the 7th European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP’07, pages 142–153, Berlin, Heidelberg. SpringerVerlag.
Perez-Wohlfeil, E., Chicano, F., and Alba, E. (2018). An Intelligent Data Analysis of the Structure of NP Problems for Efficient Solution: The Vehicle Routing Case. pages 368–378.
Prins, C. (2004). A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31(12):1985–2002.
Puljic, K. and Manger, R. (2013). Comparison of eight evolutionary crossover operators for the vehicle routing problem. Mathematical Communications, 18(2):359–375.
Rodrigues, P. R. A. (2008). Introdução aos sistemas de transporte no Brasil e à logı́stica internacional. Edições Aduaneiras.
Sanches, D., Whitley, D., and Tinós, R. (2017). Building a better heuristic for the travling salesman problem. In Proceedings of the Genetic and Evolutionary Computation Conference on - GECCO ’17, pages 329–336, New York, New York, USA. ACM Press.
Tinós, R., Whitley, D., and Ochoa, G. (2019). A New Generalized Partition Crossover for the Traveling Salesman Problem: Tunneling Between Local Optima. Evolutionary Computation, pages 1–31.
Tlili, T., Chicano, F., Krichen, S., and Alba, E. (2015). Evolutionary Algorithm Based on Partition Crossover (EAPX) for the Vehicle Routing Problem. In 2015 International Conference on Intelligent Networking and Collaborative Systems, pages 169–175. IEEE.
Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T., and Subramanian, A. (2017). New benchmark instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, 257(3):845–858.
Vigo, D. and Toth, P. (2014). Vehicle Routing; Problems, Methods, and Applications. MOS-SIAM Series on Optimization, page 467.
Whitley, D., Hains, D., and Howe, A. (2009). Tunneling between optima. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation - GECCO ’09, page 915, New York, New York, USA. ACM Press.
Publicado
15/10/2019
Como Citar
SANCHES JÚNIOR, Elcio; ABREU, Gabriel de; NODA, Vinicius; CARVALHO, Ozeas; ROCHA, Josimar; TINOS, Renato; SANCHES, Danilo.
Operador de cruzamento baseado em partições aplicado no problema de roteamento de veículos. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 16. , 2019, Salvador.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 777-786.
ISSN 2763-9061.
DOI: https://doi.org/10.5753/eniac.2019.9333.
