Diseño de redes de transporte mediante una variante del Modelo Physarum
Design of transport networks by means of a variant of the Physarum Model
Presentación: 03/12/2021
Aprobación: 11/04/2022
Víctor Hugo Cortínez
Centro de Investigaciones en Mecánica Teórica y Aplicada (CIMTA), Universidad Tecnológica Nacional FRBB, Departamento de Ingeniería, Universidad Nacional del Sur y CONICET. Bahía Blanca – Argentina.
vcortine@hotmail.com
Patricia Neri Dominguez
Departamento de Ingeniería, Universidad Nacional del Sur y Centro de Investigaciones en Mecánica Teórica y Aplicada (CIMTA), Universidad Tecnológica Nacional FRBB, Bahía Blanca – Argentina.
pdoming@uns.edu.ar
Resumen
Se considera el problema del diseño de redes de transporte, conociendo la topología factible y la matriz origen-destino de viajes. El objetivo de este trabajo es obtener las capacidades de los tramos de la red que permiten satisfacer las demandas de pasajeros (o vehículos), minimizando tanto sus recorridos de viaje como el costo de construcción. Para ello, se propone un modelo matemático, basado en una analogía con el comportamiento de aprovisionamiento de un organismo biológico (Physarum Polycephalum), consistente en un procedimiento iterativo que converge al denominado “óptimo del sistema” de transporte.
Adicionalmente, se combina esta metodología con una técnica de reducción de variables, basada en el “Método de Elementos Finitos” para minimizar el tiempo de cálculo computacional requerido al analizar grandes redes.
Palabras claves: redes de transporte, Physarum, Elementos Finitos.
Abstract
The problem of transportation network design, knowing the feasible network topology and the trip origin-destination matrix, is considered. The objective is to obtain the link capacities that allow to satisfy the passengers (or vehicles) demand minimizing, simultaneously, the path lengths of users and the construction cost of the network. The mathematical model, based on an analogy with the foraging behaviour of a biological organism (Physarum Polycephalum), consists in an iterative procedure that converges to the transport “system-optimum”. Moreover, this methodology is combined with an approach of variables reduction, based on the Finite Element Method, to minimize the computational burden required for analyzing large networks.
Keywords: transportation networks, Physarum, Finite Elements.
1.Introducción
Las redes de transporte (viales, ferroviarias, etc.) son de vital importancia para la vida humana. En consecuencia, su diseño es una actividad de gran relevancia en ingeniería.
Una manera de formular el problema de diseño de redes de transporte (DRT) consiste en determinar las capacidades de los arcos de una topología factible, para satisfacer la demanda de viajes (pasajeros, vehículos, mercancías, etc.) con un costo mínimo. En este trabajo, dicho costo se asocia a la longitud de los recorridos realizados por los usuarios para llegar a sus destinos como así también al costo de construcción. Cabe señalar que el efecto de la congestión no es tenido en cuenta en el problema de diseño bajo estudio.
El diseño de grandes redes de transporte es muy demandante desde el punto de vista computacional, razón por la cual la investigación de enfoques eficientes es de gran interés (Miandoabchi et al., 2013; Dominguez y Cortínez, 2015).
Existen metodologías exactas para resolver el problema que pueden resultar muy costosas computacionalmente para grandes redes (Dionne and Florian, 1979).Por tal razón, se ha desarrollado una serie de métodos heurísticos más convenientes para el tratamiento de redes reales.
Un enfoque interesante en tal sentido, desarrollado en los últimos años, es el algoritmo iterativo denominado “Physarum”. Éste se basa en una analogía biológica asociada a la estrategia de aprovisionamiento del moho Physarum Polycephalum consistente en la generación de una red de tubos en busca de fuentes de alimentación. Cuando se encuentra con éstas, el organismo disuelve los nutrientes en el protoplasma para transportarlos a través de los tubos al resto del cuerpo. Los tubos crecen a medida que aumenta el flujo protoplasmático, adaptándose mejor al transporte futuro ya que ofrecen menos resistencia al flujo. Por otra parte, los tubos que no transportan suficiente protoplasma se encogen y, finalmente, desaparecen. Este mecanismo es esencialmente un proceso de retroalimentación que refuerza los caminos activos y elimina los no utilizados. Se ha demostrado que la modelación matemática de tal comportamiento resuelve adecuadamente la determinación del camino más corto entre un punto de origen y uno de destino en una red (Tero et al., 2007 y 2010; Bonifaci et al., 2012).
El algoritmo Physarum básico fue modificado por Watanabe et al. (2011) para el diseño de redes de transporte con múltiples pares origen-destino. Para estudiar su eficiencia, han aplicado este método a la red ferroviaria de la ciudad de Tokio, obteniendo resultados similares a la red real existente. Asimismo, los autores mencionados demuestran que su metodología es, en algunos casos, más eficiente que otros enfoques utilizados en la bibliografía clásica. En este enfoque se asume el conocimiento imperfecto de la matriz origen-destino.
Más recientemente, Zhang et al. (2015) han aplicado una metodología similar al diseño de redes de caminos, conociendo la matriz origen-destino a partir de un modelo de “distribución de gravedad”. Este enfoque ha producido diseños eficientes, de características similares a las de las redes de autopistas mexicanas y chinas ya construidas. Por su parte, Akhand et al. (2021) han aplicado una metodología similar a la de Zhang et al. (2015) para el diseño de una red de bici-sendas en la megaciudad de Daca, Bangladesh.
Los métodos de Watanabe et al. (2011), Zhang et al. (2015) y Akhand et al. (2021) se basan en la búsqueda del camino más corto entre cada uno de los diferentes N*(N-1) pares origen-destino que existen en una red de N nodos. Tales enfoques tipo Physarum, que aquí serán mencionados como clásicos, requieren resolver en cada paso iterativo N*(N-1) sistemas de ecuaciones lineales de orden N-1, a fin de obtener el camino más corto para cada par origen-destino (Houbraken et al., 2013). Este trabajo computacional debe repetirse tantas veces como sea necesario para alcanzar la convergencia. Como tal carga computacional puede ser muy importante en el caso de grandes redes, en los trabajos aludidos se ha realizado una aproximación consistente en considerar solo algunos de los pares origen-destino (presumiblemente los más representativos). Sin embargo, no se ha indicado fehacientemente cuántos pares deben ser elegidos para la adecuada precisión de la metodología.
En este trabajo se propone una variante del enfoque Physarum a efectos de obtener la distribución óptima de flujos en cada tramo de la red que permita satisfacer la demanda de viajes entre los pares origen-destino. Con los flujos óptimos es posible diseñar luego las capacidades adecuadas para cada tramo. A diferencia de los enfoques Physarum citados previamente, el presente método no se basa en la búsqueda del camino más corto entre dos puntos de la red sino en un principio más general denominado “óptimo del sistema” (OS) (Sheffi, 1985). Se demuestra matemáticamente que el OS, en ausencia de congestión, puede ser identificado con la configuración de red de menor costo económico y asimismo con las mínimas longitudes de recorrido de los usuarios hasta alcanzar sus destinos. La metodología propuesta requiere resolver, en cada paso de iteración, N sistemas de ecuaciones de orden N-1 (un sistema para cada destino). De esta manera, el volumen de cálculo es mucho menor que el de los enfoques Physarum clásicos previamente mencionados. El presente enfoque se desarrolla como una adaptación de la metodología más general, propuesta por los autores (Cortínez y Dominguez, 2021), para el estudio del problema de asignación de tráfico vehicular en redes urbanas congestionadas (ATC).
Adicionalmente,se propone un enfoque de reducción de incógnitas, basado en el Método de Elementos Finitos (MEF) para aplicar conjuntamente con la variante del método Physarum. Esta combinación permite analizar, de manera aproximada, grandes redes de transporte con una carga computacional mucho menor manteniendo una precisión similar a la del enfoque original.
2. Una variante del algoritmo Physarum para el diseño óptimo de redes de transporte
Se considera una red de transporte con N nodos conectados por arcos. Se asume que cada uno de ellos puede actuar como origen de viajes, mientras que M de ellos pueden ser sus destinos. Se pretende determinar de manera óptima la capacidad de cada arco (cantidad y/o ancho de carriles o cantidad de vías, según el tipo de transporte considerado), conociendo las demandas de viaje estacionarias (personas, vehículos) entre cada par de nodos origen-destino. Como se ha señalado anteriormente, no se consideran en este problema los efectos de la congestión de tráfico.
La metodología de solución consiste en calcular, primeramente, la distribución de flujos que asegure el OS (Sheffi, 1985), en ausencia de congestión. Una vez obtenidos los flujos, se determinan las capacidades buscadas. Se puede demostrar que el OS asegura que los usuarios de la red recorren longitudes mínimas hasta su destino. Además, ese recorrido mínimo se puede asociar con el costo constructivo mínimo.
La metodología de diseño se formula como una adaptación del enfoque de solución del problema de asignación de tráfico urbano congestionado (ATC) hacia un destino d (Cortínez y Dominguez, 2021; Dominguez et al., 2021). Este enfoque se muestra a continuación.
2.1. Problema auxiliar: asignación de tráfico urbano congestionado (ATC) mediante un modelo Physarum
En este problema (ATC) se considera una red con N nodos (N-1 orígenes y 1 destino d) vinculados por arcos (cuyos nodos extremos se denominan i y j). Se conocen aquí las características de cada arco (capacidad y velocidad máxima permitida, entre otras) y la demanda de viajes desde cada nodo origen j hacia el destino d. Se pretende determinar la distribución de flujos
en los arcos de acuerdo con el primer principio de Wardrop (Sheffi, 1985). Este principio corresponde a una ley de comportamiento que establece que cada usuario elige el camino que minimiza su tiempo de viaje. En condiciones de equilibrio, el tiempo de viaje hasta el destino será el mismo (y el mínimo) por todos los caminos realmente utilizados. En este problema, los efectos de congestión son medidos a través del tiempo de recorrido de arco τij que es una función creciente del flujo en el mismo:
. La forma específica de esta función depende de las características de los arcos.
Este problema puede ser formulado como uno de optimización (Beckmann, 1956, ver Sheffi, 1985). Una de las formas de este enfoque es la siguiente:
(1)
s.a.
,
(2)
El sistema de ecuaciones (2) corresponde a la continuidad de vehículos en cada nodo. Las sumatorias se extienden a todos los nodos i, adyacentes a cada nodo j.
Se ha demostrado (Cortínez y Dominguez, 2017) que la solución del problema (1-2) puede reformularse a partir de una función potencial que corresponde al tiempo de viaje mínimo entre un punto i y el destino correspondiente d. Los tiempos de viaje mínimos
y los flujos
pueden ser determinados mediante la solución estacionaria (t → ∞) de las siguientes ecuaciones que constituyen una variante del denominado modelo Physarum (Xu et al., 2018; Cortínez y Dominguez, 2018 y 2021; Dominguez y Cortínez, 2021):
(3-4)
(5)
(6-7)
La función de arco se denomina conductividad del arco i-j. Se debe observar que si para t → ∞ se alcanza el estado estacionario (
), de (6) y (7) surge que
y
Luego, considerando (5) se obtiene . Por otra parte, a partir de (3) y (5) se verifica la ecuación de continuidad (2). Debe notarse que las ecuaciones (3-7) describen un sistema dinámico ficticio que constituye una herramienta de cálculo para obtener, mediante iteraciones, la solución buscada (flujos y tiempos de viaje) cuya naturaleza es independiente del tiempo.
2.2. Método Physarum para el diseño de una red de transporte sin congestión (DRT)
El algoritmo planteado en la sección anterior puede adaptarse al problema de diseño de redes de transporte analizado en el presente trabajo (DRT). Para ello, debe recordarse que en este problema no se considera la congestión, por lo cual el tiempo de recorrido de arco es igual al cociente entre la longitud del arco Lij (conocida) y la velocidad máxima Vmáx (establecida como condición de diseño), es decir τij=Lij /Vmáx. Al ser aquí τij constante, la ecuación (7) se reduce a Fij = τij . Introduciendo la variable , el sistema (3-7) puede reescribirse como:
(8)
(9)
(10)
(11)
(12)
(13)
Recordando que para t → ∞ corresponde al tiempo de viaje mínimo de i hasta d, es claro que la variable
corresponde a la distancia de recorrido mínima (DRM) desde i hasta d. Asimismo, la distribución de flujos para t → ∞ asegura que cada usuario recorre una longitud mínima hacia su destino. Por otra parte, utilizando (12), la expresión (1) se puede reescribir para este caso (descongestionado) como:
(14)
Debe observarse que el sistema (8-13) puede resolverse de manera independiente para cada destino d. Obteniendo los flujos con el algoritmo indicado para los diferentes destinos d de la red, pueden determinarse los flujos totales en cada arco:
(15)
Sumando (14) para cada destino y considerando (15) se obtiene:
(16)
Esta expresión corresponde al denominado OS. Una vez obtenidos los flujos en los arcos, es posible determinar sus capacidades de acuerdo con el tipo de transporte considerado. Por ejemplo, si se considera el transporte vehicular en una autopista (sin congestión), el flujo vehicular de un tramo puede ser asociado a la densidad óptima ρ de vehículos por unidad de longitud en cada carril, al número de carriles nij y a la velocidad máxima de circulación Vmáx :
(17)
Luego, a partir de los valores deseados de ρ y Vmáx se puede determinar el número necesario de carriles. Si los flujos resultantes fueran nulos (o despreciables) en algunos arcos, éstos podrían ser eliminados de la red. Sin embargo, para hacer la red más tolerante a fallas, en lugar de eliminar tales arcos, se los puede dejar con una capacidad mínima que asegure la conectividad de todos los nodos. Utilizando (17), la función de costo (16) puede ser expresada como:
(18)
Luego, minimizar tal función de costo implica minimizar la cantidad indicada por la sumatoria, que es proporcional al volumen de construcción necesario y, por consiguiente, al costo económico de construcción. En la Figura 1a, se muestra un esquema del procedimiento de diseño propuesto.
Es interesante comparar el tiempo de cálculo del modelo presentado con respecto a la variante clásica (Watanabe et al., 2011; Zhang et al., 2015; Akhand et al. 2021). Si se utiliza un esquema en diferencias finitas para la resolución de la ecuación de evolución (11), el enfoque requiere resolver, en cada paso de tiempo (iteración), un sistema de N-1 ecuaciones algebraicas lineales (8-9) para cada destino. Entonces, considerando M destinos e I iteraciones, se deben resolver M*I sistemas algebraicos de N-1 ecuaciones. Asimismo, el tiempo total de cálculo (TC) viene dado por TC= M*I*Ts, donde Ts es el tiempo de cálculo insumido para resolver un solo sistema lineal de ecuaciones.
Por otra parte, el enfoque clásico requiere idealmente resolver, en cada iteración, tantos sistemas de ecuaciones algebraicas lineales como pares origen-destino existan, es decir (N-1)*M sistemas. Por consiguiente, el tiempo de cálculo total del enfoque clásico (TTC) para I iteraciones se expresa como TTC=(N-1)*M*I*Ts. Considerando que el tiempo de cálculo Ts es el mismo en ambos enfoques, ya que los sistemas de ecuaciones tienen el mismo orden, y que el número de iteraciones hasta convergencia es similar (como se ha comprobado mediante experimentos numéricos), el cociente entre el tiempo total de cálculo de la variante presentada y el correspondiente al enfoque clásico viene dado por (TC/TTC)=1/(N-1). Entonces el tiempo total de cálculo de la variante propuesta es aproximadamente N veces menor que en el enfoque clásico.
Fig. 1: Esquema de los algoritmos propuestos: a) Modelo Physarum, b) Modelo Physarum reducido (MEF)
3. Modelo Physarum reducido: Enfoque de Elementos Finitos
Si bien, en comparación con el modelo original, la variante presentada es más eficiente, la carga computacional aún puede ser muy importante en el caso de grandes redes, sobre todo considerando el hecho de que el sistema (8) debe ser resuelto varias veces hasta lograr la convergencia. Por tal motivo, se propone a continuación una técnica de reducción de variables. Se pretende que el modelo resultante de la utilización de tal técnica tenga un costo computacional sustancialmente menor que el del modelo explicado, aunque con una precisión similar en el cálculo de los flujos de arco. La presente técnica de reducción se basa en el MEF utilizado en la mecánica del continuo (Chandrupatla y Belegundu, 2012).
Fig. 2: Esquema del modelo reducido de elementos finitos
La metodología parte de la subdivisión del sistema de transporte en algunos subdominios, denominados elementos finitos, que contienen una porción de la red como se muestra en la Figura 2. El contorno de tales elementos finitos puede ser de formas geométricas relativamente simples: rectángulos, triángulos, rectángulos distorsionados, etc. Sobre estos elementos se definen ciertos nodos que corresponden a las incógnitas principales , que representan las distancias de recorrido mínimo (DRM) desde los puntos K-ésimos hasta el destino correspondiente d. Dentro de cada uno de estos elementos, se aproxima tal distancia desde un punto genérico de coordenadas (x,y) hacia el centro d, mediante una interpolación de las distancias
correspondientes a los nodos principales:
(19)
Las funciones de interpolación , para ser consistentes, deben adoptar los valores
si
y
si (x, y) corresponde a cualquier otro nodo principal del elemento. Además, tales funciones son nulas fuera del elemento e considerado:
si
. Existen muchas formas para elegir las funciones de interpolación (Chandrupatla y Belegundu, 2012), alguna de las cuales será presentada en el ejemplo numérico. De acuerdo con (19), es posible escribir para cada nodo i de la red de tráfico la siguiente expresión:
(20)
donde se ha definido . La expresión anterior se puede escribir en forma matricial como:
(21)
El elemento genérico de la matriz de interpolación N es y Pd es el vector reducido de DRM hacia el destino d. Hay que observar que el número de variables involucradas en Pd es mucho menor que en pd. Para obtener el sistema de incógnitas reducido para Pd se utiliza el método de Galerkin (Chandrupatla y Belegundu, 2012; Cortínez y Domínguez, 2017). Para ello se consideran las ecuaciones (8) que pueden ser expresadas en forma matricial como:
(22)
pd es el vector de DRM nodales, qd el vector de demandas nodales y Kd la matriz de conductividad del sistema (dependiente de y de Lij ). Sustituyendo ahora la aproximación (21) en el sistema (22) y pre-multiplicando por la traspuesta de la matriz de interpolación se obtiene:
(23)
donde se ha definido:
,
(24a, b)
La función Ad es la matriz de conductividad reducida y Bd el vector de demanda reducido. Antes de resolver el sistema (23) deben imponerse las condiciones (9).
Una vez resuelto el sistema (23), pueden recuperarse las variables nodales pd mediante la expresión (21) y los flujos mediante la expresión (10). Luego se actualiza la conductividad de cada elemento de acuerdo con (11). El procedimiento se itera hasta la convergencia. En la Figura 1b se muestra un esquema de este procedimiento.
4.Resultados numéricos
A efectos de mostrar la eficiencia computacional de los métodos propuestos, se presentan a continuación dos ejemplos numéricos. El primero de ellos está destinado a mostrar la convergencia y precisión del enfoque Physarum modificado que se ha presentado en la sección 2. El segundo, por su parte, permite apreciar la eficiencia computacional del enfoque de reducción de variables basado en la combinación del modelo Physarum con el MEF que se ha presentado en la sección 3.
Ejemplo 1: Diseño óptimo de una red de transporte mediante el modelo Physarum modificado
Se considera el diseño de una red de transporte con 25 tramos y 12 nodos, que actúan como orígenes y destinos, cuya topología se muestra en la Figura 3a. En la misma, se indican las longitudes de cada tramo (en km). La matriz de demanda de viajes origen-destino se muestra en las Tabla 1. Se pretende obtener la distribución de flujos en la red que asegure el óptimo del sistema. En un paso posterior, a partir de tales flujos, podrían determinarse las capacidades de cada tramo, según se trate de redes ferroviarias, viales, etcétera.
|
Destinos |
|||||||||||||
|
orígenes |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
1 |
0 |
0.2 |
2 |
4.6 |
4.9 |
2 |
2.1 |
0.3 |
1.6 |
0.4 |
4.4 |
3.1 |
|
|
2 |
3.9 |
0 |
2.9 |
4.7 |
1.9 |
1.4 |
1.9 |
3.5 |
2.5 |
3.5 |
3.3 |
3.8 |
|
|
3 |
3.4 |
3.5 |
0 |
2.4 |
0.2 |
2.8 |
3 |
4.6 |
1.7 |
2.2 |
0.5 |
5 |
|
|
4 |
1 |
3.4 |
1.8 |
0 |
0.8 |
4.6 |
1.3 |
0.4 |
0.7 |
1.3 |
4.2 |
2.6 |
|
|
5 |
0.1 |
3.6 |
0.6 |
1.9 |
0 |
0.5 |
3 |
1.8 |
4.9 |
2.5 |
3.4 |
4.4 |
|
|
6 |
1.9 |
2.4 |
3.5 |
2.9 |
0.3 |
0 |
3.1 |
4.7 |
1.2 |
0.8 |
0.8 |
0.6 |
|
|
7 |
2.2 |
2.2 |
3.9 |
0.5 |
3.6 |
0.8 |
0 |
4.9 |
3.9 |
0.2 |
2.4 |
4.8 |
|
|
8 |
2.6 |
3.6 |
2 |
2.7 |
1.1 |
0.5 |
2.3 |
0 |
2.4 |
0.2 |
3.5 |
2.3 |
|
|
9 |
4.3 |
4.4 |
2.5 |
3.1 |
3.5 |
3 |
0.1 |
3.9 |
0 |
0.7 |
4.6 |
1.2 |
|
|
10 |
0.4 |
4.1 |
4.1 |
3.9 |
4 |
4 |
4.6 |
3.5 |
1 |
0 |
3.3 |
2.6 |
|
|
11 |
2.7 |
4 |
4.5 |
3.7 |
1.6 |
2.3 |
3.3 |
2.8 |
3.3 |
4.8 |
0 |
2.8 |
|
|
12 |
0.8 |
3.7 |
2.9 |
4.5 |
0.8 |
2.5 |
5 |
2.4 |
2.8 |
3.8 |
2.2 |
0 |
|
Tabla 1: Valores de de la matriz de demanda de viajes
Se ha resuelto el problema con las ecuaciones (8) a (11). La ecuación de evolución (11) se ha resuelto con el método de diferencias finitas (Cortínez y Dominguez, 2021).
En la Figura 3b se muestra la distribución de flujos estacionarios en la red, dirigiéndose hacia el destino 12 (para q0=1 ). Pueden observarse las intensidades de los flujos y sus sentidos. Además, puede notarse que algunos de los tramos carecen de flujo (por ejemplo, el 5-4).
Fig. 3: a) Esquema de la red, b) distribución de flujos hacia el destino 12.
Para mostrar la convergencia de la metodología, se observa en la Figura 4a la evolución del flujo y la conductividad correspondiente al tramo 8-12, cuando se considera como destino el nodo 12, y en la Figura 4b la evolución (p8 - p12)/L de acuerdo con el procedimiento de cálculo.
Fig. 4: a) Evolución del flujo y la conductividad y b) de la diferencia de DRM correspondientes al tramo 8-12 cuando se considera como destino el nodo 12.
Como se puede apreciar, en 60 pasos de tiempo (iteraciones) se alcanza el estado estacionario. El flujo y la conductividad convergen al mismo valor y la diferencia de DRM converge a la longitud del elemento ((pi−pj)/L→1) . Por otra parte, en la Figura 5 se muestra la evolución de la función de costo del sistema (expresión 14), cuando se considera ese destino. Como se aprecia, converge al valor mínimo después de 60 iteraciones. Como la función de costo es una medida global de la red para un destino particular, tal indicador puede utilizarse para decidir cuántas iteraciones deben realizarse hasta la convergencia.
En la Figura 6a, se muestra la solución completa para todos los destinos. Es decir, la distribución de flujos totales en la red. Asimismo, para cada tramo se indica el flujo en cada sentido. En la Figura 6b se muestra la convergencia del método a partir del costo total de la red hasta alcanzar el óptimo del sistema.
Fig. 5: Evolución de la función de costo considerando el destino 12.
Fig. 6: Solución para la red completa: a) distribución de flujos, b) evolución de la función de costo
Ejemplo 2: Diseño óptimo de una red de transporte mediante el enfoque de reducción de variables combinando el modelo Physarum modificado con el Método de Elementos Finitos.
Fig. 7: a) Detalle de la red original, b) esquema de elementos finitos, c) detalle de un elemento.
Se considera la red mostrada en la Figura 7a compuesta por 900 nodos y 1740 arcos de 1km de longitud cada uno. Se consideran dos destinos A y B y que los viajes se generan de manera uniforme en toda la red (q0 en cada nodo). Dicha red se ha analizado mediante el modelo Physarum modificado y también mediante el modelo reducido Physarum-Elementos Finitos, utilizando - para este caso - la división en elementos finitos mostrada en la Figura 7b. Un elemento particular se muestra en la Figura 7c. Debe observarse que, en cada iteración, deben resolverse 2 sistemas de 899 ecuaciones algebraicas simultáneas, mientras que el método reducido requiere resolver en cada paso de iteración 2 sistemas de 79 ecuaciones simultáneas. Observar que los flujos son proporcionales a q0 . Se muestran resultados numéricos para q0=1.
Fig. 8: Evolución de la función de costo total (hacia destinos A y B) obtenida mediante a) el modelo Physarum modificado y b) el enfoque reducido.
En la Figura 8a, se muestra la convergencia de la función de costo total obtenida mediante el modelo Physarum modificado y en la Figura 8b se muestra la misma magnitud obtenida con el enfoque reducido. Puede observarse que, en ambos casos, la función objetivo converge al valor mínimo, existiendo una pequeña discrepancia de 3% entre los valores estacionarios obtenidos por ambas metodologías. En la Figura 10, se muestra una comparación de los flujos obtenidos mediante ambas metodologías correspondientes al subdominio mostrado en la Figura 9. Como se puede apreciar, con el método reducido se comete un error medio en el cálculo de los flujos, correspondientes al subdominio mostrado, de aproximadamente el 5% y un error máximo del orden del 13%. Tales valores son razonables considerando la importante reducción en el volumen de cálculo.
Fig. 9: Subdominio de red utilizado para comparación de resultados
Fig. 10: Comparación de flujos totales obtenidos mediante el modelo Physarum y el modelo reducido Physarum-MEF, para el subdominio de la Fig. 9.
5. Conclusiones
Se ha presentado una modificación del modelo Physarum para el diseño de redes de transporte (sin congestión) con el objetivo de minimizar las distancias recorridas por los usuarios y el costo de construcción. Para este problema, la presente metodología es más eficiente que otros enfoques basados en el modelo Physarum. Asimismo, se ha combinado el enfoque Physarum modificado con el MEF a efectos de formular un problema aproximadamente equivalente con un menor número de incógnitas. Se ha mostrado que este último enfoque produce resultados similares con un tiempo de cálculo mucho menor. Es interesante mencionar que ambas metodologías presentadas son aptas para la programación en paralelo y pueden ser extendidas al diseño de redes congestionadas. Actualmente, se está estudiando la extensión del presente enfoque para contemplar la tolerancia a fallas en la red (obstrucción total o parcial de algunos caminos).
Referencias
Akhand, M. A. H, Habib, M. A., Kamal, M. A. S. y Siddique, N. (2021). Physarum-inspired bicycle lane network design in a congested megacity. Applied Sciences 11, 6958.
Bonifaci, V., Mehlhorn, K. y Varma, G. (2012). Physarum can compute shortest paths. Journal of Theoretical Biology 309, 121-133.
Cortínez, V.H. y Dominguez, P.N. (2017). An anisotropic continuum model for traffic assignment in mixed transportation networks. Applied Mathematical Modelling 50, 340-353.
Cortínez, V.H. y Dominguez, P.N. (2018). Una nueva interpretación del modelo Physarum para el problema de asignación de tráfico en equilibrio de usuario. Mecánica Computacional XXXVI, AMCA (ISSN: 2591-3522), 2089-2098.
Cortínez, V.H. y Dominguez, P.N. (2021). A finite element approach for the traffic assignment problem. Transportation Research Procedia 58, 13–20.
Chandrupatla, D.R y Belegundu, A.D. (2012). Introduction to finite elements in engineering, 4th ed. Ed. Pearson.
Dionne, R. and Florian M. (1979). Exact and approximate algorithms for optimal network design. Networks 9, 37-59.
Houbraken, M., Demeyer, S. Staessens, D., Audenaert P., Colle, D. y Pickavet M. (2013). Fault tolerant network design inspired by Physarum polycephalum. Natural Computing 12:2, 277-289.
Miandoabchi, E., Daneshzand, F., Szeto, W.Y. y Farahani, R.Z. (2013) Multiobjective discrete urban road network design. Computers and Operations Research, 40, 2429-2449.
Sheffi, Y. (1985). Urban Transportation Networks: Equilibrium analysis with mathematical programming methods. Prentice-Halls Inc.
Tero, A., Kobayashi, R. y Nakagaki, T. (2007). A mathematical model for adaptive transport network in path finding by true slime mold. Journal of Theoretical Biology 244, 553-564.
Tero, A., Takagi, S., Saigusa, T., Ito, K., Bebber, D.P., Fricker, M.D., Yumiki, K., Kobayashi, R. y Nakagaki, T. (2010). Rules for biologically inspired adaptive network design. Science 327, 439-442.
Watanabe, S., Tero, A., Takamatsu, A. y Nakagaki, T. (2011). Traffic optimization in railroad networks using an algorithm mimicking an amoeba-like organism, Physarum plasmodium. BioSystems 105, 225-232.
Xu, S., Jiang, W., Deng, X. y Shou, Y. (2018). A modified Physarum-inspired model for the user equilibrium traffic assignment problem. Applied Mathematical Modelling 55, 340-353.
Zhang, X., Adamatzky, A., Chan, F., Deng, Y., Yang, H., Yang, X., Tsompanas, M., Sirakoulis, G. y Mahadevan, S. A (2015). Biologically inspired network design model. Nature, Scientific Report (DOI:10.1038/srep10794).
Contribución de los Autores
|
Colaboración Académica |
||||||||||||||
|
Nombres y Apellidos del autor |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
Víctor Hugo Cortínez |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|
|
Patricia Neri Dominguez |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
x |
|
1-Administración del proyecto, 2-Adquisición de fondos, 3-Análisis formal, 4-Conceptualización, 5-Curaduría de datos, 6-Escritura - revisión y edición, 7-Investigación, 8-Metodología, 9-Recursos, 10-Redacción - borrador original, 11-Software, 12-Supervisión, 13-Validación, 14-Visualización.
Este trabajo fue realizado de manera conjunta por los autores en todos los aspectos pertinentes.