Modelamiento de distribución de productos cárnicos como un TSP (Traveling Salesman Problem) con teoría de grafos

Barra lateral del artículo

PDF HTML
Publicado: ene. 25, 2015
DOI: https://doi.org/10.21676/23897848.1461
Palabras clave:
Distribución, grafos, ruteo, transporte, TSP.

Contenido principal del artículo

Rodrigo A. Gómez-Montoya
Politécnico Colombiano Jaime Isaza Cadavid Medellín, Antioquia - Colombia Facultad de Ciencias Agrarias
Abdul Zuluaga-Mazo
Politécnico Colombiano Jaime Isaza Cadavid Medellín, Antioquia - Colombia Facultad de Administración
Jorge E. Espinosa-Oviedo
Politécnico Colombiano Jaime Isaza Cadavid Medellín, Antioquia - Colombia Facultad de Ingeniería

Resumen

El presente artículo tiene como objetivo utilizar el TSP (Traveling Salesman Problem) junto con teoría de grafos para diseñar estrategias de ruteo en una red distribución, buscando que esta se realice de manera eficiente respecto a la distancia y tiempos utilizados en la atención de los pedidos de los clientes. Adicionalmente, se desarrolla un caso de aplicación de la metodología en una empresa de cárnicos ubicada en la ciudad de Medellín. Como resultado, se obtiene que la utilización de TSP con grafos, permite obtener una ruta con la mínima distancia en la red de distribución, lo que se demuestra en el caso de aplicación.

Descargas

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

Detalles del artículo

Cómo citar
Gómez-Montoya, R. A., Zuluaga-Mazo, A., & Espinosa-Oviedo, J. E. (2015). Modelamiento de distribución de productos cárnicos como un TSP (Traveling Salesman Problem) con teoría de grafos. Clío América, 9(17), 8–16. https://doi.org/10.21676/23897848.1461
Número
Vol. 9 Núm. 17: enero - junio 2015
Sección
Artículo de Investigación Científica y Tecnológica

Esta revista proporciona un acceso abierto a su contenido, basado en el principio de ofrecer al público un acceso libre a las investigaciones ayuda a un mayor intercambio global del conocimiento. De igual forma su versión impresa es de libre acceso y no tiene costos asociados por publicación.

Biografía del autor/a

Rodrigo A. Gómez-Montoya, Politécnico Colombiano Jaime Isaza Cadavid Medellín, Antioquia - Colombia Facultad de Ciencias Agrarias

Ingeniero IndustrialMagíster en Ingeniería AdministrativaDocente investigador

Abdul Zuluaga-Mazo, Politécnico Colombiano Jaime Isaza Cadavid Medellín, Antioquia - Colombia Facultad de Administración

Ingeniero IndustrialEspecialista en Logística Integral yMagíster en AdministraciónDocente investigador

Jorge E. Espinosa-Oviedo, Politécnico Colombiano Jaime Isaza Cadavid Medellín, Antioquia - Colombia Facultad de Ingeniería

Ingeniero de SistemasMagíster en Inteligencia ArtificialDocente investigador

Citas

Albiach, J., Sanchis, J., & Soler, D. (2008). An asymmetric TSP with time windows and with time-dependent travel times and costs: An exact solution through a graph transformation. European Journal of Operational Research, 189(3), 789 - 802.

Anaya Tejero, J. J. (2007). Logística integral: la gestión operativa de la empresa. Madrid: ESIC Editorial.

Armon, A., Avidor, A., & Oded, S. (2010). Cooperative TSP. Theoretical Computer Science, 411(31 - 33), 2847 -2863.

Bahar Çavdar, J. S. (2014). A distribution-free TSP tour length estimation model for random graphs. European Journal of Operational Research, 588–598.

Ballou, R. H. (2004). Business Logistics management. The United States: Prentice Hall.

Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, 209–219.

Bin, Y., Zhong - Zhen, Y., & Baozhen, Y. (2009). An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 196(1), 171 - 176.

BoÅzejko, W., & Wodecki, M. (2009). Solving permutational routing problems by population-based metaheurísticos. Computers & Industrial Engineering, 57(1), 269 - 276.

Carvalho Oliveira, R., & Matos, A. C. (2004). An Experimental Study of the Ant Colony System for the period Vehicle Routing Problem. Lecture Notes in Computer Science, 3172, 286 - 293.

Chopra, S. (2001). Designing the distribution network in supply chain. The United States: Kellogg School of Management.

Ducrocq, C. (1991). Concurrence et stratégies dans la distribution. París: Ed. Vuibert Entreprise.

Gómez Montoya, R. A., Zuluaga Mazo, A., & Vélez Uribe, L. D. (2012). Preparación de pedidos eficiente en el Centro de Distribución utilizando VRP. Revista Escuela Colombiana de Ingeniería(88), 55 - 64.

Google Inc. (s.f.). Google Earth. Recuperado el 12 de 10 de 2013, de http://www.google.com/intl/es/earth/index.html

Kallehauge, B. (2008). Formulations and exact algorithms for the vehicle routing problem with time windows. Computers & Operations Research, 35(7), 2307 - 2330.

Miquel Peris, S., Parra Guerrero, F., Lhermie, C., & Miquel Romero, M. J. (2006). Distribución comercial (Vol. 23). Madrid: ESIC Editorial.

Navascués, R. d., & Pau Cos, J. (2000). Manual de logística integral. España: Ediciones Díaz de Santos.

Rizzoli, A., Montemanni, R., Lucibello, E., & Gambardella, L. (2007). Ant colony optimization for real-world vehicle routing problems from theory to applications. Swarm Intell, 1, 135 - 151.

Rodríguez Villalobos, A. (10 de Junio de 2013). Grafos. Obtenido de http://personales.upv.es/arodrigu/grafos

Rodríguez, A., & Ruiz, R. (2012). The effect of the asymmetry of road transportation networks on the traveling salesman problem. Computers & Operations Research, 39, 1566 - 1576.

Tutte, W. T. (2001). Graph Theory. Cambridge: Cambridge University Press.