the algorithm of location allocation (MINIMIZE_FACILITIES)

Question

Hi,

I need to understand the algorithm behind location allocation (MINIMIZE_FACILITIES). Does anyone know the details about that. The one on the GIS help website is not enough.

Basically, I need to know how GIS minimizes the number of the locations.

I suppose GIS first calculates (records) all feasible demand points a specific facility can cover within the cutoff time (this step can be done by service area). Then the GIS minimizes the total facilities number. So for the second step, does GIS use integer programming or some other ways to solve that?

Hope someone can provide some help.

Thanks a lot.

Li

LiZhang · Answer

Hi Jay,

Thanks a lot. This is really helpful.

Li

The help on Minimize Facilities here:
http://resources.arcgis.com/en/help/main/10.1/#/Location_allocation_analysis/004700000050000000/

Says

So it is a set covering but what it does is starts with an estimate of the number of facilities needed and internally calls a variation of maximize coveraege to quickly and intelligently narrow down the number of minimum facilities needed and then finishes by running maximize coverage with the minimum facilities needed to populate the results.

Regards,
Jay Sandhu

JaySandhu · Answer

The help on Minimize Facilities here:
http://resources.arcgis.com/en/help/main/10.1/#/Location_allocation_analysis/004700000050000000/

SaysMinimize Facilities is the same as Maximize Coverage but with the exception of the number of facilities to locate, which in this case is determined by the solver

So it is a set covering but what it does is starts with an estimate of the number of facilities needed and internally calls a variation of maximize coveraege to quickly and intelligently narrow down the number of minimum facilities needed and then finishes by running maximize coverage with the minimum facilities needed to populate the results.

Regards,
Jay Sandhu

LiZhang · Answer

Li,

The ArcGIS Location-Allocation does not use any integer programming to solve this complicated combinatorial problem. It uses heuristics. The LP approach cannot be used to solve lvery arge problems and can take too long to converge to a good solution.

Details about the algorithm are listed here:
http://resources.arcgis.com/en/help/main/10.1/#/Algorithms_used_by_the_ArcGIS_Network_Analyst_extension/004700000053000000/

Jay Sandhu

Hi Jay,

Thanks for that. I understand if the problem is combinatorial problem of the type N Choose P, that would use heuristics. But the 'minimize_facilities' seems not in that category, more like a set covering problem, to minimize P.

It mentioned

In addition, the location-allocation solver has options to solve a variety of location problems such as to minimize weighted impedance, maximize coverage, or achieve a target market share. Heuristics are used to solve the location-allocation problems.

which didn't include the 'minimize_facilities'.

So I am kind of confused about this.

Li