A new algorithm for solving uncapacitated transportation problem with interval-defined demands and suppliers capacities

Abstract

The uncapacitated transportation problem (UTP) deals with minimizing the transportation costs related to the delivery of a homogeneous product from multi-suppliers to multi-consumers. The application of the UTP can be extended to other areas of operations research, including inventory control, personnel assignment, signature matching, product distribution with uncertainty, multi-period production and inventory planning, employment scheduling, and cash management. Such a UTP with interval-defined demands and suppliers capacities (UTPIDS) is investigated in this paper. In UTPIDS, the demands and suppliers capacities may not be known exactly but vary within an interval due to variation in the economic conditions of the global economy. Following the variation, the minimal total cost of the transportation can also be varied within an interval and thus, the cost bounds can be obtained. Here, although the lower bound solution can be attained methodologically, the correct estimation of the worst case realization (the exact upper bound) on the minimal total transportation cost of the UTPIDS is an NP-hard problem. So, the decision-makers seek for minimizing the transportation costs and they are interested in the estimation of the worst case realization on these minimal costs for better decision making especially, for proper investment and return. In literature very few approaches are available to find this estimation of the worst case realization with some shortcomings. First, we demonstrate that the available heuristic methods fail to obtain the correct estimation of the worst case realization always. In this situation, development of a better heuristic method to find the better near optimal estimation of the worst case realization on the minimal total costs of the UTPIDS is desirable. Then this paper provides a new polynomial time algorithm that runs in O (N2) time (N, higher of the numbers of source and destination nodes) for better estimation. A comparative assessment on solutions of available benchmark instances, some randomly generated numerical example problems and a real-world application shows promising performance of the current technique. So, our new finding would definitely be benefited to practitioners, academics and decision makers who deal with such type of decision making instances.

Keywords

Heuristics upper bound least aggregated expense NP-hard problem

1 Introduction

The uncapacitaded transportation problem (TP) refers to the homogeneous product distribution from different origin nodes to target points. Here, sources or suppliers (e.g., warehouses) acts as origin nodes and consumers or destinations (e.g., supermarkets) are considered as target nodes for product transmission. The aim of the system resides in minimizing the total transportation cost satisfying overall demands. Generally, in practice, even during short time period, the range of capacity and demand among suppliers and consumers respectively may fluctuate a bit up to distinct period for some uncertainties. This consequence impacts on the total transportation cost for demand fulfilment to vary a certain range. The calculation of the lower and upper bounds (LB and UB) of the least aggregated expense s helps to make a better decision concerning the investment to be made. However, the majority of studies in literature consider fixed supply and demand quantities, disregarding the varying demands and supplies (see for detail [3–9 , 30]). Few studies in the literature focus on changes in demands and supplies in uncapacitaded transportation problem. The developed techniques are discussed here below.

Ali Ebrahimnejad and Verdegay [13] proposed a new solution technique to solve a fully intuitionistic fuzzy transportation problem. Ali Ebrahimnejad and Verdegay [14] presented an efficient solution technique for solving type-2 intuitionistic fuzzy numbers based Transportation Problems. Ali Ebrahimnejad [15] proposed a method to solve Fuzzy transportation problems (FTPs) with LR flat fuzzy numbers. Here, in FTPs, the transportation costs, supply and demand are represented by non-negative LR flat fuzzy numbers. Ali Ebrahimnejad [16] presented a fuzzy linear programming method to solve a transportation problem with interval-valued trapezoidal fuzzy numbers. Bagheri et al. [17] developed a new fuzzy DEA based technique to handle the fully fuzzy multi-objective transportation problem where all of its variables are considered fuzzy. Das et al. [1] illustrates scheme for diminishing the multi-objective transportation problem and he also categorizes the problems into several definitions: i) with the objective functions’ coefficients given in the form of interval, ii) with supply and demand factors given in the form of interval, and iii) both objective function coefficients and supply and demand parameters given in the form of interval. Masoud et al. [23], Masoud et al. [28] and Matindi et al. [24, 29] developed a scheduler for the cane transport systems with unlimited capacities to reduce the total costs with improving the performance. Safi and Razmjoo [12] considered a transportation problem with fixed and variable transportation costs given in the form of interval. They solved the problem into bi-solution steps and tested them on numerical examples. It should be noted that neither Das et al. [1] nor Safi and Razmjoo [12] considered the calculation of lower or upper bound on the least aggregated expenditure for transportation. For homogeneous product supply to multi-consumers, Liu [11] presented several methods for calculating the lower and the upper bounds on the least aggregated expenditure where the changes of supplies and demands are considered. Juman and Hoque [5] by agumented the inventory costs in the [11] model which arise in case of transportation and at the destination. Thereafter, they analyzed theoretical performances of the developed techniques for the lower and the upper bounds for this enhanced model.

1.1 The research motivation and challenges

This research is motivated by a real-world yoghurts distribution problem. The problem investigated in this paper arises from the distribution of yoghurts from two warehouses belonging to a Dambulla based company in Sri Lanka and the yoghurts are distributed island wide to all 25 distribution centres. The supply parameter range for the warehouse of the factory, unit shipping cost and the demand parameter ranges of 25 distribution centres are given in Section 4. Here, each of the supply and demand quantities of this yoghurt product varies within a certain range as given in Section 4. According to this variation, the total minimal transportation cost also varies with a certain range. So, the management parties of this company are more interested in finding the lower and upper bounds of the minimal total costs to make decisions specially, for its proper investment and return. For example, imagine, this company is willing to invest ‘x’ amount of money to transport this yoghurt product with boundaries of total minimal costs of Rs 7 million and 15 million.

