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

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

## 1 Answer

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:

• I have a solution right now that implements a linear programming solution to construction projects. I want to improve on that by adding a spatial element to it. Thanks for the papers you provided, it's going to be a fun read. – dassouki Jul 23 '13 at 13:22
• Enjoy! and good luck – julien Jul 23 '13 at 15:11
• As I read through the papers you provided, what's your recommendation on connecting these models to an existing linear programming one? furthermore, do you know if any spatial optimization problems have been solved using python, arcpy or pyqgis? – dassouki Jul 26 '13 at 11:20
• I am still having troubles solving this problem! What I tried to do is assign the each road segment a `k` factor that ranges let's say between 0 and 1. 0 means that you can't alternate the time of the project and the closer you get to 1, the further ahead you can push or bring a project in from future years. Once I get to that stage, I am not sure on how to proceed. I am aware that it's an optimization problem but I can't pinpoint exactly how to solve it. – dassouki Oct 6 '15 at 12:33