Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.11 No.2 pp.183-187
DOI : https://doi.org/10.7232/iems.2012.11.2.183

Fixed Charge Transportation Problem and Its Uncertain Programming Model

Yuhong Sheng*, 1Kai Yao
*College of Mathematical and System Sciences, Xinjiang University, Urumchi;Department of Mathematical Sciences, Tsinghua University, Beijing, China
1Department of Mathematical Sciences, Tsinghua University, Beijing, China
(Received: February 14, 2012 / Revised: April 18, 2012 / Accepted: April 23, 2012)

Abstract

In this paper, we study the fixed charge transportation problem with uncertain variables. The fixed charge transporta-tion problem has two kinds of costs: direct cost and fixed charge. The direct cost is the cost associated with each source-destination pair, and the fixed charge occurs when the transportation activity takes place in the corresponding source-destination pair. The uncertain fixed charge transportation problem is modeled on the basis of uncertainty theory. According to inverse uncertainty distribution, the model can be transformed into a deterministic form. Finally, in order to solve the uncertain fixed charge transportation problem, a numerical example is given to show the applica-tion of the model and algorithm.

11-2-09.pdf249.7KB

1. INTRODUCTION

The fixed charge transportation problem (FCTP) is an extension of the (linear) transportation problem (TP). Since the fixed charge problem was initialized by Hirsch and Dantzig (1968), it has been widely applied in many decision making and optimization problems. Interested readers may refer to Sun et al. (1998) and Gottlieb and Paulmann (1998). The TP reflects the situation of transporting amounts of a single commodity from a set of plants to a set of customers. The capacities of the plants and the demands of the customers are known in advance, and a feasible transportation plan must obey these restrictions. The goal is to minimize the overall shipping cost with the transportation cost between plants and customers depending linearly on the transported amount of the commodity. Although this is a useful model, in practice fixed costs occur once a transport is estimated between a plant and a customer. The FCTP takes these fixed charges into account, so that the TP is a FCTP with equal fixed costs 0 for all routes.

It is well-known that the TP is one of the important traditional optimization problems, and it has also been widely applied in real-life such as distributing systems, job assignment and transportation. In the traditional TP, there are two kinds of constraints: source constraint and destination constraint. There are many efficient algorithms for solving the traditional transportation problems such as Balinski (1961) and Srinivasan and Thompson (1972). As an extension of the traditional TP, the solid transportation problem (STP) was introduced by Haley (1962) and Li et al. (1997). Another important extension of the traditional TP is FCTP (Jimenez and Verdegay, 1999, 1998; Chanas et al., 1984; Bit et al., 1996). If the cost parameters of the TP are uncertain variables, they are called as uncertain cost transportation problem (UCTP). Along with the development of global economy, production and demand have a growing importance. Transportation model in logistics and supply management plays an important role in reducing costs and improving the service quality (Klingman et al., 1974). In reality, due to changes in market supply and demand, weather conditions, road conditions and other uncertainty factors, uncertainty TP is particularly important. Therefore, studying uncertain TP has important theoretical and practical significance. This paper proposes an UCTP model.

This paper consists of 6 sections, and its frame is organized as follows: In section 2, some basic concepts and properties in uncertainty theory used throughout this paper are introduced. In section 3, an uncertain FCTP model is constructed. In section 4, according to uncertainty theory, the model can be transformed to its deterministic form, and then we can use the classical method to find its solution. A numerical example is given in section 5. A brief summary is presented in section 6.

2. PRELIMINARIES

In order to deal with human uncertainty, an uncertainty theory was established by Liu (2007), and refined by Liu (2010b), which is a branch of mathematics based on normality, duality, subadditivity, and product measure axioms. Since then significant work has been done by researchers based on the uncertainty theory both in theoretical and practical aspects. In theoretical aspect, Liu (2008) proposed an uncertain process which is a sequence of uncertain variables indexed by time or space and uncertain differential equation which is a type of differential equation by canonical process in 2008. Liu (2009a) established uncertain calculus to deal with dynamic uncertain phenomena in 2009. Besides, the concept of uncertain logic was proposed by Li and Liu (2009) to describe uncertain knowledge, uncertain inference was introduced by Liu (2010a) via conditional uncertain measure. Meanwhile, some other theoretical properties of uncertain measure are studied (Gao, 2009; You, 2009). In practical aspect, Liu (2009b) designed uncertain programming that is a type of mathematical programming involving uncertain variables, which has been used to model system reliability design, project scheduling problem, vehicle routing problem and facility location problem. Now, the uncertainty theory has become a mathematical tool to model the indeterminate phenomenon in our real world. In this paper, the uncertainty fixed charge transportation problem (UFCTP) is modeled based on the uncertainty theory. We shall first introduce some information about the uncertainty theory. 

