Continuous Facility Location with Visibility Constraints

UPDATE (9/13/09): It looks like someone has already studied a very similar (or even the same) problem.

Like many other universities, the University of Miami has a number of emergency phones spread all over its campus. They are called blue-light phones because of the (you guessed it) blue light that turns on right above them at night. Here’s a map of the phone locations on campus.

Now consider the following “facility” (or resource) location problem inspired by the blue-light phones: given a street map, including building locations, we want to place “facilities” along the streets so that, no matter where you are on the map, (i) you can always see at least one facility, and (ii) the facility closest to your location is never more than L feet away. The objective is to satisfy the two conditions above while minimizing the number of facilities to install. In our case, we can assume that the dimensions of the facility/resource are negligible. It’s not hard to imagine other application domains where this problem would be relevant.

This is an interesting modeling exercise. One may be tempted to discretize the space and only consider a finite number of possible facility locations. However, I believe you should allow the facilities to be placed anywhere (i.e. use continuous variables) within each one-dimensional street segment, which apparently makes it harder to model.

I think the placement of UM’s blue-light phones could be greatly improved. It certainly violates condition (i) which, in my opinion, is crucial. Anyone interested in giving this problem a shot? It would certainly be a very interesting undergraduate research project (graduate as well, depending on how far you want to go).


Leave a comment

Filed under Applications, Modeling, Research

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s