Journal of Applied Science and Engineering

Published by Tamkang University Press

1.30

Impact Factor

2.10

CiteScore

José Ruiz-Meza This email address is being protected from spambots. You need JavaScript enabled to view it.1,2, Isaid Montes1, Arnoldo Pérez1, and María Ramos-Márquez3

1 Industrial Engineering Program, Corporación Universitaria del Caribe, Sincelejo, Colombia
2 Faculty of Engineering, Universidad de La Sabana, Chía, Colombia
3 Faculty of Engineering, Universidad Tecnológica de Bolívar, Cartagena, Colombia


 

Received: July 30, 2019
Accepted: February 15, 2020
Publication Date: June 1, 2020

Download Citation: ||https://doi.org/10.6180/jase.202006_23(2).0008  

ABSTRACT


With the increase in the transfer of products in supply chains, the organization of routes requires a complex allocation insofar as different environmental variables are considered, and VRP models are an efficient tool for the solution of routing systems of low, medium and high complexity. In this paper, we developed a vehicle routing model with hard time window, multidepot, multiproduct and heterogeneous fleet for the minimization of the distance travelled. We applied the model to a case study of a company that distributes water bottles and bales in which we made a new distribution of delivery schedules by order applied Pareto analysis. We obtained optimal computational results using exact methods in a very short computational time and minimizing the distance to 35.08% of the current route.


Keywords: Pareto analysis, mathematical model, vehicle routing, optimization.