If x<7, investing for that product is useless for the company.

If 7x<15, the company may invest for it with a risk.

If 15x, without any risk, company can invest to the product.

According to the number of choices of supplies and demands within their respective ranges of the yoghurts distribution problem, The total number of combinations (or combinatorial choices) of minimal cost is modeled to be (m+n)! $\prod^{m} (Δ S + 1) \prod^{m} (Δ d + 1)$ where m & n are the numbers of suppliers and buyers respectively and, ΔS_i is the range of the supply quantity of ith supplier and Δd_j is the range of the demand quantity of jth buyer. This equals 1.6781E+157, which is quite high in number in our yoghurt distribution problem (YDP) setup.

Besides, in general, the number of choices of supplies and demands within their respective ranges increases enormously as the number of suppliers and/or buyers increases. The total number of combinations (for example 1.6781E+157 in our YDP) of minimal cost is modeled to be (m+n)!

$\prod_{i = 1}^{m} (Δ S_{i} + 1) \prod_{j = 1}^{m} (Δ d_{j} + 1)$ , will also increase. In such a situation, although the lower bound cost (for example 7 million) can be obtained methodologically, determination of the exact upper bound cost (for example 15 million) becomes an NP hard problem. So, the yoghurt factory is keen on finding this exact (or better near optimal) upper bound cost for its proper investment and return.

How to develop a streamline method to tackle the supply and/or demand variation issue in supply chain management for the correct (or better near optimal) estimation of the worst case realization (upper bound cost) is a quite challenging research topic.

1.2 Our contribution

Determination of the correct estimation of the worst case realization (exact upper bound) of the minimal total costs of such a transportation problem with interval valued parameter becomes an NP hard problem. To deal with this type of problem, though few methods are already available, none of them, however, always yield the optimal upper bound. In this situation, development of an exact (or better near optimal) method to the UTP with interval-defined demands and suppliers capacities in finding the upper bound of the minimal total costs is desirable. Hence, the contribution of this paper is of three folds: (1) Shortcoming in the existing methods is demonstrated. (2) A polynomial time algorithm that runs in O (N2) time (N, higher of the numbers of source and destination nodes) is proposed for better near optimal estimation of the worst case realization on the least aggregated expenses of the UTPIDS in the extended form with inventory costs. (3) A numerical experiment (via benchmark, some randomly generated ones and a real world yoghurt distribution problem) is performed to measure the performance of our new polynomial time algorithm against the existing ones.

The remainder of this paper is standardized in the following sequences: mathematical formulation of the enhanced transportation issue with varying capacities of suppliers and demands is discussed in Section 2. Section 3 presents the developed technique named “α - β cut method”. A numerical experiment is maintained in section 4 for measuring the performance of the developed method. Finally, Section 5 draws the conclusion of the research.

2 Transportation model with varying supplies and demands

The following hypothesis and notations are used in the model:

hypothesis:

Transportation of homogeneous product is maintained from multi-supplier to multi-consumers.

The consumer’s product demand, D varies with time within an interval.

The aggregated supply amount by suppliers is greater than or equal to the aggregated demand by consumers and this supply also varies over time within an interval.

Adequate storage capacity is assured by each of the consumers so that they can retain the requisite inventory.

The availability of a transport media (e.g. Vehicle) is also assured for product shipment of requisite amount of units.

Supplier’s product destines to consumers inventory at the same time to fulfil the demand.

(a) Decision variable

X_ij transported product amount from i^th supplier to j^th consumers.

(b) System parameters

m Aggregated crowd of supply nodes (suppliers);

n Aggregated crowd demand nodes (consumers); C_ij Unit transportation expense from i^th supplier to j^th consumer;

t_ij Time for transportation from i^th supplier to j^th consumer

(c) Supplier (i=1,2,2,....., m)

${\hat{S}}_{i}$ Amount of supply (in units) from i^th supplier;

${\underline{S}}_{i}$ Lower bound of supplies from the i^th supplier;

${\bar{S}}_{i}$ Upper bound of supplies from the i^th supplier;

(d) Consumer (j=1,2,2,....., m)

${\hat{d}}_{j}$ The demand (in units) per unit time to j^th consumer;

${\underline{D}}_{j}$ Lower bound of demands of the j^th consumer;

${\bar{D}}_{j}$ Upper bound of demands of the j^th consumer;

h_i Holding expense for the j^th consumers per unit time S

A Flowchart of the transportation model is demonstrated in following Fig. 1 based on the hypothesis above:

Fig. 1

Flowchart of the proposed transportation model.

Here, we use the extended model developed in Juman and Hoque [5] including inventory expenses at the time of product transportation and also at reach-out point along with the cost of transportation: $\begin{matrix} \underline{Z} = Min \sum_{i = 1}^{m} \sum_{j = 1}^{n} A_{ij} x_{ij}; \\ where, A_{ij} = c_{ij} + h_{j} / 2 + t ij h_{j} \\ Subject to \sum_{j = 1}^{n} x_{ij} \leq {\hat{S}}_{i} : i = 1, 2, . . . m \\ \sum_{i = 1}^{m} x_{ij} = {\hat{d}}_{j} : j = 1, 2, . . . n \\ \sum_{i = 1}^{m} {\hat{S}}_{i} \geq \sum_{j = 1}^{n} {\hat{d}}_{j} \\ {\underline{S}}_{i} \leq {\hat{S}}_{i} \leq {\bar{S}}_{i} \forall i; \underline{D_{j}} \leq {\hat{d}}_{j} \leq {\bar{D}}_{j} \forall j; x_{ij} \geq 0, \forall i, j . \end{matrix}}$ (1)

