Uma revisão sistemática da literatura sobre o Problema de Roteirização de Veículos Capacitados com Restrições de Carregamento Bidimensional (2L-CVRP)

Authors

  • Bianca Passos Arpini UFES-Universidade Federal do Espírito Santo
  • Rodrigo Alvarenga Rosa UFES-Universidade Federal do Espírito Santo

DOI:

https://doi.org/10.14295/transportes.v25i1.867

Keywords:

Vehicle routing problem with two-dimensional loading constraints, 2L-CVRP problem, Vehicle routing problem.

Abstract

Routing and loading are two central aspects in logistics distribution management. Recently, the integrated routing and loading problem has attracted the attention of the Operations Research community. Such an interest is not only due to their enormous application potential in real situations, but also due to the challenges for their solution, because it is the combination of two problems of high computational complexity. This article aims to conduct a systematic review of key publications related to the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints (2L-CVRP). The objective is to analyze what has been published so far and identify approaches to solution features built into the problem and research gaps that have not been treated.

Downloads

Download data is not yet available.

Author Biographies

Bianca Passos Arpini, UFES-Universidade Federal do Espírito Santo

Professora do Instituto Federal do ES (IFES). Mestre em Engenharia Civil (Área de concentração: Transportes) na Universidade Federal do Espírito Santo. Graduada em Engenharia de Produção pela Universidade Federal do Espírito Santo (2012). Pesquisadora de modelos matemáticos aplicados à área de roteirização de veículos.

Rodrigo Alvarenga Rosa, UFES-Universidade Federal do Espírito Santo

Pós-doutor em Engenharia de Transportes (PET) na COPPE/UFRJ. Bolsista de Produtividade da Fundação de Amparo à Pesquisa do Espírito Santo (FAPES) recebendo a bolsa Pesquisador Capixaba (2013-2016 e 2016-2019). Doutor em Engenharia Elétrica pela Universidade Federal do Espírito Santo (UFES), Planejamento Portuário utilizando Inteligência Artificial Distribuída (2006). Mestre em Informática pela UFES, Roteirização de Veículos (1996). Graduado em Engenharia Civil pela UFES (1989). Professor adjunto no Depart. Eng. Produção da UFES. Professor permanente do Mestrado de Engenharia Civil (UFES) - Área de Transportes. Professor permanente do Mestrado Profissional de Gestão Pública (UFES) 

References

Abdal-Hammed, M.K.; Hifi, M.; Wu; L. (2014) Large neighborhood search for the vehicle routing problem with two-dimensional loading constraints. In: International Conference on Control, Decision and Information Technologies (CoDIT). IEEE, p. 054-059. DOI: 10.1109/CoDIT.2014.6996867.

Araujo, R. R. (2010) Uma abordagem de resolução integrada para os problemas de roteirização e carregamento de veículos. Tese Doutorado, Programa de Pós-Graduação em Engenharia de Produção, Universidade Federal do Rio Grande do Sul, Porto Alegre.

Arpini, B. P.; Rosa, R. de A. (2015). Planejamento da logística de suprimento de plataformas Offshore por meio de um modelo matemático 2L-CVRP com frota heterogênea e equilíbrio náutico. Transportes, v. 23, n.4, p. 67-78. DOI:10.14295/transportes.v23i4.920.

Azevedo, B. L. P. Hokama, P. H.; Miyazawa, F. K.; Xavier, E. C. (2009) A branch-and-cut approach for the vehicle routing problem with two-dimensional loading constraints. In: Simpósio Brasileiro de Pesquisa Operacional, v. 41.

Baker, B. S.; Coffman Jr., E. G.; Rivest, R. L. (1980) Orthogonal Packings In Two Dimensions. Siam Journal On Computing, v. 9, n. 4, p. 846-85. DOI:10.1137/0209064.

Bin, W.; Hong, C.; Zhi-Yong, C. (2013) Artificial bee colony algorithm for two-dimensional loading capacitated vehicle routing problem. In: International Conference on Management Science and Engineering (ICMSE), IEEE, p. 406-412. DOI: 10.1109/ICMSE.2013.6586313.

Brereton, P.; B. A. Kitchenham; D. Budgen; M. Turner e M. Khalil (2007) Lessons from applying the systematic literature review process within the software engineering domain. The Journal of Systems and Software, v. 80, p. 571–583. DOI: 10.1016/j.jss.2006.07.009.

