Simulación de Monte Carlo usando QGIS y pgRouting en la construcción óptima de aceras

17

Soy nuevo en el análisis espacial y agradecería alguna dirección general sobre un proyecto que estoy intentando, que se describe a continuación (estoy empezando desde cero).

OBJETIVO: Encontrar las mejores ubicaciones para instalar 2000 pies de aceras en mi ciudad natal a fin de conectar la mayoría de los hogares con el Distrito Central de Negocios (CBD), donde "conectado" significa a 1,2 millas caminando del CBD. Tengo archivos de forma que muestran estructuras existentes (hogares), carreteras y aceras (ya instaladas).

Aquí está mi solución propuesta / proceso de pensamiento:

  1. Convierta la red de acera en el lugar en una base de datos de nodos que están conectados por pesos (es decir, distancias). ¿Hay alguna manera de hacer esto directamente en QGIS (u otro programa) haciendo clic en todas las intersecciones?
  2. Calcule la cantidad de hogares que se encuentran a 1,2 millas a pie del Distrito Central de Negocios (por ejemplo, un punto o polígono de longitud larga) utilizando las capacidades de enrutamiento de pgRouting u otra cosa. Este será el valor base del "acceso al hogar".
  3. Usando la capa del camino como guía, coloque aleatoriamente 2000 pies adicionales (digamos, en segmentos de 10 pies) de aceras en la capa de la acera. Esto es equivalente a construir un montón de nuevas aceras arbitrariamente.
  4. Vuelva a calcular los nodos y los pesos utilizando la nueva red peatonal como en (1), y luego vuelva a calcular el número de hogares que ahora están dentro de 1.2 millas del CBD como en (2). Debería aumentar con las aceras adicionales. Guarde las ubicaciones de las aceras adicionales y el valor de "acceso doméstico" asociado en un archivo (por ejemplo, una hoja de cálculo).
  5. Repita los pasos (3) y (4) 10000 veces, similar a una simulación de Monte Carlo. Usando los 10000 conjuntos de puntos de datos, elija las ubicaciones de colocación en las aceras que maximicen el número de hogares dentro de 1.2 millas del CDB.

¿Este proceso de pensamiento suena realista? ¿Alguien tiene alguna sugerencia?

- Me gustaría lograr esto usando alguna combinación de QGIS y R, sin embargo, estoy abierto a aprender PostGIS y / o Python (o cualquier otra cosa) para lograr el objetivo.

baha-kev
fuente
1
Es posible que desee considerar un algoritmo genético en su lugar. Ese es casi el proceso que has descrito. Estoy bastante seguro de que hay bibliotecas de Python que admiten algoritmos genéticos.
Chris
1
Parece que R también tiene bibliotecas de algoritmos genéticos.
Chris
66
Es un gran problema Sin embargo, la mayoría de las ubicaciones aleatorias de 200 segmentos de acera de 10 'no conectarán nada con nada más; no se acercará a un óptimo de una manera tan no guiada. ¿Puedo sugerir centrar sus pensamientos iniciales en cómo formular el problema de manera abstracta (independientemente de cualquier estructura de datos o entorno de programación) para que pueda (a) identificar dichos problemas de antemano y (b) permanecer abierto a la gama más completa de métodos de solución disponibles? Parece prematuro proponer un método de solución particular.
whuber
2
¿Prematuro? No estoy de acuerdo. De hecho, el proceso de pensamiento descrito anteriormente es un enfoque; Espero que centre cualquier lluvia de ideas y genere comentarios útiles. Dicho esto, estoy abierto a la gama más completa de métodos de solución disponibles. Restringir los segmentos para que las aceras se coloquen de tal manera que siempre conecten las cosas sería fácil de implementar y ayudaría a encontrar una solución. Gracias por la sugerencia.
baha-kev
66
Bueno, si retrocede un poco y olvida las cosas de la aleatorización, los tipos de preguntas que se le ocurren incluyen: * ¿Qué tipo de problema de optimización es este? ¿Qué propiedades tiene? (Por ejemplo, linealidad, convexidad, cuasiconvexidad, etc.). * ¿Tiene formulaciones equivalentes, como una doble? * ¿Hay formas alternativas de representarlo, como en términos de propiedades de gráficos o con funciones de penalización? Como ejemplo, una formulación dual sería minimizar la longitud total de las aceras que sirven a una población dada. Esto podría sugerir una solución de programación dinámica.
whuber

Respuestas:

1

es posible que desee utilizar la extensión Solver en Excel, la he usado varias veces en la programación de líneas.

Aquí hay un enlace en un curso intensivo en LP, utilizando Solver:

http://www.economicsnetwork.ac.uk/cheer/ch9_3/ch9_3p07.htm

GISdork
fuente
2
Es una buena idea y puede ser útil para jugar con pequeños problemas de juguetes. Desafortunadamente, Excel no está a la altura de esta tarea. Además de ser un problema demasiado grande para manejarlo, sería extremadamente difícil codificar las restricciones de conectividad en Excel: ¡debes asegurarte de que las aceras realmente conectan a las personas con el CDB!
whuber