[0:00]Vamos a estudiar el algoritmo de Clark Wright o método de los ahorros para el problema de ruteo de vehículos. En el problema de ruteo de vehículos o VRP, el contexto es el siguiente. Se deben entregar ciertas cantidades de productos a clientes en diversos puntos, desde un centro de distribución. Tenemos un cierto número de vehículos que tienen una capacidad limitada en cuanto al volumen de producto que pueden transportar. Cada vehículo que se utilice debe salir del centro de distribución, recorrer una ruta de reparto y regresar al centro de distribución. En este problema se desea determinar la asignación de los vehículos a las rutas para hacer las entregas a diferentes clientes con el objetivo de minimizar el costo. El costo es un término genérico que realmente puede significar costo monetario, pero también puede ser el tiempo de recorrido o puede ser la distancia recorrida. O puede ser el volumen de emisiones contaminantes y se trata de minimizar alguna de estas cantidades. En el problema se tienen restricciones de tiempo de recorrido, por ejemplo, puede ser que haya un día hábil donde en 8 horas o 10 horas se tienen que hacer todas las entregas. O bien, puede ser que los conductores tengan un tiempo máximo de trabajo detrás del volante. Puede ser que tengamos restricciones también de capacidad de los vehículos, ya sea en peso, en volumen o en ambos y, por supuesto, debe satisfacerse la demanda de los clientes. En algunas situaciones también se tienen restricciones de tiempo conocidas como ventanas de tiempo. Es decir, cuando en ciertos puntos de entrega, solamente se puede hacer la entrega a ciertas horas del día. En el ejemplo que vamos a ver, no vamos a considerar ventanas de tiempo. En cuanto a los costos, estos pueden ser simétricos o no. Es decir, el costo para ir de un punto A a un punto B, puede ser diferente que el costo de regresar del punto B al punto A. En el ejemplo que vamos a manejar, los costos son simétricos. Esto nos ahorra cierto número de cálculos, los cálculos no son ni más ni menos complejos, ni el algoritmo es más o menos complejo, simplemente es más cómodo hacer los cálculos cuando los costos son simétricos. En este diagrama estamos viendo un ejemplo del contexto de este problema. Estamos viendo que tenemos seis nodos, cinco de los nodos, que son los que aparecen en azul, son los puntos a donde se va a entregar material. El nodo cero es el centro de distribución y están trazados estos arcos que corresponden a las conexiones a las trayectorias entre los diferentes nodos. Por ejemplo, esta sería la ruta que hay del cero al uno. Aquí hay una conexión del nodo uno al nodo cuatro, hay una conexión del nodo dos al nodo cinco, y así hemos representado en este dibujo todas las conexiones posibles en esta red. Aquí estamos mostrando un ejemplo de una ruta que cubriría todos los nodos, es decir, partimos del centro de distribución, del depot. Partimos del cero y se está haciendo un recorrido del tres, al cinco, al uno, al dos, al cuatro y de regreso al nodo cero. Como en nuestro ejemplo, los costos son simétricos, el recorrido tiene el mismo costo, si lo hacemos en sentido contrario, es decir, si partiéramos del cero al cuatro, luego al dos, al uno, al cinco, al tres y de regreso al cero. Este ejemplo es un caso en el cual una sola ruta, que sería equivalente a decir que un solo camión, puede hacer todas las entregas, cumpliendo con las restricciones de tiempo y de volumen transportado. En este segundo ejemplo, estamos viendo el caso donde se requirieran dos rutas para hacer las entregas en los cinco nodos. Estamos poniendo una ruta que va del cero, al dos, al cuatro, al cero y una ruta que va del cero, al tres, al cinco, al uno. Pudiera ser necesario utilizar dos camiones cuando los volúmenes de entrega exceden la capacidad de un camión, o cuando el tiempo necesario para hacer el recorrido excede el tiempo límite con el que se cuenta en el turno o en el día. Y en este caso, serían necesarias dos rutas de reparto para poder cumplir con esa restricción de tiempo. En esta situación, la primera pregunta que nos hacemos es, bueno, cuáles nodos quedan incluidos en cada una de las rutas de reparto. Por qué aquí estamos incluyendo el tres, el cinco y el uno, y en la otra ruta estamos incluyendo el dos y el cuatro. Dado que nuestro problema es un problema de minimización, ya sea de costo, de distancia, de emisiones, de tiempo, lo que nosotros queremos encontrar es cuál es la ruta de reparto que minimiza esa variable que nos interesa. De todas las posibles conexiones que aparecen en nuestra red, estaríamos utilizando aquellas conexiones que nos conducen al mínimo costo total de la operación de las rutas en esta red. Cómo optimizar? Bueno, deseamos encontrar las rutas de menor costo que satisfagan las restricciones de tiempo y volumen y se satisfaga la demanda de los clientes. Para empezar a aplicar el método de los ahorros, nuestro punto de partida es una matriz de costos. Esta matriz representa el costo, o bien, ya sabemos que puede ser distancia, puede ser tiempo que se requieren para viajar entre cada par de nodos. Por ejemplo, para ir del nodo cero al nodo uno, tenemos un costo de 35. Para ir del nodo cero al nodo tres, tendríamos un costo de 47. También tenemos los costos entre los otros nodos de la red, por ejemplo, el costo para ir del nodo uno al nodo dos, sería de 28. Para ir del nodo tres al nodo cuatro, tendríamos un costo de 26. En este ejemplo solamente estamos mostrando la matriz triangular superior, dado que los costos son simétricos y no necesitamos la otra parte de la matriz, dado que es igual el costo para ir, por ejemplo, del nodo uno al nodo cuatro. Que para ir del nodo cuatro al nodo uno, que en este caso, del cuatro al uno, el costo es de 44. Esta matriz tiene que obtenerse por otros medios, es decir, es un insumo, es un dato que necesitamos para proceder con el algoritmo de los ahorros. Y se puede haber obtenido como distancias, si son distancias, podríamos haber obtenido la distancia euclidiana o la distancia Manhattan, o bien si tenemos las coordenadas geográficas de los puntos, podríamos haber calculado las distancias geodésicas. Pero para fin de proceder, supondremos que ya tenemos esta matriz como información de insumo. Veamos a continuación, cuál es la lógica detrás del algoritmo de los ahorros. Estoy mostrando en el diagrama de la izquierda la misma red. Y lo que queremos saber es cuáles pares de nodos nos conviene incluir en una ruta. Por ejemplo, si nos regresamos aquí a este diagrama, podríamos ver que en esta ruta de color morado, hemos incluido los nodos tres, cinco y uno. Ahora bien, cómo sabemos que es conveniente unir el nodo cinco con el uno, cómo sé que es conveniente unir el tres con el cinco, con el dos con el cuatro, por qué no unimos el dos con el tres, o por qué no unimos el cuatro con el cinco? Lo que vamos a hacer en el método de los ahorros es precisamente determinar si es conveniente unir ciertos pares de nodos. Veamos este caso. Estamos viendo aquí la conveniencia de unir los nodos uno y dos en la misma ruta. Lo que nos indica este método es que calculemos los ahorros para cada par de nodos, vamos a calcular un ahorro que tiene el siguiente significado. Tomemos estos nodos, uno y dos, y el nodo de origen. Vamos a calcular el ahorro de la siguiente forma. Si nosotros queremos hacer el recorrido del cero al uno y de regreso y luego del cero al dos y de regreso, voy a calcular un costo. Vamos a calcular cuánto nos ahorraríamos si nos evitamos un regreso y nos vamos directamente entre el uno y el dos.
[9:37]Primero calculemos el costo de ir del cero al uno y regresar. Del cero al uno, me voy a mi tabla de costos, del cero al uno el costo es de 35. Como es simétrico, el regreso cuesta lo mismo, 35. De manera que el costo de ir de cero al uno, al cero, es 35 de ida, más 35 de regreso, el costo es 70. Del cero al dos. Del cero al dos, el costo es 36. Por lo tanto, el costo para ir del cero al dos y regresar es 36 de ida, 36 de regreso, en total 72. Ahora veamos cuánto nos podríamos ahorrar si nos evitamos un regreso y nos vamos directamente entre el uno y el dos. En ese caso, el costo sería del cero al uno, del uno al dos y del dos al cero. Del cero al uno, el costo es 35. Del uno al dos, lo busco en la tabla, del uno al dos, el costo es 28. Y del dos al cero, el costo es 36. De manera que el costo para hacer esta ruta de reparto sería 35 más 28, más 36, total 99. Ahora calculemos la diferencia. Cuál es el ahorro si cambiamos en lugar de hacer los dos recorridos independientes, hacemos un solo recorrido que involucre la conexión del uno al dos? El ahorro sería el siguiente. Si tomamos ida y vuelta, ida y vuelta, el costo sería 70 + 72, el costo es 142. En el esquema inicial de ir y volver, ir y volver, costo total 142. Si tomamos la ruta circular, el costo es 99, por lo tanto la diferencia es de 43. 142 menos 99, el ahorro es de 43. Este ahorro lo asociamos a la conexión del nodo uno con el nodo dos. Es decir, si incluyo el segmento del uno al dos, yo tengo un ahorro de 43. En la tabla, lo estamos mostrando aquí. Vamos a construir una matriz de ahorros, donde tenemos los ahorros que conseguimos, si vamos conectando los diferentes pares de nodos. El ahorro al incluir en una ruta el par de nodos 1-2, es de 43. Veamos otro caso. En este ejemplo, vamos a calcular el ahorro que lograríamos si incorporamos en la misma ruta los nodos tres y cinco. El mecanismo es igual. Voy a calcular primero el costo que tendríamos si hacemos el doble viaje del cero al cinco, del cinco al cero y luego del cero al tres y del tres al cero. El costo 0-5-0, que es este, sería del cero al cinco, del cero al cinco, el costo es 27. Más 27 de regreso, del cinco al cero, tenemos 27 más 27, 54. El costo del cero al tres y de tres a cero, lo buscamos aquí. Del cero al tres es 47, del tres al cero, otra vez 47. La suma nos da 94. La suma total serían 148, el costo de ir independientemente del cero al tres y del cero al cinco, la suma 148. Ahora bien, si tomamos la decisión de incluir el segmento 5-3, entonces la ruta sería 0-5-3-0. Y el costo sería el siguiente. De cero al cinco, del cero al cinco, son 27, del cinco al tres, son 23, y del tres al cero, son 47. Costo total 97. Para calcular el ahorro, sacamos la suma de los dos viajes independientes, que sería 54 + 94, que son 148, menos 97, que es lo que nos cuesta el recorrido circular. El ahorro es de 51. Entonces, en nuestra matriz de ahorros, añadiríamos para la pareja 5-3, estaríamos asignando un ahorro de 51. Aquí está para la pareja 3-5, el costo es 51. De esa manera es que se llena la matriz de ahorros y ya tenemos entonces, el ahorro correspondiente a la unión de cada uno de los pares de nodos que podemos formar en la red. Para trabajar con este ejemplo, digamos que la capacidad del camión es de 100 unidades. Estamos aplicando solamente una restricción que pudiera ser de volumen o de peso, pero también pudiéramos tener ambas. De nueva cuenta, la complejidad del problema no crece, solamente tengo que estar monitoreando las dos restricciones. También estamos agregando la información de las demandas de los clientes. Al cliente uno, en el nodo uno, tenemos que entregar 37 unidades, en el nodo dos, 35, y así sucesivamente hasta el nodo cinco, tengo que entregar 32 unidades. Recordemos que es importante considerar que la capacidad del camión es de 100 unidades. Para continuar con la aplicación del algoritmo, tomamos nuestra matriz de ahorros que ya habíamos hecho previamente. Y vamos a construir una tabla donde ordenemos en forma descendente los ahorros y los pares de nodos correspondientes. Si busco en la tabla, el mayor ahorro es 68 y ocurre entre el par 2-4. Aquí pongo en el par 2-4 el ahorro es 68. El siguiente valor en ahorros es el 66, que ocurre si incluimos en un recorrido los nodos tres y cuatro. Tres y cuatro, un ahorro de 66. El siguiente es de 58 que ocurre con el par 1-3. 1-3, 58. El 57 ocurre con el dos y con el tres, es el 57. El 51 con el 3-5 y así sucesivamente hasta llegar al más pequeño que es 31, que ocurre cuando incorporamos en una ruta el nodo uno y el nodo cinco. A continuación, vamos a proceder a construir las rutas de reparto, partiendo de aquellos pares de nodos que representan los mayores ahorros. Este sería nuestro primer paso en la construcción de la ruta. Buscamos el mayor ahorro que fue 68, que ocurre en el par 2-4. Una vez que he identificado cuál es el par que representa el mayor ahorro, tengo que verificar la factibilidad. Recuerden que estamos haciendo las entregas con camiones que tienen una capacidad de 100. Necesitamos saber si podemos entregar al nodo dos y al nodo cuatro con un solo camión para 100 unidades. Vemos la demanda y vemos que el nodo dos tiene una demanda de 35, el nodo cuatro, una demanda de 25, necesitamos 60 unidades, por lo tanto, sí caben en este primer camión. Por lo tanto, puedo incluir esta ruta inicial. Es del cero, al dos, al cuatro, al cero. Porque estamos uniendo el dos con el cuatro en la misma ruta. El ahorro es 68 y la capacidad utilizada es de 60. Para continuar con el procedimiento, podemos buscar enseguida dos caminos. Un camino, que se conoce como el método secuencial, es cuando hago lo siguiente. Si yo ya tengo incluidos los nodos dos y cuatro en la ruta, los nodos dos y cuatro los podríamos conectar con el uno, con el cinco, con el tres, con el cuatro, pero queremos ver en la tabla donde tenemos los ahorros ordenados en forma descendente, queremos ver cuál es el siguiente par de nodos que comparte un nodo con el segmento que ya tenemos en la ruta.
[18:20]Por ejemplo, si nos vamos al siguiente par de nodos que es el tres y el cuatro, el tres y el cuatro tiene una conexión con lo que ya tengo construido de la red aquí a través del cuatro. Quiere decir que a continuación, voy a agregar el nodo tres, puesto que se conecta directamente a nuestra red a través del cuatro. Pero tenemos que verificar que no exceda la capacidad del camión. Vamos a ver el nodo tres y tiene una demanda de 30. Habíamos utilizado ya 60 unidades de la capacidad. 60 más 30, tengo 90 unidades y todavía no llego a la capacidad del camión. El procedimiento que seguimos fue el siguiente, lo repito ahora. Primero construimos el segmento 2-4 y lo incorporamos a esta ruta de reparto. Me voy al siguiente par de nodos y veo que lo puedo conectar con la red anterior porque el par 3-4 tienen en común el cuatro. Por lo tanto, esto me indica que voy a ampliar la red 0-2-4-0 a 0-2-4-3-0. También podríamos seguir un procedimiento en paralelo donde vaya construyendo las rutas de reparto, aunque no tenga nodos en común. Por ejemplo, si el siguiente par de nodos incluyera al cinco, no sé, por ejemplo, 5-1 y pues haríamos otra ruta, del 0 al 5 al 1 y ya tendría dos rutas que voy construyendo en paralelo.
[20:06]La ruta 0-2-4 y la ruta 0-5-1, si es que el siguiente ahorro más grande estuviera entre el cinco y el uno. Sí puedo hacer esta red. Este procedimiento es el procedimiento en paralelo. El procedimiento secuencial, siempre me obliga a buscar un nodo que sea adyacente a la ruta que ya tengo construida. Es decir, que lo podamos añadir a la ruta anterior. Esto nos lleva a buscar pares de nodos que tengan un nodo en común con lo que ya tenemos construido. Los dos algoritmos funcionan de la misma manera y, eh, realmente no hay ninguna garantía de que si utilizo el secuencial o utilizo el paralelo vaya a obtener una mejor o peor solución. Bien, pues ya tenemos entonces, nuestra ruta 0-2-4 y el siguiente par fue el par 3-4, con un ahorro de 66. Vamos a incorporarlo a la ruta. Una vez que lo hemos añadido, nuestra ruta se convierte en 0-2-4-3-0. Continuo haciendo el recorrido en la tabla descendente de ahorros, y el siguiente par que encontramos es el par 1-3, con un ahorro de 58. 1-3, quiere decir que podría añadir este nodo uno a la red anterior porque tiene en común el nodo tres. Este 1-3, tiene un ahorro de 58 y sería agregarlo aquí junto al tres, porque es al que está aquí pegado, 1-3, y me llevaría a la ruta 0-2-4-3-1-0. Solo que antes de incorporar este nodo adicional, tengo que verificar la factibilidad. Recuerden, cuando ya llevo incluidos los nodos dos, cuatro y tres, la capacidad utilizada del camión ya es de 35 y 25, 60 y 30, 90.
[22:20]Me queda una capacidad libre de 10 unidades. Si quiero incorporar el nodo uno, como lo indica aquí mi tabla, el nodo uno tiene una demanda de 37. Entonces, no cabe. No puedo agregar el nodo uno a la red que tengo aquí en verde. Por lo tanto, continúo el recorrido en orden descendente. El siguiente par de nodos con un ahorro interesante es el par 2-3, pero el par 2-3 ya está incluido en la red, ya no me sirve. Enseguida viene el par 3-5, el par 3-5 lo podría agregar aquí junto al tres, y la ruta se convertiría en 0-2-4-3-5-0.
[23:06]Pero al verificar la factibilidad, nos damos cuenta nuevamente de que tenemos solamente una capacidad libre de 10, y la demanda del cinco es de 32. Entonces, no cabe. Enseguida, vemos, estábamos en el 3-5, vamos a ver el 4-5. Del cuatro al cinco, podríamos extender la ruta del cuatro al cinco, para incluir 0-2-4-5-3-0, pero el cuatro ya forma parte de la ruta verde. Y además, el cinco no cabe, porque tiene la siguiente par que aparece es el par 1-2, en el par 1-2, sí lo podría incorporar aquí, si es de acuerdo a la estructura de la red, sí podría agregar aquí el uno, por qué? Porque desconectaría este verde que va al depot.
[24:43]Y hago el recorrido 0-3-4-2-1-0. Sí podría, mientras el nodo adicional, como era en este caso, que es vecino el dos del uno, sí lo podría pegar aquí. El problema es que no cabe, porque la demanda del uno es 37 y en este camión solo tengo capacidad de 10. El siguiente sería el par 2-5. Sí podría incorporar el cinco, porque sería igual que con el uno, es decir, yo puedo desconectar el dos del cero, conecto el dos con el cinco, y el cinco con el cero y sigo manteniendo mi circuito cerrado, sigo manteniendo mi circuito cerrado. El problema es que el cinco, la carga del cinco, no cabe. Enseguida, 1-4, el cuatro está en medio de la red, no está conectado con el depot. Entonces, no puedo añadir el nodo uno en uno de los extremos del cuatro porque ya ambos están ocupados. Finalmente me queda el uno y el cinco. El uno y el cinco no tienen ningún nodo en común con la red anterior, por lo tanto, esto implicaría que sí los puedo utilizar abriendo una nueva ruta.
[26:08]Siempre que ocurra que un el siguiente par, cuando voy siguiendo la secuencia en orden descendente, el siguiente par queda independiente de los anteriores, lo puedo incorporar como una nueva ruta.
[26:24]En este caso, el uno y el cinco, no tiene nada en común con estos, abriría una nueva ruta 0-1-5-0, y nos quedaría de la siguiente forma. Aquí estamos añadiendo la ruta 0-1-5-0. El uno y el cinco acumulan una demanda de 69, por lo tanto es factible. Recuerden que antes de unir, en efecto, los nodos a las rutas, tengo que verificar si al agregarlos la capacidad del camión es suficiente. Puede ser que si tuviéramos un nodo que tiene una demanda de 90, pues probablemente no vaya a quedar unido con ninguno de los demás, porque el camión va lleno o casi lleno hacia ese destino, entonces tendría que hacer un viaje de ida y vuelta a ese destino solamente. Finalmente nos queda como resultado, que tengo esta ruta verde que va 0-2-4-3, la ruta negra que puse 0-1-5-0. No tengo aquí la matriz de costos, pero lo que procede a continuación es calcular cuál es la suma de los costos de la ruta verde, más la suma de los costos de la ruta negra, y ese sería el costo total de la operación de esta red que hemos construido. Resumiendo, al final los costos nos quedan de la siguiente manera. En la ruta 0-1-5-0, el costo sería del 0 al 1, 35, del 1 al 5, 31, del 5 al 0, 27. Costo total 93. De la ruta verde, sería del 0 al 2, 36, del 2 al 4, 13, del 4 al 3, 26, y del 3 al 0, 47. Costo total 122. La suma, 215. El costo total de estos dos recorridos sería 215.