Then Juman and Hoque [5] developed heuristic algorithms to extract the lower and the upper bounds on the least aggregated expense to the above model.

2.1 Deficiency in the existing UB methods

Liu [11], Juman and Hoque [5] methods provide near-UBs of the minimal total cost for the UTPIDS. However, these two methods fail to provide an exact UB of the minimal total costs. Table 1 demonstrates the deficiency in the existing methods. Supply and demand ranges of the problem is given below.

Table 1
Deficiencies in the UBL, UBJ and UBX methods

Instance No. C _ij The near optimal UB of the minimal total cost found by

[11] method J&H (2014)’s method Different by Lingo s_i& d_j

1 C₁₁ = 15, C₁₂ = 12, C₁₃ = 120, C₂₁ = 45, C₂₂ = 30, C₂₃ = 22 5,250 5,370 8,085

2 C₁₁ = 17, C₁₂ = 12, C₁₃ = 100, C₂₁ = 25, C₂₂ = 20, C₂₃ = 42 7,530 7,530 8,775

Instance No.	C _ij	The near optimal UB of the minimal total cost found by
1	C₁₁ = 15, C₁₂ = 12, C₁₃ = 120, C₂₁ = 45, C₂₂ = 30, C₂₃ = 22	5,250	5,370	8,085
2	C₁₁ = 17, C₁₂ = 12, C₁₃ = 100, C₂₁ = 25, C₂₂ = 20, C₂₃ = 42	7,530	7,530	8,775

${\underline{S}}_{1} = 60, {\bar{S}}_{1} = 120, {\underline{S}}_{2} = 150$ , and ${\underline{D}}_{1} = 45, {\bar{D}}_{1} = 90, {\underline{D}}_{2} = 30, {\underline{D}}_{2} = 60$ ${\underline{D}}_{3} = 60, {\bar{D}}_{3} = 120$

For each of the numerical problems in Table 1, the minimal total transportation cost found with different values of s_i & d_j keeping them within their respective ranges by LINGO solver, is higher than the upper bound obtained by existing approaches. These results clearly demonstrate that these two approaches are unable to provide the exact upper minimal total transportation cost bound. In this situation, development of a better near optimal method to find the upper bound on the minimal total costs of the UTPIDS is desirable.

3 Revised UB

In practice, even for the small problem instances, the interval sizes of varying supplies and demands can be quite large. Therefore, the number of possible combinations of values of all capacities and all demands can be very high. we have expressed all the varying supplies and demands as convex combinations of their respective the lower and the upper bound values. In the above example, the convex combinations are

For example, for 2 suppliers and 3 consumers, the interval given as follows

$60 \leq {\hat{S}}_{1} \leq 190; 75 \leq {\hat{S}}_{2} \leq 250; 45 \leq {\hat{d}}_{1} \leq 130; 30 \leq {\hat{d}}_{2} \leq 150; 60 \leq {\hat{S}}_{1} \leq 180$ , can be represented in the following way:

60α₁ + 190 (1 - α₁) ; 75α₂ + 250 (1 - α₂) & 45β₁ + 130 (1 - β₁) ; 30β₂ + 150 (1 - β₂) ; 60β₃ + 180 (1 - β₃).

That is, we can replace the interval parameters (supplies and demands) with their respective convex combinations. By choosing a step for the variation of values of α_i & β_j; i=1,2,...m and j=1,2,...n, the interval of possible values can be discretized. For example, if we set up the step to 0.1 for both parameters, they will take values 0.0, 0.1, 0.2, 0.3,...., 0.8, 0.9, 1.0. That is, the α_i - cuts of the supply value from i^th supplier ( ${\hat{S}}_{i}$ ) at eleven distinct α_i values: 0.0, 0.1, 0.2, 0.3,....., 0.8, 0.9, 1.0. Similarly, β_j - cuts of the demand value at the j^th consumers ( ${\hat{d}}_{j}$ ) at eleven distinct β_j values: 0.0, 0.1, 0.2, 0.3,...., 0.8, 0.9, 1.0. Therefore, at the worst case, the total number of combinatorial combinations of supplies and demands within their respective ranges in our proposed method becomes 11mn. It is given as theorem 1 below.

Theorem 1. The total number of combinatorial choices of supplies, ${\hat{S}}_{i}$ and demands, ${\hat{d}}_{j}$ within their respective ranges in our proposed method becomes $\sum_{i = 1}^{m} \sum_{j = 1}^{n} 11$ .

The following proof proceeds mainly by mathematical induction. For simplicity we prove it for m = n.

$\underline{m = n = 1}$

