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: ||  


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.



  1. [1]Baldacci, R., Toth, P., & Vigo, D. (2007). Recent advances in vehicle routing exact algorithms. 4OR, 5(4), 269–298.
  2. [2]Bektaş, T., & Laporte, G. (2011). The Pollution-Routing Problem. Transportation Research Part B, 45, 1232–1250.
  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.
  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.
  5. [5]Boussaïd, I., Lepagnot, J., & Siarry, P. (2013). A survey on optimization metaheuristics. Information Sciences, 237, 82–117.
  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.
  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).
  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.
  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.
  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.
  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.
  14. [14]Kara, I., Kara, B., & Yetis, M. (2007). Energy Minimizing Vehicle Routing Problem. In Software Engineering and Formal Methods.
  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.
  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.
  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.
  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.
  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
  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.
  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.
  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.
  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
  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.
  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
  31. [31]Solomon, M., & Desrosiers, J. (1988). Time Window Constrained Routing and Scheduling Problems. Transportation Science, 22(1), 1–13. Retrieved from
  32. [32]Sombuntham, P., & Kachitvichyanukul, V. (2010). Multi-depot vehicle routing problem with pickup and delivery requests. AIP Conference Proceedings, 1285(December), 71–85.
  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