Extended Transportation Problem with Non-Homogeneous Costs and Non-explicit Output- A DEA Based Method
Subject Areas : International Journal of Industrial Mathematicsسعید محرابیان 1 * , علی هادی 2 , حسین قهری 3
1 - Department of Mathematics, Faculty of Mathematical Science Computer, Kharazmi University, Tehran, Iran.
2 - Department of Mathematics, Science and Research Branch, Islamic Azad University Tehran, Iran.
3 - Department of Mathematics, Faculty of Mathematical Science Computer, Kharazmi University, Tehran, Iran
Keywords: Linear Programming, Non-homogeneous cost, Transportation problem, Data envelopment analysis (DEA), Production possibility set,
Abstract :
The transportation system could be considered as one of the most prevalent issues in the field of linear programming. There are various costs for shipping from one source to another destination, which are not homogenous. In a study by Amirteimoori [A. Amirteimoori, An extended transportation problem: a DEA based, Central European Journal of Operations Research, 2011], the extended transportation problem was introduced, while many significant questions regarding the production possibility set, the place of costs, the benefits, and the nature of these costs were not addressed. Considering the recent improvements provided in data envelopment analysis, in the present study, we attempt to propose a more meticulous model, which tries to solve the issue of transportation with non-homogeneous costs. Moreover, we provide a comprehensive and consistent reality solution to the transportation problem.
[1] A. Amirteimoori, An extended transportation problem: a DEA based, Central European Journal of Operations Research 14 (2011) 513-521.
[2] A. Amirteimoori, An extended shortest path problem: A data envelopment anlysis approach, Applied Mathmatics Letters 7 (2012) 1839-1843.
[3] C. P. J. Lovell, Radial DEA models without inputs or without output, European Journal of Operational Research 118 (1999) 46-51.
[4] G. R. Jahanshahloo, A Method for solving 0-1 multiple objective Linear programming problem using DEA, J. Oper. Res. Society of Japan 46 (2003) 1189-202.
[5] F. Meng, B. Su, E. Thomson, D. Zhou, P. Zhou, Measuring Chinas regional energy and carbon emission effciency with DEA models: A survey, Appl. Energy 183 (2016) 1-21.
[6] F. Hosseinzadeh Lotfi, Relationship between MOLP and DEA based on output-orientated CCR dual model, Expert Systems with Applications 37 (2010) 4331-4336.
[7] L. H. Chen, An extended assignment problem considering multiple inputs and outputs, Appl. Math. Model 3 (2007) 2239-2248.
[8] Mokhtar S. Bazaraa, Linear programming and network flows, New York: Willey, 2011.
[9] K. Djordjevic, Evaluation of EnergyEnvironment Effciency of European Transport Sectors: Non-Radial DEA and TOPSIS Approach, energies 12 (2019) 1-27.
[10] W. Maity, A new approach for solving dualhesitant fuzzy transportation problem with restrictions, Indian Academy of Sciences 75 (2018) 44-75.
[11] S. Steuer, Multiple Criteria Optimization: Theory, Computation and Application, New York: Joun Wiley and Sons, 1986.
[12] M. Zarafat, L. Angiz, An alternative approach to assignment problem with nonhomogeneous costs using common set of weights in DEA, Far. East J. Appl. Math. 10 (2003) 29-39.
[13] S. Saati, Generalized Dealing Problems with Fuzzy Differential Costs with the help of DEA, Quaterly J. of Sciences 18 (2008) 255-271.
[14] V. Gurupada Maity, Analyzing multimodal transportation problem and its application, Neural Computing and Applications 5 (2019).
[15] Y. Sudipta Midya, Intuitionistic fuzzy multistage multiobjective fixedcharge solid transportation problem in a green supply chain, International Journal of Machine Learning and Cybernetics 20 (2020).
[16] L. Cardillo, A DEA model for the efficiency evaluation of nondominated paths on a road network, European J. Oper. Res 121 (2000) 549-558.
[17] A. Charnes, Measuring the efficiency of decision making units, European Journal of Operational Research 2 (1978) 429-444.
Extended transportation problem with non-homogeneous costs and non-explicit output- A DEA based method
Saeid Mehrabian1
Department of Mathematics, Faculty of Mathematical Science Computer, Kharazmi University, Tehran, Iran
Ali Hadi
Department of Mathematics, Science and Research University, Tehran, Iran
Hoseyn Gahri
Department of Mathematics, Faculty of Mathematical Science Computer, Kharazmi University, Tehran, Iran
The transportation system could be considered as one of the most prevalent issues in the field of linear programming. There are various costs for shipping from one source to another destination, which are not homogenous. In a study by Amirteimoori [1], the extended transportation problem was introduced, while many significant questions regarding the production possibility set, the place of costs, the benefits, and the nature of these costs were not addressed. Considering the recent improvements provided in data envelopment analysis, in the present study, we attempt to propose a more meticulous model, which tries to solve the issue of transportation with non-homogeneous costs. Moreover, we provide a comprehensive and consistent reality solution to the transportation problem.
Keywords: Data envelopment analysis (DEA); Transportation problem; Non-homogeneous cost; Linear programing; Production possibility set
1. Introduction
Redundant, network flow problems were expressed in a state where only one scalar quantity was considered as an edge cost on each edge. In other words, our decision was influenced only by one factor; furthermore, the algorithms used to solve such problems All have been implemented to verify this assumption. While in the real world, there are many factors involved in decision-making.
In other words, there are several weights on each edge. The preliminary studies for these networks are based on two categories:
1. Weights are considered as constraints, these constraints are called bounded network flow problems
2. Weights are considered objective functions. These constraints are called network flow problems with several objective functions.
In addition, there is a special type of multi-objective linear programming [1].
In recent years, researchers and mathematicians have tried to present data envelopment analysis methods to address these two important network problems which can be cited by Cardillo [2], Jahanshahlo et al. [3], Who provided a method for evaluating and identifying efficient paths in the network. Subsequently, Hosseinzadeh et al. [4] presented the DEA method for identifying non-dominated paths in multi-objective circumstances associated with the shortest path.
In recent years, researchers have been working on the assignment problem and the shortest path problem with non-homogeneous costs. Amongst all these efforts, the work presented by Zarafat Angiz et. al. in [5] and Saati et.al. in [6]can be noted in which presented assignment problem with non-homogeneous costs with, respectively, deterministic and fuzzy data. Maity et al. [7]present the concept of uncertainty in a transportation problem using dual hesitant fuzzy numbers. In most of the research works, fuzzy uncertainty has been considered in transportation parameters. They present an optimal solution to the transportation problem with some restrictions under uncertainty by the traditional approach without any mathematical aids. In transportation programs decision makers can have different aims to accomplish for each possible shipment and these goals may conflict with each other. In such cases, we are interested in obtaining a transportation plan with maximum relative efficiency. So, we use the DEA model that contribute to estimating efficient solution.
Furthermore, Amirteimoori [8] describes a model of transportation problem in which any arc of the transportation network has k inputs and s outputs ,and applying DEA he introduces a model for solving such problems. The model proposed by Chen and Lu in [9] for the assignment problem with multiple input and outputs inspires his method. Then using the data envelopment analysis, presented a model for achieving the most efficient path for this problem. However, some points to be considered is firstly, one should recognize that what the production possibility set is in coordinate with the specific characteristics of the problem. Secondly, the main aim of the transportation problem is to send goods from sources to destinations with the lowest cost. However, in Amirteimoori’s work, the position of costs and the essence of costs is not clear. This leads to different situations in obtaining the final answer, and the result is a chaos for the decision maker.
Nowadays, in the competitive market scenario, minimizing the transportation cost in the business economy and government policies is the utmost important matter. Maity & Roy [10]solve transportation problems by considering the multimodal transport systems and utilizing them afterward to solve neural network problems in artificial intelligence.
Yet despite the benefits, transport activities include disadvantages related to responsibilities due to enormous energy consumption. Djordjevi'c&Krmac present the non-radial Data Envelopment Analysis (DEA) model to evaluate energy and environmental efficiency on European road, rail, and air sectors. The evaluation was conducted under the joint production framework, which considers energy and non-energy inputs and desirable and undesirable outputs for the last ten years. [15]. Midyaet. al.[16] have formulated a multi-stage multi-objective fixed-charge solid transportation problem through a supply chain network under a 'green frame' for the first time.
In this paper, after reviewing production possibility sets for the transportation problem, we studied the cost position on the transportation problem and the issue of transportation with non-homogenous costs. In addition, by introduction of the extended transportation problem with non-homogeneous costs, we tried to present a comprehensive and near-realistic approach to the transportation problem.
The organization of the paper: In the following section, we express the transportation problem and make a brief overview of the data envelopment analysis. In the third section, firstly, we study the production possibility set according to the transportation problem, and then, by examining the place of costs in the first stage, we present a method based on two different perspectives for the transportation problem with non-homogeneous costs.
2. Review of the Literature
2.1 Data Envelopment Analysis
Data envelopment analysis (DEA) was firstly introduced by Charnes et. al. [11]. This method applies mathematical programming to calculate the relative efficiency of homogeneous units. In DEA, we consider n homogeneous decision-making units (DMU), each of which applies multiple inputs to produce multiple outputs. An application of DEA models is the calculation of the relative efficiency of decision-making units. Two important models of DEA, the CCR, and BCC are as follow:
CCR OUTPUT-ORIENTED |
BCC OUTPUT-ORIENTED |
2.2 Transportation Problem
Suppose that there are m sources of a particular commodity that correspond to n destinations. Specifically, the
source must exactly propose the quantity 
, while the
destination must receive exactly the quantity; it is assumed that the total demand equals the total supply. There is an associated unit cost for transportation to each path fromsource to destination. The objective is to find paths from sources to destinations by minimizing the overall cost of transportation. Let 
assigned to the number of units shipped along the path 
from source 
to destination
. The mathematical model for the transportation problem is as follows:
To solve the forgoing transportation problem, it is possible to implement the simplex algorithm (Mokhtar S. Bazaraa et al. [16])
3. Extended transportation problem
The extended transportation problem is introduced. Considering the exact definition of the transportation problem presented in section 2.1., it is assumed that the supply and total demand are equal in quantity. In addition, considering each edge as the DMU2, sending the goods from each source to a destination can be seen as 
an input 
and s output 
problem. As a result, k + s attributes, k inputs, and s outputs for each possible arc.
Amirteimoori[1] calculated the relative efficiency for each edge from two perspectives of resources and destinations and created a combination of efficiency
and inefficiency
as the cost for each edge identified the paths with the least inefficiency.
The inefficiency as the cost of each edge, the paths with the least inefficiency is given as:
4. Transportation problem with non-homogeneous cost
Consider the transportation problem as described in section 2.1 with the difference that the shipping cost from source to destination 
is a vector with k nonhomogeneous components, i.e.:
the corresponding table for the transportation problem with non-homogeneous costs is as follows:
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The goal is to find those paths to transporting goods from sources to destinations in such a way that the overall cost of transportation is minimized.
4.1 Production possibility set
By knowing the production function, the efficiency of the decision-making unit can be calculated. However, there are various reasons in some cases the production function, is not calculated and in some cases, while is not possible to calculate the production function, production possibility set is produced and a part of its boundary is considered as an approximation of production function. One of the production possibility set properties is the ability to produce a constant return scale or its variability. On a constant return to scale, the increase in inputs does not save money, nor will it increase costs. This is not the case for today's transportation problems. For this reason, we use models that are consistent with the variable return to scale. As indicated at the beginning of this article, in Amirteimoori's approach [13], the place of costs and the nature of costs are not clear.
This will cause turbulence to the decision maker. as different results are obtained by changing the cost position between inputs and outputs. In subsequent sections, we try to provide another and more effective way to solve this problem.
4.2 Proposal method
Our approach to the transportation problem with non-homogenous costs is to reach this main goal, so that we send goods and supplies at the lowest cost, so it is an efficient path that has the lowest cost to the decision maker. Our method is inspired by Amirteimoori's method [13]in solving the transportation problem. In this way, we also consider each edge of the transportation network as a DMU. Moreover, considering efficiency from two different perspectives, in both aspects of cost considerations, we present a model for finding a cost-effective path in terms of cost.
4.2.1 Source aspect:
We first consider a situation in which a source redundant 
can send and access for all destinations. Since all sources send the goods with the same result to destination j, so we consider each house in the j column as a decision-making unit with k non-homogenous cost. In each DMU, we consider the non-homogenous cost as input, and since the source, sends every input k to send the goods, as well as the ability to send the goods for all destinations, then our output will be the same for all edges. In this case, all outputs can be considered as 1. The unit transport efficiency from source 
to destination is calculated using the CCR model-output oriented as follows:
where ε > 0 is a non-Archimedean construct to assure strongly efficient solutions. As a theoretical construct, ε > 0 performs extremely well, bounding the multipliers away from zero. Transportation cost from warehouse to each destination 
as by changes in the model. Using the above model, the unit transport efficiency from source to destination j can be obtained by changing the index j as follows: 
4.2.2. Destination aspect
we now consider the case where the j-destination can get the goods from all sources.
Since all destinations receive the same result from -th source, so we consider each house in a rowas a decision unit with k non-homogenous cost. In this case, we also consider k as input and since this destination can get its goods from all sources, the output of all units is the same. The CCR model output-oriented calculates the efficiency of the unit of transportation from each m source to the destination j as follows: The CCR model output-oriented is as follows:
Transportation cost from warehouseto each destination as 
by changes in the model. Using model (4), we can obtain the relative efficiency of 
-th destination to each source 
by changing the target destination in the model.
The two groups of relative efficiencies are obtained for the comparisons from either the source side of the destinations side. For the transportation problem with multiple inputs and a dummy variable with value 1 as the output, we need to optimize the total efficiency for the entire shipment. Therefore, we construct a composite efficiency index to integrate two kinds of relative efficiencies as follows:
Ultimately, the effective path in this method is obtained from the following equation:
The above model demonstrates that transportation problems with non-homogenous costs are classical transportation problems and can be solved by the usual algorithm.
5. Numerical example
A car manufacturer has assembly plants located in eight towns: A, B, C, D, E, F, G, and H. the cars are assembled and sent to major markets in three towns: I, J and K. The manufacturer considers three costs as input in all arcs: 1-shipping cost 2- the value of shipment 3-time Therefore the cost vector for each path is (shipping cost, the value of shipment, time). The appropriate input, availability (
), and demand (
) are listed in Table 1.
Table1. The data for the manufacture’s transporting system.
| I | J | K |
|
A | (531, 3500, 500) | (431, 380, 600) | (395, 3950, 400) | 10 |
B | (394, 2850, 600) | (418, 2395, 700) | (512, 2590, 485) | 13 |
C | (405, 310, 800) | (512, 409, 1000) | (412, 390, 1100) | 11 |
D | (355, 290, 705) | (493, 385, 617) | (570, 419, 518) | 7 |
E | (299, 415, 585) | (398, 512, 490) | (315, 255, 380) | 9 |
F | (319, 512, 488) | (464, 215, 305) | (435, 355, 512) | 9 |
G | (619, 612, 619) | (490, 510, 505) | (354, 550, 490) | 4 |
H | (456, 299, 601) | (394, 512, 432) | (439, 499, 519) | 6 |
| 30 | 25 | 14 |
|
Now by solving model (3) and model (4), we combine 3 factors (shipping cost, the value of shipment, and time) for each path. We have solved the data given in Table 1 by using models (3) and (4). The efficiencies for the set of 
and 
are obtained and given in Table2.
Table2 Results of the example
| I | J | K |
A |
|
|
|
B |
|
|
|
C |
|
|
|
D |
|
|
|
E |
|
|
|
F |
|
|
|
G |
|
|
|
H |
|
|
|
The two efficiency scores in each cell represent the efficiency values of each of the 24 units evaluated for each individually assessed aspect(destination aspect and source aspect).
Now we calculate the combined efficiency for each edge-using model 5 and display it in Table 3.
Table 3. composite efficiency
|
We determine the composite efficiency index (
) associated with the particular shipment link (
) by using model (5).
So far, we were able to achieve efficiency (based on the cost of each edge) for each edge, we can use model (6) to achieve the best transportation path from the aspect of sources and destinations. The results of model (6) are shown in Table 4.
TABLE 4. Transportation model output summary
From | TO | Amt shipped | Obj Coef | Obj Contrib |
S1: | D2 | 10 | 1.0168 | 10.1680 |
S2: | D2 | 12 | 1.1352 | 13.6224 |
S2: | D3 | 1 | 1.2569 | 1.2569 |
S3: | D1 | 11 | 1.0381 | 11.4191 |
S4: | D1 | 7 | 1.0000 | 7.0000 |
S5: | D3 | 9 | 1.0000 | 9.0000 |
S6: | D1 | 9 | 1.0000 | 9.0000 |
S7 : | D3 | 4 | 1.0782 | 4.3128 |
S8: | D1 | 3 | 1.0000 | 3.0000 |
S8: | D2 | 3 | 1.0000 | 3.0000 |
| Objective Value (minimum cost) =71.7792 |
|
|
|
Now for finding a transportation plan with maximum efficiency(minimum cost), we solve the transportation problem indicated by the data in table4.
6. Conclusion
The transportation problem is one of the most important linear programming fields, applied to many fields of specialties. In the classical case, it is considered a unit cost for each path. However, it is mostly used for shipping from a source to a destination in the real world, where one is encountered with several incomparable costs.
This paper introduced the transportation problem with non-homogenous costs by defining a k-vector of non-homogenous costs and applying a data envelopment analysis. A method is introduced to reach the most efficient path from the cost perspective. This method is beneficial in the sense that it is specifically designed to transport goods and supply demands at the lowest cost. In addition, the model's stability is ensured by changing the measurement units of the inconsistent costs. A key goal of this paper is to review available approaches critically and discuss technical challenges for the most efficient path. Finally, This method represents optimal costs for all paths. So, the optimal costs that have been achieved via the proposed method, are more realistic and accurate.
This approach is useful in this aspect, which is designed for a specific purpose that the supply of goods and the supply of demand is at a low cost. In addition, the decision maker, as developed in the transportation problem (Amirteimoori [13]), has been disturbed by the costs and different outcomes It was not due to the inclusion of costs between inputs and outputs. Finally, we also justified our generalized model by performing the outcomes on a numerical example.
Today transport is recognized as a significant energy consumer and environmental pollutant, which is considered undesirable output. Therefore, measuring ecological pollutants is a valuable opportunity to evaluate the performance of the transportation problem, while having negative data as undesirable output, and it is likely to be used as positive inputs. Also, the objective function of model SBM is not translation invariance, then we change its objective function with the RAM model. This change will make us able to replace the model with a linear program. Notwithstanding, there is still an excellent opportunity for further investigations in the future.
7. References
[1] | A. Amirteimoori, "An extended transportation problem: a DEA based," Central European Journal of Operations Research, pp. 513-521, 2011. |
[2] | Steuer, Multiple Criteria Optimization: Theory, Computation and Application, New York: Joun Wiley and Sons,, 1986. |
[3] | T. F. D.D.L. Cardillo, "A DEA model for the efficiency evaluation of nondominated paths on a road network," European J. Oper. Res, vol. 121, pp. 549-558, 2000. |
[4] | F. H. L. ,. N. S. G. T. G.R. Jahanshahloo, "A Method for solving 0-1 multiple objective Linear programming problem using DEA," J.Oper. Res. Society of Japan, vol. 46, no. 2, pp. 1189-202., 2003. |
[5] | G. J. M. S. A. E. S. M. F. Hosseinzadeh Lotfi, "Relationship between MOLP and DEA based on output-orientated CCR dual model," Expert Systems with Applications, vol. 37, pp. 4331-4336, 2010. |
[6] | S. S. M. M. M. M. Zarafat Angiz L, "An alternative approach to assignment problem with non-homogeneous costs using common set of weights in DEA," Far East J. Appl. Math , vol. 10, no. 1, pp. 29-39, 2003. |
[7] | S. M. S. a. M. A. Saati, "Generalized Dealing Problems with Fuzzy Differential Costs with the help of DEA," QUARTERLY JOURNAL OF SCIENCES, vol. 18, no. 2, p. 255, 2008. |
[8] | M. K. R. W. Maity, "A new approach for solving dual-hesitant fuzzy transportation problem with restrictions," Indian Academy of Sciences, vol. 75, pp. 44-75, 2018. |
[9] | A. Amirteimoori., "An extended shortest path problem: A data envelopment anlysis approach," Applied Mathmatics Letters, pp. 1839-1843, 2012. |
[10] | H. L. L.H. Chen, "An extended assignment problem considering multiple inputs and outputs," Appl. Math. Model, vol. 3, pp. 2239-2248, 2007. |
[11] | S. K. R. J. L. V. Gurupada Maity, "Analyzing multimodal transportation problem and its application," Neural Computing and Applications, vol. 5, 2019. |
[12] | F. Meng, B. Su, E. Thomson, D. Zhou and P. Zhou, "Measuring China’s regional energy and carbon emission effciency with DEA models: A survey.," Appl. Energy, vol. 183, pp. 1-21, 2016. |
[13] | S. K. R. V. F. Y. Sudipta Midya, "Intuitionistic fuzzy multi‑stage multi‑objective fixed‑charge solid transportation problem in a green supply chain," International Journal of Machine Learning and Cybernetics, vol. 20, 2020. |
[14] | W. C. E. R. A. Charnes, "Measuring the efficiency of decision making units," European Journal of Operational Research, pp. 429-444, 2 (1978). |
[15] | C. P. J. Lovell, "Radial DEA models without inputs or without output," European Journal of Operational Research, vol. 118, no. 1, pp. 46-51, 1999. |
[16] | J. J. J. a. H. D. S. Mokhtar S. Bazaraa, Linear programming and network flows, New York: Willey, 2011. |
[17] | K. Djordjevi´c, "Evaluation of Energy-Environment Effciency of European Transport Sectors: Non-Radial DEA and TOPSIS Approach," energies, vol. 12, no. 2907, pp. 1-27, 2019. |
[1] Corresponding E-mail address: saeid_mehrabian@khu.ac.ir
[2] Decision Making Unit