Resumen

En el problema de ruteo de vehículos con flota heterogénea y costos variables (HFVRP) se debe determinar el conjunto de rutas que se han de desarrollar para satisfacer las demandas de los clientes, teniendo en cuenta la minimización de la suma de los costos totales de la distancia recorrida. Algoritmos heurísticos basados en búsquedas locales utilizan comúnmente movimientos simples (vecindarios) para generar soluciones factibles en problemas relacionados con diseños de rutas. En este artículo se realiza un análisis comparativo de vecindarios granulares en una búsqueda tabú para el HFVRP. La comparación se ha realizado en términos de la calidad de la solución encontrada. Los experimentos computacionales, realizados sobre instancias de benchmarking para el HFVRP, muestran la eficiencia y efectividad de la implementación de algunos vecindarios en algoritmos metaheurísticos de trayectoria, como es la Búsqueda Tabú.

I. INTRODUCCIÓN

El sistema de transporte es uno de los elementos cruciales de la cadena de suministro, y su gestión es una de las actividades clave de la logística. Según [1], los costes logísticos pueden representar entre el 5 % y el 18 % del volumen de ventas de la organización. Entre estos costes, el transporte puede representar entre un tercio y dos tercios del total; por tanto, una de las decisiones más importantes en materia de transporte es la planificación y programación de las rutas.

Las decisiones sobre la programación de rutas de distribución en su contexto básico han sido modeladas matemáticamente, utilizando diferentes aproximaciones del problema de enrutamiento de vehículos con capacidades o VRP (Vehicle Routing Problem), que se considera un problema NP-duro [2].  Algunas variantes del VRP incluyen restricciones como entrega y recogida simultánea, ventanas de tiempo, longitud de las rutas, múltiples almacenes, flota heterogénea, diferentes funciones objetivo y elementos estocásticos, entre otros. Todas estas variaciones dan lugar a múltiples problemas de investigación en el ámbito del transporte en la logística. En particular, este artículo considera la variante del VRP con flota heterogénea (HFVRP), en la que cada vehículo tiene asignada una capacidad de carga, un tiempo máximo de viaje, un coste de viaje variable y un coste de adquisición fijo. El objetivo principal del HFVRP es determinar el conjunto de rutas desarrolladas que minimizan los costes totales de la distancia recorrida.

El HFVRP considera que cada cliente debe ser atendido por un único vehículo que atienda todas sus demandas; que la suma de las demandas de los clientes de la ruta no debe superar la capacidad del vehículo asignado; que la longitud de una ruta, contemplando el tiempo de recorrido y de servicio, no debe superar el tiempo máximo fijado por viaje; que los vehículos disponibles son limitados; y, por último, que cada ruta comienza y termina en el almacén.

• Materias:Tiempos y movimientos Logística Análisis de costos Transporte por carretera
• Subjects:Predetermined motion time systems Logistics Cost analysis Road transport
• Palabras claves:Búsqueda tabú; Flota heterogénea; Problema de ruteo de vehículos; Vecindarios granulares.
• Keywords:Granular neighborhoods; Heterogeneous fleet; Tabu search; Vehicle routing problems.