# Monte Carlo simulation using QGIS and pgRouting on optimal sidewalk construction

I am new to spatial analysis and would appreciate some general direction on a project I am attempting, outlined below (I am starting from scratch).

GOAL: To find the best locations to install 2000 feet of sidewalks in my hometown in order to connect the most households to the Central Business District (CBD), where "connected" means within 1.2 miles walking of the CBD. I have shapefiles showing existing structures (households), roads, and sidewalks (already installed).

Here is my proposed solution / thought-process:

1. Convert the in-place sidewalk network into a database of nodes that are connected by weights (i.e. distances). Is there a way to directly do this in QGIS (or other program) by clicking on all intersections?
2. Calculate the number of households that are within 1.2 miles walking of the Central Business District (e.g. a lat-long point or polygon) using the routing capabilities of pgRouting or something else. This will be the base case "household access" value.
3. Using the road layer as a guide, randomly place an additional 2000 feet (say, in 10 foot segments) of sidewalks onto the sidewalk layer. This is the equivalent of constructing a bunch of new sidewalks arbitrarily.
4. Re-calculate the nodes and weights using the new pedestrian network as in (1), and then re-calculate the number of households that are now within 1.2 miles of the CBD as in (2). It should increase with the additional sidewalks. Save the locations of the additional sidewalks and the associated "household access" value to a file (e.g. spreadsheet).
5. Repeat steps (3) and (4) 10000 times, similar to a Monte Carlo simulation. Using the 10000 sets of data points, choose the sidewalk placement locations that maximize the number of households within 1.2 miles of the CBD.

Does this thought process sound realistic? Does anyone have any suggestions?

-- I would like to accomplish this using some combination of QGIS and R, however I am open to learning PostGIS and/or Python (or anything else) to achieve the goal. Any thoughts or direction will be helpful. Many thanks!

-
You might want to consider a genetic algorithm instead. That's almost the process you've described. I'm pretty sure there are python libraries that support genetic algorithms. – Chris Jan 23 '12 at 19:02
It looks like R has genetic algorithm libraries as well. – Chris Jan 23 '12 at 19:17
It's a great problem. However, most random placements of 200 10' sidewalk segments won't connect anything to anything else; you won't come anywhere close to an optimum in such an unguided way. May I suggest focusing your initial thoughts on how to formulate the problem abstractly (independently of any data structures or programming environment) so that you can (a) identify such issues beforehand and (b) remain open to the fullest range of solution methods available? It seems premature to be proposing one particular solution method. – whuber Jan 23 '12 at 20:03
Premature? I do not agree. Indeed, the thought process outlined above is one approach; I'm hoping it will focus any brainstorming and result in useful feedback. That said, I am open to the fullest range of solution methods available. Constraining the segments so that sidewalks would be placed in such a way as they always connect things would be straightforward to implement, and help with finding a solution. Thanks for the suggestion. – baha-kev Jan 23 '12 at 22:04
Well, if you back up a little and forget the randomization stuff, the kinds of questions that come to mind include: * What kind of optimization problem is this? What properties does it have? (E.g., linearity, convexity, quasiconvexity, etc.). * Does it have equivalent formulations, such as a dual? * Are there alternative ways to represent it, such as in terms of properties of graphs or with penalty functions? As an example, one dual formulation would be to minimize the total length of sidewalks that serve a given population. This might suggest a dynamic programming solution. – whuber Jan 23 '12 at 22:48