ArcGIS 10.2.2 - What would be the best approach for applying minimum spanning tree or Steiner tree logic to solving a network?

Incidents: 100, Facilities: 20 Goal: Connect any subset (n-incidents of 100) to any 20 facilities that create the least cost network.

I want to find the best route to connect any n-incidents, say 80, of the 100 incidents to any facilities using the least route distance? It would be a no-circuit network that would use only the facilities necessary to connect the best 80 incidents. I've found some information but don't fully know how to implement the process.

  • Clarification: It is a single route you are after, it starts and ends at one of the facilities. Furthermore select only 80 incidents out of 100. Correct? – Uffe Kousgaard Aug 16 '14 at 5:26
  • As requests for clarifications are made via comments a good (I think the best) way to respond is with revisions to your question to make it easier to understand and answer. That way the question stands alone rather than requires a trail of comments to be read. – PolyGeo Aug 16 '14 at 6:53
  • Now the question has been completely changed, so my question and answer looks a bit strange. Much more than a revision. – Uffe Kousgaard Aug 18 '14 at 6:26

As stated in another answer, this is a type of Steiner Tree problem. The problem is NP-Complete (basically meaning you can't solve the best possible solution in any reasonable amount of time). You would need to approximate the solution - there is no tool within the ESRI platform to do this for you directly.

The closest "out of the box" tool I've found to do this would be ESRI's backhaul optimization:

For this, the number of incidents (N) would need to be a constant, but the solution would naturally choose only the best facilities. The solution works by performing closest facility from each incident to any other incident or facility. This gives a decent approximation of the answer, though it definitely will not be the best possible answer and could be pretty far off.


It is a kind of "steiner tree" problem you are trying to solve. For which you need a heuristic. You need to look way beyond ArcGIS. Further details: http://en.wikipedia.org/wiki/Steiner_tree

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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