Estudo de heurísticas para o problema de roteirização de veículos com frota heterogênea fixa, janelas de tempo, entregas fracionadas e limitações de acesso (2024)
- Authors:
- Autor USP: BARBOZA, GIOVANNI CESAR MEIRA - EP
- Unidade: EP
- Sigla do Departamento: PRO
- Subjects: ROTEIRIZAÇÃO; VEÍCULOS; HEURÍSTICA; ALGORITMOS GENÉTICOS
- Language: Português
- Abstract: Este trabalho explora o problema de roteirização de veículos com uma frota heterogênea fixa, considerando restrições de janelas de tempo, entregas fracionadas e limitações de acesso (SDHFFVRPTWSD), proposto inicialmente por Dutra et al. (2023) para melhorar a logística nas entregas da indústria de cimento. O problema foi investigado mais a fundo com o objetivo de gerar soluções alternativas à heurística de inserção originalmente proposta, que poderiam resultar em uma redução dos custos operacionais. Uma heurística construtiva, baseada na heurística de economias de Clarke-Wright, e um Algoritmo Genético foram implementados para resolver o problema. Foram feitas diversas adaptações no método proposto por Clarke e Wright (1964) para acomodar as várias restrições do problema. No entanto, a ideia central de ordenação dos clientes com base no cálculo das economias foi preservada, resultando em um algoritmo que se mantém fiel ao conceito original, mas capaz de construir rotas viáveis dentro das restrições do SDHFFVRPTWSD. A heurística de Clarke-Wright desenvolvida mostrou-se flexível o suficiente para gerar, de forma eficiente, uma variedade de soluções distintas. Essas soluções foram cruciais para povoar a população inicial da meta-heurística escolhida, o Algoritmo Genético (AG). O AG incorporou várias soluções da heurística construtiva para lidar com as restrições do SDHFFVRPTWSD. Além disso, operadores de diferentes trabalhos da literatura foram combinados e selecionados com base em sua adequação ao problema proposto. Ao testar as instâncias propostas por Dutra et al. (2023), utilizando dados reais da operação, foi possível concluir que a abordagem proposta é capaz de gerar soluções viáveis e de boa qualidade, considerando as diversas restrições envolvidas. A heurística de Clarke- Wright, apesar de nãosuperar a heurística de inserção em desempenho direto, mostrou-se altamente útil para o contexto do Algoritmo Genético (AG). Sua principal contribuição foi fornecer diversidade nas soluções iniciais, gerando o espaço de busca explorado pelo AG. Esse aumento na diversidade permitiu ao AG encontrar soluções de maior qualidade em muitos casos. A melhoria foi especialmente evidente ao analisar a redução na média do gap percentual entre os custos das heurísticas e as soluções ótimas obtidas por métodos exatos. Enquanto a heurística de inserção apresentou um gap médio de 21%, o AG conseguiu reduzir esse valor para 17%. Essa redução demonstra o potencial do AG em refinar soluções iniciais variadas, otimizando o resultado final e oferecendo soluções mais próximas do ótimo em problemas de roteirização complexos em tempo de processamento competitivo.
- Imprenta:
-
ABNT
BARBOZA, Giovanni Cesar Meira. Estudo de heurísticas para o problema de roteirização de veículos com frota heterogênea fixa, janelas de tempo, entregas fracionadas e limitações de acesso. 2024. Trabalho de Conclusão de Curso (Graduação) – Escola Politécnica, Universidade de São Paulo, São Paulo, 2024. Disponível em: https://bdta.abcd.usp.br/directbitstream/bf9eb618-ef83-4207-ad18-c8853d2e3afc/GIOVANNI_CESAR_MEIRA_BARBOZA_TF-24.pdf. Acesso em: 17 abr. 2025. -
APA
Barboza, G. C. M. (2024). Estudo de heurísticas para o problema de roteirização de veículos com frota heterogênea fixa, janelas de tempo, entregas fracionadas e limitações de acesso (Trabalho de Conclusão de Curso (Graduação). Escola Politécnica, Universidade de São Paulo, São Paulo. Recuperado de https://bdta.abcd.usp.br/directbitstream/bf9eb618-ef83-4207-ad18-c8853d2e3afc/GIOVANNI_CESAR_MEIRA_BARBOZA_TF-24.pdf -
NLM
Barboza GCM. Estudo de heurísticas para o problema de roteirização de veículos com frota heterogênea fixa, janelas de tempo, entregas fracionadas e limitações de acesso [Internet]. 2024 ;[citado 2025 abr. 17 ] Available from: https://bdta.abcd.usp.br/directbitstream/bf9eb618-ef83-4207-ad18-c8853d2e3afc/GIOVANNI_CESAR_MEIRA_BARBOZA_TF-24.pdf -
Vancouver
Barboza GCM. Estudo de heurísticas para o problema de roteirização de veículos com frota heterogênea fixa, janelas de tempo, entregas fracionadas e limitações de acesso [Internet]. 2024 ;[citado 2025 abr. 17 ] Available from: https://bdta.abcd.usp.br/directbitstream/bf9eb618-ef83-4207-ad18-c8853d2e3afc/GIOVANNI_CESAR_MEIRA_BARBOZA_TF-24.pdf
Download do texto completo
| Tipo | Nome | Link | |
|---|---|---|---|
 |
GIOVANNI_CESAR_MEIRA_BARB... | Direct link |
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
