Roteamento com restrições temporais: formulação IP, estratégias algorítmicas e casos polinomiais em grafos
DOI:
https://doi.org/10.5753/reic.2023.3425Palavras-chave:
Problema de Roteamento de Veículos, Restrições temporais, Programação Linear InteiraResumo
Esta pesquisa consistiu na investigação do Problema de Roteamento de Veículos (VRP) com restrições temporais, buscando incorporar as características dinâmicas da cadeia logística de entregas expressas. Foram explorados aspectos teóricos de modelagem e estratégias algorítmicas. Foi proposta uma formulação em Programação Linear Inteira (PLI) para o VRPRDD, uma adaptação de instâncias de cidades brasileiras para o VRPTW e realizada uma análise de casos polinomiais de VRPs que envolvem classes especiais de grafos, tais como caminhos, estrelas, estrelas subdivididas e árvores. Algoritmos de programação dinâmica e busca binária foram aplicados, sendo determinadas suas complexidades de tempo de execução.
Downloads
Referências
Archetti, C., Feillet, D., and Speranza, M. G. (2015). Complexity of routing problems with release dates. European journal of operational research, 247(3):797–803.
Clementino, T., Rosas, J., de Freitas, R., and Uchoa, E. (2022a). Contribuições na logística de entrega urbana expressa de última milha usando grandes instâncias reais de cidades brasileiras. In Anais do III Workshop Brasileiro de Cidades Inteligentes, pages 1–12. SBC.
Clementino, T., Rosas, J., De Freitas, R., and Uchoa, E. (2022b). Solving real urban vrptw instances by applying a branch-cut-and-price via vrpsolver. In 2022 XVLIII Latin American Computer Conference (CLEI), pages 1–8. IEEE.
Desaulniers, G., Madsen, O. B., and Ropke, S. (2014). Chapter 5: The Vehicle Routing Problem with Time Windows, pages 119–159.
Loggi (2021). loggibud: Loggi benchmark for urban deliveries. https://github.com/loggi/loggibud.
Pessoa, A., Sadykov, R., Uchoa, E., and Vanderbeck, F. (2020). A generic exact solver for vehicle routing and related problems. Mathematical Programming, 183(1):483–523.
Reyes, D., Erera, A. L., and Savelsbergh, M. W. (2018). Complexity of routing problems with release dates and deadlines. European journal of operational research, 266(1):29–34.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2):254–265.
Sun, X., Li, K., and Li, W. (2022). The vehicle routing problem with release dates and flexible time windows. Engineering Optimization, 54(12):2123–2139.
Yang, W., Ke, L., Wang, D. Z., and Lam, J. S. L. (2021). A branch-price-and-cut algorithm for the vehicle routing problem with release and due dates. Transportation Research Part E: Logistics and Transportation Review, 145:102167.
Downloads
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2023 Os autores
Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.