Theorem 1:

(Liu, 2010b) Let  be independent uncertain variables with uncertainty distribution , respectively. If  is a strictly increasing function, then  is an uncertain variable with inverse uncertainty distributions

Theorem 2:

(Liu, 2010b) Let  be independent uncertain variables with uncertainty distribution , respectively. If  is a strictly decreasing function, then  is an uncertain variable with inverse uncertainty distributions

Theorem 3:

(Liu, 2007) Let  and  are independent uncertain variables with expected values. Then for any real numbers  we have 

3. FIXED CHARGE TRANSPORTATION

Let m be for the origin of the number, let n be the number of destination, the direct cost and the fixed charge with respect to the transportation from source i to destination j are denoted by ξij and ηij , respectively, where i =1, 2, L, m, j =1, 2, L, n. The capacity of source i and that of destination j are denoted by   where i =1, 2, L, m, j =1, 2, L, n. Let  be the quantity to be transported from source i to destination j and yij be a 0-1 variable to describe the transporta­tion activity from source i to destination j and is de­fined as

Then the FCTP can be formulated as follows: 

where yij is defined as a function by yij =1 if xij >0, otherwise =0.

In this model, the first constraint implies that the to­tal amount transported from source i is no more than ai , and the second constraint implies that the total amount transported from i sources should satisfy the demand of destination bj . The above model is constructed under certain conditions, that is, the parameters in the model are all fixed quantities. But due to the complex nature of the real world, we may always meet uncertain phenom­ena in constructing a mathematical model. 

In this paper, we assume that the direct cost, the fixed charge, the capacity of each source and each desti­nation are all uncertain variables and denoted by  ai and bj . respectively. For such conditions, we gener­ally add the uncertain variables to the model. In order to describe the problems conveniently, we denote the cost function of model (1) as

Where x,,ξand η denote the vectors consisting of xij , ξij , and ηij , i =1,2, L, m, j =1,2, L, n, respectively.
The main idea of the uncertain programming model is to optimize the expected value of objective function under the chance constraints. 

Definition 1:

Assume that f(x, ξ, η) is an objective func­tion, and gj(x, ξ, η) are constraints functions,  j =1, 2, L,p. A solution x is feasible if and only if

for 

A solution x * is an optimal solution to the uncertain programming model if 

for any feasible solution x.
We may construct the model of the uncertain fixed charge transportation problem as follows:  

In the above model βγ,, i =1, 2, L, m, j =1, 2, L,n are predetermined confidence levels. The objective function implies optimizing the excepted value of the total transportation cost, the first constraint implies that total amount transported from source i should be no more than its supply capacity at the predetermined con­fidence level βi ; the second constraint implies that the total amount transported from i sources should satisfy the requirement of destination j at the predetermined confidence level γj .

4. CRISP EQUIVALENCE OF MODEL

We can see that there are many uncertain variables in the above models. In order to find the best solution, we must compute the expected value or uncertain meas­ure. If the uncertain variables are complex, computing objective value is actually a time-consuming work. So it is better for us to transfer the model into its crisp equiva­lence. In this section, we shall induce the crisp equiva­lence of model under some special conditions. 

Theorem 4:

Assume that ai and βare independent uncertain variables with uncertainty distributions  respectively, then the model (2) is converted to equivalence model:

Proof:

By using the linearity of expected value operator, we can easily prove this theorem, i.e., since ai and βi are independent uncertain variables with uncer­tainty distributions  respectively, then

where 

So the model (3) is converted to equivalence model: 

Note that model (4) is a deterministic programming model. 

5. NUMERICAL EXPERIMENT

In order to show the application of the model, we shall present an example of coal TP in this section. Coal is a crucial energy source in the development of econ­omy and society. Accordingly, how to transport the coal from mines to the different areas economically is also an important issue in the coal transportation. For the con­venience of description, we summarize the problem as follows. Suppose that there are four coal mines to sup­ply the coal for six cities. During the process of trans­portation, two kinds of conveyances are available to be selected, i.e., train and cargo ship. Now, the task for the decision-maker is to make the transportation plan for the next month. At the beginning of this task, the decision maker needs to obtain the basic data, such as supply capacity, demand, transportation cost of unit product, and so on. In fact, since the transportation plan is made in advance, we generally cannot get these data exactly. For this condition, the usual way is to obtain the uncer­tain data by means of experience evaluation or expert advice. Assume that all uncertain variables are normal uncertain variables, in which we suppose: 