REFERENCES


 

  1. [1]Baldacci, R., Toth, P., & Vigo, D. (2007). Recent advances in vehicle routing exact algorithms. 4OR, 5(4), 269–298. https://doi.org/10.1007/s10288-007-0063-3
  2. [2]Bektaş, T., & Laporte, G. (2011). The Pollution-Routing Problem. Transportation Research Part B, 45, 1232–1250. https://doi.org/10.1016/j.trb.2011.02.004
  3. [3]Belgin, O., Karaoglan, I., & Altiparmak, F. (2018). Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers and Industrial Engineering, 115(March 2016), 1–16. https://doi.org/10.1016/j.cie.2017.10.032
  4. [4]Blum, C. (2012). Hybrid metaheuristics in combinatorial optimization: A tutorial. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7505 LNCS(6), 1–10. https://doi.org/10.1007/978-3-642-33860-1_1
  5. [5]Boussaïd, I., Lepagnot, J., & Siarry, P. (2013). A survey on optimization metaheuristics. Information Sciences, 237, 82–117. https://doi.org/10.1016/j.ins.2013.02.041
  6. [6]Clarke, G., & Wright, J. W. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568–581. https://doi.org/10.1287/opre.12.4.568
  7. [7]Cordeau, J. F., Laporte, G., Savelsbergh, M. W. P., & Vigo, D. (2007). Vehicle Routing. In Handbooks in Operations Research and Management Science (Vol. 14, pp. 367–428). https://doi.org/10.1016/S0927-0507(06)14006-2
  8. [8]Golden, B. L., Magnanti, T. L., & Nguyan, H. G. (1972). Implementing vehicle routing algorithms. Networks, 7, 113–148.
  9. [9]Grötschel, M., & Holland, O. (1991). Solution of large-scale symmetric travelling salesman problems. Mathematical Programming, 51(1–3), 141–202. https://doi.org/10.1007/BF01586932
  10. [10]Iqbal, S., Kaykobad, M., & Rahman, M. S. (2015). Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees. Swarm and Evolutionary Computation, 24, 50–64. https://doi.org/10.1016/j.swevo.2015.06.001
  11. [11]Isaza, S. N. (2012). Desarrollo y Codificación de un Modelo Matemático para la Optimización de un Problema de Ruteo de Vehículos con Múltiples Depósitos.
  12. [12]Jourdan, L., Basseur, M., & Talbi, E. G. (2009). Hybridizing exact methods and metaheuristics: A taxonomy. European Journal of Operational Research, 199(3), 620–629. https://doi.org/10.1016/j.ejor.2007.07.035
  13. [13]Kalayci, C. B., & Kaya, C. (2016). An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery. Expert Systems with Applications, 66, 163–175. https://doi.org/10.1016/j.eswa.2016.09.017
  14. [14]Kara, I., Kara, B., & Yetis, M. (2007). Energy Minimizing Vehicle Routing Problem. In Software Engineering and Formal Methods. https://doi.org/10.1021/pr800044q
  15. [15]Koç, Ç., Bektaş, T., Jabali, O., & Laporte, G. (2016). Thirty years of heterogeneous vehicle routing. European Journal of Operational Research, 249(1), 1–21. https://doi.org/10.1016/j.ejor.2015.07.020
  16. [16]Kumar, S. N., & Panneerselvam, R. (2012). A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, 04(03), 66–74. https://doi.org/10.4236/iim.2012.43010
  17. [17]Laporte, G., Nobert, Y., & Arpin, D. (1986). An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 6(9), 291–310. https://doi.org/10.1007/BF02023807
  18. [18]Laporte, Gilbert. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345–358. https://doi.org/10.1016/0377-2217(92)90192-C
  19. [19]Laporte, Gilbert, Louveaux, F. V, & Mercure, H. (1994). A Priori Optimization of the Probabilistic Traveling Salesman Problem. Operations Research, 42(3), 543–549. Retrieved from http://www.jstor.org/stable/171892
  20. [20]Lüer, A., Benavente, M., Bustos, J., & Venegas, B. (2009). El problema de rutas de vehŕculos: Extensiones y métodos de resolución estado del arte. CEUR Workshop Proceedings, 558(JANUARY 2009).
  21. [21]Montoya-Torres, J. R., López Franco, J., Nieto Isaza, S., Felizzola Jiménez, H., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers and Industrial Engineering, 79, 115–129. https://doi.org/10.1016/j.cie.2014.10.029
  22. [22]Olivera, A. (2004). Heurísticas para problemas de ruteo de vehículos. Instituto de Computacion - Facultad de Ingenieria., 63.
  23. [23]Parthanadee, P., & Logendran, R. (2002). Multi-Product Multi-Depot Periodic Distribution Problem.
  24. [24]Pérez-Rodríguez, R., & Hernández-Aguirre, A. (2019). A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows. Computers and Industrial Engineering, 130(February), 75–96. https://doi.org/10.1016/j.cie.2019.02.017
  25. [25]Puente-Riofrío, M. ;, & Andrade-Domínguez, F. (2016). Relación entre la diversificación de productos y la rentabilidad empresarial. Revista Ciencia UNEMI, 9(18), 73–80.
  26. [26]Renaud, J., Laporte, G., & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229–235. https://doi.org/10.1016/0305-0548(95)O0026-P
  27. [27]Rocha, L., González, C., & Orjuela, J. (2011). Una revisión al estado del arte del problema de ruteo e vehiculos: Evolución histórica y métodos de solución. Ingeniería, 16(2), 35–55. Retrieved from https://dialnet.unirioja.es/servlet/articulo?codigo=4797255#
  28. [28]Ruiz, E., Soto-Mendoza, V., Ruiz Barbosa, A. E., & Reyes, R. (2019). Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers and Industrial Engineering, 133(August 2018), 207–219. https://doi.org/10.1016/j.cie.2019.05.002
  29. [29]Sajjadi, S. R., Cheraghi, S., Assadi, M., & Krishnan, K. (2010). Meta-heuristic approach for multi-product multi-depot vehicle routing problem. In IIE Annual Conference and Expo 2010 Proceedings.
  30. [30]Sarmiento Lepesqueur, A. (2014). Estudio del problema de ruteo de vehículos con balance de carga :Aplicación de la meta-heurística Búsqueda Tabú. Retrieved from http://hdl.handle.net/10818/9798
  31. [31]Solomon, M., & Desrosiers, J. (1988). Time Window Constrained Routing and Scheduling Problems. Transportation Science, 22(1), 1–13. Retrieved from http://www.jstor.org/stable/25768291
  32. [32]Sombuntham, P., & Kachitvichyanukul, V. (2010). Multi-depot vehicle routing problem with pickup and delivery requests. AIP Conference Proceedings, 1285(December), 71–85. https://doi.org/10.1063/1.3510581
  33. [33]Wilson, N. H. M., Sussman, J. M., Wong, H.-K., & Higonnet, T. (1971). Scheduling algorithms for a dial-a-ride system. Massachusetts Institute of Technology. Urban Systems Laboratory.
  34. [34]Young, R. R., & Esqueda, P. (2005). Vulnerabilidades de la cadena de suministros: consideraciones para el caso de América Latina. Academia. Revista Latinoamericana de Administración, (34), 63–78. Retrieved from http://www.redalyc.org/articulo.oa?id=71603405