Abstract
This paper investigates the fixed charge multi-item solid transportation problem, in which the fixed charges, direct costs, transportation capacities, supply and demand are uncertain variables. Based on the uncertainty theory, expected value programming model and chance-constrained programming model for fixed charge multi-item solid transportation problem are constructed, respectively. We can obtain the optimal solution of two models via solving the relevant deterministic models. Finally, a numerical experiment is implemented to illustrate the application of the models.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
1 Introduction
The transportation problem (TP) is a well-known optimization problem in operational research, which goal is to minimize the total transportation cost and improve the transportation quality. In the traditional transportation problem, source constraint and destination constraint are taken into consideration. But, in real life, there are other constraints be considered. Firstly, solid transportation problem which was defined as transportation of goods by a sequence of two different conveyances was introduced by Haley (1962). After that, Bhatia et al. (1976) gave a method and obtained the minimum time for the solid transportation problem (STP). Li et al. (1997) proposed neural network approach for multi-criteria solid transportation problems. Ojha et al. (2010) provided a solid transportation problem with discounted costs, fixed charges and vehicle costs, which was formulated as a linear programming problem. Secondly, multi-item solid transportation problem (MISTP) is discussed by Kennington and Unger (1976) and Sun et al. (1998). Fixed charge is another research aspect for TP. Since Hirsch and Dantzig (1968) proposed fixed charge transportation problem (FCTP), there are many researchers who investigated this problem: Lotif and Moghaddam (2013) proposed a genetic algorithm using priority-based encoding for linear and nonlinear fixed charge transportation problem.
In classical models of transportation problem, the parameters of the models are supposed to be crisp numbers. However, some nondeterminacy factors might occur in many situations, such as market supply and demand, weather conditions, road conditions. Some researchers believed that these nondeterministic phenomena conform to randomness, and they introduced probability theory into the transportation network problem. Williams (1963) proposed a stochastic transportation model, in which the demands were supposed to be random variables. Following Williams, Yang and Feng (2007) studied a bicriteria solid transportation problem with stochastic parameters. Romeijna and Sargutb (2011) presented a branch-and-price algorithm for solving a class of stochastic transportation problems with single-source constraints.
However, it is not suitable to regard every nondeterminacy phenomenon as random phenomenon, because of the lack of available samples. For instance, when the extreme events occur, it is impossible to get probability distribution. But experts can estimate, based on their experience, the belief degree can be got. In order to deal with this kind of human uncertainty, (2007) founded uncertainty theory, which was refined by Liu (2010b). Since then, uncertainty theory and its application have experienced explosive growth, such as uncertain process (Liu 2008), uncertain differential equation (Chen and Liu 2010; Yao 2013; Gao 2016; Yao and Chen 2013; Yang and Ralescu 2015; Wang et al. 2015, Yang and Shen 2015), uncertain set theory (Liu 2010a; Yao 2015), uncertain programming (Liu 2009a; Li and Qin 2014; Sheng and Gao 2016), uncertain inference (Gao et al. 2010), uncertain economics (Yang and Gao 2017), uncertain management (Gao et al. 2017; Gao and Yao 2015), uncertain finance (Chen and Gao 2013; Guo and Gao 2017), uncertain statistics (Liu 2010b; Gao et al. 2016) and uncertain differential game (Yang and Gao 2013, 2016). Up to now, the uncertainty theory has become a branch of mathematics.
With respect to the uncertain factors of transportation problem, some authors used the uncertainty theory to handel this problem. Sheng and Yao (2012) gave the uncertain model for fixed charge TP. Cui and Sheng (2012) considered the solid transportation problem in uncertain environment and proposed an expected constrained model. Dalman (2017) consider multi-item STP. Zhang et al. (2016) investigated the fixed charge solid transportation problem under uncertainty. Gao et al. (2016) studied uncertain models on railway transportation planning problem. Chen et al. (2017) investigated the solid transportation problem based an entropy in uncertain environment.
Based on their motivations, we extend this work to fixed charge multi-item solid transportation problem (FCMISTP). Uncertain transportation models, namely expected value programming model and chance-constrained programming model, are proposed, respectively. Based on the uncertainty theory, it can be shown that the optimal solution to transportation models can be obtained via solving a relevant deterministic model. Finally, a numerical experiment is implemented to illustrate the application of the models.
The remainder of this paper is organized as follows. In Sect. 2, some basic concepts and properties in uncertainty theory used in this paper are introduced. Sect. 3 is problem description, where the fixed charge multi-item solid transportation problem is briefly explicate, the expected value programming model for FCMISTP is constructed. And a relevant deterministic model can be obtained by uncertainty theory. In Sect. 4, the chance-constrained model for FCMISTP is constructed. And a relevant deterministic model can be obtained by uncertainty theory. In Sect. 5, numerical examples are given to illustrate the models. In Sect. 6, we give a brief summary to this paper.
2 Preliminary
Uncertainty theory provides an axiomatic system to cope with the imprecise information in experts’ experiment data. In this section, we state some basic concepts and properties in uncertainty theory (2007), which will be used to throughout this paper.
Definition 1
(Liu 2007) Let \(\varGamma \) be a nonempty set, and \({{\mathcal {L}}}\) be a \(\sigma \)-algebra over \(\varGamma \). A set function \({\mathcal {M}}:{\mathcal {L}}\rightarrow [0,1]\) is called an uncertain measure if it satisfies the following axioms:
- Axiom 1. :
-
(Normality Axiom) \({\mathcal {M}}\{\varGamma \} = 1\) for the universal set \(\varGamma \).
- Axiom 2. :
-
(Duality Axiom) \({\mathcal {M}}\{\varLambda \} + {\mathcal {M}}\{\varLambda ^{c}\} = 1\) for any event \(\varLambda \).
- Axiom 3. :
-
(Subadditivity Axiom) For every countable sequence of events \(\varLambda _{1}, \varLambda _{2}, \ldots \), we have
The triple \((\varGamma ,{\mathcal {L}},{\mathcal {M}})\) is called uncertainty spaces. Furthermore, Liu (2009b) defined a product uncertain measure by the fourth axiom.
- Axiom 4. :
-
(Product Axiom) Let \((\varGamma _{k},{\mathcal {L}}_{k},{\mathcal {M}}_{k})\) be uncertainty spaces for \(k=1,2,\ldots \). The product uncertain measure \({\mathcal {M}}\) is an uncertain measure satisfying
where \(\varLambda _{k}\) are arbitrarily chosen events form \({\mathcal {L}}_{k}\) for \(k=1,2,\ldots ,\) respectively.
Definition 2
(Liu 2007) An uncertain variable is a measurable function \(\xi \) from an uncertainty space \((\varGamma ,{{\mathcal {L}}},{\mathcal {M}})\) to the set of real numbers, i.e., for any Borel set B of real numbers, the set
is an event.
Definition 3
(Liu 2007) The uncertainty distribution \(\varPhi \) of an uncertain variable \(\xi \) is defined by
for any real number x.
Definition 4
(Liu 2009b) The uncertain variables \(\xi _1,\)
\(\xi _2,\ldots , \xi _n\) are said to be independent if
for any Borel sets \(B_1, B_2,\ldots , B_n\) of real numbers.
Definition 5
(Liu 2010b) Let \(\xi \) be an uncertain variable with regular uncertainty distribution \(\varPhi (x)\). Then the inverse function \(\varPhi ^{-1}(\alpha )\) is called the inverse uncertainty distribution of \(\xi \).
We usually assume that all uncertainty distributions in practical applications are regular. Otherwise, a small perturbation can be imposed to obtain a regular one. The following Theorem 1 shows that the inverse uncertainty distribution has good operational properties, which makes it easy to obtain the solution for the uncertain programming problem.
Theorem 1
(Liu 2010b) Let \(\xi _1,\xi _2,\ldots , \xi _n\) be independent uncertain variables with regular uncertainty distributions \(\varPhi _1, \varPhi _2,\ldots , \varPhi _n\), respectively. If \(f(\xi _1,\ldots ,\xi _n)\) is strictly increasing with respect to \(\xi _1,\xi _2,\ldots ,\xi _m\) and strictly decreasing with respect to \(\xi _{m+1}, \xi _{m+2}, \ldots , \xi _n\), then
has an inverse uncertainty distribution
Definition 6
(Liu 2007) Let \(\xi \) be an uncertain variable. Then the expected value of \(\xi \) is defined by
provided that at least one of the two integrals is finite.
Theorem 2
(Liu 2007) Let \(\xi \) be an uncertain variable with regular uncertainty distribution \(\varPhi \). Then
Theorem 3
(Liu 2010b) Let \(\xi \) and \(\eta \) be independent uncertain variables with finite expected values. Then for any real numbers a and b, we have
3 Expected value programming model for FCMISTP
3.1 Notations
In this section, we will state fixed charge multi-item STP in detail. The fixed charge multi-item STP is to make a transport plan so that the total transportation cost is minimized. We will consider two types of costs, which are the direct cost and the fixed charge. When the conveyance moves on a link, the direct costs will arise along with the cost of per unit. The direct cost, naturally, is a function related to the conveyance type and the characteristic of links.
Different conveyances and different links have different fixed charge. Furthermore, the capacity of each link during the planning period is limited, which is mainly presented in two aspects. First, during one period, the frequency of using each link is limited. Second, on each link, the capacity of every conveyance is limited. To construct the mathematical models for FCMISTP, we need to determine the parameters as follows (Table 1).
3.2 Objective function and constraints
The total fixed charge of opening link is
If \(y_{ijp}=0\), link (i, j) will not be open in this transportation network, so there is no fixed charge in this link. If \(y_{ijp}\ne 0\), the transportation activity is assigned on link (i, j), then the corresponding fixed charge will occur. The total direct transportation cost is
So the total relevant cost can be formulated as
The total quantity carried from source i is no more than \(a_i^k\), we can give the following constraint
The total quantity in destination j is less than \(b_j^k\), so we have
Also, the total amount transportation by conveyance p is no more than its transportation capacity. Then we have the following constraint
3.3 Expected value programming model
Let \(\bar{f}\) be a predetermined maximal cost, the most transportation plan of FCMISTP is that the maximal uncertain measure of the cost less than or equal to \(\bar{f}\).
Definition 7
A solution \((\mathbf {x}^*,\mathbf {y}^*)\) is called most transportation plan of FCMISTP if
holds for any feasible solution \((\mathbf {x},\mathbf {y})\), and \(\bar{f}\) is a predetermined maximal cost.
The main idea of expected value programming model is to optimize the expected value of the objective function, under the expected value constraints. We may construct the model for FCMISTP as follows:
where \(i\in [1,m],j\in [1,n],p\in [1,q],k\in [1,l],~i,j,p,k\in z^{+}.\)
3.4 Deterministic transformation
In order to solve the constructed model, we can transfer them into deterministic form.
Theorem 4
We assume that \({\xi ^{k}_{ijp}}, {\eta _{ijp}}, {a_{i}^k}, {b_{j}^k},{c_{ijp}}\) are independent uncertain variables with regular uncertainty distributions \(\varPhi ^{k}_{ijp}\), \(\varPsi _{ijp}\), \(\varUpsilon _{i}^k\), \(\varLambda _{j}^k\), \(\varTheta _{ijp}\), respectively, then the model (5) is equivalent to the following deterministic transportation model
where \( i\in [1,m],j\in [1,n],p\in [1,q],k\in [1,l],~i,j,p,k\in z^{+}\), and \((\varPhi ^{k}_{ijp})^{-1}\), \((\varPsi _{ijp})^{-1}\), \((\varUpsilon _{i}^k)^{-1}\), \((\varLambda _{j}^k)^{-1}\), \((\varTheta _{ijp})^{-1}\) are the inverse distribution of the distribution \(\varPhi ^{k}_{ijp}\), \(\varPsi _{ijp}\), \(\varUpsilon _{i}^k\), \(\varLambda _{j}^k\), \(\varTheta _{ijp}\), respectively.
Proof
By Theorem 2 and 3, we can get
Similarly, we can prove that \(E\left[ \sum \limits _{p=1}^q \sum \limits _{j=1}^n x^k_{ijp}-a_i^k\right] \le 0\) is equivalent to
\(\mathrm{E}\left[ \sum \limits _{p=1}^q \sum \limits _{i=1}^m x^k_{ijp}-b_j^k\right] \ge 0\) is equivalent to
and \(\mathrm{E}\left[ \sum \limits _{k=1}^lx^k_{ijp}-y_{ijp}{c_{ijp}}\right] \le 0\) is equivalent to
We complete the proof. \(\square \)
4 Chance-constrained programming model for FCMISTP
4.1 Chance-constrained programming model
Let \(\alpha \) be a predetermined confidence level, with \(\alpha \in (0,1)\). The decision maker hopes to get a smallest value \(\bar{f}\) such that uncertain variable \(f(\mathbf {x}^*,\mathbf {y}^*;\mathbf {\xi },\mathbf {\eta })\) is less than or equal to \(\bar{f}\) with predetermined confidence level \(\alpha \).
Definition 8
A solution \((\mathbf {x}^*,\mathbf {y}^*)\) is called \(\alpha -\) transportation plan of FCMISTP if
holds for any feasible solution \((\mathbf {x},\mathbf {y})\) and \(\alpha \in (0,1)\) is a predetermined confidence level.
In order to deal with the optimal problem with uncertain variables, we choose the chance-constrained programming model. When the decision maker gets a transportation plan under the chance-constrained, the model for FCMISTP can be constructed as follows:
where \(i\in [1,m],j\in [1,n],p\in [1,q],k\in [1,l],~i,j,p,k\in z^{+},\) and \(\alpha , \alpha _i^k, \beta _{j}^k, \gamma _{ijp}, ~i=1,2,\ldots ,m,~j=1,2,\ldots ,n,~p =1,2,\ldots ,q,~k=1,2,\ldots ,l\) are predetermined confidence levels.
4.2 Deterministic transformation
Theorem 5
We assume that \({\xi ^{k}_{ijp}}, {\eta _{ijp}}, {a_{i}^k}, {b_{j}^k}, {c_{ijp}}\) are independent uncertain variables with regular uncertainty distributions \(\varPhi ^{k}_{ijp}\), \(\varPsi _{ijp}\), \(\varUpsilon _{i}^k\), \(\varLambda _{j}^k\), \(\varTheta _{ijp}\), respectively, then the model (7) is equivalent to the following deterministic transportation model
where \(i\in [1,m],j\in [1,n],p\in [1,q],k\in [1,l],~i,j,p,k\in z^{+},\) and \((\varPhi ^{k}_{ijp})^{-1}\), \((\varPsi _{ijp})^{-1}\), \((\varUpsilon _{i}^k)^{-1}\), \((\varLambda _{j}^k)^{-1}\), \((\varTheta _{ijp})^{-1}\) are the inverse distribution of the distribution \(\varPhi ^{k}_{ijp}\), \(\varPsi _{ijp}\), \(\varUpsilon _{i}^k\), \(\varLambda _{j}^k\), \(\varTheta _{ijp}\), respectively.
Proof
Let
which is a continuous strictly increasing function. Since \({{\xi ^{k}_{ijp}}, \eta _{ijp}}\) are independent uncertain variables with regular uncertainty distributions, we can suppose \(\tilde{\xi }\) have a regular uncertainty distributions \(\varGamma \), which has inverse uncertainty distributions \(\varGamma ^{-1}\). And by Theorem 1, we can prove that
is equivalent to
So we proved that
is equivalent to
Since \(a_i^k\) is a strictly increasing continuous function, and \(a_i^k\) is uncertain variables with inverse uncertainty distributions \((\varUpsilon _{i}^k)^{-1}\), by Theorem 1, we have
is equivalent to
By the same way, we can prove that
is equivalent to
and
is equivalent to
So the model (7) is equivalent to the deterministic transportation model
where \(i\in [1,m],j\in [1,n],p\in [1,q],k\in [1,l],~i,j,p,k\in z^{+}.\) Model (9) is equivalent to (8). We complete the proof.
\(\square \)
5 Numerical experiments
In this section, a numerical example of uncertain transportation problem is presented to show the application of the models. We consider two items to be transported by two distinct conveyances from two sources to three destinations. The decision maker should make a transportation plan such that the transportation cost minimized. Assume that all uncertain variables are independent zigzag uncertain variables, which are listed in Tables 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11, respectively.
The expected value model (6) for FCMISTP can be converted as follows
In the following model, suppose that the total cost at confidence levels \(\alpha \) is not less than 0.9 , and assume that \(\alpha _i^k=\beta _j^k=r_{ijp}=0.9,~ i=1,2,~j=1,2,3,~p=1,2,~k=1,2\). Thus, the corresponding equivalent model to model (8) is constructed as follows:
For expected value model (10) and chance-constrained model (11), we can use LINGO to obtain the optimal plan in Tables 12 and 13, respectively.
We can also get the optimal transportation cost of model (10) and (11), as follows
6 Conclusion
This paper mainly investigated the multi-item solid transportation problem with uncertainty theory. Based on the uncertainty theory, uncertain transportation models, namely expected value programming model and chance-constrained programming model, are proposed, respectively. In order to solve the model conveniently, we transformed them into its equivalent deterministic form. Finally, as an application of the model, we presented a actual transportation problem as example, the excepted value model and the chance-constrained model were employed as the experimental models.
References
Bhatia H, Swarup K, Puri M (1976) Time minimizing solid transportation problem. Math Oper Stat 7:395–403
Chen X, Liu B (2010) Existence and uniqueness theorem for uncertain differential equations. Fuzzy Optim Decis Mak 9(1):69–81
Chen X, Gao J (2013) Uncertain term structure model of interest rate. Soft Comput 17(4):597–604
Chen B, Liu Y, Zhou T (2017) An entropy based solid transportation problem in uncertain environment. J Ambient Intell Humaniz Comput. doi:10.1007/s12652-017-0535-z
Cui Q, Sheng Y (2012) Uncertain programming model for solid transportation problem. Information 15(12):342–348
Dalman H (2017) Uncertain programming model for multi-item solid transportation problem. Int J Mach Leant Cybern. doi:10.1007/s13042-016-0538-7
Gao R (2016) Milne method for solving uncertain differential equations. Appl Math Comput 11(274):774–785
Gao J, Yao K (2015) Some concepts and theorems of uncertain random process. Int J Intell Syst 30(1):52–65
Guo C, Gao J (2017) Optimal dealer pricing under transaction uncertainty. J Intell Manuf 28(3):657–665
Gao X, Gao Y, Ralescu D (2010) On Liu’s inference rule for uncertain systems. Int J Uncertain Fuzz 18(1):1–11
Gao R, Sun Y, Ralescu D (2016) Order statistics of uncertain random variables with application to k-out-of-n system. Fuzzy Optim Decis Mak 16(2):159–181
Gao Y, Yang L, Li S (2016) Uncertain models on railway transportation planning problem. Appl Math Model 40:4921–4934
Gao J, Yang X, Liu D (2017) Uncertain Shapley value of coalitional game with application to supply chain alliance. Appl Soft Comput 56:551–556
Haley K (1962) The solid transportation problem. Oper Res 11:446–448
Hirsch W, Dantzig G (1968) The fixed charge problem. Naval Res Logist Quart 15:413–424
Kennington J, Unger V (1976) A new branch and bound algorithm for the fixed charge transportation problem. Manag Sci 22:1116–1126
Li X, Qin Z (2014) Interval portfolio selection models within the framework of uncertainty theory. Econ Model 41:338–344
Li Y, Ida K, Gen M, Kobuchi R (1997) Neural network approach for multicriteria solid transportation problem. Comput Ind Eng 33(3–4):465–468
Liu B (2007) Uncertainty theory, 2nd edn. Springer, Berlin
Liu B (2008) Fuzzy process: hybrid process and uncertain process. J Uncertain Syst 2(1):3–16
Liu B (2009) Theory and practice of uncertain programming, 2nd edn. Springer, Berlin
Liu B (2009) Some research problems in uncertainty theory. J Uncertain Syst 3(1):3–10
Liu B (2010) Uncertain set theory and uncertain inference rule with application to uncertain control. J Uncertain Syst 4(2):83–98
Liu B (2010) Uncertainty theory: a branch of mathematics for modeling human uncertainty. Springer, Berlin
Lotif MM, Moghaddam RT (2013) A genetic algorithm using priority-based encoding with new operators for fixed charge transportation problems. Appl Soft Comput 13:2711–2722
Ojha A, Das B, Mondal S, Maiti M (2010) A solid transportation problem for an item with fixed charge vechicle cost and price discounted varying charge using genetic algorithm. Appl Soft Comput 10:100–110
Romeijna HE, Sargutb FZ (2011) The stochastic transportation problem with single sourcing. Eur J Oper Res 214(2):262–272
Sheng Y, Yao K (2012) Fixed charge transportation problem and its uncertain programming model. Ind Eng Manag Syst 11(2):183–187
Sheng Y, Gao Y (2016) Shortest path problem of uncertain random network. Comput and Ind Eng 99:97–105
Sun M, Aronson JE, McKeown PG, Drinka D (1998) A tabu search heuristic procedure for the fixed charge transportation problem. Eur J Oper Res 106:441–456
Wang X, Ning Y, Moughal T, Chen X (2015) Adams–Simpson method for solving uncertain differential equations. Appl Math Comput 271:209–219
Williams A (1963) A stochastic transportation problem. Oper Res 11:759–770
Yang L, Feng Y (2007) A bicriteria solid transportation problem with fixed charge under stochastic environment. Appl Math Model 31:2668–2683
Yang X, Gao J (2013) Uncertain differential games with applicatians to capitalism. J Uncertain Anal Appl l: Article 17
Yang X, Ralescu D (2015) Adams method for solving uncertain differential equations. Appl Math Comput 270:993–1003
Yang X, Shen Y (2015) Runge-Kutta method for solving uncertain differential equations. J Uncertain Anal Appl 3 (Article 17)
Yang X, Gao J (2016) Linear-quadratic uncertain differential games with applicatians to resource extraction problem. IEEE T Fuzzy Syst 24(4):819–826
Yang X, Gao J (2017) Bayesian equilibria for uncertain bimatrix game with asymmetric information. J Intell Manuf 28(3):515–525
Yao K (2013) Extreme values and integral of solution of uncertain differential equation. J Uncertain Anal Appl 1: Article 2
Yao K (2015) Inclusion relationship of uncertain sets. J Uncertain Anal Appl 3: Article 13
Yao K, Chen X (2013) A numerical method for solving uncertain differential equations. J Intell Fuzzy Syst 25(3):825–832
Zhang B, Peng J, Li S, Chen L (2016) Fixed charge solid transportation Pproblem in uncertain environment and its algorithm. Comput Ind Eng 102(2016):186–197
Acknowledgements
This work was supported by the Natural Science Foundation of China (No. 11626234), the Hubei Provincial Natural Science Foundation (No. 2016CFB308), the Higher Educational Science and Technology Program Foundation of Shandong Province (No. J13LI10), and the Foundation of Liaocheng University (No. 318011303).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflicts of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants performed by any of the authors.
Additional information
Communicated by Y. Ni.
Rights and permissions
About this article
Cite this article
Liu, L., Zhang, B. & Ma, W. Uncertain programming models for fixed charge multi-item solid transportation problem. Soft Comput 22, 5825–5833 (2018). https://doi.org/10.1007/s00500-017-2718-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-017-2718-0