problema de rutas con vehículos capacitados - CVRP
distancia total mínima
Dentro de la denominación de problemas de rutas de vehículos (Vehicle Routing Problem - VRP) realmente se engloba todo un amplio conjunto de variantes y personalizaciones de problemas. Desde aquellos más sencillos hasta algunos mucho más complejos que incluso hoy en día son materia de investigación. Grafos puede ser utilizado para la resolución y optimización de problemas de rutas para vehículos capacitados (CVRP)
Los problemas de rutas de vehículos (Vehicle Routing Problem - VRP) tratan determinar el conjunto de rutas de una flota de vehículos para dar servicio a un conjunto de clientes. Este tipo de problemas es de los más importantes, y de los más estudiados dentro de los problemas de optimización combinatoria. Dantzig y Ramser fueron los primeros en introducir este tipo de problemas en 1959, cuando describieron una aplicación real concerniente a la distribución de gasolina para estaciones de servicio. Además se propuso una formulación matemática del problema, y una aproximación algorítmica. Unos años después, Clarke y Wright aportaron una propuesta de algoritmo voraz (greedy algorithm) que mejoraba la aproximación algorítmica de Dantzig y Ramser. A partir de estos dos trabajos iniciales, ha surgido toda una fértil línea de investigación y desarrollo que ha crecido mucho en los últimos años. En la actualidad hay incluso soluciones informáticas en el mercado para este tipo de problemas. Este gran interés en este tipo de problemas se deriva por un lado en el sentido práctico de su aplicación en problemas reales, y por otro lado en la gran complejidad de este tipo de problemas. Al igual que la mayoría de los problemas VRP, el problema CVRP es de complejidad NP-completo. Esto es así, porque el número de posibles soluciones crece exponencialmente con el número de nodos del grafo (clientes o puntos de paso), y rápidamente sobrepasa las capacidades de cálculo de los ordenadores más potentes. Los problemas de unos 50 clientes pueden ser resueltos mediante métodos y formulaciones exactas, sin embargo, los problemas de mayor complejidad sólo pueden ser resueltos de manera óptima en algunos casos particulares, dada su gran complejidad numérica. Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: problemas de preparación de pedidos en un almacén (picking), de rutas de vehículos, planificación de transporte urbano, planificación de recogida de residuos o de aprovisionamiento, problemas de reparto o distribución, sistemas de navegación GPS, planificación de movimientos de robots, vehículos autoguiados (AGV), etc.
El Problema CVRP básico trata de determinar los recorridos de $k$ vehículos de capacidad $c_k$ que partiendo de un origen común deben pasar por un conjunto de lugares de interés (clientes) para recoger o distribuir mercancías según una demanda $d_i$, y volver de nuevo al origen de manera que la distancia total recorrida (el coste o el tiempo empleado) por el conjunto de vehículos sea mínima. En el tipo de problema más sencillo no se tiene en cuenta el horario de entrega o recogida en cada lugar de interés (ventanas horarias).
A partir de este problema básico aparecen todo un conjunto de extensiones o particularizaciones. Por ejemplo, la función objetivo podría ser:
- minimizar el número total de vehículos (o conductores) requeridos para dar servicio a todos los clientes.
- minimizar los costes fijos asociados con el uso de los vehículos (o los conductores)
- minimizar el coste total de transporte (coste fijo más variable de la ruta)
- balancear las rutas, por tiempo de viaje o carga de vehículo
- minimizar las penalizaciones asociadas para un servicio parcial a los clientes
A continuación se muestra el modelo completo del problema:
$$ \displaystyle{\min \sum_{i \in V} \sum_{j \in V} {c_{ij}} \sum_{k \in 1}^K {x_{ij}}}$$
y está sujeto a las restricciones:
$$ \displaystyle{\sum_{k=1}^K {y_{ik}} =1 \quad i \in V \setminus \{0\}} $$
$$ \displaystyle{\sum_{k=1}^K {y_{0k}} =K } $$
$$ \displaystyle{\sum_{j \in V} {x_{ijk}} = \sum_{j \in V} {x_{jik}} = y_{ik} \quad \forall i \in V, k= 1 \ldots K} $$
$$ \displaystyle{\sum_{i \in V} {d_i y_{ik}} \leq c_k \quad \forall k=1 \ldots K } $$
$$ \displaystyle{\sum_{i \in S} \sum_{j \notin S} {x_{ijk} \geq y_{hk}} \quad \forall S \subseteq V \setminus \{0\}, h \in S, k = 1 \ldots K} $$
$$ \displaystyle{x_{ijk} \in \{0,1\} \quad \forall i,j \in V, k=1 \ldots K}$$
$$ \displaystyle{y_{ijk} \in \{0,1\} \quad \forall i,j \in V, k=1 \ldots K}$$
Para un conjunto $i, j$ de nodos del grafo, se expresa la función objetivo que intentará minimizar el coste total de todos los arcos recorridos en la solución. La variable binaria $x_{ijk}$ indica si el vehículo $k$ tendrá una ruta utilizando el arco $ij$. Mientras, la variable binaria $y_{ik}$ indica si el nodo $i$ con demanda $d_i$ será atendido por el vehículo $k$ con capacidad $c_k$. Como se puede ver en la primera restricción cada nodo cliente deberá ser atendido únicamente por un vehículo (en el problema básico CVRP). En cambio del nodo origen 0 pueden partir todos los vehículos $K$ de la flota. A continuación aparecen las restricciones de continuidad donde el vehículo que llegue a un cliente deberá también partir desde él. Tan sólo faltan las restricciones de capacidad: la demanda atendida por un vehículo (suma de di) no debe exceder su capacidad $c_k$. En el caso en que todos los vehículos tengan la misma capacidad, los valores $c_k$ serán iguales. Por último aparecen condiciones de Miller y Tucker, y la definición de variables binarias.
Más información en:
—-