El problema de ruteo de vehículos
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 10% y el 20% 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. Este tipo de situación, como se había mencionado anteriormente, es una generalización del problema del agente viajero, el mismo que puede ser explicado de la siguiente manera:
Existe un agente de ventas que debe visitar a sus clientes ubicados en diferentes ciudades y luego volver a su ciudad de partida, y dicha actividad debe ser llevada a cabo con el menor costo posible (Ahuja et al., 1993); según Hermosilla y Barán (s/f) el costo de la ruta puede estar dado por la duración total de la misma (en tiempo o distancia). El problema de ruteo de vehículos se representa en un grafo con nodos y arcos, los cuales representan la ubicación de los clientes y la red vial por la cual pueden circular los vehículos.
Una recopilación de técnicas exactas de solución existentes para los problemas de ruteo de vehículos puede encontrarse en Laporte (1992); no obstante los de gran dimensión resultan imposibles de solucionar en tiempo polinomial, por lo que el VRP se denomina NP-hard (Machado et al., 2000; Olivera, 2004), donde no es posible alcanzar una solución óptima, y, dependiendo de las características especiales de clientes, locaciones y producto/servicio, requiere la elaboración de una metodología de solución específica con la cual sea posible aproximarse lo mejor posible al óptimo. Las diferentes variaciones y restricciones del problema generan una “familia” de VRP (Medaglia, 2005) de la que vale la pena mencionar ocho casos típicos, los cuales al compartir características pueden dar lugar a todo un universo de problemas VRP. Los principales problemas de ruteo de vehículos se ilustran en la
Figura 1 y pueden ser descritos así:
CVRP
(Capacited VRP), es el VRP más general y consiste en uno o varios vehículos con capacidad limitada y constante encargados de distribuir los productos según la demanda de los clientes (Olivera, 2004; Lee et al., 2002). Este problema ha sido resuelto mediante búsqueda Tabú (Olivera, 2004; Rego, s/f), algoritmos genéticos (Machado et al, 2002; Machado et al., 2003 (a); Olivera, 2004), algoritmos de colonias de hormigas (Olivera, 2004), Constraint programming (Shaw, 1998) y algoritmos híbridos de recocido simulado y algoritmos genéticos (Wendt y König, s/f).
MDVRP
(Multi-Depot VRP), o VRP con múltiples depósitos es un caso de ruteo de vehículos en el que existen varios depósitos (cada uno con una flota de vehículos independiente) que deben servir a todos los clientes, caso resuelto por Tansini et al., (s/f) mediante técnicas de cluster first – routen second, que serán descritas posteriormente.
PVRP
(Period VRP), contempla en su planteamiento un horizonte de operación de M días, periodo durante el cual cada cliente debe ser visitado una vez, problema propuesto por Francis et al., (2004) y resuelto por los mismos autores mediante relajación lagrangiana.
SDVRP
(Split Delivery VRP), o VRP de entrega dividida, donde se permite que un cliente pueda ser atendido por varios vehículos si el costo total se reduce, lo cual es importante si el tamaño de los pedidos excede la capacidad de un vehículo, (Lee et al., 2002; Archetti et al., 2001), resuelto en 2002 por Lee et al.
SVRP
(Stochastic VRP), se trata de un VRP en que uno o varios componentes son aleatorios; clientes, demandas y tiempos estocásticos son las principales inclusiones en este tipo de problemas. El SVRP ha sido resuelto por Bianchi et al., (s/f) a través de búsqueda Tabú, recocido simulado, algoritmos de colonias de hormigas, algoritmos genéticos y otros algoritmos evolutivos.
VRPPD
(VRP Pickup and Delivery), o VRP con entrega y recogida, es aquel en el que cabe la posibilidad de que los clientes pueden devolver determinados bienes, por tanto, se debe tener presente que estos quepan en el vehículo. Esta restricción hace más difícil el problema de planificación y puede causar una mala utilización de las capacidades de los vehículos, un aumento de las distancias recorridas o a un mayor número de vehículos (Volkan, 2005; Dethloff, 200; Halse, 1992; Gendreau et.al., 1994; Min, 1989). Una forma de solucionar el VRPPD mediante la utilización de algoritmos genéticos fue propuesta por Volkan en 2005, quien afirma que si este problema incluye la restricción de culminar todas las entregas antes de iniciar las recogidas se da lugar a un VRP con backhauls oVRPB, variación del VRP estudiada por Charlotte y Goetschalckx (1998).
MFVRP
(Mix Fleet VRP), es un VRP en el que se suponen vehículos con distintas capacidades o capacidad heterogénea, por lo que es necesario considerar estas capacidades en la ruta que seguirá cada recurso, ya que un camión más grande podrá realizar una ruta más larga o que tenga mayor concentración de demanda, lo cual fue estudiado inicialmente por Liu y Shen (1999) y posteriormente resuelto por Barchett y Campion mediante Búsqueda Tabú en 2002.
VRPTW
(VRP with Time Windows), es aquel en el que se incluye una restricción adicional en la que se asocia a cada cliente una ventana de tiempo, es decir, cada cliente sólo está dispuesto a recibir el bien o servicio durante un intervalo de tiempo predeterminado; este tipo de problema ha sido resuelto por diferentes autores, entre los que vale la pena mencionar a Olivera (2004), quien presenta una solución mediante búsqueda Tabú, Gendreau et al., (1998) proponen una heurística de inserción; Olivera (2004), Vacic (2002), Bräysy (2001), Zhu (2000) y Louis et al (1999) lo resuelven con algoritmos genéticos y Barán y Schaerer (2003) y Gambardella et al., (1999) presentan una propuesta a través de algoritmos de colonia de Hormigas.
Los diferentes problemas VRP, y básicamente los que utilizan múltiples vehículos (Restori, s/f; Olivera, 2004) y/o depósitos (Tansini et al., s/f), pueden reducir su complejidad acotando el universo de soluciones, disminuyendo el conjunto de clientes a ser visitados por cada vehículo o desde cada depósito, esto es, asignar a cada vehículo/depósito un conjunto de clientes para atender, lo que Medaglia (2005) llama set covering, o lo que otros autores conocen como clusterizar o asignar primero, rutear después cluster first – routen second (Olivera, 2004).
La clusterización de los clientes puede ser realizada a través de diferentes heurísticas, entre las que vale la pena mencionar:
Heurística de barrido o sweep, esta técnica propone establecer un punto de origen en el depósito y desde allí realizar un barrido para abarcar toda el área geográfica del problema, determinando así cada uno de los clusters(anónimo, s/f).
3
Heurística de asignación generalizada de Fisher y Jaikumur, basa la generación de clusters en la solución de un problema de asignación generalizada (GAP) sobre los clientes, fue realizada por Fisher y Jaikumur (1981).
Heurística de localización de Bramel y Simchi-Levi, se utiliza una metodología de solución similar a la propuesta por Fisher y Jaikumur (1981); sin embargo, la solución inicial es determinada por la de un problema de localización de concentradores con capacidades (Bramel y Simchi-Levi, 1995).
Una vez definido el conjunto de clientes a atender (cluster) se procede a realizar la asignación de la mejor ruta, este subproblema generalmente subyace en un caso de problema de agente viajero (TSP) y puede resultar tan pequeño como para ser solucionado mediante una técnica de optimización como la programación lineal (Ahuja et al., 1993).
Descripción del problema
La problemática tratada en este y los próximos artículos se basa en la necesidad que presenta una empresa manufacturera para decidir la localización de una bodega desde la cual sea posible distribuir su producto a 53 centros de consumo (en adelante se numerarán consecutivamente de 1 a 53), cada uno de los cuales tiene una demanda periódica constante,
4 como se ilustra en la
Tabla 1.
La empresa cuenta con máximo seis vehículos con capacidad constante y homogénea de 5.500 unidades, con los cuales debe entregar en cada periodo la totalidad de productos que se demandan (cada vehículo realiza un recorrido por periodo). El punto de partida de los vehículos es uno de tres centros de consumo que por sus características resultan opcionados para convertirse en bodegas de distribución (9, 28 y 49). La demanda del centro de consumo que se convierte en bodega se satisface in situ, por lo que no requiere desplazamiento ni consumo de la capacidad de los vehículos. La compañía realiza la distribución durante las 24 horas del día y se considera que el tiempo de entrega es despreciable.
La decisión de la empresa consiste en establecer el centro de consumo desde el cual operar la bodega y determinar las rutas de cada uno de los vehículos minimizando de la distancia total a recorrer para satisfacer la demanda de los 53 municipios de la zona. Con el propósito de establecer responsabilidades, ha definido que cada uno de los vehículos encargados de la distribución debe atender un número determinado de municipios y encargarse de satisfacer a cabalidad sus demandas; por esto se entiende que los centros de consumo han de subdividirse en seis conjuntos, de manera que cada vehículo atienda sólo un conjunto y cada conjunto sea atendido por un solo vehículo.
Para el caso práctico del presente y los subsiguientes artículos se ilustrará la zona de influencia de la empresa con un grafo, en el cual los nodos representan los centros de consumo y los arcos las rutas directas existentes entre pares de centros (para el lector interesado se presenta la longitud de los arcos en el
apéndice: “Matriz de distancias entre centros de consumo”, tabla en la cual se resaltan las distancias entre los arcos conectados de manera directa). El grafo de la
Figura 2 ilustra la zona de influencia de la empresa y la ubicación geográfica de los centros de consumo, además se resaltan las tres posibles ubicaciones de la bodega de distribución.
Formulación del problema
Teniendo en cuenta la descripción del problema realizada anteriormente, es posible determinar que el problema planteado es un problema clásico de localización de una sola instalación (Schroeder, 1996) teniendo en cuenta un solo criterio de tipo tangible (Guerrero y Osorio, 2003) que puede ser denominado: “minimización de la distancia total a recorrer para la satisfacción de la demanda”
5. Sabiendo que debido a criterios intangibles (Ballou, 1999) el universo de posibilidades para la localización de la bodega de la empresa queda reducida a tres posibilidades (centros de consumo 9, 28 y 49), el problema puede ser solucionado como tres subproblemas independientes de ruteo con múltiples vehículos, lo que Thomson y Orlin (1989) llaman multi-vehicle routing and scheduling, o lo que se ha descrito en este artículo como ruteo de vehículos con capacidad limitada CVRP (Olivera, 2004; García, 2000). La propuesta final de localización se ha de realizar teniendo en cuenta el mínimo costo de la ruta para cada una de las tres posibles localizaciones. Para este caso específico, y con base en lo dicho por Hermosilla y Barán (s/f), se asume que el costo de la ruta está dado por la longitud total de la misma, y se supone velocidad constante y unitaria para los vehículos.
Es importante aceptar que un problema similar al planteado se presentó en el concurso Whizzkids '96 (Applegateet al., 2001) y fue resuelto por Jan Karel Lenstra y Emile Aarts et al. (Hurkens, 1997) mediante la utilización de Recocido Simulado (Simulated Anealing) y que el mismo problema ha sido abordado por otros autores como Thomson y Orlin (1989) y Machado et al., (2003, a; 2003, b), entre otros.
Formulación matemática general
Teniendo en cuenta que el problema se abordará como tres subproblemas de ruteo de vehículos, uno para cada posible localización de la bodega, en cada uno de los cuales se encontrará la menor distancia total a recorrer para atender la demanda de la empresa, el problema global puede ser definido como la minimización del mínimo de las distancias totales a recorrer para satisfacer la demanda de la zona de influencia de la empresa, partiendo desde cada uno de los tres centros de consumo opcionados (expresión 1).
Donde,
DTi : Distancia total recorrida para satisfacer la demanda al localizar la bodega en el centro de consumo i (i= 9,28,49).
Formulación matemática de los subproblemas: VRP
Dado un número máximo de seis (6) vehículos con una capacidad homogénea determinada u=5500, que tienen como centro de operaciones único la bodega en el nodo 0 (centros de consumo 9, 28 y 49), y deben satisfacer a una cantidad de 52 clientes (centros de consumo), que se representan por j= 1,2,…,52, cada uno de los cuales tiene una demanda conocida dj (véase
Tabla 1), es posible realizar la siguiente formulación matemática:
Índices
Los índices del modelo son:
i = nodo de partida i (1,2,…,52)
j = nodo de llegada j (1,2,…,52)
k = vehículo k (1,2,…, K)
Variables
Las variables que se definen en el modelo son:
6
K = Número de recursos (vehículos) a utilizar.
Parámetros
Los parámetros del problema son:
cij= Costo de transporte del nodo i al nodo j
di= Demanda en el nodo j
u= Capacidad del recurso k
n= Cantidad de clientes
Modelo matemático
El modelo matemático que representa cada uno de los tres subproblemas de ruteo se puede plantear según los aportes de Ahuja et al. (1993) y Olivera (2004) como sigue:
7
Sujeto A:
El conjunto A se define como: A={(i,j) : yij=1}.
La restricción (3) se encarga de hacer obligatoria la asignación de un vehículo a la ruta (i,j), si esta es recorrida, y no asignarlo si la ruta no se va a recorrer, esta restricción contiene la variable de decisión xkij que indica sí si (xkij=1) o no (xkij=0) se utiliza el vehículo k en el arco (i,j).
La variable yij presente en las restricciones (4) y (5) indica la activación del arco (i,j), lo que determina un recorrido entre los nodos i,j, además se asegura que todo cliente es un nodo intermedio de alguna ruta. Los grupos de restricciones (6) y (7) indican que k es la cantidad de vehículos utilizados en la solución y que todos los que parten del depósito deben regresar al mismo. La restricción (8) observa que cada vehículo no sobrepase su capacidad. La restricción (9) vigila que la solución no contenga ciclos usando los nodos 1,2,…n. De otra manera los arcos de A contendrían algún ciclo pasando a través de un conjunto de nodos Q y la solución violaría la restricción, porque el lado izquierdo de la restricción sería al menos |Q|. La restricción (10) limita el número máximo de vehículos a utilizar hasta una cantidad máxima. Las restricciones (10) y (11) indican que tanto la variable xkij como la variable yij son binarias.
Consideraciones finales
Una vez definida la formulación matemática con la que se describe el problema al que se enfrenta el presente artículo y teniendo en cuenta que los parámetros dj, u y n son conocidos, sólo resta determinar un inputfundamental del CVRP, el costo de cada ruta (cij), que para este caso será la distancia de cada ruta.
Según lo expresado por Olivera (2004), puede suponerse que el grafo es completo, pues entre todo par de lugares de una red de transporte razonable, debería existir algún camino, concepto que necesariamente debe ser usado en el desarrollo del presente artículo; así, aunque existan nodos que sólo tienen una vía de acceso (véase por ejemplo nodo 50 en la
Figura 2), es necesario suponer que entre cada par de nodos existe un arco que los une, por lo anterior los autores decidieron construir arcos ficticios que representen la conexión existente entre todo par de nodos del grafo, a través de la ruta más corta entre ellos.
La construcción de los arcos ficticios anteriormente mencionados supone la solución de problemas de ruta más corta (Shortest Path Problems), específicamente lo que Ahuja et al. (1993) llaman All-pair shortest path problemy que pretende encontrarla entre todo par de nodos de un grafo, problema que puede ser solucionado según los mismos autores mediante la aplicación de repeated shortest path algorithm, que consiste en la aplicación de un algoritmo para encontrar rutas más cortas para un solo origen n veces (donde n es el número de nodos), o bien,all-pairs lebel-correcting algorithm, que se basa en la aplicación del algoritmo de Floyd-Warshall. Los dos métodos mencionados pretenden alcanzar la condición de optimalidad representada por la expresión 13, donde d[i,j] representa la distancia más corta entre los nodos i, j.
Para crear la matriz de distancias entre todo par de centros de distribución del apéndice Matriz de distancias entre centros de consumo se decidió calcular la ruta más corta para cada municipio respecto de los demás (repeated shortest path algorithm) mediante la aplicación del algoritmo de Dijkstra (Taha, 1997).
Una vez hecho el recorrido bibliográfico pertinente, descrito y formulado el problema y recopilada la información necesaria para enfrentar el problema, los autores utilizaron diferentes técnicas aplicadas a encontrar la asignación que reduzca al máximo la distancia total recorrida por los vehículos encargados de satisfacer la demanda de los 53 centros de consumo, y con base en los resultados decidir la mejor localización para la empresa. Los resultados numéricos de la aplicación de cada una de las técnicas, al igual que la descripción de las mismas, se encontrarán en los dos artículos siguientes.
Conclusiones
El de ruteo de vehículos es la generalización del problema del agente viajero y encierra una familia de que debe ser resuelta según las características específicas de cada caso.
La formulación matemática del ruteo de vehículos debe contener familias de restricciones que imposibiliten la construcción de ciclos o subtoures.
En los siguientes artículos los autores expondrán diferentes metodologías de solución para el caso de estudio ilustrado.
Fuente:
Pagina de Enlace del autor del texto.
