In today’s lecture, we address location
and layout. Location essentially deals with, where we want to locate the facilities and
layout deals with, how we locate the other facilities inside, once the location is chosen. So, we are going to see two things, one is called location, which answers the larger
question of, where do we where do we locate a facility and layout, how do we relatively locate facilities inside a choosen location so we ask two questions, one is on location and the other is on layout. Now, location decisions are important as well as the layout decisions are. Location decisions are strategic in nature and location decisions mostly are qualitative in nature, even through several quantitative models are available
for location. The decision on location would also depend on many qualitative factors, some of which we will see now. The first important decision is raw material, if we are looking
at locating a manufacturing plant or a facility, which is raw material intensive, then it is
customary to locate these near the places, where we have raw material is available.
Sometimes, location decisions are also based on labor availability. Areas where labor is
abundantly available and labor is not very costly. Sometimes, location of facilities
also happens near the demand areas, particularly retail stores, banks, etcetera are all located
near the demand area. Sometimes, locations are also made based on transportation decisions for example, near a sea port, depending on the amount of material that come in and have to be transported. Sometimes, the location decisions also depend on the policies of the government. Governments can give subsidy to locating certain types
of industry in certain areas. Certain areas in the state are declared as areas that are
suitable or that are allocated for location of manufacturing plants and people who choose to locate plant there, would get certain benefits and subsidies on tax, etcetera. So, these
are other things that force the manufacturing and other organizations to locate plants in
certain areas, depending on the policies of the government. Now, the location decisions also become slightly different when we want to locate public facilities such as a police station or a fire station, etcetera. In such cases, the reach becomes
a dominant factor and we try to locate them in such a way that, the time or distance between the place, where these central facilities are located and the farthest customer is minimized. So, it will be like a mini max problem, where we try to minimize the maximum distance between the location and any one of the customers. Now, in addition to these qualitative factors,
there are other quantitative models that are available for location. And in this lecture
series, we would concentrate a little more on the quantitative models that are available for location as well as for layout. So, the first model that we will see is called
the p median model and this model originated from location and layout, though this has
several useful applications. Now, the p median model is like this, and suppose we have 8
points, say we call them 1 to 8. Now, from the location point of view, what we are interested is, is there are 8 points and these 8 points represent demand areas or 8 customer demand areas, where we do locate the facilities such that, we are able to meet the demand with minimum distance of transportation. Now, as far as the p median problem is concerned, to begin with we may say that, there are 8 points and the coordinates of these 8 points are known. So, we can also have a distance matrix d i j between points i and j, so d
i j will represent the distance between i and j. Now, let us assume that, these 8 points represent 8 demand points or areas where the products are required. And we wish to locate, let us say p facilities, let us say 2 facilities such that, we produce in these two facilities and we meet the demand in all the 8 facilities with minimum transportation distance.
Example, if we decide to have say 5 and 3 as the two facilities, if we decide to do
that then we say we are going to locate facilities in these two points. And we will say that,
we will find out, to which facility the remaining six points are to be attached such that, there is minimum distance. So, if we fix 3 and 5 then we will attach 1 to 5, because 1 to 5
is assumed to be lesser than 1 to 3, 2 will go to 3, because 2 to 3 is lesser than 2 to
5. Let us say 4 will go to 5, 7 will go to 5, 8 will also go to 5 and let us say, 6 goes
to 3, because 6 3 is lesser than 6 5. So, if we fix 3 and 5 as the two places, where we are going to locate the facilities then based on minimum distance we may say that, 1 4 7 and 8 will go to 5 and 2 and 6 will go to 3. Now, at the moment, we are not looking at, what are the demands in these eight places or we may assume that, the demands are equal. We are not looking at, when we locate a facility in 5 and attach 1 4 7 8 as well as 5 to itself,
we assume that, this facility will have enough capacity to meets the demands of all the points that are attached to it. So, this being a first model, we are not looking explicitly at what is the demand and what is the capacity or alternatively we assume
that, capacity is enough to meet the demand of all the points that are assigned to it
and therefore, the decision is based only on minimum distance. Now, these two are called the median points and since we are talking of p medians, this problem is called the p
median problem. Now, this problem can be formulated as a binary integer programming problem, which we will see right now. So, we will assume now that, we will have
X j j equal to 1 if point j is a median and X i j equal to 1 if a non median i is attached to a median j, so X j j equal to 0, otherwise automatically follows. Now, since we have
defined X j j equal to 1 if point j is a median, for this feasible solution, we would have
X 3 3 equal to 1 and X 5 5 equal to 1. Now, there are 8 possible values of X j j and if there are m general points, there are m possible values for X j j. So, the first constraint would be that sigma X j j, j equal to 1 to n is equal to p, so
in our example, j equal to 1 to 8, X j j equal to 2 and this feasible solution has X 3 3
equal to 1, X 5 5 equal to 1, so for p equal to 2, this will be satisfied. The next constraint is the non medians 1 2 4 7 6 and 8 will have to attached to some median. So, we write this as a constraint, which is like this, sigma X i j, i equal to 1 to n equal to 1, this
is j equal to 1 to n for every i. Now, there are 8 points here, now each point is attached to only one other point, which could be itself or it could be some other
point. So, as far as this solution is concerned, X 1 5 is equal to 1, X 2 3 is equal to 1,
X 3 3 is equal to 1, X 4 5 is equal to 1, X 6 3 is equal to 1, X 7 5 equal to 1 and
X 8 5 equal to 1. So, if I take a particular i then for that i, it has to be attached to
only one j, which could be itself or it could be some other point. Then we have another constraint, which is called X i j, should be less than or equal
to X j j for every i j. This means, that a non median i can be attached only to a median, this tells that, every point whether it is a median or a non median, is attached to only one point. If it is a median then it is attached to itself, which comes out of this. If the
point is a non median then it can be attached only to another median, but it is attached
only to one point comes from here. And from here it says that, if it is a non median,
it has to be attached only to a median for example, if we take this solution, 1 is a
non median. If 3 and 5 are declared as medians, we cannot have X 1 2 equal to 1, because X i j as less than or equal to X j j. So, since 3 and 5
are medians, X 3 3 equal to 1, X 5 5 equal to 1, but X 2 2 is equal to 0. Since X 2 2
equal to 0, we cannot have X 1 2 equal to 1, X 1 2 has to be 0, because X i j is less
than or equal to X j j. Therefore, a non median point 1 can only be attached to either 3 or
to 5, so it will be attach, so either X 1 3 will be equal to 1 or X 1 5 equal to 1,
so that way for a non median point 1, this will be satisfied, this would also be satisfied. This will ensure that, a non median point 1 does not get attached to more than one point or more than one median. This will ensure that, it will get attached to only one median and cannot get attach to a non median point, so all these are taken care of, by this set
of constraints. So, the objective function now is to minimize d i j X i j, where the moment there is a link
X i j, there is a distance that is going to be travelled. So, we want to minimize the
sum of the distances, so obviously d j j is 0, distance between a point and itself is
0, so we want to minimize the sum of d i j X i j. So, in this example with 8 points and 2 medians, there will be 6 distances whose, sum we try
to minimize. Or essentially, what we try to minimize is, if there are, these are the two
median points and if we take the remaining 6 non median points and assign them to the median with minimum distance, we are automatically minimizing the d i j X i j. So, the objective
function double sigma d i j X i j would take care of, minimizing the distance between the non median points and the median points under the assumption that, every non median point is attached to only one median point and that distance is taken. So, as a binary integer programming, so X i j equal to 0 1, so if there are n median
points, there are n square variable, n square decision variables. Now, there are n constraints here, one for each point, there is one constraint there is one constraint here and there are n square constraints that come from here for every X i j. So, this will be 1 plus n plus n square constraints in this
formulation. This formulation can also be seen as, given 2 seed points, the problem
is to allocate the rest of the non medians or non seed points. The medians acts as seed points, so given 2 medians or p medians, the problem of it
is to find out, how the non medians are allocated to the medians such that, the distance is
minimized. So, the thumb rule is, allocate or assign each non median to the closest median. So, given the median points, getting this other rest of the solution is very easy and
it is not very difficult at all. The real issue in the p median is, how do I find the
correct median points? Now, if there are 8 points and if we want
2 medians, we are looking at 8 C 2 ways of actually creating the medians. And for each
median set that contains p medians, the remaining n minus p non median points are allocated
to closest median. So, the problem is about, essentially enumerating if necessary, all
the n C p ways of getting p medians out of n points. Now, this problem is also a difficult problem to solve from a binary integer programming
point of view and many times, heuristic solutions are given to solve this problem. So, we will
look at one heuristic solution to this problem and also we will compare that heuristic solution with an optimum solution to this problem. So, let us take 6 points, instead of 8 and
the distance matrix among these six points is given here. Now, we can assume symmetry, so distance between 1 and 3 is 18 distance between 3 and 1 is also 18. So, let us try
and solve this problem for p equal to 2, now if we take for example, 1 and 2 as the two
median points then the non median points 3 4 5 and 6 will have to be allocated to the
two median points 1 and 2. So, for 3, the minimum distance 3 to 1 is 18, 3 to 2 is 22,
so the two median points are here. The non median point 3, 3 to 1 is 18, 3 to
2 is 22, so 3 goes to this with value 18. 4 to 1 is 14, 4 to 2 is 18, so 4 goes to 1
with 14. 5 to 1 is 16, 5 to 2 is 30. So, 5 also goes here with 16. 6 to 1 is 12, 6 to
2 is 26, so 6 also goes here with 12. So, we get the solution with facility located
in 1, will meet the requirements of 1 3 4 5 and 6, facility created at 2 will meet the
requirements of 2 only and the total distance will be 8 plus 4, 12, 18 20 2 6, so total
distance will be 60, if we look at this solution. Now, let us look at another solution for p
equal 2, now we have not given the coordinates of the 6 points, but we are given the distance matrix among the six points, but let if we assume that, there are some six points, which are like this. And we are interested in two medians, if we choose the two medians here then we realize that, we may not get a very good solution. Whereas, if we choose one of these as median and one of the other three as another median then we automatically get a solution, which is slightly better than choosing two medians that are near each other. So, a simple thumb rule is to choose medians that are far away from each other so that,
they can attract other points, which are nearer to them. So, using this, we can look at the
largest number in this matrix, which happens to be 32 for 3 and 4, so choose 3 and 4 as
the two medians. So, the two medians based on a thumb rule will be X 3 3 equal to 1 and
X 4 4 equal to 1. So, thumb rule is to choose two points, which are farthest away as two
medians. Now, when we do this, we have the two medians 3 and 4, the non medians are 1 2 5 and 6, so 1 to 3 1 to 4, so 1 will go with 4 with
distance equal to 14. 2, 2 to 3 and 2 to 4, so 2 will also go to 4 with distance equal
to 18. 5, 5 to 3 is 20, 5 to 4 is 20, so let us put 5 here with 5 to 3 as 20 and 6, 6 to
3 is 22, 6 to 4 is 22. So, let us put 6 here, so 6 is 22. So 18 plus 14 is 42 62 64, distance equal to 74. So, we would now end up locating two medians, which are at 3 and 4, the location at 3 will meet the requirements of 3 5 and 6, the location at 4, would meet the requirements of 1 2 and 4. Now, if we compare this arbitrary solution
here with this, we realize that, this seems to be better than this. So, the thumb rule
base solution did not work very well for this particular type of data. Now, if we try and
solve this problem as a binary integer programming problem with, as I said n equal to 6, so there are 36 decision variables. And then we have 36 plus 6, 42 plus 1, 43
constraints we would get the optimum solution X 1 1 equal to 1 and X 2 2 equal to 1. So,
the optimum solution has 1 and 2 as median points and we have already calculated the
assignment of the non median points with 1 and 2 as median points and the solution is
shown here. So, with 1 and 2 as median points, the optimum solution is 3 4 5 and 6, all of
them get attached to 1 and 2 is by is itself. So, point 2 will meet the requirement of customer number 2, which is itself and point 1 will meet the requirements of 1 3 4 5 and 6 with distance traveled equal to 60. So, the p median problem also can be solved, let us say for 3 groups, in which case we would put X j j equal to 3. So, 3 out of the
6 will become medians and the remaining non medians will then be attached to the chosen medians. Now, in that case, there are can be 6 C 3 ways of trying to fix the medians,
after which fixing the non medians becomes easy, because each non median will get attached to that median point, with which it has the least distance. But then if we want this thumb rule based algorithm to find out based on a thumb rule, three different median. It is customary to take the largest distance and those two points as the first two medians. Now, going by what we saw here, all the three medians have to
be away from each other, for them to attract points that are nearby. So, the third median
that we should choose should be such that, it is far away from the first two chosen medians. So, generally another thumb rule is used, where if points i and j have distance greater
than the average distance of this then they qualified to be medians. So, using this thumb rule, we can chose three points such that, their mutual distances are
all greater than the average, that way three median points are chosen and the non medians can go and get attached to the medians. In any case, solving this problem optimally for
p equal to 3, would give us the best allocation for a three median problem out of this given data. Now, there are two more aspects that have to be looked at in the p median problem.
Now, one of which is, the p median problem is also seen as a way to group points or to
group entities, where distances among these points or similarities among these entities
are given. Another way of looking at it is, I have 6 points here, I want to make them
into two groups or two clusters as they are called such that, the distances are minimized.
Now, we would say after solving a p median problem that, points 1 3 4 5 6 will become
one cluster and point 2 will become another cluster. Now, if distances are not the criteria for clustering and some similarities are the criteria for clustering then the p median problem now will become one of maximizing s i j X i j,
where s i j would be the similarity and the rest of the constraints will remain the same. So, p median can be seen as some kind of an optimization problem to cluster points or
entities, that is another application in use of the p median problem. Second is, as I mentioned in the beginning, when we looked at say these six points, assuming that these are the six
points, we are not looking explicitly as what are the demands. We are also assuming that, if we have these two points as medians, say and locate facilities,
the cost of locating the facility at any median point is the same. And therefore, it is not
going to influence the choice of the location, the choice of the location is merely influenced
only by the distance between the median and the non medians, which also means that, the cost of location in any of the six points is the same. The demands are not explicitly
taken, which is also can be assumed that, the demands are the same in all the six points. Capacities are not explicitly taken which means that, we have assumed that, capacity is a either infinite or each median when a plant is located there, has the capacity to
handle the requirement of all the six points. So, p median can be seen as a location model with certain assumptions that, the cost of locating in every facility is the same, demands are equal and when a facility is located, it will have the capacity to meet the requirements of all the customers or all the points. Each point here acts like a customer, so obviously the next location model will be like, if I have some demand points and if I have some potential location points, where do I locate, with some restrictions on capacity, with some different requirements at different points and with different costs of locating the facility. Now, such a problem is called the fixed charge problem or it is called a location allocation
problem that we will see now. Now, in a fixed charge problem or a location allocation problem, we may say that, say we have three potential locations, where we want to locate a facility and let us say, there are 8 customer points that are there. Now, let us say that, if we choose to locate a facility in point i, we choose to locate a
facility in point i, i equal to 1 to 3, there is a fixed cost of locating a facility, which is given by f i. We could also say, that there is a capacity which is C i, which is the maximum that this facility can produce. Now, there are say 8 demand points and there is a demand D j in point j, which has to be met. Now, the products are made manufactured in these facilities and if let us assume a single product for the sack of convenience
then there is a unit cost of transportation between i and j, which is C i j. Let us assume that, this is upper case C, which represents the capacity and this is the lower case C
i j, which represents the unit cost of transportation from i to j. Now, the question is, if I want to locate say 2 facilities such that, I have enough
capacity to meet the demands and I am able to meet the demands at minimum cost of locating
the facility and distributing it or transporting it from the chosen facilities to the demand
points. Now, for this problem, the formulation is
as follows, Y i equal to 1 if location i is chosen and X i j is the quantity transported
from i to j. So, the objective function has two costs, costs of location and costs of
distribution. Now, this distribution is also called allocation, where in the located facilities, how much of this capacity that is available in the located facility, is allocated to meet
the demands of each of these points. So, this problem is also called location allocation problem. It is also called a fixed charge problem, because this problem explicitly assumes that, there is a fixed cost or a fixed charge of locating facilities. So, it is called fixed
charge problem, it is also a called location allocation problem. So, the two components of the objective function are the fixed cost, which are the location cost and the transportation cost, which are the allocation costs. So, the location costs are sigma f i Y i,
i equal to 1 to m, there are m possible places, Y i equal to 1 if it is chosen and therefore,
there is a fixed cost, plus there is an allocation cost sigma C i j X i j, i equal to 1 to m,
j equal to 1 to n. So, here, n is equal to 8 and m is equal to 3, so whatever is allocated from i to j, there is a transportation cost. Now, we can have a constraint, if we say that, we want to allocate a exactly 2 facilities then we would have a constraint sigma Y i
is equal to 2, i equal to 1 to m. Now, with every facility, there is a capacity
C i, so whatever goes out of the facility, should be less than or equal to it is capacity. So, if I take this facility then X i j summation over j, whatever goes out of this to the various destination points should be less than or equal to it is capacity. So, this should be
less than or equal to C i Y i, the C i is the capacity and Y i comes, because only when Y i is equal to 1, this capacity is available when the facility is located there.
So, if this is not chosen then nothing can out of it, because the right hand side will
becomes 0, all the corresponding left hand sides will have to be 0. Now, as far as each
demand point is concerned, whatever it receives should be greater than or equal to the demand there. So, sigma X i j summed over i is greater than or equal to D j and then we will have
Y i and X i j - Y i is binary and X i j greater than or equal to 0, X i j need not be declared as a binary variable. So, this is the basic location allocation
problem or a fixed charge problem. Many times it is not necessary to have this constraint,
whereas this is an additional further binding on this. Sometimes, unless we are very sure about this constraint, this constraint can actually harm the optimization. For example, if sum of all these demands, let us say is 10000 and let us say the capacities are 4000 each, so automatically we need to locate in all the three places. If we put a restriction that we need only 2 then it will be becoming infeasible, because the capacities will not able to meet the demands. So, unless we are very sure about capacities as well as demands, or unless we have some very binding constraints that we do not want more than a sort of number then we do not use this. We use this, only when we have some other additional restrictions that we want locate exactly a certain number or we do not want locate more than a certain number, otherwise this can be left out and this is enough.
It will automatically ensure that, minimum number of facilities will be located, because locating an additional facility is going to increase this f i Y i. So, the problem will
automatically find out the correct number of facilities to be opened such that, this
cost is minimized. Now, there is another variation to this problem or variant to this problem,
now if we look at this problem, the way this is formulated. Now, we can have a situation, where both these facilities are opened and both these facilities transport to this.
So, this does not assume that, every customer is attached to only one facility, which was
the assumption in p median. Every customer or every non median point was attached to
only one median point; here we can have situations, where both two facilities can actually supply to one particular customer. Many times this is desirable, but sometimes it is also necessary to have each customer being supplied from a dedicated facility or each customer is attached purely or entirely to only one facility. So, we would bring that also into the optimization. The model slightly changes, where Y i equal to 1 if facility i is located are chosen, X i j equal to 1 if demand j or demand at
j is met entirely from i. So, the objective function will be to minimize sigma f i Y i plus sigma C i j X i j D j,
because C i j is the unit cost of transportation, the entire D j is transported, so D j into
X i j will be the total quantity that is transported. Now, these two constraints will be, for every facility that is chosen, summation over j D j X i j is less than or equal to C i Y i.
So, if a facility is located here let us say, wherever it supplies, it should be able to
meet the entire demand of the customers to which there is supply from this place. So,
C i Y i is the actually supply, because that supply exist only when Y i equal to 1. Now,
if this one is supplying to these three customers, when we should be able meet to D 1 plus D
2 plus D 3, which is given by sigma D j X i j, it is less than or equal to C i Y i.
Then you will have sigma X i j equal to 1, for every j summed over i, because every demand point will receive the entire thing only from one supplier. So, sigma X i j equal to 1 for every j and in this case, Y i X i j both are binary, so
this is the variation or variant of this model, where all the demand of a customer is met
from only one supply point. And this is a more generalized version, where a supply point can meet the demands, part demands or full demands of more than one customer. So, here in this case, we can model a situation, where this will supply to this and this or more
importantly, this can get from this and this. Whereas, in the second model, this can get
only from one of the chosen points, so these are the two variations in the fixed charge
problem or location allocation problem. We explain this further using a numerical illustration and we will see that in a next lecture.
