Contribuições na logística de entrega urbana expressa de última milha usando grandes instâncias reais de cidades brasileiras
Resumo
Neste artigo, o problema de roteamento de veículos com janelas de tempo é abordado, como forma de incorporar características de dinamicidade da cadeia logística de entregas expressas, explorando aspectos teóricos que melhor definem o problema e suas instâncias. O problema consiste em determinar rotas de custo mínimo que devem ser executadas por uma frota de veículos respeitando suas capacidades e as janelas de tempo de entregas de cada cliente. Uma estratégia que utiliza o método de Branch-Cut-and-Price através da ferramenta VRPsolver foi aplicada em dois conjuntos de instâncias, sendo a primeira as instâncias clássicas artificiais de Solomon e, a segunda, instâncias reais brasileiras adaptadas do benchmark loggiBUD.
Palavras-chave:
instâncias urbanas reais, loggibud, método BCP, programação inteira, VRPsolver, VRPTW
Referências
Baldacci, R., Mingozzi, A., and Roberti, R. (2011). New route relaxation and pricing strategies for the vehicle routing problem. Operations research, 59(5):1269–1283.
Baldacci, R., Mingozzi, A., and Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1):1–6.
Bard, J. F., Kontoravdis, G., and Yu, G. (2002). A branch-and-cut procedure for the vehicle routing problem with time windows. Transportation Science, 36(2):250–269.
Bent, R. and Van Hentenryck, P. (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 38(4):515–530.
Blocho, M. and Czech, Z. J. (2013). A parallel memetic algorithm for the vehicle routing problem with time windows. In 2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, pages 144–151. IEEE.
Bräysy, O. and Gendreau, M. (2005). Vehicle routing problem with time windows, part i: Route construction and local search algorithms. Transportation science, 39(1):104–118.
Cavalcanti, L. J. E. and Doneux, N. F. (2021). Análise de fatores determinantes na decisão de compra online: reflexões sobre o impacto da pandemia no comportamento do consumidor brasileiro.
Christofides, N., Mingozzi, A., and Toth, P. (1981). State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2):145–164.
Damião, C. M., Silva, J. M. P., and Uchoa, E. (2021). A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. 4OR, pages 1–25.
Dantzig, G. B. and Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1):80–91.
Desaulniers, G., Madsen, O. B., and Ropke, S. (2014). Chapter 5: The vehicle routing problem with time windows. In Vehicle Routing: Problems, Methods, and Applications, Second Edition, pages 119–159. SIAM.
Fonseca-Galindo, J. C., Surita, G. d. C., Neto, J. M., de Castro, C. L., and Lemos, A. P. (2020). A multi-agent system for solving the dynamic capacitated vehicle routing problem with stochastic customers using trajectory data mining. arXiv preprint arXiv:2009.12691.
Gehring, H. and Homberger, J. (2001). A parallel two-phase metaheuristic for routing problems with time-windows. Asia Pacific Journal of Operational Research, 18(1):35–48.
Jepsen, M., Petersen, B., Spoorendonk, S., and Pisinger, D. (2008). Subset-row inequalities applied to the vehicle-routing problem with time windows. Operations Research, 56(2):497–511.
Knight, K. and Hofer, J. (1968). Vehicle scheduling with timed and connected calls: A case study. Journal of the Operational Research Society, 19(3):299–310.
Laporte, G. and Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. Operations-Research-Spektrum, 5(2):77–85.
Lim, A. and Zhang, X. (2007). A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. INFORMS Journal on Computing, 19(3):443–457.
Loggi (2021). loggibud: Loggi benchmark for urban deliveries. https://github.com/loggi/loggibud.
Lysgaard, J. (2006). Reachability cuts for the vehicle routing problem with time windows. European Journal of Operational Research, 175(1):210–223.
Madsen, O. (1976). Optimal scheduling of trucks-a routing problem with tight due times for delivery. Optimization applied to transportation systems, pages 126–136.
Pecin, D., Contardo, C., Desaulniers, G., and Uchoa, E. (2017). New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing, 29(3):489–502.
Pessoa, A., Sadykov, R., and Uchoa, E. (2021). Solving bin packing problems using vrpsolver models. In Operations Research Forum, volume 2, pages 1–25. Springer.
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.
Pugliese, L. D. P. and Guerriero, F. (2013). A survey of resource constrained shortest path problems: Exact solution approaches. Networks, 62(3):183–200.
Rosas, J., Clementino, T., and de Freitas, R. (2021). Resolvendo instâncias de entregas urbanas reais com janelas de tempo baseadas no benchmark loggibud e aplicando um branch-cut-and-price via vrpsolver. In Workshop PBP-Loggi.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):254–265.
Toth, P. and Vigo, D. (2014). Vehicle routing: problems, methods, and applications. SIAM.
Vidal, T., Crainic, T. G., Gendreau, M., and Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & operations research, 40(1):475–489.
Vidal, T., Laporte, G., and Matl, P. (2020). A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, 286(2):401– 416.
Zhang, Z., Luo, Z., Qin, H., and Lim, A. (2019). Exact algorithms for the vehicle routing problem with time windows and combinatorial auction. Transportation Science, 53(2):427–441.
Baldacci, R., Mingozzi, A., and Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1):1–6.
Bard, J. F., Kontoravdis, G., and Yu, G. (2002). A branch-and-cut procedure for the vehicle routing problem with time windows. Transportation Science, 36(2):250–269.
Bent, R. and Van Hentenryck, P. (2004). A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, 38(4):515–530.
Blocho, M. and Czech, Z. J. (2013). A parallel memetic algorithm for the vehicle routing problem with time windows. In 2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, pages 144–151. IEEE.
Bräysy, O. and Gendreau, M. (2005). Vehicle routing problem with time windows, part i: Route construction and local search algorithms. Transportation science, 39(1):104–118.
Cavalcanti, L. J. E. and Doneux, N. F. (2021). Análise de fatores determinantes na decisão de compra online: reflexões sobre o impacto da pandemia no comportamento do consumidor brasileiro.
Christofides, N., Mingozzi, A., and Toth, P. (1981). State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2):145–164.
Damião, C. M., Silva, J. M. P., and Uchoa, E. (2021). A branch-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. 4OR, pages 1–25.
Dantzig, G. B. and Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1):80–91.
Desaulniers, G., Madsen, O. B., and Ropke, S. (2014). Chapter 5: The vehicle routing problem with time windows. In Vehicle Routing: Problems, Methods, and Applications, Second Edition, pages 119–159. SIAM.
Fonseca-Galindo, J. C., Surita, G. d. C., Neto, J. M., de Castro, C. L., and Lemos, A. P. (2020). A multi-agent system for solving the dynamic capacitated vehicle routing problem with stochastic customers using trajectory data mining. arXiv preprint arXiv:2009.12691.
Gehring, H. and Homberger, J. (2001). A parallel two-phase metaheuristic for routing problems with time-windows. Asia Pacific Journal of Operational Research, 18(1):35–48.
Jepsen, M., Petersen, B., Spoorendonk, S., and Pisinger, D. (2008). Subset-row inequalities applied to the vehicle-routing problem with time windows. Operations Research, 56(2):497–511.
Knight, K. and Hofer, J. (1968). Vehicle scheduling with timed and connected calls: A case study. Journal of the Operational Research Society, 19(3):299–310.
Laporte, G. and Nobert, Y. (1983). A branch and bound algorithm for the capacitated vehicle routing problem. Operations-Research-Spektrum, 5(2):77–85.
Lim, A. and Zhang, X. (2007). A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. INFORMS Journal on Computing, 19(3):443–457.
Loggi (2021). loggibud: Loggi benchmark for urban deliveries. https://github.com/loggi/loggibud.
Lysgaard, J. (2006). Reachability cuts for the vehicle routing problem with time windows. European Journal of Operational Research, 175(1):210–223.
Madsen, O. (1976). Optimal scheduling of trucks-a routing problem with tight due times for delivery. Optimization applied to transportation systems, pages 126–136.
Pecin, D., Contardo, C., Desaulniers, G., and Uchoa, E. (2017). New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS Journal on Computing, 29(3):489–502.
Pessoa, A., Sadykov, R., and Uchoa, E. (2021). Solving bin packing problems using vrpsolver models. In Operations Research Forum, volume 2, pages 1–25. Springer.
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.
Pugliese, L. D. P. and Guerriero, F. (2013). A survey of resource constrained shortest path problems: Exact solution approaches. Networks, 62(3):183–200.
Rosas, J., Clementino, T., and de Freitas, R. (2021). Resolvendo instâncias de entregas urbanas reais com janelas de tempo baseadas no benchmark loggibud e aplicando um branch-cut-and-price via vrpsolver. In Workshop PBP-Loggi.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations research, 35(2):254–265.
Toth, P. and Vigo, D. (2014). Vehicle routing: problems, methods, and applications. SIAM.
Vidal, T., Crainic, T. G., Gendreau, M., and Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers & operations research, 40(1):475–489.
Vidal, T., Laporte, G., and Matl, P. (2020). A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research, 286(2):401– 416.
Zhang, Z., Luo, Z., Qin, H., and Lim, A. (2019). Exact algorithms for the vehicle routing problem with time windows and combinatorial auction. Transportation Science, 53(2):427–441.
Publicado
31/07/2022
Como Citar
CLEMENTINO, Thailsson; ROSAS, Juan; FREITAS, Rosiane de; UCHOA, Eduardo.
Contribuições na logística de entrega urbana expressa de última milha usando grandes instâncias reais de cidades brasileiras. In: WORKSHOP BRASILEIRO DE CIDADES INTELIGENTES (WBCI), 3. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 1-12.
DOI: https://doi.org/10.5753/wbci.2022.222570.
