The p-median model

hello we are moving on to another topic called the p median right which is not a coverage anymore uh but it is made out of two different components a location problem and an allocation problem so not only do we need to decide where we're going to locate the facilities we also need to decide how we how we're going to allocate each demand node or demand unit centroid whatever to the location so it's actually a very complicated problem to solve compared to maybe some of this coverage model that we talked about earlier in the class so i'd like to show you a little problem here and those triangles represent potential location for schools okay now each of these purple dots here represent a demand note and the question is if for instance i could afford to open all the facilities right so one two three four five okay that's very easy in this case i can open all of them right right here and then the next question would be how should the demand be allocated well the main objective of the p median is to minimize the distance or the travel now assuming here that the travel is sort of circular at euclidean what you can do is then assign each demand node or demand unit to its closest facility right so this one probably this one okay this one this one here this one for over here this one probably here let's see this one here this one here here here here this one here this one probably here here here like this so you're assigned to the closest one and this one for sure here and then this one maybe over here okay so those are also sometimes called spiderman now that's a pretty straightforward problem this one would be much harder to solve if p is equal to 2 which do you choose and i don't know the answer right we could do all this combination if we wanted to but let's assume that we have the you know optimal solution and let's suppose that this is the optimal solution right then you will see that generally right the demand node will be assigned to their closest facility so i'll just do this quickly here okay and maybe this one here like this okay now there are some issues and i say generally they're assigned to their closes but not always and that could be the problem when you have capacities right so schools for instance they work at a certain capacity so you may not always have this assignment to the closest open facility but that's a desirable goal so we'd like to introduce some new notation to our problem right um the new decision variable is x i j which is equal to one if i the main node i is allocated to facility j and zero otherwise we have this new uh variable although in the coverage model it was we use axis so now we just switch uh which is y sub j is equal to one if we open a j right so if the facility is selected 0 otherwise and then we have d i j which is the distance from i to j and then you also have p which limits the number of facilities another element that is relatively important is a sub i which is a d minor i and so it's not just gonna be okay each of these dots represent one unit right but we will be taking the demand into account like for the mclb we try to maximize the population that was covered here of course we're going to multiply the distance that you know the demand has to travel to receive service by by the demand of course okay so let's move into the formulation the formulation for the p median is this follow we're trying to minimize the weighted demand that is assigned to uh various facilities and we sum this up right so we sum up open demands and also over the facilities that's why you have two summation sign the next um equation here is the first constraint and it stipulates that each demand node must be assigned to one facility right at most one facility and at least one facility so that's why it's equal to one so no single demand node can be left unassigned here we're basically saying that if a demand node is assigned to a facilitated j then that facility must be open otherwise it's not it doesn't make any sense this one is also quite important this is sort of the upper budget where we are saying that the total sum of the facilities that can open should be equal to p you could also have less or equal to p and then you have the regular integer constraint a couple of things that i want to mention we're not taking into account capacity problems in this one okay we'll talk about this later and then here x i j should be zero one so this is quite important because a student cannot be sent fifty percent to a school and fifty percent to another school at least in before that's a that's an example right um so this uh could be um you know could become fractional uh in in other examples but but certainly not in this one of school for instance

Channel: Eric Delmelle

Views: 1,500

Keywords:

Id: ff7sCKhn1e0

Length: 5min 57sec (357 seconds)

Published: Mon Oct 05 2020