Que debemos construir un camino. Parte 1

El itinerario diario de la mayoría de nosotros se limita a viajar desde casa al trabajo y viceversa. Y el obstáculo más difícil que puede ralentizar nuestro movimiento son los atascos. Pero en nuestro país hay una gran cantidad de lugares donde solo puedes subirte a vehículos especiales.


Tal transporte es bueno si no necesita transportar grandes vol√ļmenes de carga o viajar a √°reas inaccesibles de manera regular. Entonces ya deber√≠amos pensar en la construcci√≥n de infraestructura, cuyo movimiento es posible en el transporte civil habitual.


Y es bueno si toda la complejidad del dise√Īo de una ruta futura radica en encontrar una regla y un l√°piz para dibujar una l√≠nea recta en el mapa que conecte un par de objetos. Pero, por desgracia, nuestra realidad es muy diferente a esto. ¬ŅQu√© pasa si el terreno que vuela sobre √©l se parece a un buen pedazo de queso suizo?


Durante m√°s de un a√Īo, hemos estado trabajando con colegas del laboratorio de investigaci√≥n de Dise√Īo Digital para crear una herramienta que pueda construir varias redes de comunicaci√≥n en modo autom√°tico. Para m√°s detalles, bienvenido a cat.


Como empezó todo


Por lo general, los viajes a lugares tan remotos se deben a ciertos beneficios financieros. Y aunque a menudo se sabe de antemano que el desarrollo de estas √°reas traer√° buenas ganancias, ¬Ņpor qu√© no ahorrar dinero en cosas que se pueden hacer sin dificultades especiales? ¬ŅQu√© sucede si una ruta dise√Īada de manera m√°s competente nos permite no construir varios kil√≥metros adicionales de la carretera?


Pero solo la disponibilidad de carreteras para recibir ganancias significativas es claramente insuficiente. Y b√°sicamente solo es tra√≠do por dep√≥sitos minerales. Por lo tanto, adem√°s de las carreteras, es necesario dise√Īar una red de varias tuber√≠as, una red de tuber√≠as de agua, una red de l√≠neas el√©ctricas con subestaciones el√©ctricas colocadas correctamente. Toda esta infraestructura puede designarse como objetos lineales.


Y cuando un ingeniero se enfrenta a la tarea de dise√Īar una red de comunicaciones en el terreno con condiciones complejas de ingenier√≠a y geol√≥gicas, una tarea anal√≠tica incre√≠blemente compleja recae sobre √©l.


¬ŅC√≥mo no entrar en la zona de inundaci√≥n del r√≠o? ¬ŅC√≥mo minimizar el camino en los suelos de permafrost? ¬ŅC√≥mo ahorrar en la cantidad de colch√≥n de arena al tender una carretera a trav√©s de un pantano? ¬ŅD√≥nde conseguir arena para esta almohada?
Esta es solo una peque√Īa fracci√≥n de las preguntas que se hace un ingeniero durante el trabajo y, sin embargo, a√ļn debe tener en cuenta varios GOST y SNiP. Y bueno, si quieres conectar solo dos objetos, y si hay un par de docenas de objetos?

Por lo tanto, la industria del dise√Īo necesita urgentemente una herramienta que pueda calcular tanto el costo de los objetos lineales dise√Īados por un ingeniero como la capacidad de construirlos en modo autom√°tico.


Datos


Lo primero que tuvimos que enfrentar cuando comenzamos la tarea fue la b√ļsqueda de datos. ¬ŅQu√© datos se requieren? ¬ŅD√≥nde conseguirlos? Y si la segunda pregunta puede resolverse con la ayuda del usuario, para comprender la primera pregunta necesitamos an√°lisis serios.


Y los datos para el cálculo correcto requieren realmente mucho, comenzando por la marca más banal del área en la que se marcan los lagos y ríos, varios pantanos, así como áreas kársticas, en las que se recomienda no construir debido a la amenaza de colapso. Por lo tanto, además de las áreas que se pueden ver desde el satélite, aquí también se requieren datos de estudios geológicos del área.


Pero no todos los datos están limitados a objetos naturales en nuestro país. También hay un montón de cosas que fueron creadas por el hombre. Por ejemplo, en el caso de la construcción de carreteras, podemos usar las carreteras que se construyeron anteriormente. Pero en la construcción de tuberías, el uso de la infraestructura existente está lejos de ser siempre posible. Dado que la conexión de una nueva tubería a una red existente puede no pasar el cálculo hidráulico.


Además de la reutilización de lo que fue creado previamente por el hombre, también se deben tener en cuenta varias restricciones en la construcción cerca de cualquier objeto. Por ejemplo, para la construcción de líneas eléctricas, debe tener en cuenta las muescas de los lugares de habitación humana dependiendo del voltaje en la línea eléctrica misma.


Pero no es del todo correcto considerar el cálculo del problema solo en un avión, ya que además del terreno plano, hay áreas con una gran diferencia de elevación, en las que tampoco se puede llevar a cabo la construcción.


