1
$\begingroup$

I am not a mathematician so please correct me if I am making any mistakes while explaining my problem (and please help me set the right tags as well because I am not sure what class of problem I am facing). While trying to solve it, I am also trying to frame the right question.

From some mobility data that I collected from an experiment I was conducting, I plotted the following spatial distribution graph for the area that I am analyzing. For about 30 people, this graph gives a distribution of how long each person spent in the area (which is a plane with dimensions 200x200). So for instance, over the period of observation (18 hours), the upper-left is the most visited region.

alt text http://i52.tinypic.com/33myia9.jpg

I am trying to place an experimental delivery service that has a proximity of 40m (circle) in the region is a way that it covers the maximum density region. The idea is that I have only a limited amount of resources and need to make the best use of them i.e. within the 40m proximity I should be able to cover the maximum number of people during the observation period.

I am guessing that my problem is not a new one and was hoping if someone could guide me in the right direction of understanding and solving this problem.

$\endgroup$

1 Answer 1

1
$\begingroup$

I am specialized in this at all, so there may be far better methods but here is one you could use.

I assume from that your data is discretized, so you are searching for an optimal position in a $200\times 200$ grid. You can simply start from a position $(x_0,y_0)$, not a too bad one if possible (like at distance ~$50$ from the upper left corner, in the diagonal direction). From here, you can perform the following algorithm: from a current position $(x_n,y_n)$, you compute the number of visitors in the disc of radius $40$ around the position (or use the previously computed value), and you do the same for the four positions $(x_n\pm1,y_n\pm1)$. Then you take as a new position $(x_{n+1},y_{n+1})$ the one achieving the highest value among the five investigated. If this means $(x_{n+1},y_{n+1})=(x_n,y_n)$ then you stop.

The default of this simple gradient method is that you can stop at a local minimum instead of a global one. There are methods to circumvent this issue (I am thinking about simulated annealing), but here your situation is so simple that you could apply it twice, starting at the two local maximums of your function, and that should be enough.

If you want to be sure to have the best location, you can also compute the number of people in each of the $40000$ discs of radius $40$; this seems in range of any reasonable computer. In fact, you can diminish a little bit the number of discs to be computed, since there is no use placing its center to close to the boundary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.