In the extended model, we replace ${\hat{S}}_{i}$ & ${\hat{d}}_{j}$ by $α_{i} S_{i} + (1 - α_{i}) {\bar{S}}_{i} & β_{j} D_{j} + (1 - β_{j}) {\bar{D}}_{j}; \forall i, j$ respectively; where, 0 ≤ α_i ≤ 1 & 0 ≤ β_j ≤ 1; i=1,2,...m and j=1,2,...n.. That is the replacement is done by convex combinations of their respective lower and upper bound values. Since, m = n= 1 we have i=1 and j=1. So, we have only the ${\hat{S}}_{1}$ & ${\hat{d}}_{1}$ in the extended model with the replacement of $α_{1} S_{1} + (1 - α_{1}) {\bar{S}}_{1} & β_{1} D_{1} + (1 - β_{1}) {\bar{D}}_{1}$ respectively. The α₁ - cuts of the supply value from i^th supplier ( ${\hat{S}}_{i}$ ) at eleven distinct α₁ values: 0.0, 0.1, 0.2, 0.3,...., 0.8, 0.9, 1.0. Similarly, β₁ - cuts of the demand value at the j^th consumers ( ${\hat{d}}_{j}$ ) at eleven distinct β₁ values: 0.0, 0.1, 0.2, 0.3,...., 0.8, 0.9, 1.0. Thus for both ranges of supplies and demands ( ${\underline{S}}_{i} \leq {\hat{S}}_{i} \leq {\bar{S}}_{i}$ ; i=1 and ${\underline{D}}_{j} \leq {\hat{d}}_{j} \leq {\bar{D}}_{j}$ ; j=1), we have 22 number of choices in total. This is $equal to \sum_{i = 1}^{1} \sum_{j = 1}^{1} 11, i . e . N = \sum_{i = 1}^{1} \sum_{j = 1}^{1} 11$ (A1)

m = n = 2 Similarly, it can be proved easily that we can have 44 number of choices in total for both ranges of supplies and demands ( ${\underline{S}}_{i} \leq {\hat{S}}_{i} \leq {\bar{S}}_{i}$ ; i=1,2 and ${\underline{D}}_{j} \leq {\hat{d}}_{j} \leq {\bar{D}}_{j}$ ; j=1,2). This is equal to $\sum_{i = 1}^{2} \sum_{j = 1}^{2} 11, i . e . N = \sum_{i = 1}^{2} \sum_{j = 1}^{2} 11$ (A2)

The assertion is true for m = n = P. Then the total number of combinatorial choices of supplies, ${\hat{S}}_{i}$ and demands, ${\hat{d}}_{j}$ within their respective ranges in our proposed method becomes $\sum_{i = 1}^{p} \sum_{j = 1}^{p} 11 = [11 (p + p)] . i . e . N = \sum_{i = 1}^{p} \sum_{j = 1}^{p} 11$ (A3)

We have to prove that the assertion is true for m = n = P+1.

m = n= P+1 is equal to (m = n= P) + (m = n= 1). It has been already proved that N = $\sum_{i = 1}^{1} \sum_{j = 1}^{1} 11$ when m = n= 1. So, N = ( $\sum_{i = 1}^{p} \sum_{j = 1}^{p} 11$ + $\sum_{i = 1}^{1} \sum_{j = 1}^{1} 11$ ) for m = n= P+1. This is equal to N = $\sum_{i = 1}^{p + 1} \sum_{j = 1}^{p + 1} 11$ , which shows that this assertion holds for m = n= P+1. This together with the fact that it holds for (m = n= 1),,,,,, (m = n= 2) and (m = n= P) concludes that N = $\sum_{i = 1}^{m} \sum_{j = 1}^{n} 11$ is valid for any m = n.

However, the number of choices of supplies and demands within their respective ranges in Juman and Hoque [5] upper bound technique is $\sum_{i = 1}^{m} \sum_{j = 1}^{n} \min [({\bar{S}}_{i} - {\underline{S}}_{i} + 1), ({\bar{D}}_{j} - {\underline{D}}_{j} + 1)]$ . The number of choices of supplies and demands within their respective ranges in our proposed method is less than the number of choices of supplies and demands within their respective ranges in Juman and Hoque [5] upper bound technique. This is provided in the following Theorem 2.

Theorem 2. The number of choices of supplies and demands within their respective ranges in our proposed method is less than the number of choices of supplies and demands within their respective ranges in Juman and Hoque [5] upper bound technique.

i.e. $\sum_{i = 1}^{m} \sum_{j = 1}^{n} 11 < \sum_{i = 1}^{m} \sum_{j = 1}^{n} \min [({\bar{S}}_{i} - {\underline{S}}_{i} + 1), ({\bar{D}}_{j} - {\underline{D}}_{j} + 1)]$

The proof is obvious. Because, $\sum_{i = 1}^{m} \sum_{j = 1}^{n} 11$ is equal to $\sum_{i = 1}^{m} \sum_{j = 1}^{n} \min [11, 11]$ and $\sum_{i = 1}^{m} \sum_{j = 1}^{n} \min [11, 11] < \sum_{i = 1}^{m} \sum_{j = 1}^{n} \min [({\bar{S}}_{i} - {\underline{S}}_{i} + 1), ({\bar{D}}_{j} - {\underline{D}}_{j} + 1)]$ we have $\sum_{i = 1}^{m} \sum_{j = 1}^{n} 11 < \sum_{i = 1}^{m} \sum_{j = 1}^{n} \min [({\bar{S}}_{i} - {\underline{S}}_{i} + 1), ({\bar{D}}_{j} - {\underline{D}}_{j} + 1)]$ . Note that, this proof also can be preceded by mathematical induction.