Obtener datos sobre el terreno es un proceso mucho más simple que los datos sobre el marcado de áreas y la infraestructura existente. Para simplificar el desarrollo, utilizamos datos de elevación SRTM (Shuttle Radar Topography Mission) abiertos que cualquiera puede obtener.




Entonces, tenemos los datos, sabemos d√≥nde podemos construir, d√≥nde no podemos construir, hay costos de construcci√≥n para diferentes √°reas del terreno. Tenemos una regi√≥n, tiene un conjunto de objetos que queremos conectar a una sola red de comunicaci√≥n. En t√©rminos matem√°ticos, esto parecer√° una b√ļsqueda de una soluci√≥n al problema de Steiner.


Un poco de matem√°tica


Se sabe que cada f√≥rmula reduce a la mitad el n√ļmero de lectores, por lo que redujimos dr√°sticamente esta secci√≥n ...


Para optimizar la ruta de la instalaci√≥n lineal dise√Īada, es necesario poder calcular su costo de construcci√≥n. Cada objeto lineal se puede representar como una polil√≠nea L = \ {A_i, B_i \} _ {i = 0} ^ n que consiste en segmentos ABi .
El costo de construcción de cada sección recta se puede representar como un valor de función CABi , donde cada segmento se especifica paramétricamente:

