17

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.

Improve this question
6
  • 1
    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
    Commented Jan 23, 2012 at 19:02
  • 1
    It looks like R has genetic algorithm libraries as well.
    – Chris
    Commented Jan 23, 2012 at 19:17
  • 6
    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
    Commented Jan 23, 2012 at 20:03
  • 2
    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
    Commented Jan 23, 2012 at 22:04
  • 6
    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
    Commented Jan 23, 2012 at 22:48

1 Answer 1

Reset to default
1

you might want to utilize the Solver extension in excel, I have used it a few times in liner programming.

here is a link on a crash course on LP, utilizing Solver:

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

Improve this answer
1
  • 2
    It's a nice idea and might be useful for playing with small toy problems. Unfortunately, Excel is not up to this task. Besides being far too large a problem for it to handle, it would be prohibitively difficult to code the connectivity constraints in Excel: you must make sure that the sidewalks actually connect people to the CBD!
    – whuber
    Commented Mar 5, 2012 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.