Based on this notion, the new solution method for finding the upper least aggregated expense bound is described below.

An Algorithm: α - β cut method

Step 1: In the extended model, replace ${\hat{S}}_{i}$ & ${\hat{d}}_{j}$ by $α_{i} S_{i} + (1 - α_{i}) {\bar{S}}_{i} & β_{j} D_{j} + (1 - β_{j}) {\bar{D}}_{j}; \forall i, j$ respectively; where, 0 ≤ α_i ≤ 1 & 0 ≤ β_j ≤ 1 ∀ i, j.

Step 2: By setting α_i = 0 & β_j = 0; i=1,2,...m & j=1,2,...n, the least aggregated expense "C₀₀" of the extended transportation model is calculated. Set UB_(temp) : = C₀₀ and Set $X_{temp} : = ({\bar{X}}_{mxn})$ which is the upper bound solution associated with C₀₀.

Step 3: Set i=1 & j=1.

Step 4: Set k=1.

Step 5: If both α_i ≠ 1 & β_j ≠ 1, then increase α_i by 0.1 and the calculate the respective β_j by $β_{j} = β_{j}^{p} + ({\underline{S}}_{i} / {\underline{D}}_{j}) * (0.1)$ ; where $β_{j}^{p}$ is the previous value of β_j.

Else, If (α_i = 1 & β_j ≠ 1) or (α_i = 1 & β_j = 1) then go to step 13

Else go to step 12.

Step 6: If α_i > 1 or β_j > 1 then by setting α_i = 1 or β_j = 1 the respective α_i or β_j is calculated by using $β_{j} = β_{j}^{p} + ({\underline{S}}_{i} / {\underline{D}}_{j}) * (0.1)$ or $α_{i} = α_{i}^{p} + ({\underline{D}}_{j} / {\underline{S}}_{i}) * (1 - β_{j}^{p})$ ; where $α_{i}^{p}$ and $β_{j}^{p})$ are the previous values of α_i and β_j) respectively.

Step 7: Solve the resulted mathematical model and find the least aggregated expense C_ij (say) & its corresponding solutions $(X_{ij}^{k})_{mxn}$ (say).

Step 8: If (k <10) and (α_i ≠ 1 & β_j ≠ 1) then set k=k+1 and go to step 5

Step 9: Find C_ij = $Max C_{ij}^{k} : \forall$ possible value of k & its corresponding solutions (X_ij) _mxn; and its corresponding α_i & β_j values are a_i & b_j respectively.

Step 10: If C_ij >UB_(temp) then set UB_(temp):= C_ij; set α_i = a_i & β_j = b_j where a_i & b_j are associated with C_ij; set X₍temp) = (X_ij) _mxn which is the upper bound solutions associated with C_ij.

Step 11: If both α_i ≠ 1 & β_j ≠ 1 then go to the next step. Else go to step 5.

Step 12: If j<n then set j=j+1 and go to step 4.

Step 13: If i<m then set i=i+1 and go to step 4.

Step 14: Stop. Take the current UB₍temp) as the upper least aggregated expense bound, the corresponding X₍temp) as its solution, and the corresponding α_i & β_j; i=1,2,..m & j=1,2,...n values.

Figure 2 shows a flowchart of the proposed transportation model and algorithms.

Fig. 2

Flowchart of the proposed transportation model.

4 A comparative study of the [11] approach, Juman and Hoque [5] approach and the technique developed here

Our proposed algorithm is intended to solve the benchmark, some considerably haphazard conditions and a real-world yoghurt distribution and comparison is maintained with [11] and [5], so that the performance of our method is assessed.

4.1 Test-1: Comparison on benchmark instance and some randomly generated ones

The initial solution to the eight 2-supplier 3-consumers numerical problems were evolved by Juman and Hoque [5] and [11] techniques. In this paper, this similar problem is innovatively solved in our proposed developed algorithm. For these eight benchmark instances, our proposed algorithm impact on achieving remarkably higher (or same) upper bound solutions. For the numerical instances 2, 6, and 8 from Table 1 of Ref.([5]) which are sequentially the instances 6, 7, and 8 in Table 1, our new method obtains better closer-optimal upper bound on the least aggregate expenditure as compared to [11] and [5] techniques. The upper bound of the least aggregated expenditure for each of remaining ones (instances 1, 3, 4, 5, and 7), our new method obtains the best similar achievement of [11] and [5] techniques. Moreover, the upper bound of the least aggregated expenditure for each of instances 1, 2, 3, and 4 from Table 2 of Ref.([5]), our new method obtains the best similar achievement of [11] and [5] techniques.

Table 2
Comparative results of eight numerical problems obtained by [11] method, Juman and Hoque [5] method and our method

Numerical problems Upper minimal T.cost bound (Z) by % increase in the Upper Bound by our method over

[11] method J &H (2014)’s method Our method [11] method J &H (2014)’s method

1 7710 7710 10285 33.4 33.4

2 7530 7530 8990 19.4.4 19.4

3 5250 5370 10230 94.9 90.5

4 8515 8515 10115 18.8 18.8

5 13235 13235 15060 13.8 13.8

6 4350 4725 4800 10.30 1.59

7 4350 7725 7800 79.30 0.97

8 7290 8010 8460 16.10 5.62

