Aplicación de la metodología GRASP al problema de Rutificación de Vehículos

  1. Priore Moreno, Paolo
  2. Pino Díez, Raúl
  3. Martínez Carcedo, Carlos
  4. Villanueva Madrileño, Verónica
  5. Fernández Quesada, Isabel
Revista:
Dirección y organización: Revista de dirección, organización y administración de empresas

ISSN: 1132-175X

Año de publicación: 2012

Número: 48

Páginas: 46-55

Tipo: Artículo

DOI: 10.37610/DYO.V0I48.411 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Dirección y organización: Revista de dirección, organización y administración de empresas

Resumen

En este trabajo se describe el desarrollo e implementación de un Sistema de Soporte a la Decisión (DSS) que ayudará en el proceso de cálculo de rutas y llenado de camiones, que tienen que transportar un número considerable de vehículos desde 8 orígenes y distribuirlos entre más de 3.000 posibles destinos repartidos por España y Por tugal (incluidos algunos de Francia, Alemania, etc.). Se analiza, en primer lugar, el comportamiento de distintas metodologías a la hora de resolver un problema de rutas del tipo MDVRP y VRPTW. Tras ello, se opta por la utilización de la heurística GRASP como núcleo del optimizador que será desarrollado como una aplicación Web. El resultado es una mejora en la utilización del cubicaje de los vehículos, y una racionalización en las rutas que se traducen en un descenso de los costes de transporte.

