topic Re: Algorithm used by location-allocation (Maximize Coverage problem type) in ArcGIS Network Analyst Questions

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

SusannaRasasnen — Thu, 24 Mar 2016 07:53:46 GMT

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)?

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

DanPatterson_Retired — Thu, 24 Mar 2016 09:37:46 GMT

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.

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

JaySandhu — Thu, 24 Mar 2016 17:11:33 GMT

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:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.26.4638&rep=rep1&type=pdf

Regards,

Jay Sandhu