Make your own free website on Tripod.com

Description of the solution plan:

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.

Sensitivity Analysis

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.