Numerical problems	Upper minimal T.cost bound (Z) by % increase in the Upper Bound by our method over
1	7710	7710	10285	33.4	33.4
2	7530	7530	8990	19.4.4	19.4
3	5250	5370	10230	94.9	90.5
4	8515	8515	10115	18.8	18.8
5	13235	13235	15060	13.8	13.8
6	4350	4725	4800	10.30	1.59
7	4350	7725	7800	79.30	0.97
8	7290	8010	8460	16.10	5.62

Figure 3 shows several approaches comparing with the proposed method. From Fig. 3, we can deduce that the performance of the proposed method.

Fig. 3

Comparison results of several approaches.

In order to analysis the efficiency of the new heuristic algorithm in attaining the upper least expenditure bound to the problem instances, here we also maintain analogous investigation of our proposed algorithm with [11]and [5] methods on the upper bound found for 5 randomly generated instances (numerical instances 1-5 from Table 1 of this paper). The data for these problems are revealed in Appendix A and the pertaining output are demonstrated in Table 2. In the table the performance of the new method of this paper is calculated and denoted as the increase of percentage valuein the upper least aggregated expenditure bound of a numerical problem attained by this new algorithm and it also corresponds over the initially evolved [11] and the [5] techniques. This is illustrated at the right hand columns of Table 2.

The proposed algorithm in this research is accountable for increasing upper bound of the lease aggregated expenditure percentage to all the eight problems. This contribution of our algorithms is elucidated in Table 2 at right hand column. As a paradigm, in Table 2, for numerical problem 3, the close-optimal upper least aggregated expense bound found by both [11] and [5] approaches are 5250 and 5370 respectively. But, the near-optimal upper least aggregated expenditure bound evaluated by this approach is 10230, which increases by 94.9% and 90.5% in comparison to those found by [11] and [5] approaches sequentially. This shows that in certain cases, even for small size problems, both [11] and [5] approaches find the close-optimal upper least aggregated expenditure bound distant beneath the exact upper bound on the least aggregated expenditure. In order to see the validity of our proposed method further, our method is applied to a real-world yoghurt distribution problem and got very satisfactory results compared to the existing methods.

4.2 Test-2: Comparison on a real world application

The two warehouses of the yoghurt factory are located in two different places at Ibbankatuwa, Dambulla, Sri Lanka and the yoghurts are distributed island wide to all 25 distribution centres. All required data were collected from yoghurt factory and used for obtaining the upper minimal total cost bound of the concerned transportation problem with varying demands and supplies. The supply parameter range for the warehouse of the factory, unit shipping cost and the demand parameter ranges of 25 distribution centres are given in the following Tables 3, and 4 respectively.

Table 3
Supply range for the warehouse of the factory

Minimum Value Maximum Value

Warehouse 1 1,783,563 2,629,780

Warehouse 1 891,782 1,314,890

	Minimum Value	Maximum Value
Warehouse 1	1,783,563	2,629,780
Warehouse 1	891,782	1,314,890

Table 4

Demand ranges for the Distribution centres and cost coefficient values

Distribution centre	Minimum value (num. of yoghurts)	Maximum value (num. of yoghurts)
Anuradhapura	111,432	154,394
Ampara	105,421	152,096
Badulla	107,932	154,291
Batticaloa	103,832	153,904
Colombo	112,930	166,653
Galle	109,320	158,345
Gampaha	109,792	159,710
Hambantota	108,943	159,502
Jaffna	107,378	158,303
Kalutara	109,356	158,423
Kandy	109,546	157,301
Kegalle	106,950	156,422
Killinochchi	108,558	157,521
Kurunegala	107,354	158,341
Mannar	103,831	159,321
Matale	102,532	157,931
Matara	109,983	159,213
Monaragala	104,348	157,310
Mullativu	106,590	157,310
Nuwara Eliya	99,034	156,193
Polonnaruwa	106,492	157,391
Puttalam	101,853	158,542
Ratnapura	109,867	159,342
Trincomalee	107,990	159,321
Vavuniya	100,002	156,903

The above unit costs and the varying supply and demand values can also be represented by the following network diagram.

The following Table 2 represents the comparative solution of the upper minimal total cost bound obtained by [5, 11] techniques and the technique developed here.

For the above real world problem, the new method developed here finds the higher near-optimal upper minimal total cost bound in comparison with previous ones. Thus the new Algorithm performs much better than [5] and [11] approaches in obtaining the upper minimal total cost bound to the above studied real world yoghurt distribution problem. This shows how approximately our method can at least provide a better measure than that of the existing benchmark measures.

Here, we solve all benchmark instances from [5] and some randomly generated instances and a real-world application by these methods and found that the proposed algorithm provides the same or significantly better near-optimal upper least aggregated expenditure bound disregarding any restriction to operational design domain. Thus the new heuristic performs more efficiently than [11] and [5] methods in obtaining the upper bound on the least aggregated expenditure for these studied numerical problems.

5 Discussion