Côté, J.-F.; Gendreau, M.; Potvin, J.-Y. (2013) The Vehicle Routing Problem with Stochastic Two-Dimensional Items, CIRRELT-2013-84.

Clarke, G., Wright, J.W. (1964) Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, v. 12, p. 568–581. DOI: 10.1287/opre.12.4.568.

Cunha, Claudio Barbieri. Aspectos práticos da aplicação de modelos de roteirização de veículos a problemas reais. Transportes, v. 8, n. 2, 2000. DOI: 10.14295/transportes.v8i2.188

Dominguez, O.; Juan, A. A.; Faulin, J. A. (2014a) Biased‐randomized algorithm for the two‐dimensional vehicle routing problem with and without item rotations. Intern. Transactions in Operational Research, p. 1-14.

DOI:10.1111/itor.12070.

Dominguez, O.; Juan, A. A.; Barrios, B.; Faulin, J.; Agustin, A. (2014b) Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet. Annals of Operations Research, p. 1-22. DOI: 10.1007/s10479-014-1551-4.

Duhamel, C.; Lacomme, P.; Quilliot, A.; Toussaint, H. (2011) A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem. Computers & Operations Research, v. 38, n. 3, p. 617-640. DOI: 10.1016/j.cor.2010.08.017.

Fuellerer, G.; Doerner, K. F.; Hartl, R. F.; Iori, M. (2009) Ant colony optimization for the two-dimensional loading vehicle routing problem. Computers & Operations Research, v. 36, p. 655 – 673. DOI: 10.1016/j.cor.2007.10.021.

Gendreau, M.; Iori, M.; Laporte, G.; Martello, S. (2008) A Tabu Search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks, v. 51, n. 1, p. 4–18. DOI: 10.1002/net.20192.

Hamdi-Dhaoui, K. ; Labadie, N.; Yalaoui, A. (2012) Problème de tournées de véhicules avec chargement bidimensionnel et contraintes de conflits partiels multi-objectif. Proceedings of MOSIM'12.

Iori, M.; Gonzáles, J. J. S.; Vigo, D. (2007) An exact approach for the vehicle routing problem with two-dimensional loading constraints. Transportation Science, v. 41 (2), p. 253-264. DOI: 10.1287/trsc.1060.0165.

Iori, M.; Martello, S. (2010) Routing problems with loading constraints. Top, v. 18, n. 1, p. 4–27. DOI: 10.1007/s11750-010-0144-x.

Iori, M.; Martello, S. (2013) An annotated bibliography of combined routing and loading problems. The Yugoslav Journal of Operations Research. ISSN: 0354-0243 EISSN: 2334-6043, v. 23, n. 3. DOI: 10.2298/YJOR130315032I.

Khebbache-hadji, S.; Prins, C.; Yalaoui, A.; Reghioui, M. (2013) Heuristics and memetic algorithm for the two-dimensional loading capacitated vehicle routing problem with time windows. Central European Journal of Operations Research, v. 21, n. 2, p. 307-336. DOI: 10.1007/s10100-011-0204-9.

Laporte, G.; Louveaux, F. V. (1993) The integer L-shaped method for stochastic integer programs with complete recourse. Operations research letters, v. 13, n. 3, p. 133-142. Doi:10.1016/0167-6377(93)90002-X.

Labadie, N.; Prins, C. (2012) Vehicle Routing Nowadays: Compact Review and Emerging Problems. In: Mejía, G.; Velasco, N. (Ed.). Production systems and supply chain management in emerging countries: best practices, Springer, p. 141-166.

Leung, S. C. H.; Zheng, J. Zhang, D.; Zhou, X. (2010) Simulated annealing for the vehicle routing problem with two-dimensional loading constraints. Flexible services and manufacturing journal,v.22, p. 61-82. DOI: 10.1007/s10696-010-9061-4.

Leung, S. C. H.; Zhou, X.; Zhang, D.; Zheng, J. (2011) Extended guided tabu search and a new packing algorithm for the two-dimensional loading vehicle routing problem. Computers & Operations Research, v. 38, p. 205 – 215. DOI: 10.1016/j.cor.2010.04.013.

Leung, S. C. H.; Zhang, Z..; Zhang, D.; Hua, X.; Lim, M. K. (2013) A meta-heuristic algorithm for heterogeneous fleet vehicle routing problems with two-dimensional loading constraints. European Journal of Operational Research, v. 225, p. 199–210. DOI: 10.1016/j.ejor.2012.09.023.

