Metaheuristicas para el ruteo de vehiculos

Ingeniería e Investigación
Universidad Nacional de Colombia
revii_bog@unal.edu.co

ISSN (Versión impresa): 0120-5609 COLOMBIA

2006 Guillermo González Vargas / Felipe González Aristizábal METAHEURÍSTICAS APLICADAS AL RUTEO DE VEHÍCULOS. UN CASO DE ESTUDIO. PARTE 1: FORMULACIÓN DEL PROBLEMA Ingeniería e Investigación, diciembre, año/vol. 26, número 003 Universidad Nacional de ColombiaBogotá, Colombia pp. 149-156

Red de Revistas Científicas de América Latina y el Caribe, España y Portugal Universidad Autónoma del Estado de México
http://redalyc.uaemex.mx

REVISTA INGENIERÍA E INVESTIGACIÓN VOL. 26 No.3, DICIEMBRE DE 2006 (149-156)

Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio. Parte 1: formulación del problema
Metaheuristics applied to vehicle routing.A case study. Parte 1: formulating the problem
Guillermo González Vargas1 y Felipe González Aristizábal2 RESUMEN En este artículo se presentan la formulación matemática del problema de ruteo de vehículos (VRP) y una serie de metodologías utilizadas por diferentes autores para resolver sus variaciones. Se presenta con el propósito de introducir al lector a una serie de artículos referentes a ladecisión de localización de una empresa manufacturera tomando como criterio de selección la distancia total a recorrer para distribuir su producto.

Palabras clave: distribución, ruteo de vehículos, formulación matemática.
ABSTRACT This paper deals with VRP (vehicle routing problem) mathematical formulation and presents some methodologies used by different authors to solve VRP variation. Thispaper is presented as the springboard for introducing future papers about a manufacturing company’s location decisions based on the total distance traveled to distribute its product.

Keywords: distribution, vehicle routing problem, mathematical formulation.
Recibido: abril 18 de 2006 Aceptado: septiembre 3 de 2006

Introducción
Este artículo es el primero de una serie de tres, en los cualesse ilustrará la aplicación de técnicas metaheurísticas en la solución de un problema de ruteo de vehículos (VRP por las , siglas en inglés de Vehicle Routing Problem). Esta serie de artículos tiene su origen en un caso de aplicación desarrollado para una empresa manufacturera colombiana, la cual ha solicitado expresamente a los autores mantener en anonimato su identidad; por tanto, se ilustrará lametodología y los resultados obtenidos de la manera más abstracta posible, manteniendo los datos de entrada reales con los cuales se aplicaron las diferentes técnicas y la calidad y rigurosidad académica que merecen. El artículo tiene como fin presentar al lector el problema que se abordará en los dos artículos siguientes, iniciando con una revisión bibliográfica en la que se ilustra laproblemática del ruteo de vehículos y las técnicas utilizadas para resolverla, seguida por una breve descripción del problema; posteriormente se enuncia la formulación matemática del mismo y se finaliza con las conclusiones pertinentes.

El problema de ruteo de vehículos en la literatura
Centrados en el problema de distribución, en el que se enmarca el presente artículo, es importante recurrir a laafirmación de Toth y Vigo (2000): “El problema de distribuir productos desde ciertos depósitos a sus usuarios finales juega un papel central en la gestión de algunos sistemas logísticos, y su adecuada planificación puede significar considerables ahorros. Esos potenciales ahorros justifican en gran medida la utilización de técnicas de investigación operativa como facilitadoras de la planificación, dadoque se estima que los costos del transporte representan entre el 10% y el 20% del costo final de los bienes”. Dentro de este problema de transporte es necesario determinar el tipo de recurso a utilizar, la cantidad y las rutas a seguir, lo que se denomina problema de ruteo, y es tratado en la literatura como el problema del agente viajero (TSP por las siglas en inglés de , Traveling Salesman...