Location Allocation, type Maximize Capacitated Coverage is running slow, how to speed up?

325
6
Jump to solution
10-20-2021 01:51 PM
Ling-PoShih
New Contributor

Hi,

I'm using Maximize-Capacitated-Coverage as a way to distribute polling station so the voters don't have to walk 750 meters. The max capacity of a polling station should not exceed 1200 voters, so the counting process will be quickly done after the votes has been cast. 

There a 53 polling stations and about 66000 voters. I'm using arcgis pro 2.6.1 running on Windows 10 & VM Ware client. It takes now 24 hours to complete 81% (and still running). Does this suppose to run this long? How to speed it up? Will 2x stronger computer be 2x faster? Will GPU help? 

Because my other part of the city has 191 polling stations and 212000 voters. So I need more speed. 

Thanks!

Ling-Po

0 Kudos
1 Solution

Accepted Solutions
JaySandhu
Esri Regular Contributor

The Location-Allocation solver does not use a GPU or parallel computing. It first needs to compute the travel distances (over the network) for every candidate to every demand point within the cutoff. And then the capacitated solver needs to make sure that the capacity is not exceeded. That requires more work then the default Minimize Weighted Impedance problem type. 

Location-Allocation uses heuristics to solve the various problem instances and hard to say the complexity in terms of O notation. 

I would suggest solving with the default Minimize Weighted Impedance with 750 cutoff and seeing how long it takes for the problem to finish, and also if the resulting allocation already honors the 1200 demand. If it does not, see the max distance travelled. Maybe it will give you a better cutoff to use that will help reduce the problem space and help speed up the Maximize Capacity case.

Jay Sandhu

 

 

View solution in original post

6 Replies
JaySandhu
Esri Regular Contributor

You mention that you have 66000 voters and 53 polling stations. Are these the number of demand locations and candidate facilities loaded into the Location-Allocation layer? Or do you have larger set of candidate locations from which you are choosing to locate 53? You also have a cutoff of 750 meters and a capacity of 1200. Does each of the 66000 voter locations have 1 demand value? That is, in total there are 66,000 voters. So with 1200 capacity, you need at a minimum of 55 voting locations to satisfy everyone.

In general the speed of the Location-Allocation depends on how many candidates it has AND how many demand locations are within the cutoff. The bigger this number, longer it takes to solve.

So please give some more details as asked above.

Jay Sandhu

0 Kudos
Ling-PoShih
New Contributor

Hi Jay,

Are these the number of demand locations and candidate facilities loaded into the Location-Allocation layer? Yes

Does each of the 66000 voter locations have 1 demand value? Yes

We want to look for suitable places for mobile polling stations. 

Thanks!

Ling-Po

 

0 Kudos
JaySandhu
Esri Regular Contributor

Do you know approximately how many of the 66000 locations are within the 750 meter cutoff from any of the 53 polling locations? if there are a lot, perhaps you can reduce the cutoff to say 100 meters and try solving again.

I do not know the extent of your data, so you could try a different, more reasonable cutoff.

Jay Sandhu

0 Kudos
Ling-PoShih
New Contributor

Unfortunately, I can not change 1200 or 750. Is there a way in arcgispro to activate a GPU? Or parallel computing? Or use more memory or more cpu core? Divide in smaller batches? what will help to improve speed according to your experience?  What algorithm does arcgispro use in terms of big O notation? 

0 Kudos
JaySandhu
Esri Regular Contributor

The Location-Allocation solver does not use a GPU or parallel computing. It first needs to compute the travel distances (over the network) for every candidate to every demand point within the cutoff. And then the capacitated solver needs to make sure that the capacity is not exceeded. That requires more work then the default Minimize Weighted Impedance problem type. 

Location-Allocation uses heuristics to solve the various problem instances and hard to say the complexity in terms of O notation. 

I would suggest solving with the default Minimize Weighted Impedance with 750 cutoff and seeing how long it takes for the problem to finish, and also if the resulting allocation already honors the 1200 demand. If it does not, see the max distance travelled. Maybe it will give you a better cutoff to use that will help reduce the problem space and help speed up the Maximize Capacity case.

Jay Sandhu

 

 

Ling-PoShih
New Contributor

Thanks!

0 Kudos