In practice, even for the small problem instances, the interval sizes of varying supplies and demands can be quite large. Therefore, the number of possible combinations of values of all capacities and all demands can be very high (for example, our yoghurt distribution problem), Fig. 4. So, these supplies-demands interval range must be handled very carefully to obtain a better estimation of the worst case realization on the minimal total costs of our studied problem. So, unlike in the other existing methods, in our proposed method all interval ranges are transformed into their respective convex combinations. Meaning that, we have expressed all the varying supplies and demands as convex combinations of their respective the lower and the upper bound values. Hence, we can systematically handle the supplies-demands interval ranges on the concerned problem. This may be one of the major reasons for our method to provide a better near optimal estimation of the worst case realization on the minimal total costs of our studied problem compared to the existing methods, Table 5. However, the optimality of our proposed method to find the estimation of the worst case realization on the minimal total costs cannot be guaranteed, though it provides a better near optimal upper bound. Besides, to the best of our knowledge, none of the existing methods can determine the optimal upper least aggregated expenditure bound to our studied problem, UTPIDS. So, determination of an exact upper least aggregated expenditure bound to the UTPIDS would be a challenging research topic in future.

Fig. 4

Transportation system of the factory.

Table 5

Comparative upper bound solution of the real-world application obtained by [5] and [11] techniques and our method

Numerical problems	Upper minimal T.cost bound (Z) by % increase in the Upper Bound by our method over
	[11] method	J &H (2014)’s method	Our method	[11] method	J &H (2014)’s method
1	933,546	933,546	1,376,777	47.5	47.5

6 Conclusion

The uncapacitated transportation problem with interval-defined demands and suppliers capacities (UTPIDS) is investigated in this paper. There lies an extreme NP complexity in determining the upper lease aggregated expenditure bound of UTPIDS. Juman and Hoque [5] extended the [11] model to include the inventory costs during transportation and at destinations, as they are interrelated factors. Then they developed two heuristic techniques to find the lower and the upper minimal total cost bounds to this extended model. In comparison with [11], although it provided the same or better upper minimal total cost bound to all the instances considered, it was observed that even for some problems, Juman and Hoque [4] sometimes finds the near-optimal upper bound far below the exact upper bound on the minimal total cost of the UTPIDS; (e.g., the third numerical example problem in Table 2). Besides, in this paper, we demonstrate that the existing methods unable to find an exact upper minimal total cost bound to a UTPIDS. So, it creates a scope of finding an exact or a better near-optimal upper lease aggregated expenditure bound to the UTPIDS. Hence we develop here a convex combination based polynomial time algorithm that runs in O (N2) time (N, higher of the numbers of source and destination nodes) to find a better near-optimal upper lease aggregated expenditure bound of UTPIDS. A comparative study on each solution of benchmark instances, randomly generated ones, and a real world yoghurt distribution show that this new method significantly outperforms the existing techniques for finding an upper bound on the minimal total cost. Thus the contribution in this paper enriches the current literature with respect of finding a better upper lease aggregated expenditure bound to UTPIDS. This helps the decision makers in making a better decision specially, for proper investment and return to such types of the decision making problems. In our perspective, interestingly, the exact upper lease aggregated expenditure bound of UTPIDS may not occur at the highest total shipment. So, by fine-tuning the supply and/or demand parameter values in their given ranges, more better upper lease aggregated expenditure bound to the UTPIDS could be attained. Future research could be carried out in the following directions: (1) Future research will be devoted to the development of an exact solution method to UTPIDS. (2) In developing the new method, the demand is assumed to be a variable. However, variation in the demand may follow a particular trend. Hence future research might be carried out in extending the extended model, to include an appropriate trend of demand distribution. We intend to devote ourselves in these directions of our future research.

Footnotes

Acknowledgment

The author acknowledges that this research is supported by a research grant of University of Peradeniya, Sri Lanka.

Appendix A

References

Das

S.K.

, Goswami

, Alam

S.S.

, Multiobjective transportation problem with interval cost, source and destination parameters, European Journal of Operational Research 117 (1999), 100–112.

Hitchcock

F.L.

, The distribution of a product from several sources to numerous locations, Journal of Mathematical Physics 20 (1941), 224–230.

Juman

Z.A.M.S.

, Nawarathne

N.G.S.A.

, An efficient alternative approach to solve a transportation problem, Ceylon Journal of Science 48(1) (2019), 19–29.

Juman

Z.A.M.S.

, Hoque

M.A.

, A heuristic solution technique to attain the minimal total cost bounds of transporting a homogeneous product with varying demands and supplies, Applied Soft Computing 34 (2015a), 813–826.

Juman

Z.A.M.S.

, Hoque

M.A.

, A heuristic solution technique to attain the minimal total cost bounds of transporting a homogeneous product with varying demands and supplies, European Journal of Operational Research 239 (2014), 146–156.

Juman

Z.A.M.S.

, Hoque

M.A.

, Buhari

M.I.A.

, Sensitivity analysis and an implementation of the well-known Vogel’s approximation method for solving unbalanced transportation problems, Malaysian Journal of Science 32(1) (2013a), 66–72.

Juman

Z.A.M.S.

, Hoque

M.A.

, Buhari

M.I.

