El problema del enrutamiento de vehículos. Propuestas para la búsqueda del camino más corto. Aplicación al entorno docente y Pymes

  1. JUAN JESÚS BERNAL GARCÍA 1
  2. ELOY HONTORIA HERNÁNDEZ 1
  3. DARKO ALEKSOVSKI 2
  1. 1 Universidad Politécnica de Cartagena
    info

    Universidad Politécnica de Cartagena

    Cartagena, España

    ROR https://ror.org/02k5kx966

  2. 2 Jožef Stefan Institute
    info

    Jožef Stefan Institute

    Liubliana, Eslovenia

    ROR https://ror.org/05060sz93

Revista:
Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

ISSN: 1575-605X

Año de publicación: 2013

Título del ejemplar: Serie Monografías. Métodos cuantitativos e informática

Volumen: 4

Número: 1

Páginas: 25-42

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openDialnet editor

Otras publicaciones en: Rect@: Revista Electrónica de Comunicaciones y Trabajos de ASEPUMA

Resumen

El enrutamiento de vehículos o VRP (Vehicle Routing Problem) es un problema típicamente planteado para la optimización de las rutas de transporte y vehículos asociados a ellas. Para su planteamiento y búsqueda de soluciones óptimas se recurre en investigación operativa a modelos matemáticos como Branch and Bound o programación dinámica entre otros. Estos modelos proporcionan soluciones exactas pero presentan una gran complejidad para su uso práctico en el entorno docente y de las PYMES. El objetivo del presente trabajo es la presentación de la utilidad informática Solver, que incorporada en Excel y debidamente programada con VBA (Visual Basic for Applications) permite la obtención de soluciones de manera sencilla para su uso docente y para la pequeña y mediana empresa. Como aplicación práctica para mostrar la metodología elaborada y su operatividad, se ha recurrido a un caso práctico consistente en la determinación de la ruta más corta entre ciudades españolas. Para contrastar la validez de los resultados obtenidos, se han comparado éstos con los proporcionados con un algoritmo de búsqueda exhaustiva mediante fuerza bruta (BSF) diseñado “ad hoc”. Este algoritmo que explota la aplicación de distancias de rutas de Google Maps, proporciona mejoras con respecto al modelo anterior basado en Solver [1], suministrando información más actualizada y completa sobre el problema y, pudiendo aportar en un futuro una visión de costes al problema de enrutamiento de vehículos.

Referencias bibliográficas

  • Applegate, D.L., Bixby, R.E., Chvátal, V., Cook , W.J. (2007). “The traveling salesman problem, A computational study”. Princeton. University Press, Princeton, NJ.
  • Bachelet, B., Yon, L. (2007). “Model enhancement: Improving theoretical optimization with simulation”. Simulation Modelling Practice and Theory 15 (6), pp 703-715.
  • Baldacci, R., Christofides, N., Mingozzi, A. (2008). “An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts”. Mathematical Programming . 115 (2), pp 351–385.
  • Bernal García, JJ. (2000). “Los modelos de red y la minimización de costes. Monta S.A., desea conocer la mejor forma de organizar el transporte de abastecimiento de sus fábricas, así como de elegir la ruta más corta para hacerlo a su nueva planta”.
  • Christofides, Nico (1976). “The Vehicle Routing Problem”. Revue française d'automatique, d'informatique et de recherche opérationnelle. Recherche opérationnelle, 10 (2), pp. 55-70
  • Dantzig, G., Fulkerson, R., Johnson, S. (1954). “Solution of a large scale traveling salesman problem”. Oper. Res. 2, pp 393-410.
  • De la Fuente-Aragon, MV., Hontoria, E., Ros-McDonell, L. (2012). “A Simulation-Based Solution for Optimal Logistics of Heavy and Variable-Size Items”. Industrial Engineering: Innovative Networks. Springer Link pp 291-298 Estrategia Financiera (CISS-Especial Directivos). Volumen Nº. 160, pp 22-28. Madrid.
  • Fisher, Marshall L. (1994). “Optimal solution of vehicle routing problems using minimum K-trees”. Operations Research, 42 (4), pp. 626-642.
  • http://www.lindo.com/ (03/04/2013).
  • http://www.wiley.com/college/tech/winqsb.htm (03/04/2013).
  • Laporte, G. (1992). “The Vehicle Routing Problem: An overview of exact and approximate algorithms”. European Journal of Operational Research, 59 (3), pp. 345-358.
  • Laporte, G. (2007).” What you should know about the vehicle routing problem”. Naval Research Logistics 54 (8), pp. 811–819.
  • Laporte, G., Gendreau, M., Potvin, J.Y., Semet, F. (2000). “Classical and Modern Heuristics for the Vehicle Routing Problem”. International Transactions in Operational Research 7, pp 285-300.
  • Montemanni, R., Gambardella, L.M., Rizzoli, A.E., Donati, A.V. (2005). “Ant Colony System for a Dynamic Vehicle Routing Problem”. Journal of Combinatorial Optimization 10 (4) pp 327-343.
  • Solomon, Marius M. (1987). “Algorithms for the Vehicle Routing and scheduling problems with time window constraints”. Operations Research, 35 (2), pp. 254-265.
  • Toth, P., Vigo, D. (2002). “Models, relaxations and exact approaches for the capacitated vehicle routing problem”. Discrete Applied Mathematics, 123 (1-3), pp. 487-512.
  • Walkenbach, J. (2011). “Excel 2010. Programación con VBA”. Anaya Multimedia.-Wiley. Madrid.
Fuente de los datos: Dialnet