I have encountered an optimization problem that I would like advice on what types of methods I could use to solve it.
Let's suppose a town is represented by a Polygon. The town contains n points (addresses) according to the two parameters latitude and longitude. The goal is to determine a "hotspot" by selecting the best array of addresses.
Every address broadcasts a 300m signal, so the algorithm must find the ideal combination of points while minimizing its number.
For example: Town and points
So every point has a range of 300m, thus for this dataset we have: points and range
Here, I've made a classification so useless zones are deleted. If I proceed to a simple calculation we have: Final representation
With:
- Covered Area: 0.0005055475481536275
- Total area: 0.0007334658607563916
- Relative coverage: 68.92584579632353
- Computation delay: 96.36 sec
So, the project is to consider all the addresss from a town, then finding an optimisation algorithm that selects the best hotspots that cover 100% of the area.
I hope that my explanation was clear enough. What are methods that could assist me in this? Some algorithms that could be adapted to my problem? I have attended optimization and operations research courses, but for this problem, can't find a shoe fitting on my foot.
Thank you for you help!
Suppose that the total area of the greyed land is denoted by the constant LA.
Let the collection of addresses be denoted as a list of elements $n_{ij}$ where $i$ corresponds to the latitude of each address, and $j$ corresponds to the longitude of each address. We’ll also need to represent $n_{ij}$ as a binary value on whether the model selects the address $n$ or not.
In addition, let $m_{a_{ij}}$ denote the euclidean points in terms of (lat, long) of each address.
The area of each signal from an address is $300^2\pi=90000\pi$. Of course the address near the boarder of the map will need to be accounted for and have their total areas reduced by the amount they overflowed over the edge. We can then denote the total area of the signal of each address by an list of elements $A_{ij}$ where $i$ denotes the latitude of the address and $j$ denotes the longitude of an address.
Let $N$ be a constant integer value for the allowable total amount of hotspots to be turned on at once. This will be allowed to change per iteration, as the first goal of this model is to cover the most area, and the next goal of the model is to use the minimal amount of addresses to cover that same amount of area.
Then we can proceed to find the minimum amount of addresses by using a rough template minimization model of the sort:
$$\text{Minimize } z = LA -\sum^{|n_i|}_{i=0}\sum^{|n_j|}_{j=0}A_{ij}\cdot n_{ij}$$
Subject to: $$\sum^{|n_i|}_{i=0}\sum^{|n_j|}_{j=0}n_{ij} \le N $$ $$\sqrt{m_{a_{ij}} ^2+ m_{a_{ij}} ^2}\ge300\text{ }\forall ij\text{ where } i\ne j$$
$$\text{where } n_{ij}\in\{0,1\}\text{ }\forall ij$$
However, this is definitely not the best way to do this, but it would be a start in the right direction towards what you want to do. A reason why this model is not the best is due to the second constraint. There, it’s saying that the distance per address must be greater or equal to the radius of a signal to prevent overlapping. This will cause issues if the address is a boarder address, or that the optimal solution will probably have overlap. However, this would produce an "acceptable" solution. In other words, this will give you a platform to start.