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

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 la decisión de localización de una empresa manufacturera tomando como criterio de selección la distancia total a recorrer para distribuir su producto.

Introducción

Este artículo es el primero de una serie de tres, en los cuales se 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á la metodologí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 la problemá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 la afirmació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, dado que se estima que los costos del transporte representan entre el 1O% y  el  2O% 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 Problem), o en términos generales, para problemas con capacidad definida (Machado et al., 2002), es generalizado el VRP (Olivera, 2004).

El ruteo de vehículos (VRP) es un problema de optimización combinatoria complejo, considerado ya un paradigma en la literatura especializada (Hermosilla y Barán, s/f), que surgió, según Olivera (2004), desde 1959.