Reducción De Tráfico Vehicular Usando El Teorema Max Flow Min Cut
Introducción
El congestionamiento del flujo vehicular es uno de los mayores problemas de la transportación en la zona urbana que ocurre cuando el volumen excede la capacidad de las instalaciones viales. Esto se debe a la libertad de poseer vehículos propios, pobres vías de movilización terrestres, y el crecimiento urbano sin medida. Por lo tanto, creemos necesario analizar dicho problema de manera que podamos ponerle fin o al menos minimizar el impacto que este conlleva en las calles (Perez, Bautista, Salazar, & Macias, 2014).
Con la ayuda de nuestro conocimiento en ciencias de la computación, algoritmos de análisis de flujos y algunos teoremas, planeamos intentar resolver un problema que se presenta en numerosas cantidades a lo largo del territorio hondureño, el cual es el congestionamiento del flujo vehicular terrestre. Para ello decidimos utilizar el teorema de Max-flow min-cut (Máximo-flujo mínimo-corte) para intentar resolver por medio de análisis de flujo de cargas. Con este teorema podemos analizar desde un punto de vista científico el problema con la alta congestión en las calles urbanas y carreteras del país.
Preguntas de investigación
· ¿Cómo se soluciona la problemática del congestionamiento vehicular en otros países?
· ¿Existirá algún algoritmo que se pueda aplicar para generar una solución para este tipo de problemas?
· ¿Qué tan efectivo sería usar un algoritmo para problemas de este tipo?
· ¿Existirá algún caso real en donde un algoritmo haya solucionado la problemática del congestionamiento vehicular?
Objetivos
Objetivo general
Proponer una solución para solventar la problemática del flujo vehicular de San Pedro Sula, Cortés, Honduras utilizando estrategias parecidas a las encontradas en casos de éxito que utilicen algoritmos de control de flujo como parte de la solución,
Objetivos específicos
Identificar los cuellos de botella del flujo vehicular en la ciudad de San Pedro Sula, Cortés, Honduras usando el teorema max-flow min-cut.
Investigar casos donde se utilizó algún algoritmo de control de flujo para solventar la problemática del flujo vehicular en una región.
Proponer una solución en base a lo investigado para solventar la problemática del flujo vehicular de San Pedro Sula, Cortés, Honduras.
Marco teórico
En busca de ofrecer un mejor entendimiento de los temas a tratar, a continuación se presenta un breve marco teórico sobre temas clave para la investigación.
Definición de un grafo
En teoría de grafos y la informática en general se define un grafo G como un par de ordenado (V, E) donde:
- V representa un conjunto de vértices o nodos.
- E representa un conjunto de aristas que conectan los vértices.
Grafo no dirigido
Un grafo no dirigido es un Grafo G = (V,E) donde:
- V no es vacío.
- E es un conjunto no ordenado de aristas.
Esto es, la arista a = (v,w) es igual a la arista b = (w,v).
Grafo dirigido
Por lo contrario, un grafo dirigido G = (V,E) es un grafo dónde:
- V es un conjunto no vacío y,
- E es un conjunto de pares ordenados o aristas.
Por lo tanto, la arista a = (v,w) difiere de la arista b = (w,v).
Adyacencia
Se dice que dos vértices son adyacentes si son unidos por una arista. Dos aristas son adyacentes si tienen un vértice o nodo en común.
Tráfico vehicular
El tráfico vehicular (llamado tránsito vehicular o tráfico) es un fenómeno ocasionado por el flujo de automóviles en una vía, calle o autopista. Thomas & Bull (2001) afirman que:
La causa fundamental de la congestión es la fricción entre los vehículos en el flujo de tránsito. Hasta un cierto nivel de tránsito, los vehículos pueden circular a una velocidad relativamente libre, determinada por los límites de velocidad, la frecuencia de las intersecciones, etc. (pág. 8)
El congestionamiento vehicular representa un problema cotidiano para casi cualquier sociedad en la actualidad. Como mencionan Perez, Bautista, Salazar, & Macías (2014): “El tráfico representa en la actualidad un gran reto a resolver debido al número de usuarios cada vez mayor que necesitan transportarse hacia las grandes ciudades para realizar sus actividades económicas, sociales, culturales y de cualquier índole.”
El tráfico vehicular se puede categorizar en dos: recurrente y no recurrente. El tráfico no recurrente es aquel que es ocasionado por cualquier número de eventos inesperados que pueden causar un retraso en el flujo vehicular. El trafico recurrente por otro lado, se refiere al congestionamiento creado por plazos de tiempo, denominados horas pico, donde el flujo de vehículos es elevado constante y consistentemente. El tráfico no recurrente es difícil de manejar, desde el punto de vista de optimización de flujo vehicular, ya que su naturaleza impredecible impide poder dar una solución concreta.
Causas del tráfico vehicular
Como cualquier fenómeno, el tráfico vehicular no ocurre naturalmente, es producto de diferentes condiciones que contribuyen a su creación. Entre los más importantes podemos mencionar:
- Las vías de la región son frecuentemente mal diseñadas y mal conservadas; Si las vías que existen y las prontas a existir carecen de una buena infraestructura y mantenimiento adecuado, no son capaces de ofrecer su máxima oferta vial a los conductores (Thomas & Bull, 2001)
- Conducta inadecuada de ciertos automovilistas: Los usuarios que inciden en conductas inadecuadas al estar frente al volante no sólo aumentan el número de accidentes, aumentando el congestionamiento como resultado, pero también crean frustración y sentimientos de injusticia en sus compañeros viales (Thomas & Bull, 2001)
- La información deficiente sobre las condiciones del tráfico: Si no se puede obtener un reporte actualizado y correcto de tiempo real sobre la situación vehicular en las calles más transitadas, existe una mayor incidencia de aumento de tránsito en vías ya congestionadas.
Adicionalmente también podemos mencionar factores que pueden influir en la creación y mantención prolongada de congestionamiento vehicular como:
- La elección de un usuario por un medio de transporte personal más seguro y cómodo, llámese vehículo, contribuye mucho más al congestionamiento, aumentando el número de vehículos y espacio por transeúnte vial, que opciones como autobuses y taxis (Thomas & Bull, 2001).
- Sobre todo en zonas urbanas, la creación de infraestructura vial para satisfacer la demanda vial de los horarios pico (plazos de tiempo donde el tráfico tiende a elevarse con frecuencia) tiene un costo muy elevado (Thomas & Bull, 2001).
Situación en San Pedro Sula
El fenómeno afecta a miles de ciudades alrededor del mundo. Sin embargo, para efectos de esta investigación nos centraremos en la situación de la ciudad de San Pedro Sula, Cortés ubicada al noreste Honduras.
Las causas del congestionamiento vehicular en San Pedro Sula
Muchas veces, el embotellamiento de la ciudad ocurre por accidentes. Estos accidentes tienden a ocurrir en áreas muy utilizadas por los conductores sampedranos, lo que causa filas extremadamente largas de automóviles que retrasan el movimiento de los ciudadanos. Según el portavoz de la Policía de Tránsito, José Rodríguez Montoya, la mayoría de los accidentes no se debe al estado de las calles, o a conductores ebrios, sino a la imprudencia de los conductores (Las cinco causas principales de accidentes viales en Honduras, 2016).
La mayoría de accidentes ocurren entre las 2:00 pm y 6:00 pm, horas que tienden a tener una gran cantidad de movimiento, por lo que son comúnmente conocidas como horas pico. De los tres bulevares principales en nuestra ciudad, el boulevard del este (salida a La Lima) es donde más accidentes con daños materiales y humanos se registran. El transporte público está involucrado en el 45% de los accidentes de tránsito, mientras que el 55% es causado por conductores particulares (Las cinco causas principales de accidentes viales en Honduras, 2016).
El tráfico de nuestra ciudad es causado también por construcciones. La desorganización en cuanto horarios apropiados de trabajo para dichas construcciones y reparaciones causan que vías esenciales de la ciudad sean bloqueadas, o severamente dañadas, forzando a varios conductores a buscar alternativas o avanzar a paso lento, en sí retrasando el flujo de los automóviles (Las cinco causas principales de accidentes viales en Honduras, 2016).
La cantidad de vehículos que se encuentran en la ciudad sobrepasan los límites de calles, siendo estas usualmente estrechas, e incapaces de albergar varias filas de automóviles para permitir el flujo. Esta falta de espacio provoca a que lo conductores recurren a imprudencias, como rebasar en áreas altamente riesgosas, o alternar por áreas que no poseen carretera (ej. aceras).
El clima, también, posa un gran atraso al tráfico, puesto que cuando hay fuertes lluvias, varias calles de la ciudad son inundadas, y los conductores tienden a mantener velocidades bajas para intentar evadir accidentes. Otras razones también son la saturación de vendedores en las calles, la lentitud de los semáforos, y la lentitud e ineficiencia de la policía para hacer levantamiento legal de cuerpos en caso de crímenes (Las cinco causas principales de accidentes viales en Honduras, 2016).
Estadísticas relevantes
Existen 289,362 unidades vehiculares registradas en San Pedro Sula, de las cuales 216,511 son automóviles y 72,851 son motocicletas (Medio millón de vehículos obligan a abrir nuevas vías en San Pedro Sula, 2018). En adición, hay alrededor de 289000 unidades no registradas, lo que implica que en la ciudad hay más de 578000 unidades circulando.
Las horas pico, horas de congestionamiento elevado, de San Pedro Sula son: el periodo de 6:00 AM a 9:00 AM y el periodo de 2:00 PM a 7:00 PM
Las áreas más afectadas son los bulevares, siendo los bulevares del este y del norte los que más carga reciben. Los accidentes de tráfico son la segunda causa de muerte más frecuente en el país (Conozca los once puntos más críticos del tráfico en San Pedro Sula, 2016).
Teorema Max Flow Min Cut
En ciencias de la computación y la teoría de la optimización, el teorema de corte mínimo del flujo máximo establece que en una red de flujo, la cantidad máxima de flujo que pasa de la fuente al sumidero es igual al peso total de los bordes en el corte mínimo, es decir, el peso total más pequeño de los bordes que, si se eliminan, desconectarían la fuente del fregadero (Wayne, 2004).
El teorema relaciona dos cantidades: el flujo máximo a través de una red y el peso mínimo de un corte de la red.
Se basa en dos algoritmos: flujo máximo y corte mínimo.
Problema del corte mínimo
Este problema necesita de un grafo dirigido, aristas con capacidades, nodo fuente s y nodo sumidero t.
El problema del corte mínimo se enfoca en encontrar el mejor conjunto de aristas que eliminar para desconectar el nodo origen de un nodo sumidero.
Un corte se define como una partición de nodos (S, T) tal que s pertenece a S y t a T. La capacidad de (S, T) se define como la suma de los pesos de las aristas que salen de S (Wayne, 2004).
Por lo tanto, para encontrar el mejor conjunto de aristas a eliminar, debemos encontrar un corte s-t de capacidad mínima.
Problema del flujo máximo
El problema del flujo máximo pretende asignar flujo a las aristas de manera que se ecualicen el flujo entrante y saliente de cada nodo intermedio así como maximizar el flujo de un nodo origen s a un nodo sumidero t (Wayne, 2004).
Al igual que el problema del corte mínimo, este problema necesita de un grafo dirigido, aristas con capacidades, nodo fuente s y nodo sumidero t.
El flujo f es una asignación de peso a las aristas tal que:
- Capacidad : y
- Se conserve el flujo, es decir, excepto en nodo s o en el nodo t.
Por lo tanto, lo que se busca es encontrar un flujo que maximice el flujo neto hacia el sumidero.
Por lo tanto al usar ambos algoritmos en conjuntos, como propone Ford-Fulkerson (1956): “En cualquier red, el valor del flujo máximo es igual a la capacidad de corte mínimo”.
Este teorema tiene distintas aplicaciones. A continuación se presenta una solución utilizando este teorema y el algoritmo Ford-Fulkerson para la problemática del congestionamiento vehicular.
Aplicabilidad
Moore et al. (2013) estudiaron el flujo máximo en redes de carreteras con capacidades de velocidad dependientes de la aplicación al tráfico en Bangkok. Un problema de flujo de tráfico tomó los pesos de las aristas que representaban las capacidades de las carretera, definidas como vehículos por hora, que eran funciones de la velocidad del tráfico, definida como kilómetro por hora, y la densidad del tráfico (vehículos por kilómetro) (Abdullah & Hua, 2017).
Para estimar la capacidad de la carretera para una velocidad dada, se utilizaron datos empíricos sobre separaciones seguras de vehículos para una velocidad dada. Se desarrolló una versión modificada del algoritmo Ford-Fulkerson para resolver los problemas de flujo máximo con capacidades dependientes de la velocidad, con múltiples nodos de origen y destino. Se encontró que el flujo de tráfico máximo seguro se produjo a una velocidad de 30 km/h (Abdullah & Hua, 2017).
Baruah & Baruah (2013) presentaron el teorema de corte mínimo, flujo máximo aplicado utilizando el conjunto de cortes de un grafo ponderado al flujo de tráfico. Un grafo ponderado fue un grafo resultante con un número real que sirvió como modelo estructural en el transporte. La estrategia de control de tráfico de corte mínimo y flujo máximo fue minimizar el número de bordes en una red y la capacidad máxima de los vehículos que se movieron a través de estos bordes. Con un corte mínimo en la red de tráfico, se permitió un tiempo de espera mínimo de los participantes del tráfico para un flujo de tráfico suave e incongruente (Abdullah & Hua, 2017).
Dong y Zhang (2011) presentaron una investigación sobre el método de identificación de cuellos de botella en la red de tráfico según el teorema de corte mínimo, flujo máximo. Permitió identificar la sección débil de la carretera y proporcionó una solución para el problema del tráfico. Las redes de tráfico deben formarse en el mapa de la teoría de grafos antes de la identificación del cuello de botella. Aplicaron el teorema de corte mínimo, flujo máximo para descubrir el cuello de botella de la red. […] Se determinó la capacidad máxima de toda la red. Las partes débiles identificadas de la carretera permiten a ingenieros de tráfico saber qué partes de la carretera necesitan ser ampliadas. Además, propusieron una manera de resolver el cuello de botella del tráfico que era aumentar las líneas de carreteras. El software de simulación, ExSpect se aplicó para realizar la simulación en la nueva red con la cual se agregó la línea de carretera para probar la eficiencia de la solución. Los resultados mostraron que la identificación del cuello de botella basado en el teorema de corte mínimo, flujo máximo podría así determinar el cuello de botella de manera efectiva (Abdullah & Hua, 2017).
En base a lo investigado, sobre casos de soluciones aplicadas en lugares como Kota Kinabalu, Sabah, Malasia y el distrtito Changyi, de la ciudad Jilin en China, proponemos que se revisen cada una de estas aplicaciones del teorema min cut, max flow para solventar la problemática de San Pedro Sula.
Conclusiones
La congestión vehicular es un problema grande en nuestra región y por lo tanto debemos utilizar todas las herramientas disponibles para intentar solucionarlo. Una sola solución nunca será suficiente por muy bueno resultado que ofrezca, se recomiendo combinar distintas estrategias para maximizar la optimización del flujo vehicular en San Pedro Sula.
Utilizar el teorema de max-flow min-cut nos permitiría visualizar los cuellos de botella del flujo vehicular, identificando las rutas más problemáticas en una subregión.
Tomamos en cuenta varios casos donde se logró reducir la congestión vehicular mediante el uso de algoritmos como Ford-Fulkerson y el teorema de Max-Flow Min-Cut y analizamos las soluciones que se podrían aplicar a nuestra región.
Alternativamente, como medida adicional la implementación de rutas alternas, mejora de la información disponible en tiempo real sobre el estado del tráfico actual, y aplicar las leyes de transito son posibles soluciones para aumentar el flujo en rutas críticas.
Bibliografía
- Accidentes de tránsito han provocado 1,133 muertes durante 2018 en Honduras. (5 de Octubre de 2018). El Heraldo. Obtenido de https://www.elheraldo.hn/pais/1222053-466/accidentes-de-tr%C3%A1nsito-han-provocado-1133-muertes-durante-2018-en-honduras
- Bull, A. (2003). Congestión de Tránsito, el problema y cómo enfrentarlo. Santiago: Naciones Unidas.
- Conozca los once puntos más críticos del tráfico en San Pedro Sula. (16 de Mayo de 2016). La Prensa. Obtenido de https://www.laprensa.hn/honduras/960952-410/conozca-los-once-puntos-m%C3%A1s-cr%C3%ADticos-del-tr%C3%A1fico-en-san-pedro-sula
- Las cinco causas principales de accidentes viales en Honduras. (5 de Octubre de 2016). La Prensa.
- Medio millón de vehículos obligan a abrir nuevas vías en San Pedro Sula. (19 de Abril de 2018). La Prensa. Obtenido de https://www.laprensa.hn/honduras/1170666-410/veh%C3%ADculos-obligan-abrir-nuevas-v%C3%ADas-san_pedro_sula
- Perez, F., Bautista, A., Salazar, M., & Macias, A. (2014). Análisis del flujo de tráfico vehicular a través de un modelo macroscópico. DYNA, 81, 36-40.
- Thomas, I., & Bull, A. (2001). La congestión del tránsito urbano: causas y consecuencias económicas y sociales. Santiago: Naciones Unidas.
- Wayne, K. (2004). Max Flow, Min Cut. Algorithms and Data Structures. Princeton University. Obtenido de http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf
