Algorithm used by location-allocation (Maximize Coverage problem type)

03-24-2016 12:53 AM
New Contributor

Which algorithm does the location-allocation Maximize Coverage problem type use? I already found on the ArcGIS help that location-allocation uses a vertex substitution heuristic to solve the p-median problem (Teitz and Bart), but I didn't find, which algorithm the Maximize Coverage uses. Is it also solved as a p-median problem (Teitz and Bart)?

0 Kudos
2 Replies
MVP Esteemed Contributor

esri normally doesn't specify which algorithms they use, but you could try going to help file link for a topic and on the bottom right, there is a "Provide Feedback link".  You could send a message there stating that you would like to see a reference to the describe the method used for the tool.  They may respond... otherwise, you are left with doing a trial and error should there be alternatives.  I would check your reference link to see if the methodology is applicable in different scenarios.

0 Kudos
Esri Regular Contributor

The algorithms used by Network Analyst are described here:

Algorithms used by the ArcGIS Network Analyst extension—Help | ArcGIS for Desktop

As discussed there, for Location-Allocation, we use a vertex substitution heuristic to solve the p-median problem. And we use a process called Hillsman editing to first transform a particular problem type such as Maximize Coverage to a P-median and then use the same heuristic.

Here is a reference to the original paper by Ed Hillsman:

Hillsman, E.L. (1984). The p-median structure as a unified linear model for location-allocation analysis. Environment and Planning A, 16 (3), 305-318

And here is another researcher using a similar approach:


Jay Sandhu