ÿ Coordination
of the cities and the distances between them:
ÿ In the approach of getting the
distances between the cities, on Turkey's City map we originated the (0,0)
point, the origin, onto the left top corner. Then, we calculated with a ruler
the X and Y coordinates of each city (52 cities, including the towns) distinctly.
Also from the scale of the map, that is 2.1cm = 50 km, we manipulate those data
into the unit of kms. Distance between cities is taken as Euclidian and the K
factor is taken as 1.15. When we come to the point of determining the distances
between the cities, is really hard with a hand calculator because there are
51*50 (for 52 cities) calculations. But with the help of the insertion of
formula in the cells of an excel sheet the problem is tackled. You can see the
coordinates in cm and in km`s at Appendix 1 and also the
52*52 distance matrix Appendix 2.
After determining the coordinates of each city in kms,
we grouped the cities into 19 subgroups, taking into account the geographical
nearness and weights of each city step wisely, since Lingo can not handle this
much of variables in the 52*52 matrix. As you know Lingo software allows 500
variables and 1000 constraints. The primal criteria in grouping are as follows;
we summon the less weighted cities to the larger weighted cities and then
conclude with 19 subgroups. And sometimes during grouping we had another
criteria, which was: some cities like Diyarbakir, Konya that have also higher
weights are not grouped because according to our assumptions we decided to take
them as single.ÿ In grouping there is
another important fact which is collecting cities around a higher weighted city
may be wrong in sometimes according to their coordinates because if the center
which has the highest weight is not near to the center of the group then that
grouping will not be exactly correct. In fact groupings should also be done by
optimization but again we needed to define Xij`s in which i changes from 1 to
52 and j changes from 1 to 52 so we could not find the optimum grouping. So our
grouping can be taken as an assumption. As we have taken 19 cities as centers
of groups the distance matrix is changed and this matrix's index is different
than the initial distance matrix's index. Like the city with index number 11 in
the last distance matrix in fact is the 28th city in the initial
distance matrix. You can see the reindexed last matrix (19*19) at Appendix 3. Another important point that you may
have noticed it when looking at Appendix 3 is that
distances between the same cities are not taken as zero. This has a special
reason and the logic of finding these distances will be mentioned later. In
fact this is a consequence of solving the problem with groups, if we had the
chance to solve for 52 cities it would be easier. You can see the groupings at Appendix 4.
Modeling of the problem:
Firstly you can see our discrete model at Appendix 5. This is the model for the discrete solution. We
did not put the model for the continuous solution because it is slightly
different than the other one and will be mentioned later.ÿ
As an initial approach, we determined the
weights of each 52 cities` weights by dividing the number of customers of each
city in the given table Table 1 with 40, which is given, as the number of
customers served at every trip, and multiplying the result by 52 for each city
distinctly. After determining the new weights, we rounded them to the nearest
greater integer for adequacy. If you look at also for the rents of the cities
we get the annual rental prices of each city again from the given table 1.
Firstly we have used LINGO in our solutions of the problem. We have 52
cities and therefore a matrix of 52*52. But for some of the cities, we do not
follow this approach since these cities are so far away from the surrounding
cities or the surrounding cities also have the similar weight as this city. For
instance, for the cities Istanbul A, Kocaeli and Sakarya, we follow up the
primal approach we explained. Then numbered as the first group with a total
weight of 5330, which is the sum of weights of the cities in the group
multiplied by 52 and divided by 40. And also, in the name of giving an example
to the single citied groups; Konya as an example was taken to be alone due to
its being in the mid part of the map-plane, which has no near city and when we
make an assumption like the city Kirsehir is a city which is not closer to
Konya than to Nevsehir, the assumption will clearly set the solution as
grouping Kirsehir with the city Nevsehir, which has the same weight with Konya.
So, the cities Konya, Bodrum, Diyarbakir and Malatya was taken to be single. In
the data section of the model the weights are represented by W (I) which are constant
ant given W=. in the data section.
For the discrete case modeling; the decision variables are as follows:
Xij: 1 if the i th city is assigned to the depot in the j th city, note
that this variable is not a binary variable.
Yij: 1 if at the j th city a depot is established, and 0 if otherwise.
dij: the distance between the cities i and j
Also the assumptions we have made are followed by these:
The grouping method, by the way the strategy was given before.
In the modeling we take into account the fix costs of establishing
depots, and also we have already given the sequence of the cities with their
regions in Turkey, as seen in Appendix 1. The first 25
cities are belonging to the Marmara, Aegean, and Mediterranean regions and the
other cities belong to the other regions. Therefore for these cities the
establishment costs are different from the cities in the other regions other
than mentioned.
The groups and the center of the each groups are given in the Appendix 4.Note that the calculations we do are annual,
since in the Table 1, the given table, the customer numbers are given weekly.
So, the weights are weekly, then we will multiply these by 52 as a year has 52
weeks. Also we calculate the fix costs Fj`s (the fix cost of the depot in city
j) as being annual.
Also since the sensitivity analysis will be conducted, the prices of
the gasoline, P, and the drivers wage Dr, are taken to be variable. Therefore
the weekly fix costs are:
For the Marmara, Aegean and Mediterranean regions fix costs are:
FIX COST = (150 M TL*15+ Dr)*12
We defined this fixed cost in the model as
RW1+Dr, which are:
RW1: annual wage of 15 workers. Dr: Annual
wage of driver
For the other regions:
FIX COST=(150 M TL*10+ Dr)*12
This fixed cost is defined as RW2 + Dr
which are:
RW2: Annual wage of 10 workers. Dr is
same.
Also for the transportation costs,
initially as we mentioned, we determined the dij values Note here that in the
rows and columns the cities numbers are given, here we refer Appendix
1 for the cities that we sequenced from 1 to 52. Note that Dij values are
taken from the 19*19 distance matrix, which is at Appendix 3.
As one of the transportation cost is the
gasoline consumption and the proportional maintenance cost. It is simply
calculated by dividing the total distance taken by 6 and then multiplying by
1,25 because maintenance cost is 0,25 times of the fuel total cost. Then this cost
is defined as W (I)*D (I, J)*X (I, J)*P*0.2084*2. 0.2084 is 01,25/6 and 2 is
for calculating the total distance because truck goes and return back.
ÿAs
we are given that the drivers are working 8 hours a day and the wages they earn
is 800 M, the cost of the drivers are calculated by the number of drivers used
times the wage of the drivers. Again here we have made some assumptions like we
had to know the speed of a truck. We took it as 50 km per hour and another
assumption here is that a driver works 180 hours per month. Then we found how
many kilometers a driver can take in one year, which is
180hour/month*50km/hour*12month. It equals to 108000 kms. This is defined in
the objective function as (W(I)*X(I,J)*D(I,J)*Dr/108000). In fact this
expression in sum does not give an integer value. For this reason we tried to
make it integer by defining another variable K and K is bigger than this
expression and we defined K as integer. Unfortunately when we put K in the
model we could not get a feasible solution so we took this cost into
consideration in this way.
Another assumption that we have mentioned
before but have not explained is that at the distance matrix the distance from
the same city to that city is not taken as zero. Suppose that we take them zero
then the optimal solution will try to build more plants because the
transportation cost in group will be zero then. Like when it builds a plant at
Trabzon then the transportation cost from Trabzon to Rize, Giresun,
Ordu,Erzurum will be zero and that would be wrong. In fact only transportation
cost from Trabzon toTrabzon can be taken as 0. in order to solve this problem
we put distances to every Dij where I=J. the calculations of these distances
are logical. We will give as example the calculation of only D(6,6) {note that
D(6,6) belongs to the distance matrix in the model}. Our aim is that if a depot
is built at city 6, which is Adana. Then we want the cost to be {((weight of
Hatay)*(distance of Hatay to Adana) + (weight of Icel)*(distance of icel to
Adana))/(weight Adana+weight Hatay+weight Icel)} and we assume cost from Adana
to Adana is zero. This cost is defined as D (6,6). When a depot is built at
Adana then W (6), which is the total weight of Adana, Hatay, Icel is multiplied
by D (6,6) which is the above expression then we have the upper part of the
expression which is the transportation cost within the city. For the other
groups we don't show the calculation. They are all calculated in the same
logic.
To tell about theÿ expressions in the model briefly:
The objective function:
Total transportation cost:
@SUM(ARC(I,J):W(I)*D(I,J)*X(I,J)*P*0.2084*2)+@SUM(ARC(I,J):W(I)*X(I,J)*D(I,J)*Dr*2/108000)
Total fixed costs:
@SUM(CITY(I)|I#LE#9:Y(I)*(RW1+(Dr*1.5)))
+@SUM(CITY(I)|I#GE#10:Y(I)*(RW2+(Dr*1.5)))
+@SUM(CITY(I):Y(I)*R(I)*1300000)
Here different staff costs of building plants at different regions
are held.
Also the rent and the utility are taken together. 1300000 stands for in fact
1.3 time 1 million. 1.3 for rent + utility and as rents are definedÿ
in millions million stand for that.
The
constraints:
The constraint to assign every city to one plant (it can be to many depot
then Xij will be in fraction. İn discrete model it have to be to one
depot)
@FOR(CITY(I):@SUM(CITY(J):X(I,J))=1)
At a city if there
is not depot then there will be no transport. This is satisfied by:
@FOR(ARC(I,J):-X(I,J)+Y(J)>=0)
Maximum depot
building constraints:
@SUM(CITY:Y)<=N
Y(j) values
are to be binary in the discrete model:
@FOR(CITY:@BIN(Y))
We will not
explain the continious model so much because the only difference betwen them is
one constraint type which is
ÿÿÿÿÿÿÿÿÿÿÿÿ @FOR(CITY:Y<=1). This
constraint is put in the place ofÿ
@FOR(CITY:@BIN(Y))
In the continious model there is no two alternative for Y to be 0 or 1. it
can be between but if we look at the results we can easily see that all Y
variables are 0 or 1 because it is the optimum for that. As the output of these
two medels are very long we took the necessaty parts. You will easily recognize
that. An output when fully given is 60 pages. You can see the output of the
discrete model at Appendix 4. When we observed the
output of the continious model we saw that the outputs are same so we did not
put it in the appendices. For the continious model it is logical that Y values
are all 0 or 1.ÿ At this point, we think
that the reason for this is that this problem is uncapacitated plant location
problem so it builds the depot dierctly on the place that is optimum but in the
capacitated problem every city has the probability of supplying their needs
from different depots. İn the uncapacitated version type Xij variables
also will be 0 or 1 because there will be only 1 depo that is related with any
city or any city will supply fromonly one depot in the uncapacitated type plant
location problems.
TOTAL COST FUNCTIONS
At our solutions we have found that building 13 depots is optimal for the
problem. The cost functions according to the depots built is plotted. To find
the cost values other than the optimal value, we changed one of the
constraints. That constraint is: @SUM(CITY:Y)<=N. When you put 1 instead of
N, you find total cost of openning only one depot. This is same for the values
up to 13. when you want to build 14 or more depots then you have to change that
constraint by @SUM(CITY:Y)>=N. By this way the values are observed. We
plotted the cost function. You can find it at Appendix 6.
These values are recorde according to the table:
|
ALTRENATIVES |
OBJECTIVE |
PLANT LOCATIONS |
|
DISCRETE1 |
88491,36 |
12 |
|
DISCRETE2 |
55686,21 |
3,14 |
|
DISCRETE3 |
45033,49 |
1,8,14 |
|
DISCRETE4 |
38020,63 |
1,8,14,18 |
|
DISCRETE5 |
32855,6 |
1,4,7,14,18 |
|
DISCRETE6 |
29428,41 |
1,5,7,14,15,17 |
|
DISCRETE7 |
27056 |
1,5,7,14,15,17,18 |
|
DISCRETE8 |
24956,05 |
1,5,7,10,14,15,17,18 |
|
DISCRETE9 |
23407,96 |
1,5,6,7,10,14,17,18,19 |
|
DISCRETE10 |
22191,54 |
1,5,6,7,9,10,14,17,18,19 |
|
DISCRETE11 |
21305,01 |
1,5,6,7,9,10,14,15,17,18,19 |
|
DISCRETE12 |
20448,37 |
1,5,6,7,9,10,13,14,15,17,18,19 |
|
DISCRETE13 |
20147,62 |
1,5,6,7,9,10,13,14,15,16,17,18,19 |
|
DISCRETE14 |
20178,67 |
1,4,5,6,7,9,10,13,14,15,16,17,18,19 |
|
DISCRETE15 |
20262 |
1,4,5,6,7,9,10,12,13,14,15,16,17,18,19 |
|
DISCRETE16 |
20361,11 |
1,3,4,5,6,7,9,10,12,13,14,15,16,17,18,19 |
|
DISCRETE17 |
20652,96 |
1,3,4,5,6,7,9,10,11,12,13,14,15,16,17,18,19 |
With corresponding cities as depot locations:
1 Afyon
2 Bursa,Nevsehir
3
IstanbulA,Marmaris,Nevsehir
4
IstanbulA,Marmaris,Nevsehir,Trabzon
5
IstanbulA,Marmaris,Nevsehir,Trabzon,Antalya
6
IstanbulA,Izmir,Antalya,Nevsehir,Kmaras,Samsun
7
IstanbulA,Izmir,Antalya,Nevsehir,Kmaras,Samsun,Trabzon
8
IstanbulA,Izmir,Antalya,Nevsehir,Kmaras,Samsun,Trabzon,Ankara
9
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir
10
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum
11
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras
12
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras,Konya
13
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras,Konya,Malatya
14
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras,Konya,Malatya,Canakkale
15
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras,Konya,Malatya,Canakkale,afyon
16
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras,Konya,Malatya,Canakkale,afyon,Bursa
17
IstanbulA,Izmir,Antalya,Nevsehir,Samsun,Trabzon,Ankara,Adana,Diyarbakir,Bodrum,Kmaras,Konya,Malatya,Canakkale,afyon,Bursa,Bolu
The total
cost function for the continiou solution is same so we did not put its
plotting. The optimal one is the one with 13 cities. Here another point should
be notified which is we made all our calculations according tot he 19 grouped
cities but nearby there are 52 cities. So for each group it is necessary to
look in between the 19 groups whether there is a need for another depot in the
other group members other then the one with the highest weight. For this
purpose we cahnged our model accordingly and tried to find out whether there is
a need for any extra depot locations.ÿ
We have not tried all of the groups because it was explicit for many of
the groups that there would not be any extra other depots. So we looked at
groups especially at groups 3 and 19. As a result we have found that there is
no need for extra depots other than Kirklareli because at the solution for
group 3 two Y values are 1. One of them is Istanbul-E and the other is
Kirklareli. There is no need to put a depot at Istanbul-E because it is not
supported by the general solution. As a result we decided to add also
Kirklareli.
We have seen according to our experience with the results of the diffrent
several runs that building a depot or supplying a service by transportation have
thin line between them. When the ratios of the gasoline price (P) or wage rate
of the driver changes slightly results do not change slightly. From this point
of view we think that building a plant as cost is not much higher from the cost
of transportation to anywhere. But in fact this is impossible in real life,
building depots should cost much higher. From this point of view we tried to
investigate on the reasons of this issue and we reached to a solution. It is
that: the cost of building a depot consists of the costs of the workers, a
chief and annual rent plus some maintenance. There is no other costs like
supplying inventory to these depots or any other fixed costs of building a
depot. The depots work as if there are always stocks inside without any cost.
We mean whereever you build a stock, you only incur the mentioned costs. For
example the depot build in Diyarbakir does not have a problem with its
resources. There is no transportation cost for this depot. In the view of these
suggestions we think that the results give more number of depots to be built
with respect to real life conditions.
We made our analysis on two factors which are P and Dr. Changing these
variables slightly gave very diffrent results but the total costs not changing
so much respectively. The results for changing gasoline prices:
P as new value |
ÿÿÿ Optimum number of depots |
|
50,000,000 |
19 (put depots to evry
city in fact) |
|
1,000,000 |
16 |
|
550,000 |
14 |
|
537,500 |
14 |
|
531,250 |
14 |
|
525,000 |
13 |
ÿThe results for changing Dr values:
|
Factors that Dr value
is multiplied with |
Number of optimum
depots |
|
2 |
14 |
|
1.5 |
14 |
|
1.375 |
14 |
|
1.3125 |
13 |
|
1.25 |
13 |
CONCLUSION
In the problem, we think that it is very important to make the assumptions
in a logical way.ÿ As we had to group
the cities, we faced with some extra problems. It would be very easy for us if
we had the chance of putting the 52 cities as variables in the model. In ideal
condition, the groupings should also be done by optimization. We should find
the optimum number of groups and the cities in them so that the total distances
{for any city the distance to the center of its group is taken} are minimized
and then also solving the problem in between the groups you can get the exact
solution.
Between two of the models we choose the continious one because it is in fact a
relaxation of the other model. In lingo you can not do range analysis to a
model which includes binary variables so to the continious model you can do the
range analysis and less time to solve. The model is also very sensitive to any
changes because building a depot and supplying service with transportation does
not have so much difference in between.
You can see the depots which are the results of the model at Appendix 7. All the cities are plotted there according to
their coordinates. The cities which have stars around are the ones where we
built the depots.