Publicado

2014-09-01

An algorithm for the routing problem with split deliveries and time windows (SDVRPTW) applied on retail SME distribution activities

Un algoritmo para el problema de ruteo de vehículos con entregas divididas y ventanas de tiempo (SDVRPTW) aplicado a las actividades de distribución de PYMEs del comercio al por menor

DOI:

https://doi.org/10.15446/dyna.v81n187.46104

Palabras clave:

Routing, SME, Distribution, SDVRPTW, Split deliveries (en)
Ruteo de, PYME, Distribución, SDVRPTW, Entregas divididas (es)

Descargas

Autores/as

  • Juan Sepúlveda Universidad Nacional de Colombia
  • John Wilmer Escobar Pontificia Universidad Javeriana Cali
  • Wilson Adarme-Jaimes Universidad Nacional de Colombia
In this paper, particular conditions of retail trade SMEs was analyzed, identifying not enough financial resources for using powerful tools for solve vehicle routing problem (VRP). On the other hand, in literature revised could not be identified studies about application of current approaches for solving VRP in SMEs. Additionally because of high cost, commercial software do not fit investment budget of those companies. Through a simple insertion heuristic for VRP with split deliveries and time windows (SDVRPTW), developed on an accessible technology platform like Microsoft® Excel™, was validated that SDVRPTW is an appropriate approach for solving vehicle routing problem on retail trade SMEs. Computational results show that the heuristic proposed can reduce about 50% the fleet size.
En este artículo, se analizan las condiciones particulares de las PYMEs del comercio al por menor, identificando recursos insuficientes en el uso de herramientas robustas para la solución del problema de ruteo de vehículos (VRP). Por otra parte, en la literatura revisada no se encuentra evidencia de estudios sobre la aplicación de enfoques actuales para la solución de VRP en PYMES, y aunque existe software comercial, por su alto costo no se ajustan al presupuesto de inversión de dichas compañías. Mediante una heurística de inserción sencilla para el VRP con entregas divididas y ventanas de tiempo (SDVRPTW), implementada en una plataforma tecnológica de fácil acceso como Microsoft® Excel™, se validó que el SDVRPTW es un enfoque adecuado para abordar la problemática de ruteo de vehículos en compañías PYMEs del sector comercial al por menor. Los resultados computacionales muestran que la heurística propuesta logra reducir aproximadamente en un 50% el número de vehículos empleados.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Archetti, C., Savelsbergh, M. and Speranza, M., An optimization-based heuristic for the split delivery vehicle routing problem. Transportation Science, 42 (1), pp. 22-31. 2008. DOI: 10.1287/trsc.1070.0204

Archetti, C., Bouchart, M. and Desaulniers, G., Enhanced Branch-and-Price-and-Cut for vehicle routing with split deliveries and time windows. Transportation Science 45 (3), pp. 285-298, 2011. DOI: 10.1287/trsc.1100.0363

Archetti C. and Speranza M., Vehicle routing problems with split deliveries. International Transactions in Operational Research 19, pp. 3-22, 2012.

Dantzig G. and Ramser R., The truck dispatching problem, Management Science, 6, pp. 80-91. 1959. DOI: 10.1111/j.1475-3995.2011.00811.x

Desaulniers G., Branch-and-Price-and-Cut for the split delivery vehicle routing problem with time windows. Operations Research, 58, pp. 179-192, 2010. DOI: 10.1287/opre.1090.0713

Desrochers M., Lenstra J., Savelsbergh, M. and Soumis F., Vehicle routing with time windows: Optimization and approximation. Vehicle routing: Methods and studies. Elsevier, New York. 1988.

Dror, M. and Trudeau P., Savings by split delivery routing. Transportation Science, 23 (2), pp. 141-145, 1989.

Dror, M. and Trudeau P., Split delivery routing. Naval Res. Logistics, 37, pp. 383-402. 1990.

Fisher. M. and Jaikumar, R., A generalized assignment heuristic for the vehicle routing problem. Networks, 11, pp. 109-124. 1981.

Frizzel, P. and Giffin, J., The split delivery vehicle scheduling problem with time windows and grid network distances. Computers and Operation Research, 22, pp. 655-667, 1995.

Gendreau, M., Dejax, P., Feillet, D. and Guegen, C., Vehicle routing with time windows and split deliveries. Technical Report, 2006-851, Laboratoire Informatique d' Avignon, 2006.

Guerrero, A., Pérez, R. and Olivares, E., Un caso logístico del problema de ruteo vehicular múltiple m-VRP resuelto con la heurística de Fisher & Jaikumar. 4to Taller Latino Iberoamericano de Investigación de Operaciones 2011, Acapulco, Guerrero, México, 2011.

Guimarans, D., Herrero, R., Riera, D., Juan, A. and Ramos, J., Combining constraint programming, Lagrangian relaxation and probabilistic algorithms to solve the vehicle routing problem. In Proceedings of the 17th International RCRA workshop (RCRA 2010): Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion Bologna, Italy, 2010.

Hagen, J., Lobo, Z. and Mendoça, C., The benefits of cargo bikes in Rio de Janeiro: A case of study. 13th World Conference on Transport Research, Rio de Janeiro-Brazil. 2013.

Ho, S. and Haugland, D., A tabu search heuristic for the vehicle routing problem with time windows and split deliveries. Computers and Operations Research, 31, pp. 1947-1964, 2004. DOI: 10.1016/S0305-0548(03)00155-2

Juan, A., Marull, J., Jorba, J., Hester, J., Marquès, J. and Vilajosana, X., Using agent-based simulation and distributed computing to solve vehicle routing problems. Integrationsaspekte der Simulation: Technik, Organisation und Personal GertZülch & Patricia Stock (Hrsg.) Karlsruhe, KIT Scientific Publishing, 2010.

Mullaseril, P., Dror, M. and Leung, J., Split-delivery routing in livestock feed distribution. Journal of the Operational Research Society, 48, pp. 107-116, 1997.

Nieto, A., García, A. y Crespo, D., ELOCONS un algoritmo de construcción de rutas eficiente para la pequeña y mediana empresa de distribución, Dyna Ingeniería e Industria, 87 (2), pp. 222-228, 2012. DOI: 10.6036/4360

Salani, M. and Vacca, I., Branch and Prlice for the vehicle routing problem with discrete split deliveries and time windows. European Journal of Operational Research, 213, pp. 470-477, 2011. DOI: 10.1016/j.ejor.2011.03.023

Solomon, M., Algorithms for the vehicle routing and scheduling problem with time window constraints. Operations Research, 35, pp. 234-265, 1987.

Arango-Serna, M., Adarme-Jaimes, W. and Zapata-Cortes, J., Commodities distribution using alternative types of transport. a study in the colombian bread SME's. DYNA, 77 (163), pp. 222-233. 2010.

Wilck, J. and Cavalier, T., A construction heuristic for the split delivery vehicle routing problem. American Journal of Operations Research, 2, pp. 153-162, 2012

Licencia

Derechos de autor 2014 DYNA

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.

El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.