Algoritmos genéticos híbridos sem delimitadores de rotas para problemas de roteirização de veículos (2007)
- Authors:
- Autor USP: ARAUJO, CARLOS EDUARDO DI GIACOMO - EP
- Unidade: EP
- Sigla do Departamento: PTR
- Subjects: HEURÍSTICA; ALGORITMOS GENÉTICOS; ROTEIRIZAÇÃO
- Language: Português
- Abstract: Apesar de serem utilizados com sucesso em problemas de roteirização clássicos como o do caixeiro-viajante e o de roteirização de veículos com janelas de tempo, os algoritmos genéticos não apresentavam bons resultados nos problemas de roteirização de veículos sem janelas de tempo. Utilizando-se de uma tendência recente de hibridização de algoritmos genéticos, Prins (2004) elaborou um algoritmo para o problema de roteirização de veículos sem janelas de tempo, monoperíodo, e que obrigatoriamente atenda a todos os clientes cujos resultados, quando aplicado a instâncias de Christofides et al. (1979) e de Golden et al. (1998), são comparáveis aos melhores códigos elaborados com base na busca tabu. Diferentemente da maioria dos algoritmos genéticos apresentados para solução de problemas de roteirização de veículos, no método desenvolvido por Prins (2004) o cromossomo é composto apenas pelos pontos a serem atendidos, não contendo delimitadores de rotas. Estas são definidas a partir de um procedimento de particionamento do cromossomo. Este trabalho implementa o algoritmo descrito por Prins (2004) e propõe a este melhorias em diversas de suas etapas, como inicialização, operação de crossover, operação de mutação, reinicialização e particionamento do cromossomo. As alterações implantadas são aplicadas às instâncias de Christofides et al. (1979) e comparadas com o algoritmo inicial em termos de qualidade de solução e tempo de processamento. Finalmente, é elaborado um algoritmo genético que contempla as alterações que obtiveram resultados positivos.
- Imprenta:
- Data da defesa: 07.12.2007
-
ABNT
ARAÚJO, Carlos Eduardo Di Giacomo. Algoritmos genéticos híbridos sem delimitadores de rotas para problemas de roteirização de veículos. 2007. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2007. Disponível em: http://www.teses.usp.br/teses/disponiveis/3/3148/tde-28032008-161354/. Acesso em: 19 abr. 2024. -
APA
Araújo, C. E. D. G. (2007). Algoritmos genéticos híbridos sem delimitadores de rotas para problemas de roteirização de veículos (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/3/3148/tde-28032008-161354/ -
NLM
Araújo CEDG. Algoritmos genéticos híbridos sem delimitadores de rotas para problemas de roteirização de veículos [Internet]. 2007 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3148/tde-28032008-161354/ -
Vancouver
Araújo CEDG. Algoritmos genéticos híbridos sem delimitadores de rotas para problemas de roteirização de veículos [Internet]. 2007 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/3/3148/tde-28032008-161354/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