Referencias bibliográficas

  • BAYKASOGLU, A.; OZBAKIR, L.; TAPKAN, P. (2007): «Artificial Bee Colony Algorithm and Its Application to generalized Assignment Problem». Swarm Intelligence: Focus on Ant and particle swarm optimization. Itech Education and Publishing. Vienna. Austria.
  • BLANTON, J. L.; WAINWRIGHT, R. L. (1993): «Multiple vehicle routing with time and capacity constraints using genetic algorithms». Proceedings of the 5th International Conference on Genetic Algorithms. San Francisco: Morgan Kaufmann, pp. 452-459.
  • CHAO, I. M.; GOLDEN, B. L.; WASIL, E. (1995): «An improved heuristic for the period vehicle routing problem». Networks, vol.26 (1), pp. 25-44.
  • CRISTEA, P.; ARSENE, A.; NITULESCU, B. (2000): «Evolutionary Intelligent Agents». Evolutionar y Computation, 2000. IEEE, vol.2, pp.1320-1328.
  • DAVIDSSON, P.; HENESEY, L.; RAMSTEDT, L.; TÖRNQUIST, J.; WERNSTEDT, F. (2005): «An analysis of agentbased approaches to transport logistics». Transportation Research part C-Emerging Technologies, vol.13(4), pp. 255- 271.
  • DE LA FUENTE, D., LOZANO, J., OCHOA, E., DÍAZ, M. (2011) Estado del ar te de algoritmos basados en colonias de hormigas para la resolución del problema VRP. XV Congreso Ingeniería de Organización. CIO 2011.
  • DORIGO, M.; MANIEZZO, V.; COLORNI, A. (1996): «Ant system: Optimization by a colony of cooperating agents». IEEE Transactions on Systems, Man, and Cybernetics, Part B, vol.26 (1), pp. 29-41.
  • FRANKLIN, S.; GRAESSER, A. (1997): «Is it an agent, or just a program?: A taxonomy for autonomous agents». Lecture Notes in Computer Science, vol.1193, pp. 21-35.
  • GARCÍA-NAJERA, A.; BULLINARIA, J. A. (2011): «An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows». Computers & Operations Research, vol. 38 (1), pp. 287-300.
  • GLOVER, F.; LAGUNA, M. (1997): Tabu Search. Kluwer Academic Publishers. Boston. USA.
  • GUTIERREZ-JARPA, G.; DESAULNIERS, G.; LAPORTE, G.; MARIANOV, V. (2010): «A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows». European Journal Of Operational Research, vol. 206 (2), pp. 341-349.
  • HANNA, L.; CAGAN, J. (2009): «Evolutionary Multi-Agent Systems: An adaptive and Dynamic Approach to Optimization». Journal of Mechanical Design, vol.131(1), Article Number : 011010, pp.1-8.
  • HO, S. C.; HAUGLAND, D. (2004): «A tabu search heuristic for the vehicle routing problem with time windows and split deliveries». Computers & Operations Research, vol. 31 (12), pp.1947-1964.
  • HO, W.; HO, G.T.S.; J. I, P.; LAU H. C. W. (2008): «A hybrid genetic algorithm for the multi-depot vehicle routing problem». Engineering Applications of Artificial Intelligence, vol. 21 (4), pp. 548-557.
  • JIN, M. Z.; LIU, K.; BOWDEN, R. O. (2007): «A two-stage algorithm with valid inequalities for the split delivery vehicle routing problem». International Journal Of Production Economics, vol. 105 (1), pp. 228-242.
  • KONTORAVDIS, G.; BARD, J.F. (1995): «A GRASP for the Vehicle Routing Problem with Time Windows». ORSA Journal on Computing, vol. 7 (1), pp. 10-23.
  • LIM AND ZHANG (2007): «A Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the VRPTW». INFORMS Journal on Computing, vol. 19 (3), pp. 443-457.
  • MATOS, A. C.; OLIVEIRA, R. C. (2004): «An experimental study of the ant colony system for the period vehicle routing problem». Lecture Notes in Computer Science, vol.3172, pp. 286-293.
  • PADBERG, M.; RINALDI, G. (1989): «A branch-and-cut approach to a traveling salesman problem with side constraints». Management Science, vol. 35 (11), pp. 1391- 1412.
  • PADBERG, M.; RINALDI, G. (1991): «A Branch-and-Cut al- gorithm for the resolution of large-scale symmetric travelling salesman problems». Society for Industrial and Applied Mathematics REVIEW, vol.33 (1), pp. 60-100.
  • PARUNAK, H. V. D. (1999): «Industrial and practical applications of DAI». Multiagent Systems. MIT Press. Massachusetts (USA).
  • PHAM, D. T.; CASTELLANI, M. (2009): «The Bees Algorithm: modelling foraging behaviour to solve continuous optimization problems». Proc. Institution of Mechanical Engineers Part C-Journal of mechanical Engineer Science, vol. 223 (12), pp. 2919-2938.
  • PINO, R.; LOZANO, J.; MARTÍNEZ, C.; VILLANUEVA, V. (2011) Estado del arte para la resolución de enrutamiento de vehículos con restricciones de capacidad. XV Congreso Ingeniería de Organización. CIO 2011.
  • PINO, R.; VILLANUEVA, V.; MARTÍNEZ, C.; LOZANO, J.; DEL PINO, B.; ANDRÉS, C. (2011) Heuristic Solutions to the Vehicle Routing Problem with Capacity Constraints. ICAI-Worldcomp’11.
  • PISINGER, D.; ROPKE, S. (2005): «A general heuristic for vehicle routing problems». Computers & Operations Research, vol. 34 (2007), pp. 2403-2435.
  • RUSSELL, R. A.; CHIANG, W-C. (2004): «Scatter search for the vehicle routing problem with time windows». European Journal Of Operational Research, vol. 169 (2), pp. 606-622.
  • SALHI, S.; SARI, M. (1997): «A multi-level composite heuristic for the multi-depot vehicle fleet mix problem». European Journal of Operational Research, vol. 103 (1), pp. 95-112.
  • SHAW, P. (1998): «Using constraint programming and local search methods to solve vehicle routing problems». CP98, Four th International conference on principles and practice of constraint programming. Lecture notes in Computer Science, vol. 1520 (1998), pp. 417-431.
  • TAO, Z. (2008): «TSP Problem solution based on improved Genetic Algorithm». Proceedings of Fourth International Conference on Neural Computation, vol.1, pp. 686- 690.
  • TOTH, P.; VIGO, D. (2000): «Models, relaxations and exact approaches for the capacitated vehicle routing problem». Discrete Applied Mathematics, vol. 123 (1-3), pp. 487-512.
  • TSAI CF.; TSAI, CW. (2002): «A New Approach for Solving Large Traveling Salesman Problem Using Evolutionary Ant Rules». IEEE International Joint Conference on Neural Networks (IJCNN), vols.1-3, pp. 1540-1545.
  • WANG CH.; LI CH.; HSU Y. (2009): «Optimization of an established multi-objective delivering problem by an improved hybrid algorithm». CIE: 2009 International Conference on Computers and Industrial Engineering, vols.1- 3, pp. 572-577.
  • WOOLDRIDGE, M. (2009): Multiagent Systems. John Wiley & Sons. West Sussex (UK).
  • YU T.; DAVIS, L. (2008): «An introduction to evolutionary computation in practice». Evolutionary Computation in Practice, studies in computational intelligence. Springer. Berlin. Germany.
Fuente de los datos: Dialnet