$$ display $$ {\ displaystyle AB_i \ colon \ left \ {{\ begin {alineado} & s = s \ left (t \ right) - \ mbox {curva parametrizada}, \\ & h = h \ left (s (t ) \ right) - \ mbox {función de altura de elevación}, \\ & c = c \ left (s (t) \ right) - \ mbox {función del costo unitario de construcción en un punto}, \\ \ end {alineado}} \ right .} $$ display $$

donde t in left[0,1 right] - parametrizaci√≥n del segmento.

CABi= int limitsABic left(s(t) right) sqrt left[gxy(s(t))+ frac partialh parcialsx cdot frac partialh partialsy right] dotsx dotsydt donde g - el tensor m√©trico de la superficie de la Tierra sin tener en cuenta el relieve, es decir, en palabras simples, la funci√≥n de medir la distancia en la superficie de la Tierra.


Debido al hecho de que nuestro planeta tiene la forma de un geoide, es necesario usar fórmulas especiales para medir distancias. Para esto usamos la fórmula de Haversinus. En él, la forma del planeta parece una esfera, pero esto es suficiente para nuestros propósitos, ya que el error de medición es de aproximadamente 0.3% , y la velocidad de cálculo de distancias por este método sigue siendo alta.


Enfoques para encontrar la mejor manera




Pero antes de pasar a unirte a un grupo de objetos, debes aprender a encontrar el camino óptimo entre los dos. Dos formas de hacer esto vienen a la mente de inmediato:

  1. construya un gr√°fico y luego aplique los m√©todos de b√ļsqueda de ruta m√°s cortos;
  2. use una solución basada en métodos de optimización.

Al implementar el primer método, tenemos un problema asociado con el método de construir un gráfico para obtener la mayor precisión posible de la solución. Es necesario encontrar un equilibrio entre la cantidad de vértices y aristas en el gráfico, la calidad de la solución y el tiempo necesario para calcularla.



En el segundo caso, el principal problema son los mínimos locales. Es fácil elegir un caso en el que la solución no converja o esté lejos de ser óptima. Dado que la solución obtenida por este método depende increíblemente de la aproximación inicial. Si tenemos una buena aproximación inicial, el resultado será de alta calidad.



Entonces, tenemos dos enfoques para resolver este problema. El primero tiene una calidad bastante baja, pero no hay problema de mínimos locales. El segundo tiene un problema de mínimos locales, pero una solución de alta calidad. Y si combina correctamente estos dos enfoques, las deficiencias de cada uno desaparecerán. Tomamos la solución obtenida en el gráfico como una aproximación inicial y luego le aplicamos métodos de optimización.


En esta parte del artículo, consideraremos exactamente la solución propuesta para este problema en el gráfico.


Selección de herramienta


Se ha delineado un plan de acción, solo queda "codificarlo". Como en la etapa inicial de redacción de la solicitud teníamos poco conocimiento sobre el área temática, necesitábamos un lenguaje flexible para que, en caso de algunos errores de cálculo arquitectónicos, reescribiéramos el código completo para un par de latas de cerveza de la tarde. Opcionalmente, también quería bibliotecas para todas las ocasiones, a fin de no recurrir a la invención de las bicicletas. Por lo tanto, Python fue elegido como el lenguaje de programación principal.


En la aplicación, utilizamos una impresionante pila tecnológica, que no se limita a lo siguiente:

  • bien proporcionado para trabajar con datos geom√©tricos como pol√≠gonos y polil√≠neas;
  • geopandas para trabajo conveniente con bien proporcionado ;
  • scipy para almacenar el gr√°fico calculado y encontrar el camino m√°s corto en √©l, as√≠ como encontrar los √°rboles de expansi√≥n m√≠nima;
  • PyTorch para trabajar con la funci√≥n de costo;
  • Almohada para trabajar con im√°genes.

Implementación


El módulo se puede dividir en varias etapas:

  • generaci√≥n de funci√≥n de costo;
  • generaci√≥n de cuadr√≠cula computacional;
  • construir un gr√°fico basado en una cuadr√≠cula;
  • ponderaci√≥n de grafos;
  • c√°lculo de los caminos m√°s cortos en un gr√°fico.

Dado que los bordes del gr√°fico son segmentos, podemos ponderar estos bordes calculando el valor de una determinada integral, que se presenta arriba. Pero hay muchos bordes en el gr√°fico y, en consecuencia, los valores de los costos y las alturas deber√°n obtenerse para una gran cantidad de puntos, lo que puede llevar mucho tiempo.


Inicialmente, la idea era encontrar el costo unitario de construcción determinando si un punto pertenece a un polígono. Pero esta idea se observó debido a la alta complejidad algorítmica de este enfoque, ya que puede haber muchos polígonos, y cada uno de ellos tiene una gran cantidad de vértices.


Por lo tanto, para resolver este problema, podemos representar todos los polígonos que tenemos en forma de imagen, que en forma matemática es una matriz. Por lo tanto, podemos obtener el costo unitario de construcción en un punto más allá de O (1) y, por lo tanto, podemos obtener el costo de construir una costilla en particular con alta precisión.


Ahora estamos listos para construir un gr√°fico, pero no hay una forma √ļnica y correcta de construirlo para obtener soluciones de alta precisi√≥n. Para construir un gr√°fico, es necesario generar una cuadr√≠cula computacional, es decir, un conjunto de puntos en la regi√≥n en consideraci√≥n, conectados en el orden correspondiente por segmentos que forman las caras de las celdas. Las cuadr√≠culas se pueden dividir en dos tipos: uniformes y desiguales.



El modelo de cuadrícula uniforme describe las coordenadas de puntos individuales, de modo que la distancia entre los nodos de la cuadrícula es la misma. Una cuadrícula desigual aparece como un conjunto aleatorio de puntos individuales.


El uso de una cuadrícula uniforme no siempre dará un resultado de alta calidad para encontrar el camino más corto, por lo tanto, es necesario probar este enfoque en una cuadrícula desigual. La más versátil es la malla triangular.


La cuadrícula se generó introduciendo ruido con cierto coeficiente en una cuadrícula rectangular uniforme y luego aplicando puntos de triangulación de Delaunay para este conjunto de puntos.


La eficacia de las cuadrículas construidas se probó en varios mapas modelo del área, que tuvieron en cuenta los diferentes costos de las regiones y el alivio, y luego se realizó una comparación con la solución obtenida analíticamente. Al buscar la longitud del borde del gráfico y el coeficiente de introducción de ruido en la cuadrícula uniforme, se encontraron parámetros óptimos para construir la ruta óptima entre dos puntos.


Problemas mayores


Al principio todo salió bien, el algoritmo calculó las redes óptimas, pero una vez que hubo un problema con la calidad de la ruta construida. El caso era bastante simple: había que conectar dos objetos en un mapa bastante largo. El algoritmo no quería construir una ruta que obviamente fuera correcta.


El problema, como siempre, fue con la cuadrícula computacional. Continuamos nuestros experimentos con la apariencia de las cuadrículas y llegamos a la conclusión de que conectar los vértices a un gráfico, donde cada vértice está conectado a los n vecinos más cercanos, es la solución a nuestros problemas.


Redes


Despu√©s de que aprendimos c√≥mo encontrar caminos √≥ptimos entre dos puntos, el siguiente paso fue resolver el problema de construir una red √≥ptima de objetos lineales. Los algoritmos encontrados en la literatura para construir √°rboles de Steiner en gr√°ficos est√°n orientados a problemas m√°s generales y, por lo tanto, ser√°n ineficaces en nuestro caso. Nuestro gr√°fico es muy escaso, con un peque√Īo n√ļmero de v√©rtices terminales, en relaci√≥n con el n√ļmero total de v√©rtices en el gr√°fico, y nuestra tarea tambi√©n se aplica. Por lo tanto, por varias otras razones, se decidi√≥ desarrollar nuestro propio algoritmo que utiliza una cierta heur√≠stica para construir de manera efectiva una red √≥ptima.


La descripción del algoritmo para construir la red óptima en el gráfico para nuestro caso es un tema para una publicación separada, no lo consideraremos aquí. Dado que al calcular una tarea real, es necesario tener en cuenta muchas condiciones adicionales de la industria de la construcción que son relevantes para el usuario final, que imponen ciertas restricciones en el algoritmo utilizado.


Caso real


Entonces, ahora pasamos a los resultados del algoritmo. Nuestra tarea es conectar un conjunto dado de objetos con una red de comunicación. La comparación de los resultados del algoritmo ocurrió con una red de carreteras previamente construida. La longitud total de la red existente es 153.5 km versus 122.6 km para la calculada. Esto proporciona una reducción de aproximadamente un 25% en la longitud de la red de carreteras, lo que finalmente ahorrará entre un 5 y un 15% en los costos de construcción de capital.





Puede ver más de cerca los resultados de cálculo aquí .

Una descripción de los métodos de optimización utilizados estará en la siguiente parte del artículo.

Source: https://habr.com/ru/post/437478/


All Articles