Lodi, A.; Martello, S.; Vigo, D. (1999) Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS Journal on Computing, v. 11, n. 4, p. 345-357. DOI: 10.1287/ijoc.11.4.345.

Malapert, A.; Guerét, C.; Jussien, N.; Langevin, A.; Rousseau, L.-M. (2008) Two-dimensional pickup and delivery routing problem with loading constraints. In Proceedings of the First CPAIOR Workshop on Bin Packing and Placement Constraints (BPPC'08), France.

Martello, S.; Pisinger, D.; Vigo, D. (2000) The Three-Dimensional Bin Packing Problem. Operations Research, v. 48, n. 2, p. 256-267. DOI: 10.1287/opre.48.2.256.12386.

Martínez, L.; Amaya, C. A. (2013) A vehicle routing problem with multi-trips and time windows for circular items. Journal of the Operational Research Society, v. 64, n. 11, p. 1630-1643. DOI: 10.1057/jors.2012.128.

Mine, M. T., Silva, M. D. S. A., Ochi, L. S., Souza, M. J. F., & Silva, T. C. B. D. (2010). O problema de roteamento de veículos com coleta e entrega simultânea: uma abordagem via Iterated Local Search e GENIUS. DOI: 10.14295/transportes.v18i3.452.

Muñoz, A. L. (2011) Solución al problema de ruteo de vehículos con restricciones de capacidad y reordenamiento de carga en los sitios de demanda. 84 f. Tesis Doutorado, PUC de Chile, Chile.

Okoli, C. e K. Schabram (2010) A Guide to Conducting a Systematic Literature Review of Information Systems Research. Sprouts: Working Papers on Information Systems, v. 10, n. 26. http://sprouts.aisnet.org/10-26

Ranck Júnior, R.; Yanasse, H. H. (2010) O Problema Integrado de Carregamento e Roteamento de Veículos: uma revisão parcial dos trabalhos da literatura. In: X Worcap. Instituto Nacional de Pesquisas Espaciais – INPE: São José dos Campos.

Shen, Y.; Murata, T. (2012) Pick-up Scheduling of Two-dimensional Loading in Vehicle Routing Problem by using GA. In: Proceedings of the International MultiConference of Engineers and Computer Scientists, IMECS, v. 2, p. 1532-1537, Hong Kong.

Strodl, J.; Doerner, K.F.; Tricoire, F.; Hartl, R.F. (2010) On index structures in hybrid metaheuristics for routing problems with hard feasibility checks: An application to the 2-dimensional loading vehicle routing problem. In: Blesa, M.J.; Blum, C.; Raidl, G.; Roli, A.; Sampels, M. Hybrid Metaheuristics, v. 6373 of Lecture Notes in Computer Science, p. 160-173. DOI:

1007/978-3-642-16054-7_12.

Toth, P., D. Vigo. (2002) The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications (SIAM), Philadelphia.

Wang, F.; Tao, Y.; Shi, N. (2009) A survey on vehicle routing problem with loading constraints. In: International Joint Conference on Computational Sciences and Optimization, p. 602-606.

Zachariadis, E. E.; Kiranoudis, C. T.; Tarantilis, C. D. (2009) A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints. European Journal of Operational Research, v. 195, n. 3, p. 729–743. DOI: 10.1016/j.ejor.2007.05.058.

Zachariadis, E. E.; Tarantilis, C. D.; Kiranoudis, C. T. (2013) Integrated distribution and loading planning via a compact metaheuristic algorithm. European Journal of Operational Research, v. 228, p. 56–71. DOI: 10.1016/j.ejor.2013.01.040.

Wei, L., Zhang, Z., Zhang, D., Lim, A. (2015) A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, v. 243, n.3, p. 798-814. DOI: 10.1016/j.ejor.2014.12.048.

Downloads

Published

2017-03-01

How to Cite

Arpini, B. P., & Rosa, R. A. (2017). Uma revisão sistemática da literatura sobre o Problema de Roteirização de Veículos Capacitados com Restrições de Carregamento Bidimensional (2L-CVRP). TRANSPORTES, 25(1), 61–72. https://doi.org/10.14295/transportes.v25i1.867

Issue

Vol. 25 No. 1 (2017)

Section

Artigos

License

Authors who submit papers for publication by TRANSPORTES agree to the following terms:

  1. Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  2. Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.

  3. Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.

  4. Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.

  5. Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.