Which spatial bundling or grouping algorithm optimally groups elements by attribute?

Question

As I delve deeper into GIS, I find myself trying to improve efficiencies of certain procedures and processes.

The one process I'm working on now is spatially scheduling construction projects. For example, consider the two construction schedules outlined in the images below. The first one is perhaps the defacto non spatially planned schedule; however, the second, is more optimal and due to bundling of contracts would be cheaper as well.

This is easy when the network has 30 links; however, the one I am working on has ~50,000 links.

Question: What should I read upon or learn to implement such algorithms? Further more, are there any application type paper that you can reference to help my understanding on the matter?

Which GIS algorithm can I use to move the schedule from above to something similar as in the bottom image?

Note: I'm not looking for a software tool to do the work for me, I'm looking to understand the process and perhaps implement it as a plugin in QGIS or ArcGIS

Answer 1

Very nice problem indeed!

I good approach might be to build an explicit cost function returning a cost estimation for a given construction schedule - the 'best' construction schedule might then be obtained using optimisation techniques to minimise this cost function. What you might need are:

• Criteria to build the cost function. You should list what has an impact on the final cost and makes a given construction schedule better than another. According to the figures, these criteria should include cost data given by the constructor quotations. Trivial measures such as the link length and topological relations should certainly be used. You might have a look at some spatial analysis measures traditionally used in road network generalisation algorithms, especially network links topological proeminence measures based on graph theory, and also the notion of strokes:

  Thomson, R. C., 2006. The 'stroke' concept in geographic network; generalization and analysis. In: SDH'06

  Touya, G., Oct. 2010. A road network selection process based on data enrichment and structure detection. Transactions in GIS 14 (5), 595-614.

  Mackaness, W. A., and Beard, M. K. (1993), Use of Graph Theory to Support Map Generalization. Cartography and Geographic Information Systems, 20, 210 - 221

  Zhang, Q., 2005. Road network generalization based on connection analysis. pp. 343-353.

• An optimisation method to determine what is the best schedule to minimise the cost function. Typical optimisation methods such as hill climbing, simulated annealing or why not genetic algorithms could be used. See wikipedia or Russell and Norvig's book (chapter 2).