Oil Refinery Transportation Problem Computer Science Essay

Published: Last Edited:


ABC is a large, wholly incorporated petroleum company based in the United Arab Emirates. Most of the oil the company produces is in its own oil fields and the rest is imported from Saudi Arabia. The oil is transported to the company's refineries and then to transport the petroleum products from the refineries to ABC's distribution centers through a wide spread distribution network.

ABC is continuing to increase market share for several of its major products. Therefore, management has made the decision to expand output by building an additional refinery and increasing imports of crude oil from Saudi Arabia. The crucial remaining decision is where to locate the new refinery. The addition of the new refinery will have a great impact on the operation of the entire distribution system, including decisions on how much crude oil to transport from each of its sources to each refinery (including the new one) and how much finished product to transport from each refinery to each distribution center. Therefore, the three key factors for management's decision on the location of the new refinery are

1. The cost of transporting the oil from its sources to all the refineries, including the new one.

2. The cost of transporting finished product from all the refineries, including the new one,

to the distribution centers.

3. Operating costs for the new refinery, including labor costs, taxes, the cost of needed supplies (other than crude oil), energy costs, the cost of insurance, the effect of financial incentives provided by the state or city, and so forth. (Capitol costs are not a factor since they would be essentially the same at any of the potential sites.)

Management has set up a task force to study the issue of where to locate the new refinery.

After considerable investigation, the task force has determined that there are three attractive potential sites.

Other relevant factors, such as standard-of-living considerations for management and employees, are considered reasonably comparable at these sites. Here the availability as well as requirements of the various depots are finite and constitute the limited resources. This type of problem is known as distribution or transportation problem in which the key idea is to minimize the cost or the time of transportation. Transportation problems are also

linear programming problems and can be solved by simplex method but because of practical significance the transportation problems are of special interest and it is tedious to solve them through simplex method.


After completion of this lesson you will be able to:

solve the transportation problems by:

Lowest cost entry method.

Test the optimality of the solution.


Let there be three units, producing oil, say, A1, A2 and A3 from where the oil has to be supplied to four refineries say B1, B2, B3 and B4. B4 being one of the potential sites for the refinery.

Let the amount of oil supplied by A1, A2 and A3 be a1, a2 and a3 respectively and the demands at the refineries be b2, b1, b3 and b4 respectively.

We assume the condition:

a1+a2+a3 = b1+b2+b3+b4

i.e., all oil produced is supplied to the different refineries.

Let the cost of transportation of million barrels of oil from A1 to B1 be c11. Similarly, the cost of transportations in other cases are also shown in the figure.

Let out of a1 amount of oil available at A1, x11 be taken at B1 refinery, x12 be taken at B2 refinery and to other refineries as well, as shown in the following figure.

Fig 1.2: Network diagram for the transportation problem

Total amount of oil to be transported from A1 to all destination, i.e., B1, B2, B3, and B4 must be equal to a1.


Similarly, from A2 and A3 the oil transported must be equal to a2 and a3 respectively.



On the other hand it should be kept in mind that the total number of oil delivered to B1 from all units must be equal to b1, i.e.,





With the help of the above information we can construct the following table :

Table 2.1: Generalized Transportation problem table

The cost of transportation from Ai (i=1,2,3) to Bj (j=1,2,3,4) will be equal to


Where the symbol put before cij xij signifies that the quantities cij xij must be summed over all i = 1,2,3 and all j = 1,2,3,4.

Thus we come across a linear programming problem given by equations (1) to (7) and a linear function (8).

We have to find the non-negative solutions of the system such that it minimizes the function (8).


We can think about a transportation problem in a general way if there are m sources (say A1, A2, ..., Am) and n destinations (say B1, B2,....,Bn). We can use ai to denote the quantity of oil products concentrated at points Ai(i=1,2,...., m) and bj denote the quantity of oil products expected at points Bj(j =1,2,...,n).

We assume the condition:


