Problema de Localización y Ruteo con Restricciones de Capacidad: Revisión de la Literatura

The capacitated location routing problem: review of literature

En este artículo se hace una revisión exhaustiva del estado del arte de las metodologías de solución existentes para el problema combinado de localización y ruteo con restricciones de capacidad (CLRP). El problema de CLRP tiene una gran cantidad de aplicaciones prácticas en temas relacionados con transporte. Se ha propuesto el siguiente esquema de clasificación de acuerdo al método de solución: (1) Algoritmos Heurísticos Constructivos, (2) Algoritmos Heurísticos Basados en Clústeres, (3) Algoritmos Heurísticos Basados en Trayectoria, (4) Algoritmos Heurísticos Basados en Población, (5) Algoritmos Heurísticos Combinados, (6) Métodos Exactos. Se hace especial énfasis en fortalezas y debilidades de cada metodología publicada, identificando oportunidades de investigación y desarrollo en el área, en el contexto de la aplicación práctica de la problemática.

INTRODUCCIÓN

El estudio de problemas combinados de logística es un área de investigación relativamente nueva [1]. Una de las problemáticas comunes en este campo es la consideración de decisiones de localización y ruteo simultáneamente. Los diferentes aspectos de estas decisiones tales como la localización, asignación y ruteo han sido estudiados generalmente de manera independiente. Este hecho puede ser explicado debido a que la localización es una decisión estratégica la cual es tomada por un largo período de tiempo, mientras que el ruteo es una decisión operacional que puede ser modificada dinámicamente muchas veces en un período corto de tiempo. Sin embargo estas decisiones están íntimamente relacionadas. De hecho, la decisión de localización de un depósito es frecuentemente influenciada por los costos de transporte y viceversa [2].

Este artículo presenta una revisión exhaustiva de los métodos de solución para el problema de localización y ruteo con restricciones de capacidad (CLRP). El CLRP puede ser modelado mediante el siguiente problema de grafos: Sea un grafo no dirigido indirecto, donde es un conjunto de nodos que contiene un subconjunto, de depósitos potenciales y un subconjunto de clientes. Cada depósito potencial tiene una capacidad y un costo de apertura. Cada cliente tiene una demanda, la cual debe ser satisfecha por un depósito abierto. Un conjunto de vehículos idénticos, cada uno con capacidad y costo fijo, está disponible en cada depósito. Cada arco tiene asociado un costo de viaje que es proporcional a la distancia entre ambos puntos.

El objetivo del CLRP es determinar los depósitos a ser abiertos, los clientes a ser asignados a cada depósito abierto y las rutas a ser desarrolladas para satisfacer las demandas de los clientes. Una solución factible para el CLRP debe considerar las siguientes restricciones: i) cada ruta debe comenzar y finalizar en el mismo depósito; ii) cada cliente debe ser visitado exactamente una vez en una sola ruta; iii) la carga total de cada ruta no debe exceder la capacidad del vehículo; iv) La carga total de las rutas asignadas a un depósito abierto no debe exceder su capacidad.