Simulation de Monte Carlo utilisant QGIS et pgRouting sur la construction optimale de trottoirs

17

Je suis nouveau dans l'analyse spatiale et j'apprécierais une direction générale sur un projet que j'essaie, décrit ci-dessous (je pars de zéro).

OBJECTIF: Trouver les meilleurs emplacements pour installer 2 000 pieds de trottoirs dans ma ville natale afin de connecter le plus de ménages au quartier central des affaires (CBD), où "connecté" signifie à moins de 2 km à pied du CBD. J'ai des fichiers de formes montrant les structures existantes (ménages), les routes et les trottoirs (déjà installés).

Voici ma solution / processus de réflexion proposé:

  1. Convertissez le réseau de trottoirs sur place en une base de données de nœuds connectés par des poids (c.-à-d. Des distances). Existe-t-il un moyen de le faire directement dans QGIS (ou un autre programme) en cliquant sur toutes les intersections?
  2. Calculez le nombre de ménages qui se trouvent à moins de 2 km à pied du quartier central des affaires (par exemple, un point ou un polygone lat-long) en utilisant les capacités de routage de pgRouting ou autre chose. Ce sera la valeur de base "accès des ménages".
  3. En utilisant la couche de route comme guide, placez au hasard 2 000 pieds supplémentaires (par exemple, en segments de 10 pieds) de trottoirs sur la couche de trottoir. C'est l'équivalent de construire arbitrairement un tas de nouveaux trottoirs.
  4. Recalculez les nœuds et les poids à l'aide du nouveau réseau piétonnier comme dans (1), puis recalculez le nombre de ménages qui se trouvent maintenant à moins de 2 km du CBD comme dans (2). Il devrait augmenter avec les trottoirs supplémentaires. Enregistrez les emplacements des trottoirs supplémentaires et la valeur "accès des ménages" associée dans un fichier (par exemple, une feuille de calcul).
  5. Répétez les étapes (3) et (4) 10000 fois, comme pour une simulation Monte Carlo. En utilisant les 10000 ensembles de points de données, choisissez les emplacements de placement sur le trottoir qui maximisent le nombre de ménages à moins de 2 km du CBD.

Ce processus de pensée semble-t-il réaliste? Est-ce que quelqu'un a des suggestions?

- Je voudrais accomplir cela en utilisant une combinaison de QGIS et R, mais je suis ouvert à l'apprentissage de PostGIS et / ou Python (ou toute autre chose) pour atteindre l'objectif.

baha-kev
la source
1
Vous voudrez peut-être envisager un algorithme génétique à la place. C'est presque le processus que vous avez décrit. Je suis presque sûr qu'il existe des bibliothèques python qui prennent en charge les algorithmes génétiques.
Chris
1
Il semble que R possède également des bibliothèques d'algorithmes génétiques.
Chris
6
C'est un gros problème. Cependant, la plupart des placements aléatoires de 200 segments de trottoir de 10 pieds ne relieront rien à autre chose; vous ne vous rapprocherez pas d'un optimum d'une manière aussi peu guidée. Puis-je suggérer de concentrer vos réflexions initiales sur la façon de formuler le problème de manière abstraite (indépendamment de toute structure de données ou de tout environnement de programmation) afin de pouvoir (a) identifier ces problèmes au préalable et (b) rester ouvert à la gamme la plus complète de méthodes de solution disponibles? Il semble prématuré de proposer une méthode de solution particulière.
whuber
2
Prématuré? Je ne suis pas d'accord. En effet, le processus de réflexion décrit ci-dessus est une approche; J'espère que cela focalisera tout brainstorming et donnera des retours utiles. Cela dit, je suis ouvert à la gamme la plus complète de méthodes de solution disponibles. Contraindre les segments afin que les trottoirs soient placés de telle manière qu'ils relient toujours les choses serait simple à mettre en œuvre et aiderait à trouver une solution. Merci pour la suggestion.
baha-kev
6
Eh bien, si vous sauvegardez un peu et oubliez les choses sur la randomisation, les types de questions qui vous viennent à l'esprit incluent: * Quel genre de problème d'optimisation est-ce? Quelles sont ses propriétés? (Par exemple, linéarité, convexité, quasiconvexité, etc.). * A-t-il des formulations équivalentes, comme une double? * Existe-t-il d'autres façons de le représenter, par exemple en termes de propriétés des graphiques ou avec des fonctions de pénalité? Par exemple, une double formule consisterait à minimiser la longueur totale des trottoirs qui desservent une population donnée. Cela pourrait suggérer une solution de programmation dynamique.
whuber

Réponses:

1

vous voudrez peut-être utiliser l'extension Solver dans Excel, je l'ai utilisée plusieurs fois dans la programmation de lignes.

voici un lien sur un cours intensif sur LP, utilisant Solver:

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

GISdork
la source
2
C'est une bonne idée et pourrait être utile pour jouer avec de petits problèmes de jouets. Malheureusement, Excel n'est pas à la hauteur de cette tâche. En plus d'être un problème beaucoup trop important pour être traité, il serait extrêmement difficile de coder les contraintes de connectivité dans Excel: vous devez vous assurer que les trottoirs connectent réellement les gens au CBD!
whuber