implying that the total stock of oil is equal to the summed demand for it.


The following terms are to be defined with reference to the transportation problems:

(A) Feasible Solution (F.S.)

A set of non-negative allocations xij >=0 which satisfies the row and column restrictions is known as feasible solution.

(B) Basic Feasible Solution (B.F.S.)

A feasible solution to a m-origin and n-destination problem is said to be basic feasible solution if the number of positive allocations are (m+n-1).

If the number of allocations in a basic feasible solutions are less than (m+n-1), it is called degenerate basic feasible solution (DBFS) (otherwise non-degenerate).

(C) Optimal Solution

A feasible solution (not necessarily basic) is said to be optimal if it minimizes the total transportation cost.


Gathering the necessary data:

Let us consider the numerical version of the problem stated in the introduction and the mathematical formulation of the same in the next section.

The task force needs to gather a large amount of data, some of which requires considerable digging, in order to perform the analysis requested by management.

Management wants all the refineries, including the new one, to operate at full capacity. Therefore, the task force begins by determining how much crude oil each refinery would need to receive annually under these conditions. Using units of 1 million barrels, these needed amounts are shown on the upper side of Table 2.2. The bottom side of the table shows the current annual output of crude oil from the various oil fields. These quantities are expected to remain stable for some years to come. Since the refineries need a total of 360 million barrels of crude oil, and the oil fields will produce a total of 240 million barrels, the difference of 120 million barrels will need to be imported from Saudi Arabia.

Table 2.2: Production data for the case study

Since the amounts of crude oil produced or purchased will be the same regardless of which location is chosen for the new refinery, the task force concludes that the associated production or purchase costs (exclusive of shipping costs) are not relevant to the site selection decision. On the other hand, the costs for transporting the crude oil from its source to a refinery are very relevant. These costs are shown in Table 2.3 for both the three current refineries and the three potential sites for the new refinery.

Table 2.3: Cost data for transporting crude oil to ABC's refineries

In order to find the solution of this transportation problem we have to follow the steps given below.

(A) Initial basic feasible solution

(B) Test for optimization.

Let us consider these steps one by one.

(A) Initial Basic Feasible Solution :

Lowest cost entry method:

Table 2.4: Oil refinery problem model

Number of constraints = number of rows + number of columns

Total oil field supply must equal total oil refinery demand.

Potential refinery site DUBAI:

In this method we start with the lowest cost position. Here it is (2,4), allocate the smallest amount of supply or demand and then strike off the other positions in row 2, since all the available units are distributed to these positions.

Table 2.5: 1st allocation

(b) Consider the next higher cost positions among the remaining cells, i.e., (1,1) and (4,1) positions, allocate the cell where maximum allocations can be made. That is in (1,1) the amount allocated will be 80 while in (4,1) it will be 100. Therefore allocate (4,1) with the value 100. Hence the allocations in the column 1 is complete, so strike off the remaining cells in column 1.

Table 2.6: 2nd allocation

With the help of the above facts complete the allocation table as given below:

Table 2.7: Final allocations for Dubai

From the above facts, the cost of transportation from the oil fields to the refineries including the dubai site is:

=20*4+60*3+60*1+20*7+80*3+100*2+20*3 = 960

Potential refinery site SHARJAH:

After doing similar operations for the Sharjah site, we get the following cost results:

Table 2.8: Final costs for Sharjah

From the above facts, the cost of transportation from the oil fields to the refineries including the Sharjah site is:



Potential site ABU DHABI:


Table 2.9: Final costs for Abu Dhabi

From the above facts, the cost of transportation from the oil fields to the refineries including the Abu Dhabi site is:



(B) Test for Optimization :

In part (A) of this section we have obtained an initial basic feasible solution. Solutions so obtained may be optimal or may not be optimal, so it becomes essential for us to test for optimization.

For this purpose we first define non-degenerate basic feasible solution.

Definition: A basic feasible solution of an (m & n) transportation problem is said to be non-degenerate if it has following two properties :

