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

The Vehicle Routing Problem (VRP) is a common problem presented to optimize the transport routes and vehicles involved. For its approach and search of optimal solutions in operational research, mathematical models like Branch and Bound or dynamic programming among other options are used. These tools provide exact solutions, but the disadvantage is it´s difficult practical application for teaching or SME´s. The purpose of this researching work is to present Solver, a deployed application in Excel which properly programmed in BVA (Visual Basic for Applications) allows us to obtain easily solutions for teaching purpose or to be applied in SME´s. As a practical application to show the designed methodology and its operability, a practical case consisting in the calculation of the shortest path between several Spanish cities will be presented. To test the validity of the results obtained through Solver´s application, they will be contrasted with others obtained through an algorithm based in the Brute Force Search (BFS) specifically designed for this purpose. By using this algorithm, which uses Google Maps´s application for route distances, some improvements are reached compared with the previous model based in Solver, providing more current and complete information about the problem and a future cost perspective to the Vehicle Routing Problem.

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