then the model (4) is equivalent to the following model: 

And the associated uncertain data are listed in the following Tables 1-4, 

Table. 1.

Table. 2.

Table. 3.

Table. 4.

We also suppose the confidence level is βi =0.9, γj =0.9, i =1, 2, 3, 4, j =1, 2, 3, 4, 5, 6. Then we can get transportation problem cost is 941.1438. And the corre­sponding transportation plan is: 

6. CONCLUSION

This paper mainly investigated the uncertain fixed charge transportation problem based on an uncertainty theory, and an uncertain model was constructed. By ap­plying the uncertainty theory, the uncertain model can be transformed to a deterministic form, and then we can find its solution by the classical method. Finally, as an application of the model and algorithm, we presented a coal transportation problem as example, and the result showed that the proposed uncertain cost transportation problem model works well. 

Reference

1.Balinski, M. L. (1961), Fixed-cost transportation problems, Naval Research Logistics Quarterly, 8, 41-54.
2.Bit, A. K., Biswal, M. P., and Alam, S. S. (1993), Fuzzy programming approach to multiobjective solid transportation problem, Fuzzy Sets and Systems, 57, 183-194.
3.Chanas, S., Kolodziejczyk, W., and Machaj, A. (1984), A fuzzy approach to the transportation problem, Fuzzy Sets and Systems, 13, 211-221.
4.Gao, X. (2009), Some properties of continuous uncertain measure, International Journal of Uncertain, Fuzziness and Knowledge-Based Systems, 17, 419-426.
5.Gottlieb, J. and Paulmann, L. (1998), Genetic algorithms for the fixed charge transportation problem, Proceedings of the IEEE International Conference on Evolutionary Computation, Anchorage, Alaska, 330-335.
6.Haley, K. B. (1962), New methods in mathematical programming: the solid transportation problem, Operations Research, 10, 448-463.
7.Hirsch, W. M. and Dantzig, G. B. (1968), The fixed charge problem, Naval Research Logistics Quarterly, 15, 413-424.
8.Jimenez, F. and Verdegay, J. L. (1998), Uncertain solid transportation problems, Fuzzy Sets and Systems, 100, 45-57.
9.Jimenez, F. and Verdegay, J. L. (1999), Solving fuzzy solid transportation problems by an evolutionary algorithm based parametric approach, European Journal of Operational Research, 117, 485-510.
10.Klingman, D., Napier, A., and Stutz, J. (1974), NETGEN: a program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems, Management Science, 20, 814-821.
11.Li, X. and Liu, B. (2009), Hybrid logic and uncertain logic, Journal of Uncertain Systems, 2, 83-94.
12.Li, Y., Ida, K., Gen, M., and Kobuchi, R. (1997), Neural network approach for multicriteria solid transportation problem, Computers and Industrial Engineering, 33, 465-468.
13.Liu, B. (2007), Uncertainty Theory (2nd ed.), Springer-Verlag, Berlin, Germany.
14.Liu, B. (2009a), Some research problems in uncertainty theory, Journal of Uncertain Systems, 3, 3-10.
15.Liu, B. (2009b), Theory and Practice of Uncertain Programming (2nd ed.), Springer-Verlag, Berlin, Germany.
16.Liu, B. (2010a), Uncertain set theory and uncertain inference rule with application to uncertain control, Journal of Uncertain Systems, 4, 83-98.
17.Liu, B. (2010b), Uncertainty Theory: A Branch of Mathematics for Modeling Human Uncertainty, Springer, Heidelberg, Germany.
18.Liu, B. (2008), Fuzzy process, hybrid process and uncertain process, Journal of Uncertain Systems, 2, 3-16.
19.Srinivasan, V. and Thompson, G. L. (1972), An operator theory of parametric programming for the transportation problem-II, Naval Research Logistics Quarterly, 19, 227-252.
20.Sun, M., Aronson, J. E., McKeown, P. G., and Drinka, D. (1998), A tabu search heuristic procedure for the fixed charge transportation problem, European Journal of Operational Research, 106, 441-456.
21.You, C. (2009), On the convergence of uncertain sequences, Mathematical and Computer Modelling, 49, 482-487.
Do not open for a day Close