(a) Initial basic feasible solution must contain exactly m+n-1 number of individual allocations.

(b) These allocations must be in independent positions. Independent positions of a set of allocations means that it is always impossible to form any closed loop through these allocations.

The following theorem is also helpful in testing the optimality.

Theorem: If we have a B.F.S. consisting of m+n-1 independent positive allocations and a set of arbitrary number ui and vj (i=1,2,...m; j=1,2,...n) such that crs = ur+vs for all occupied cells (r,s) then the evaluation dij corresponding to each empty cell (i, j) is given by

Algorithm for optimality test :

In order to test for optimality we should follow the procedure as given below:

Step 1: Start with B.F.S. consisting of m+n-1 allocations in independent positions.

Step 2: Determine a set of m+n numbers ui (i=1,2,....m) and vj (j=1,2,...n) such that for each occupied cells (r,s) crs = ur+vs

Step 3: Calculate cell evaluations (unit cost difference) dj for each empty cell (i,j) by using the formula,

dij = cij - ( ui+vj )

Step 4: Examine the matrix of cell evaluation dij for negative entries and conclude that

(i) If all dij > 0 , Solution is optimal and unique.

(ii)If all dij < 0 or At least one dij = 0 , Solution is optimal and alternate solution also exists.

(iii) If at least one dij < 0 , Solution is not optimal. If it is so, further improvement is required by repeating the above process. See step 5 and onwards.

Step 5: (i) See the most negative cell in the matrix [ dij ].

(ii) Allocate x to this empty cell in the final allocation table. Subtract and add the amount of this allocation to other corners of the loop in order to restore feasibility.

(iii) The value of x, in general is obtained by equating to zero the minimum of the allocations containing -x (not + x) only at the corners of the closed loop.

(iv)Substitute the value of x and find a fresh allocation table.

Step 6: Again, apply the above test for optimality till you find all dij < 0

Computational demonstration for optimality test:

Stepping stone method:

Consider the initial basic feasible solution as obtained by Least cost method in section (A) of this article.

DUBAI site:

Step 1: (i) In this table number of allocations = 4+4-1=7.

(ii) All the positions of allocations are independent.

Step 2: Determine a set of (m+n), i.e., (4+4) numbers u1, u2, u3,u4 and v1, v2, v3, and v4. for each occupied cells. For this consider the row or column in which the allocations are maximum (here, let us take first row). Now, take u1 as an arbitrary constant (say zero) then by using cij = ui+vj try to find all ui and vj as

Table 2.10: Final allocations for Dubai for

performing the stepping stone method








Thus u1 =0, u2=-2, u3=3 u4=-1 and v1 =3, v2=4, v3=0 and v4=3.

Step 3: Compute the opportunity cost for all the empty cells using ui+vj-cij.

Table 2.11: Opportunity cost calculation

Step 4

Check the sign of each opportunity cost. If the opportunity costs of all the unoccupied cells is negative, the given solution is the optimum solution. On the other hand, if one or more unoccupied cell has either positive or zero opportunity cost, the given solution is not an optimum solution and further savings in transportation cost are possible.

Step 5

Select the unoccupied cell with the largest positive opportunity cost as the cell to be included in the next solution.

Step 6

Assign alternate plus and minus signs at the occupied cells on the corner points of the closed path with a plus sign at the cell being evaluated.

Table 2.12: x determination

x-20=0 => Therefore x=20

The new allocations are:

Table 2.13: Final allocations after 1st iteration of stepping stone method

After repeating the process till we get all negative values in the south west corners, we reach the optimal solution:

Table 2.14: Optimal solution for Dubai

Therefore the optimal cost for the Dubai site is,



After performing the Stepping Stone Method on the Sharjah and Abu Dhabi site data also, the optimal transportation cost for:

The Sharjah site has come down from 960 to 920

The Abu Dhabi site it has come down from 1020 to 960.