Journal of Applied Science and Engineering

Published by Tamkang University Press

ESCI jase impact factor scopus logo open access rate of Scopus journal

VRP Model with time window, multiproduct and multidepot

 2020

 Volume 23, Issue 2

José Ruiz-Meza1,2, Isaid Montes1, Arnoldo Pérez1, and María Ramos-Márquez3

1Industrial Engineering Program, Corporación Universitaria del Caribe, Sincelejo, Colombia

2Faculty of Engineering, Universidad de La Sabana, Chía, Colombia

3Faculty of Engineering, Universidad Tecnológica de Bolívar, Cartagena, Colombia

Received: July 30, 2019
Accepted: February 15, 2020
Publication Date: May 10, 2026

上傳圖片

Graphic representation of multiproduct and multidepot VRP

 Copyright The Author(s). This is an open access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are cited.

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

Download PDF

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] Richard R. Young and Paul Esqueda. Vulnerabilidades de la cadena de suministros: consideraciones para el caso de América Latina. Academia : Revista Latinoamericana de Administración, (34):63–78, 2005.
  2. [2] Ricardo Pérez-Rodríguez and Arturo Hernández-Aguirre. A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows. Computers and Industrial Engineering, 130:75–96, apr 2019.
  3. [3] Onder Belgin, Ismail Karaoglan, and Fulya Altiparmak. Two-echelon vehicle routing problem with simultaneous pickup and delivery: Mathematical model and heuristic approach. Computers and Industrial Engineering, 115:1–16, 2018.
  4. [4] Pandhapon Sombuntham and Voratas Kachitvichyanukul. Multi-depot vehicle routing problem with pickup and delivery requests. In AIP Conference Proceedings, volume 1285, pages 71–85, 2010.
  5. [5] Efrain Ruiz, Valeria Soto-Mendoza, Alvaro Ernesto Ruiz Barbosa, and Ricardo Reyes. Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers and Industrial Engineering, 133:207–219, 2019.
  6. [6] Martin Grötschel and Olaf Holland. Solution of large-scale symmetric travelling salesman problems. Mathematical Programming, 51(1-3):141–202, jul 1991.
  7. [7] B. L. Golden, T. L. Magnanti, and H. Q. Nguyen. Implementing vehicle routing algorithms. Networks, 7(2):113148, 1977.
  8. [8] G. Clarke and J. W. Wright. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4):568–581, aug 1964.
  9. [9] Angélica Sarmiento Lepesqueur. Estudio del problema de ruteo de vehículos con balance de carga : Aplicación de la meta-heurística Búsqueda Tabú. Universidad de La Sabana, 2014.
  10. [10] Jairo R. Montoya-Torres, Julián López Franco, Santiago Nieto Isaza, Heriberto Felizzola Jiménez, and Nilson Herazo-Padilla. A literature review on the vehicle routing problem with multiple depots, 2015.
  11. [11] Alfredo Olivera. Heurísticas para problemas de ruteo de vehículos. Instituto de Computacion- Facultad de Ingenieria., page 63, 2004.
  12. [12] Linda Bibiana Rocha Medina, Elsa Cristina González LaRota, and Javier Arturo Orjuela Castro. Una revisión al estado del arte del proble- ma de ruteo de vehículos : Evolución histó- rica y métodos de solución State of the art review of the vehicle routing problem : A historic account with solving methods Resumen. Ingeniería. Universidad Francisco José de Caldas, 16(2):35–55, 2011.
  13. [13] Roberto Baldacci, Paolo Toth, and Daniele Vigo. Recent advances in vehicle routing exact algorithms. 4OR, 5(4):269–298, nov 2007.
  14. [14] Marius M. Solomon and Jacques Derosiers. Time window constrained routing and scheduling problems. Transportation Science, 22(1):1–13, 1988.
  15. [15] Jacques Renaud, Gilbert Laporte, and Fayez F. Boctor. A tabu search heuristic for the multi-depot vehicle routing problem. Computers and Operations Research, 23(3):229–235, 1996.
  16. [16] G. Laporte, Y. Nobert, and D. Arpin. An exact algorithm for solving a capacitated location-routing problem. Annals of Operations Research, 6(9):291–310, sep 1986.
  17. [17] Gilbert Laporte, François V. Louveaux, and Hélène Mercure. A Priori Optimization of the Probabilistic Traveling Salesman Problem. Operations Research, 42(3):543–549, 1994.
  18. [18] N. Wilson H., J. Sussman M., H. K. Wong, and T. Higonnet. Scheduling algorithms for a dial-a-ride system. Technical report, Massachusetts Institute of Technology, Urban Systems Laboratory, 1971.
  19. [19] Imdat Kara, Bahar Y. Kara, and M. Kadri Yetis. Energy minimizing vehicle routing problem. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 4616 LNCS, pages 62–71, 2007.
  20. [20] Tolga Bektaş and Gilbert Laporte. The PollutionRouting Problem. Transportation Research Part B: Methodological, 45(8):1232–1250, 2011.
  21. [21] Gilbert Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3):345–358, jun 1992.
  22. [22] Jean François Cordeau, Gilbert Laporte, Martin W. P. Savelsbergh, and Daniele Vigo. Vehicle Routing, 2007.
  23. [23] Ç. Koç, Tolga Bektaş, Ola Jabali, and Gilbert Laporte. Thirty years of heterogeneous vehicle routing, feb 2016.
  24. [24] Santiago Nieto Isaza. 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. 2012.
  25. [25] Sumaiya Iqbal, M. Kaykobad, and M. Sohel Rahman. Solving the multi-objective Vehicle Routing Problem with Soft Time Windows with the help of bees. Swarm and Evolutionary Computation, 24:50–64, oct 2015.
  26. [26] Suresh Nanda Kumar and Ramasamy Panneerselvam. A Survey on the Vehicle Routing Problem and Its Variants. Intelligent Information Management, 04(03):66–74, 2012.
  27. [27] Mariana Puente Riofrio and Francisco Andrade Dominguez. Relación entre la diversificación de productos y la rentabilidad empresarial / Relationship between product diversification and corporate profitability. Ciencia Unemi, 9(18):73, 2016.
  28. [28] P. Parthanadee. A Multi-Product. Multi-Depot Periodic Distribution Problem. Technical report, 2002.
  29. [29] S. Reza Sajjadi, S. Hossein Cheraghi, Morteza Assadi, and Krishna Krishnan. Meta-heuristic approach for multi-product multi-depot vehicle routing problem. In IIE Annual Conference and Expo 2010 Proceedings, 2010.
  30. [30] Can B. Kalayci and Can Kaya. 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, dec 2016.
  31. [31] Armin Lüer, Magdalena Benavente, Jaime Bustos, and Bárbara Venegas. In CEUR Workshop Proceedings.
  32. [32] Christian Blum. Hybrid metaheuristics in combinatorial optimization: A tutorial. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 7505 LNCS, pages 1–10, 2012.
  33. [33] Ilhem Boussaïd, Julien Lepagnot, and Patrick Siarry. A survey on optimization metaheuristics. In Information Sciences, volume 237, pages 82–117, jul 2013.
  34. [34] L. Jourdan, M. Basseur, and E. G. Talbi. Hybridizing exact methods and metaheuristics: A taxonomy. European Journal of Operational Research, 199(3):620–629, dec 2009.