Abstract
This paper deals with the multi-choice transportation problem (TP) in which the parameters of the TP such as the cost coefficients of the objective function, supplies and demands of the constraints are all followed multi-choice parameters. The main aim of this paper is to select an appropriate choice from the multi-choices for the cost coefficients of the objective function, supplies and demands of the constraints in TP by introducing Lagrange’s interpolating polynomial in such a way that the total cost is minimum. Finally, a non-linear mathematical model has been formulated. Using LINGO software, the optimal solution of the proposed problem is obtained. A real-life problem on multi-choice TP is considered to illustrate the proposed method in this paper.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Introduction
Transportation problem deals with the distribution of goods from several points of supply, such as factories, often known as sources, to a number of points of demand, such as warehouses, often known as destinations. Each source is able to supply a fixed number of units of the product, usually called the capacity or availability, and each destination has a fixed demand, usually known as requirement. The main objective of TP is to schedule shipments from sources to destinations so that the total transportation cost is minimum. The transportation problem mainly contains three parameters namely cost coefficient, supply and demand parameters. Due to some uncountable factors, these parameters are not always stable or not known exactly. This imprecision occurs from the lack of exact information.
Most of the real world decision making problems of practical importance are modeled on multi-choice parameters. The methods of multi-choice optimization have become increasingly important in the field of economics, industry, transportation, military purpose and technology etc. The cost coefficients \( C_{ij} \) of the objective function may represent the transportation cost of unit product from source \(i\) to destination \(j\). Due to increase of the fuel price and other considerable factors, let us introduce multi-choice type for the cost coefficients of the objective function for the transportation problem. Again due to the fluctuations of market price for any type of products, the supply and demand parameters should also follow multi-choice type.
During past few years, many researchers have showed great interest in the field of transportation problem and a number of methods have been proposed for solving it by several researchers [1–4]. The transportation model was first studied by [2], who gave an incomplete algorithm for obtaining the solution and [1] considered the problem of minimizing the cost of distribution of products from several factories to a number of customers. He also developed a procedure to solve the transportation problem.
Healy [5] first developed a procedure for linear programming problem with zero-one variables, which is called multiple choice programming. A method for modeling the multi-choice programming problem, using binary variables was presented by Chang [6]. He presented a mathematical model where the multiplicative terms of binary variables were replaced by continuous variables. Again Chang [7] proposed a revised method of multi-choice goal programming model which does not involve multiplicative terms of binary variables to satisfy the multiple aspiration levels. Biswal and Acharya [8] formulated the interpolating polynomials to handle the multi-choice parameters included in the linear programming problem in which the constraints were associated with some multi-choice parameters. Roy et al. [9], Mahapatra et al. [10] and Roy [11] presented the procedures to solve the multi-choice stochastic transportation problem where the authors converted the multi-choice transportation problem into a standard mathematical programming through the selection of binary variables, bounds for binary codes and restriction of binary codes using auxiliary constraints. Recently Maity and Roy [12, 13] presented the studies on multi-choice TP and their applications to real-life transportation problems.
Most of the multi choice programming problems are based on selection of binary variables, bounds for binary codes and restriction of binary codes using auxiliary constraints which are very difficult to transform and solve the mathematical programming involving more number of alternatives or choices. To avoid the computational burden and other difficulties, Lagrange’s interpolating polynomial is incorporated to select a particular choice from the multi choice parameters. The multi choice parameters of TP are replaced by Lagrange’s interpolating polynomial and using some standard numerical methods [14] we have formulated the nonlinear programming problem and then to solve it, which is the main motivation in this paper. Due to increase the fuel price, road tax, market fluctuation, and other considerable factors, this paper considers the cost coefficients of the objective function, supply and demand parameters based on multi-choices for the real-life transportation problem.
The remainder is organized as follows: “Mathematical Model” section derives the mathematical model of the proposed transportation problem. “Case Study” section contains a case study to illustrate the proposed methodology. “Conclusion” section discusses the conclusion regarding this article.
Mathematical Model
Considering the situation having \(m\) origins (sources) \(S_i~ (i=1,2,\ldots ,m)\) and \(n\) destinations (demands) \(D_j~(j=1,2,\ldots ,n)\) for the classical transportation problem. The sources may be production facilities, warehouses, supply points and the destinations are consumption facilities, warehouses or demand points. Let the supplies \((a_1,a_2,\ldots ,a_m)\) be the quantity of homogeneous product, which are to transport from \(m\) origins \(S_i~(i=1,2,\ldots ,m)\) to \(n\) destinations \(D_j~(j=1,2,\ldots ,n)\) and satisfy the demands \((b_1,b_2,\ldots ,b_n)\) respectively. The cost coefficients \( C_{ij} \) of the objective function may represent the transportation cost, unfulfilled supply and demand, and others are provided with transporting a unit of product from source \(i\) to destination \(j\). Here \( z \) represents the minimum value of the objective function and assuming that \( a_i>0,~~ b_j>0,\) and \(C_{ij}> 0.\) Again assuming that \(C_{ij} \in \{C^{1}_{ij},C^{2}_{ij},\ldots ,C^{{s}_{ij}}_{ij}\}\), \(a_i\in \{a^{1}_{i},a^{2}_{i},\ldots ,a^{{o}_{i}}_{i}\} \) and \(b_j \in \{b^{1}_{j},b^{2}_{j},\ldots ,b^{{d}_{j}}_{j}\}, ~~(i=1,2,\ldots , m),~~(j=1,2,\ldots , n)\) are multi-choice parameters. The mathematical model of the multi-choice transportation problem is presented as follows:
Model 1
where
The following cases are to be considered:
-
1.
When \(C_{ij} ~( i=1,2,\ldots , m,~~j=1,2,\ldots , n)\) follows multi-choice parameter.
-
2.
When \(a_i~ (i=1,2,\ldots , m)\) follows multi-choice parameter.
-
3.
When \(b_j ~( j=1,2,\ldots , n)\) follows multi-choice parameter.
Model Under Lagrange’s Interpolating Polynomial
Lagrange’s interpolating polynomial is constructed for the multi-choice parameters taking some integral values for the nodal points. Each node corresponds to exactly one functional value of a multi-choice parameter. Exactly \(o_{i} ~~\text{ or } ~~d_{j} ~~\text{ or } ~~s_{ij} \) number of nodal points are needed if a parameter has \(o_{i} ~~\text{ or } ~~d_{j}~ \text{ or }~ s_{ij} \) number of choices. The multi-choice parameters are replaced by Lagrange’s interpolating polynomial and using some standard numerical methods which selects a parameter from multi-choice parameters.
When \(C_{ij} ~( i=1,2,\ldots , m,~~j=1,2,\ldots , n)\) Follows Multi-choice Parameter
The objective function (1) of Model 1 is defined as follows:
Let \(0,1,\ldots , (s_{ij}-1)\) be \(s_{ij}\) number of node points, where \(C_{ij}^{1},C_{ij}^{2},\ldots ,C^{s_{ij}}_{ij}\) are the associated functional values of the interpolating polynomial at \(s_{ij}\) different node points.
Lagrange’s interpolating polynomial \(P_{s_{ij}-1}(z^{ij})\) of degree \((s_{ij}-1)\) which interpolates the data from Table 1 has been derived as follows:
Then Lagrange’s interpolating polynomial for \(ij\)-th multi-choice parameters has been formulated as follows:
Hence, the objective function (1) is to redefine by considering the Eq. (6) as follows:
Though, in this paper, I have used the Lagrange’s interpolation formula to formulate the objective function into deterministic form, one can use a transformation technique using binary variables (see [13]) to formulate objective function in another form also.
When \(a_i ~(i=1,2,\ldots , m)\) Follows Multi-choice Parameter
The constraint (2) whose right hand side i.e, supply follows multi-choice parameters of the TP of Model 1 is recalled as follows:
Let \(0,1,\ldots , (o_{i}-1)\) are \(o_{i}\) number of node points and \(a^{1}_{i},a^{2}_{i},\ldots , a^{{o}_{i}}_{i}\) are the functional values of Lagrange’s interpolating polynomial at \(o_{i}\) distinct node points.
Lagrange’s interpolating polynomial \(P_{o_{i}-1}(y^{i})\) of degree \((o_{i}-1)\) which interpolates the data from Table 2 has been derived as follows:
Lagrange’s interpolating polynomial for \(i\)-th multi-choice parameters has been constructed as follows:
Using the Eq. (9), the constraint (2) can be transformed as follows:
When \(b_j ~( j=1,2,\ldots , n)\) Follows Multi-choice Parameter
The constraint (3) whose right hand side i.e, demand follows multi-choice parameters of the TP of Model 1 is rewritten as follows:
Let \(0,1,\ldots , (d_{j}-1)\) are \(d_{j}\) number of node points and \(b^{1}_{j},b^{2}_{j},\ldots ,b^{{d}_{j}}_{j}\) are the functional values of Lagrange’s interpolating polynomial at \(d_{j}\) distinct node points.
Lagrange’s interpolating polynomial \(P_{d_{j}-1}(z^{j})\) of degree \((d_{j}-1)\) which interpolates the data from Table 3 has been obtained as follows:
Lagrange’s interpolating polynomial for \(j\)-th multi-choice parameters has been formulated as follows:
Using the Eq. (12), the constraint (3) can be transformed as follows:
Finally, using the Eqs. (7), (10) and (13), the equivalent mathematical programming (Model 2) from the multi-choice transportation problem of Model 1 has been derived as follows:
Model 2
The following case study on petroleum refinery industry is considered to demonstrate the use of proposed methodology in this paper.
Case Study
A petroleum refinery company acts as a leader in the petroleum refinery and marketing sector. The company processes crude oil to produce petroleum products such as petrol, diesel, LPG and kerosene. The company has three storage terminals (here three supplies in terms of TP) and four depots (here four destinations in terms of TP) in a particular region. The company transports refined oil from the storage terminals to depots via tankers over the highways and railways. The transportation cost (in Rupees) for one unit (one gallon ) of refined oil, each treated as of multi-choice parameter. This happens for different uncountable factors such as toll tax, fluctuation of fuel price etc. Due to these factors, assuming that the cost coefficients of TP follow multi-choice parameters (i.e, there are various routes are available from sources to destinations) and the cost matrix of the TP is defined as follows:
where the first element {16, 19, 20} of the above cost matrix indicates that
\(x_{11}\) route either \(16\) or \(19\) or \(20\) required admissible cost\(/\)unit in Rupees.
The other elements of the above cost matrix of TP are defined in the similar way.
Due to manpower, electricity and other factors, assuming that supply amounts follow multi-choice parameters at \(S_{1},~ S_{2},~\text{ and }~ S_{3}\) which are given as \(a_{1}\in \{7,9,10,11, 14\}\), \(a_{2}\in \{10,12,15\}\) and \(a_{3} \in \{4,5,7,8 \}\) respectively. Due to market condition and other unpredictable factors, demand amounts also follow multi-choice type at each destination \(D_{1},~ D_{2},~D_{3}~\text{ and }~ D_{4}\) which are given as \(b_{1} \in \{9,11 \}\), \(b_{2} \in \{3,4,6\}\), \(b_{3} \in \{2,3,5,6\}\) and \(b_{4} \in \{5,6,7,9\}\) respectively. Then the mathematical model of the case study can be expressed as follows:
Model 3:
Using the methodology presented in see “Model Under Lagrange’s Interpolating Polynomial” section, the following equivalent mathematical model has been formulated (Model 4) of the above Model 3 as:
Model 4
Result and Discussion
Using Lingo10 package, the above Model 4 is solved and listed the optimal solution. The optimal solution of the Model 4 is obtained as: \(x_{11}= 6.00,~~x_{13}=2.00,~~x_{22}= 3.00,~~x_{31}= 3.00,~~x_{34}= 5.00,\) and rest of the decision variables are zero. The minimum cost of the objective function is (in Rupees) \(254.00\). The selected parameters for cost coefficients of objective function, supply and demand that provide optimal solution to the problem are as follows:
After obtaining the optimal solution, the problem stated in the case study, the decision maker has decided for selecting the cost of each route, the necessary supply at each origin and the particular demand at each destination. The problem cannot be solved directly without using the multi-choice programming technique.
Conclusion
The aim of this paper is to discuss the solution procedure for multi-choice transportation problem with the consideration of all the parameters which are multi-choice types. Most of the real-life transportation problems, the cost coefficients of the objective function, supply and demand parameters may not be known previously due to uncountable factors. Due to this reason, the cost coefficients of the objective function, supply and demand parameters are multi-choices rather than single choice and keeping in view of all these factors, multi-choice transportation model has been formulated. In mathematical programming, there is no direct methodology to handle the multi-choice parameters. For the first time, and in this paper, Lagrange’s interpolating polynomial is used to handle the multi-choice parameters of TP. Here, the following are the main advantages when Lagrange’s interpolating polynomial is used to solve multi-choice transportation problem.
-
Computation burden is less.
-
The size of the problem is not increased due to absent of auxiliary constraints.
-
Any number of choices for goal can be accommodated.
Finally, the proposed model is highly applicable for solving the real-life transportation problem and by following this model, the decision maker will be more benefitted to take right decision for giving more information.
In future study, the presented methodology of this paper can be extended to multi-objective interval valued multi-choice transportation problem and this methodology may be useful to extract better solution of decision making problems in supply chain management.
References
Hitchcock, F.L.: The distribution of a product from several sources to numerous localities. J. Math. Phys. 20, 224–230 (1941)
Kantorovich, L.V.: Mathematical methods of organizing and planning production. Manag. Sci. 6, 336–422 (1960)
Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963)
Tao, Z., Xu., J.: A class of rough multiple objective programming and its application to solid transportation problem. Inf. Sci. 188, 215–235 (2012)
Healy, W.C.: Multiple choice programming: (a procedure for linear programming with zero-one variables). Oper. Res. 12(1), 122–138 (1964)
Chang, C.T.: Multi-choice goal programming. Omega Int. J Manag. Sci. 35, 389–396 (2007)
Chang, C.T.: Revised multi-choice goal programming. Appl. Math. Model. 32, 2587–2595 (2008)
Biswal, M.P., Acharya, S.: Solving multi-choice linear programming problems by interpolating polynomials. Math. Comput. Model. 54, 1405–1412 (2013)
Roy, S.K., Mahapatra, D.R., Biswal, M.P.: Multi-choice stochastic transportation problem with exponential distribution. J. Uncertain Syst. 6(3), 200–213 (2012)
Mahapatra, D.R., Roy, S.K., Biswal, M.P.: Multi-choice stochastic transportation problem involving extreme value distribution. Appl. Math. Model. 37(4), 2230–2240 (2013)
Roy, S.K.: Multi-choice stochastic transportation problem involving Weibull distribution. Int. J. Oper. Res. 21(1), 38–58 (2014)
Maity, G., Roy, S.K.: Solving multi-choice multi-objective transportation problem: a utility function approach. J. Uncertain. Anal. Appl. 2, 11 (2014). doi:10.1186/2195-5468-2-11
Maity, G., Roy, S.K.: Solving a multi-objective transportation problem with nonlinear cost and multi-choice demand. Int. J. Manag. Sci. Eng. Manag. (2015). doi:10.1080/17509653.2014.988768
Scarborough, J.B.: Numerical Mathematical Analysis. John Hopkins University Press, Baltimore (1950)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Roy, S.K. Lagrange’s Interpolating Polynomial Approach to Solve Multi-choice Transportation Problem. Int. J. Appl. Comput. Math 1, 639–649 (2015). https://doi.org/10.1007/s40819-015-0041-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s40819-015-0041-y