2.6.- Mejora de la solución factible: método Stepping-Stone.

Es una técnica que garantiza una solución óptima.

Lo normal es partir de una matriz de asignación obtenida por algunas de las anteriores técnicas.

Esta técnica está basada en un criterio de ahorro de costes al intercambiar unidades de carga entre diferentes rutas, siempre y cuando este intercambio de cargas no afecte a la satisfacción de las capacidades de los centros de origen y destino.

¿Cómo interpretamos los datos? Cuando se obtienen las rutas, después de aplicar el método, para realizar el análisis de la evaluación de trayectorias tendremos en cuenta lo siguiente:

Si la evaluación es negativa, podemos ahorrar dinero intercambiando unidades entre las casillas del camino de evaluación negativa.
Si la evaluación es positiva, al intercambiar unidades entre las casillas del camino considerado, sufrimos un incremento de costes. Para ahorrar no interesan caminos con evaluaciones positivas.
Si la evaluación es nula, al intercambiar unidades entre casillas del camino no obtenemos ni ahorro ni incremento de costes. Si podríamos intentarlo pero obtendríamos una “solución alternativa”.

Veamos con un ejemplo cómo se aplica este método.

Ejercicio resuelto

Partimos de una solución inicial básica para desarrollar el método de Stepping-Stone, para ello contamos con la siguiente matriz previamente construida con el método Vogel. La tabla de la izquierda muestra los costes de transporte para cada ruta, y la tabla de la derecha la asignación de rutas que minimiza el coste de transporte.

Costes de transporte por cada ruta
	D₁	D₂	D₃	OT
O_A	1	3	6	30
O_B	2	3	4	40
O_C	5	2	5	10
DT	20	30	30

Asignación de rutas que minimiza el coste de transporte
	D₁	D₂	D₃	OT
O_A	20	10		30
O_B		10	30	40
O_C		10		10
DT	20	30	30

El coste total de transporte para esas rutas es: 220 um.

Calcula si se puede obtener una solución óptima de transporte aplicando el método Stepping-Stone.

Retroalimentación

Para aplicarlo tenemos que dibujar los caminos cerrados posibles partiendo de todas las celdas sin asignación atendiendo a las siguientes reglas:

Avanzar hasta llegar a una celda con asignación y girar en ángulo recto hasta alcanzar otra celda llena. Así de forma sucesiva hasta cerrar el camino en la celda vacía del inicio. Es importante que los caminos estén cerrados.
Es posible saltar las celdas vacías o llenas necesarias.
Todos los recorridos estarán compuestos por un número par de celdas.
Se tiene que cumplir la siguiente premisa: el número de filas más el número de columnas, restándole uno tiene que ser mayor que el número de asignaciones. Si no ocurre esto se dice que la matriz es degenerada. Para solucionar esto se puede añadir un coste cero a alguna celda vacía.

En el ejemplo se puede encontrar cuatro celdas vacías. Tomamos como partida la celda O_AD₃ y aplicamos las reglas anteriores, por lo que sólo podemos avanzar siguiendo este camino a la izquierda:

Tabla asignación 1
	D₁	D₂	D₃	OT
O_A	20	10 ↓	← •	30
O_B		10 →	↑ 30	40
O_C		10		10
DT	20	30	30

Camino: O_AD₃-O_AD₂-O_BD₂-O_BD₃

También existe la posibilidad de obtener el mismo resultado haciendo el recorrido en sentido contrario. En dicho camino observamos que no se vuelve a apuntar la celda de inicio al final del nuevo recorrido.

Evaluamos la trayectoria y formarán parte de un recorrido las celdas donde se haya hecho una parada para girar en ángulo recto hacia otra celda llena.

La evaluación queda de la siguiente forma:

Costes O_AD₃: 6-3+3-4=2

Observa que los signos son: más menos más menos. Es decir, el procedimiento de evaluación de una trayectoria consiste en anotar los costes de las celdas que la forman alternando los signos, empezando por positivo para la primera celda. Posteriormente se suman los costes.

A continuación se selecciona otra celda vacía: O_BD₁. El camino posible es el siguiente:

Tabla asignación 2
	D₁	D₂	D₃	OT
O_A	20↓	← 10		30
O_B	• →	↑ 10	30	40
O_C		10		10
DT	20	30	30

Camino: O_BD₁-O_BD₂-O_AD₂-O_AD₁.

La evaluación del coste es: 2-3+3-1=1.

Volvemos a seleccionar otra celda vacía y en la que sea posible marcar un ángulo recto cumpliendo con las anteriores reglas. En este caso sería la celda O_CD₁.

Tabla asignación 3
	D₁	D₂	D₃	OT
O_A	20↓	← 10		30
O_B	↓	↑10	30	40
O_C	• →	↑10		10
DT	20	30	30

Camino: O_CD₁-O_CD₂-O_AD₂-O_AD₁.

Coste: 5-2+3-1=5.

Y por ultimo, la única celda que nos queda vacía es O_CD₃.

Tabla asignación 4
	D₁	D₂	D₃	OT
O_A	20	10		30
O_B		10 ↓	← 30	40
O_C		10 →	↑•	10
DT	20	30	30

Camino: O_CD₃-O_BD₃-O_BD₂-O_CD₂.

Coste: 5-4+3-2=2.

Como resumen, los recorridos con sus respectivas evaluaciones son:

Camino O_AD₃; evaluación igual a 2.
Camino O_BD₁; evaluación igual a 1.
Camino O_CD₁; evaluación igual a 5.
Camino O_CD₃; evaluación igual a 2.

En el ejemplo vemos que todas las evaluaciones son positivas, por tanto las asignaciones de la matriz corresponden a una solución óptima donde el coste de transporte es mínimo, es decir con el método de Vogel ya obtuvimos una solución óptima de transporte.

« Anterior | Siguiente »