Resumen

Este artículo aborda un estudio de caso en una industria de bebidas relativo al problema de rutas asimétricas de vehículos con una flota heterogénea limitada (AVRPHL). El objetivo es definir las rutas de los vehículos para reducir los costes de distribución. El PRVAFHL pertenece a la clase NP-difícil, es decir, resolverlo utilizando métodos exactos es una tarea extremadamente ardua. En la práctica, los problemas de esta naturaleza suelen tratarse de forma heurística. Entre los diversos enfoques existentes, se decidió adaptar una heurística de la literatura que demostró ser eficiente y capaz de generar soluciones de alta calidad en un tiempo de ejecución aceptable. Se realizaron experimentos computacionales con un conjunto de 7 instancias obtenidas de la empresa en cuestión. Los resultados muestran una reducción considerable del número de vehículos utilizados y de la distancia total recorrida en comparación con las soluciones adoptadas por la empresa.

1. INTRODUCCIÓN

El Problema de Rutas de Vehículos (VRP) es uno de los problemas de distribución logística más conocidos y estudiados en el campo de la optimización combinatoria debido a su aplicabilidad e importancia, especialmente en la cadena de suministro. Dada su elevada complejidad, la resolución del VRP se considera NP-hard, es decir, la dificultad para encontrar la solución óptima aumenta exponencialmente a medida que también lo hace el número de clientes.

En su forma clásica, el VRP puede definirse de la siguiente manera. Sea G = (V,E) un grafo donde V = {v₀,v₁, ...,v_n} es el conjunto de vértices y E = {(v_i, v_j):v_i, v_j ∈ V i<j} es el conjunto de aristas. El vértice v0 representa el depósito en el que se encuentra una flota de m vehículos idénticos con capacidad Q, mientras que el resto de vértices representan a los clientes. Cada cliente vi tiene una demanda qi no negativa. A cada arista {v_i, v_j} se le asocia un coste de viaje no negativo cij, que puede interpretarse en términos de distancia, tiempo y costes de viaje. El VRP consiste en determinar un conjunto de rutas (cada una de ellas asociada a un vehículo), de forma que cada cliente sea visitado exactamente una vez y por un único vehículo, de forma que se minimice la suma de los costes de viaje y se satisfaga la demanda de cada cliente. Cada vehículo debe comenzar y terminar la ruta en el depósito v0 y la suma de las demandas de cada ruta no debe superar la capacidad del vehículo. Este problema se conoce como Problema de Rutas de Vehículos con Capacidad. En la Figura 1 se muestra una representación gráfica de una solución VRP que contiene 3 rutas.

• Materias:Sistemas de distribución Optimización de procesos Operación logística
• Subjects:Distribution systems Process optimization Logistics operation
• Palabras claves:Optimización; Industria de bebidas; Búsqueda local iterada; Logística
• Keywords:Optimization; Beverage industry; Iterated Local Search; Logistics