Monday, 26 October 2009

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

3 comments:

  1. Muy buena solución para buscar los caminos! Por cierto, no vi que trataras el caso de que existan ciclos en el grafo, aunque puede que no sea el caso. Una forma rápida de hallar el número caminos de longitud n en un grafo es con la matriz de adyacencia, eso te podría ayudar para verificar el número de caminos obtenidos. Saludos y estamos en contacto

    ReplyDelete
  2. Grácias por tu comentario. En éste algoritmo no se tienen en cuenta los ciclos ya que intento encontrar la solución a las diferentas rutas que hay entre un equipo a otro. Para entendernos necesito llevar un producto de un equipo a otro equipo final y se que no habrán ciclos. Te animo a que pruebes la aplicación y me comentes lo que te ha parecido.

    ReplyDelete
  3. Claro que sí, probaré la aplicación. estamos en contacto... voy a leer la próxima entrada.. jeje ya tienes 2 nuevas...¡vaya que escribes rápido! jeje.. ciao!

    ReplyDelete