Cálculo de rutas de transporte parte II

Continuando con mi anterior artículo, he mejorado el algoritmo de búsqueda de caminos, de tal manera que ahora permite la búsqueda de un sinfín de posibilidades con tiempos extremadamente pequeños. En la versión anterior me di cuenta de que había un problema con el diseño del algoritmo y era referente a que a la hora de buscar los nodos adyacentes, éstos tienen que estar ordenados por el número de conexiones entrantes que tienen. De ésta manera podemos calcular cosas tan complejas como éstas:

A simple vista parece ser bastante difícil el obtener el número de caminos disponibles pero al final acaba siendo un simple recorrido de nodos:

Como podéis ver en la última imagen, hay 31 rutas disponibles. Además, en ésta última versión, ya está resuelto el problema de multi-orígenes y multi-destinos de tal manera que el algoritmo ya es capaz de recorrerlos todos con un coste cuadrático. Hay que mejorar un poco el coste pero estamos hablando de hacer el cálculo de unas 30 rutas en unos 16 mili segundos.

Si nos fijamos en la siguiente imagen, podréis ver la resolución con múltiples orígenes y múltiples destinos:

Si os fijáis en la imagen también queda marcado el camino seleccionado en la grid, de ésta manera visualmente podemos reconocer la ruta seleccionada y comprobar que los cálculos estén correctamente realizados.

El cálculo ahora es bastante diferente de como se hacía en el artículo anterior. Se me ocurrió la idea de realizar la búsqueda a través de la tabla de adyacentes sin tener que hacer antes un barrido. De ésta manera realizando una serie de operaciones que ahora detallaré, tenemos resuelto el problema del cálculo de rutas de transporte.

Con el siguiente código realizamos el recorrido total de la lista de adyacentes:

fila := 1;
filas := 0;
columna := 1;
for i := 0 to length(AdjacentList) - 1 do
begin
   if AdjacentList[i].isSource then
   begin
       grid[columna, fila] := Inttostr(AdjacentList[i].source);
       grid[columna + 1, fila] := Inttostr(AdjacentList[i].destiny);
       AdjacentList[i].visited := true;
       filas := filas + 1;
       fila := fila + 1;
   end;
end;

bVisited := false;
while not bVisited do
begin
   sum := 0;
   for i := 1 to filas do
   begin
       columna := getLastColumn(i);
       SetLength(Connector, 0);
       GetList(Connector, AdjacentList, StrToInt(grid[columna - 1, i]));
       if Length(Connector) <> 0 then
           grid[columna, i] := IntToStr(Connector[0].destiny);
           if Length(Connector) > 1 then
           begin
               newRows := CloneRow(i, Connector);
               sum := sum + newRows;
           end;
   end;
   filas := filas + sum;
   bVisited := AllRowsFinished(filas, DestinoList);
end;

• ¿Como funciona?

Primero buscamos los orígenes de la lista de adyacentes y los situamos en la grid, por ejemplo:

1 2
1 3

Luego recorremos ésta lista buscando los adyacentes de los últimos nodos, 2 y 3. Por lo tanto encontraremos que el 2 estará conectado con el 4 y el 5 y el 3 solo con el 6. En el momento que tenemos que añadir el valor 4 detrás del 2, si vemos que hay más conexiones, realizamos un clonado de la línea que estamos tratando y insertamos el siguiente valor en la línea clonada:

1 2 4
1 3
1 2 5 (clonado)

Continuamos con la siguiente fila:

1 2 4
1 3 6
1 2 5

Ahora, tenemos que volver a empezar y volver a añadir las conexiones de los nodos posteriores e ir clonando las diferentes filas hasta llegar al final:

1 2 4 8
1 3 6 7 8
1 2 5 8
1 3 6 8

De ésta manera tan fácil conseguimos construir la lista de rutas de transporte, siempre teniendo en cuenta los diferentes orígenes y destinos que nos podemos encontrar.

Podéis descargar la última versión de la aplicación con los ejemplos aquí:

• ThundaxBoxManager v2.4.0 build 10.rar (With Data).

PD : Para la ejecución del algoritmo correcto, hay que ir al menú Citect -> Calc Routes 2 una vez el diagrama está abierto.