Um Algoritmo Híbrido para o Problema de Roteamento de Veículos com Frota Heterogênea Robusto
Resumo
Este trabalho aborda o Fleet Size and Mix Vehicle Routing Problem, que visa não apenas planejar rotas de custo mínimo, mas também determinar a melhor composição de veículos para realizar as entregas. Sob a perspectiva da otimização robusta, modelou-se as demandas como valores pertencentes a um conjunto de incertezas. Foram propostas uma combinação do algoritmo de Busca Local Iterada com um método exato de particionamento de conjuntos e estruturas de dados para realizar as buscas locais de maneira eficiente. Experimentos computacionais mostram a eficácia do método, que foi capaz de alcançar a maioria dos melhores limitantes superiores conhecidos da literatura, além de melhorar limitantes para algumas instâncias.Referências
Ben-Tal, A. and Nemirovski, A. (1999). Robust solutions of uncertain linear programming. Operations Research Letters, 25:1–13.
Bertsimas, D. and Sim, M. (2004). The price of robustness. Operations Research, 52(1):35–53.
Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49–66.
Lourenço, H. R., Martin, O. C., and Stützle, T. (2019). Iterated Local Search: Framework and Applications, pages 129–168. Springer International Publishing, Cham.
Penna, P. H. V., Subramanian, A., Ochi, L. S., Vidal, T., and Prins, C. (2019). A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet. Annals of Operations Research, 273(1):5–74.
Savelsbergh, M. W. P. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4(1):285–305.
Subramanyam, A., Repoussis, P. P., and Gounaris, C. E. (2018). Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. arXiv:1810.04348 [cs, math].
Subramanyam, A., Repoussis, P. P., and Gounaris, C. E. (2020). Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. INFORMS Journal on Computing, 32(3):661–681.
Vidal, T., Crainic, T. G., Gendreau, M., and Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3):658–673.
Bertsimas, D. and Sim, M. (2004). The price of robustness. Operations Research, 52(1):35–53.
Golden, B., Assad, A., Levy, L., and Gheysens, F. (1984). The fleet size and mix vehicle routing problem. Computers & Operations Research, 11(1):49–66.
Lourenço, H. R., Martin, O. C., and Stützle, T. (2019). Iterated Local Search: Framework and Applications, pages 129–168. Springer International Publishing, Cham.
Penna, P. H. V., Subramanian, A., Ochi, L. S., Vidal, T., and Prins, C. (2019). A hybrid heuristic for a broad class of vehicle routing problems with heterogeneous fleet. Annals of Operations Research, 273(1):5–74.
Savelsbergh, M. W. P. (1985). Local search in routing problems with time windows. Annals of Operations Research, 4(1):285–305.
Subramanyam, A., Repoussis, P. P., and Gounaris, C. E. (2018). Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. arXiv:1810.04348 [cs, math].
Subramanyam, A., Repoussis, P. P., and Gounaris, C. E. (2020). Robust optimization of a broad class of heterogeneous vehicle routing problems under demand uncertainty. INFORMS Journal on Computing, 32(3):661–681.
Vidal, T., Crainic, T. G., Gendreau, M., and Prins, C. (2014). A unified solution framework for multi-attribute vehicle routing problems. European Journal of Operational Research, 234(3):658–673.
Publicado
06/08/2023
Como Citar
NEVES, Carlos; SUBRAMANIAN, Anand; MUNARI, Pedro.
Um Algoritmo Híbrido para o Problema de Roteamento de Veículos com Frota Heterogênea Robusto. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 175-179.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2023.230923.