, A study of transportation problem and use of object-oriented programming, 3rd International Conference on Applied Mathematics and Pharmaceutical Sciences (ICAMPS’Singapore, (2013b), 353–354.

Juman

Z.A.M.S.

, Perera

A.K.S.S.

, When can VAM with balanced feature provide an improved solution to an unbalanced transportation problem? European Journal of Scientific Research 135(3) (2015b), 268–275.

Juman

Z.A.M.S.

, Hoque

M.A.A.

, Multi-source multi-destination integrated transportation-inventory system. Proceeding of the third International Conference of Institution of Engineering and Technology (IET), September 17–18, Brunei Darussalam, (2012).

10.

Juman

Z.A.M.S.

, Hoque

M.A.

, An efficient heuristic approach for solving the transportation problem. Proceedings of the International Conference on Industrial Engineering and Operations Management (IEOM), January 7 –9, Grand Hyatt Bali, Indonesia. ISBN: 978-0-9855497-1-8, ISSN: 2169-8767.

11.

Liu

S.T.

, The total cost bounds of the transportation problem with varying demand and supply, Omega 31 (2003), 247–251.

12.

Safi

M.R.

, Razmjoo

, Solving fixed charge transportation problem with interval parameters, Applied Mathematical Modelling 37 (2013), 8341–8347.

13.

Ebrahimnejad

, Verdegay

J.L.

, A new approach for solving fully intuitionistic fuzzy transportation problems, Fuzzy Optimization and Decision Making 17(4) (2018), 447–474.

14.

Ebrahimnejad

, Verdegay

J.L.

, An efficient computational approach for solving type-2 intuitionistic fuzzy numbers based transportation problems, International Journal of Computational Intelligence Systems 9(6) (2016), 1154–1173.

15.

Ebrahimnejad

, New method for solving fuzzy transportation problems with LR flat fuzzy numbers, Information Sciences 357 (2016a), 108–124.

16.

Ebrahimnejad

, Fuzzy linear programming approach for solving transportation problems with interval-valued trapezoidal fuzzy numbers. Sādhanā 41(3) (2016b), 299–316.

17.

Bagheri

, Ebrahimnejad

, Razavyan

, Hosseinzadeh Lotfi

and Malekmohammadi

, Solving the fully fuzzy multi-objective transportation problem based on the common set of weights in DEA, Journal of Intelligent & Fuzzy Systems 39(3) (2020), 3099–3124.

18.

Sharma

R.R.K.

, Prasad

, Obtaining a good primal solution to the uncapacitatedtransportation problem, European Journal of Operational Research, 144 (2003), 560–564.

19.

Sharma

R.R.K.

, Sharma

K.D.

, A new dual based procedure for the transportation problem, European Journal of Operational Research 122(3) (2000), 611–624.

20.

Vancroonenburg

, Croce

F.D.

, Goossens

, Spieksma

F.C.R.

, The red–bluetransportation problem, European. Journal of Operational Research 237 (2014), 814–823.

21.

Masoud

, Kozan

, Kent

, A constraint programming approach to optimise sugarcane rail operations. In Proceedings of the 11th Asia Pacific Industrial Engineering and Management Systems Conference: (2010). (pp. 1–7). University of Malaysia.

22.

Masoud

, Kozan

, Kent

G.A.

, A new approach to automatically producing schedules for cane railways. In Proceedings of the 34th Conference of the Australian Society of Sugar Cane Technologists (Vol. 34). Australian Society of Sugar Cane Technologists (2012).

23.

Masoud

, Kozan

, Kent

, A near Optimal Cane Rail Scheduler under Limited and Unlimited Capacity Constraints. In Proceedings of 21st International Congress on Modelling and Simulation (2015, November), (pp. 1738–1744).

24.

Matindi

, Masoud

, Hobson

, Kent

, Liu

, Harvesting and transport operations to optimise biomass supply chain and industrial biorefinery processes, International Journal of Industrial Engineering Computations 9(3) (2018), 265–288.

25.

Masoud

, Kozan

, Kent

, Liu

S.Q.

, An integrated approach to optimise sugarcane rail operations, Computers & Industrial Engineering 98 (2016), 211–220.

26.

Masoud

, Kozan

, Liu

S.Q.

, Elhenawy

, Corry

, Burdett

, D’ariano

, A real-world transport scheduler applied to Australian sugarcane industry. In 23rd IEEE International Conference on Intelligent Transportation Systems (2020, September).

27.

Masoud

, Kozan

, Kent

, Liu

S.Q.

, A new constraint programming approach for optimising a coal rail system, Optimization Letters 11(4) (2017), 725–738.

28.

Masoud

, Khalifa

H.A.

, Liu

S.Q.

, Elhenawy

, Wu

, A fuzzy goal programming approach for solving fuzzy multi-objective stochastic linear programming problem. In International Conference on Industrial Engineering and Systems Management (IESM) (2019, September) (pp. 1–6). IEEE.

29.

Matindi

, Hobson

, Masoud

, Kent

, Liu

, Developing a versatile simulation, scheduling and economic model framework for bioenergy production systems, International Journal of Industrial Engineering Computations 10(1) (2019), 17–36.

30.

, Xi

, Liu

S.Q.

, Li

, Chen

, Wu

, Masoud

, An improved evaluation framework for industrial green development: Considering the underlying conditions, Ecological Indicators 112 (2020), 106044.

A new algorithm for solving uncapacitated transportation problem with interval-defined demands and suppliers capacities

Abstract

Keywords

1 Introduction

1.1 The research motivation and challenges

1.2 Our contribution

2 Transportation model with varying supplies and demands

4.1 Test-1: Comparison on benchmark instance and some randomly generated ones

Table 3 Supply range for the warehouse of the factory Minimum Value Maximum Value Warehouse 1 1,783,563 2,629,780 Warehouse 1 891,782 1,314,890

Footnotes

Acknowledgment

Appendix A

References

Table 3
Supply range for the warehouse of the factory

Minimum Value Maximum Value

Warehouse 1 1,783,563 2,629,780

Warehouse 1 891,782 1,314,890