Cálculo de rutas de transporte parte I

Después de unos días muy ajetreados y con mucho trabajo (y que no falte) he podido medio acabar la primera aplicación profesional sobre mi framework. Ésta se trata sobre el cálculo de rutas. He utilizado diversos tipos de algoritmos para su recorrido y búsqueda de diferentes caminos para obtener la ruta de un origen a un destino pasando por una serie de nodos. Luego vincularé la búsqueda de éstas rutas con mi anterior aplicación Thundax Genies Scanner y así poder crear mapas mentales de aplicaciones Scada para la búsqueda de caminos automáticos. En que consiste ésta idea?

Como podéis ver en la siguiente imagen:

Disponemos de un origen marcado en verde y un destino marcado en fucsia. Con mi framework he generado el diagrama y aplicado diversas propiedades a las diferentes cajas y conectores. El problema que se presenta, es el de calcular las diferentes rutas que hay de un punto a otro y guardarlas en algún sitio para poder utilizar éstos datos y evitar sobretodo el cálculo manualmente. Poco a poco, os iré explicando la utilizad de ésto y el propósito de su cálculo.

Por lo tanto, si nos fijamos en la imagen existen 2 rutas para ir del origen (1) al destino (19):

Así, calcularíamos:

RUTA1: 1-4-8-11-19 RUTA2: 1-5-9-11-19

• ¿Dónde está la complicación aquí?

Parece fácil, no?. Pues no lo es. Es un problema bastante complicado a la que empiezan a haber cruzamientos entre nodos. Si aparecen diversas conexiones entre sí, el numero de combinaciones empieza a crecer exponencialmente.

Si observamos mi aplicación, veremos como se calculan las rutas automáticamente:

Ahora un ejemplo más real:

Como podéis comprobar, son los mismos nodos, pero ahora tenemos 7 rutas disponibles!.

El cálculo de sus rutas es el siguiente:

Aún estoy acabando de perfilar el algoritmo y calculando sus diferentes costes para una mejora en su rendimiento. Dentro de poco tendré disponible la versión para búsqueda de rutas con múltiples orígenes y múltiples destinos. Y poder realizar la búsqueda de rutas de diagramas como el siguiente:

Si os fijáis, incluso he creado un tipo de enlace nuevo con la imagen de una cadena. Éste enlace consiste en un enlace de bloqueo donde los nodos están fuertemente vinculados y también se tienen que tener en cuenta a la hora de escribir la ruta de transporte. Ésto significa que si queremos pasar por un nodo de éstos, el otro debe aparecer bloqueado (en términos de fluidos seria cerrar uno de los caminos).

• ¿Cómo funciona el algoritmo?

El algoritmo que he creado es del tipo backtracking recorriendo los diferentes nodos y marcando las rutas visitadas. Lo que hago es crear una lista de adyacentes marcando la cantidad de conexiones que tiene cada nodo.

Primero calculo los orígenes y destinos en función del color de la caja:

for i := 0 to boxlist.count - 1 do
begin
if boxlist.items[i].properties.fillColor = clLime then
    SetArrayValue(OrigenList, StrToInt(boxlist.items[i].properties.getText));
if boxlist.items[i].properties.fillColor = clFuchsia then
    SetArrayValue(DestinoList, StrToInt(boxlist.items[i].properties.getText));
end;

Luego, nos centramos en calcular la lista de adyacentes en función del tipo de conexión. Además existe una lista de bloqueos en función del tipo de conector utilizado:

for i := 0 to connectorList.count - 1 do
begin
  conn := connectorList.items[i];
  pos1 := StrToInt(conn.SourceBox.properties.getText);
  pos2 := StrToInt(conn.TargetBox.properties.getText);
  if not conn.Line.ClassNameIs('TAbstractDottedDoubleLinkedArrowLine') and
      not conn.Line.ClassNameIs('TAbstractSimpleDoubleLinkedArrowLine') then
      SetAdjacentValue(AdjacentList, pos1, pos2)
  else
  begin
      SetAdjacentValue(InterlockList, pos1, pos2);
      SetAdjacentValue(InterlockList, pos2, pos1);
  end;
end;

El siguiente paso es marcar los diferentes nodos con su peso marcado por la cantidad de nodos conectados a un nodo.

for i := 0 to length(AdjacentList)-1 do
begin
  AdjacentList[i].weight := getWeight(AdjacentList, AdjacentList[i].source);
  if AdjacentList[i].weight = 1 then
      AdjacentList[i].unique := true;
end;

Esto nos permite crear un diagrama con la siguiente información:

function TfrmMain.ExamineNodes(firstNode: integer; lastNode: integer; AdjacentList: TAdjacentArray): string;
var
nodeVisited: integer;
res: TArrayInteger;
i: integer;
father: integer;
begin
nodeVisited := firstNode;
father := nodeVisited;
while (nodeVisited <> lastNode) do
begin
    res := GetConnections(AdjacentList, nodeVisited);
    if length(res) = 0 then exit;
    for i := 0 to length(res) - 1 do
    begin
        nodeVisited := res[i];
        if isVisited(AdjacentList, father, nodeVisited) then
        begin
            visit(AdjacentList, father, nodeVisited);
            setRoute(nodeVisited, father);
            ExamineNodes(nodeVisited, lastNode, AdjacentList);
        end;
    end;
end;
end;

Cómo podéis ver el algoritmo es bastante simple pero se puede mejorar bastante. El coste de calculo es O(n2) para visitar todos los nodos. Aquí os dejo la última versión de la aplicación ThundaxBoxManager v2.3.0 build 57 con los diagramas de ejemplo. Para si resolución hay que ir al menú Citect y allí ejecutar la opción Backtracking2.

• ThundaxBoxManager v2.3.0 build 57.rar (with Data).