# An Interactive Approach for Solving the Multiobjective Minimum Cost Flow Problem in the Fuzzy Environment

Authors: Majed G. Alharbi; Hamiden Abd El-Wahed Khalifa; E. E. Ammar
Journal: Journal of Mathematics
 (2020)

---

## Abstract

This paper deals with the multiobjective minimum cost flow (F-MOMCF) with fuzzy penalty characterized by trapezoidal fuzzy numbers. Through the use ofα-cut, the F-MOMCF problem is transformed into the α-MOMCF problem. The α-MOMCF problem can be solved using an interactive approach combined with the weighting Tchebycheff problem. The advantages of this method are that it elicits information from the decision maker (DM) to modify the given constraint set, it gives the optimum penalty, and the effort required for obtaining the solution is reduced. The stability set of the first kind related to the α-best compromise solution is determined. A numerical example is given for illustration and to check the validity of the approach.


---

## Body

## 1. Introduction

Network optimization [1, 2] makes a large part of combinatorial optimization. Pardalos et al. and Migdalas et al. [3, 4] presented a model which is used for a large number of real-world applications in numerous disciplines including communications [5], production and inventory planning, transportation, construction projects [6], water resources management [7], and supply chain management [8]. Minimum cost flow (MCF) problem is one of the most important problems in combinatorial optimization, and it is also a generalized network flow problem which aims to find the least cost of the shipment of a commodity through a capacitated network so as to satisfy demands at certain nodes from available supplies at other nodes. It has enormous applications in practical problems such as transportation, communication, urban design, and job scheduling models [9, 10]. In addition, it is used for solving several real-world problems such as nurse scheduling, project assignment, college course assignment, and multistage production inventory (Ahuja et al. [11]). In real-life situations, fuzzy parameters may be involved since parameters are not always constant.Fuzzy set theory introduced by Dubois and Prade [12] has been widely used to solve many practical problems, including financial risk management, since it allows us to describe and treat imprecise and uncertain elements present in a decision problem. Then, the imperfect knowledge of the returns on the assets and the uncertainty involved in the behavior of financial markets may also be introduced by means of fuzzy m quantities and/or fuzzy constraints. Kumar et al. [13] extended the use of algebraic operations on real numbers to fuzzy numbers by the use of a fuzzification principle. Sakawa and Yano [14] proposed a new computing procedure for solving fuzzy Pythagorean TP, where they extended the interval basic feasible solution and then the existing optimality method to obtain the cost of transportation. Orlovski [15] introduced the concept of α-Pareto optimality of fuzzy parametric programs. One of the difficulties which occurs in the application of mathematical programming is that the parameters in the problem formulation are not constants but fluctuating and uncertain. Tanaka and Asai [16] formulated general multiobjective nonlinear programming problems with fuzzy parameters. El-Sherbeny [17] formulated multiobjective linear programming problems with fuzzy parameters. Ghatee and Hashemi [18] developed a new algorithm of the fuzzy minimum cost flow problem with fuzzy time windows (FMCFPFTW) with an efficient polynomial-time algorithm based basically on Dijkstra’s algorithm. Kumar and Kaur [19] defined the total order on L-R fuzzy numbers and introduced three models for the MCF problem: MCF problem with fuzzy cost, MCF problem with fuzzy supply-demand, and a combination of two cases. Hamacher et al. [20] proposed a new method for solving the single- and multiobjective MCF problem in the fuzzy environment. Sifaleras [21] reviewed theory and algorithms for solving the multiobjective MCF problem that is for continuous and integer case exact and approximation algorithms. Shilaja and Ravi [22] gave a survey of minimum cost network flow (MCNFP). Chen et al. [23] developed an enhanced flower pollination algorithm to solve the optimal power flow (OPF) problem with multiple objectives of minimizing generating cost, transmission loss, and power plant emission and to improve voltage stability. Pankajakshan et al. [24] proposed a novel constraint processing approach, namely, the constraints-prior Pareto-domination approach, for solving the constrained multiobjective optimal power flow problem. Osman [25] proposed a multiobjective optimal experimental design framework to enhance the efficiency of the online model-identification platform.In his earlier work, Osman and El-Banna [26] analyzed the concepts of the solvability set and the stability set of the first and second kinds for parametric convex nonlinear programming problems. Hu et al. [27] introduced the stability of fuzzy multiobjective nonlinear programming problems. Hu and Lee [28] presented a method for the MCF problem which holds complementary slackness and found an augmenting path with the dual approach.In this paper, the minimization problem with fuzzy objective function parameters is reduced into an interval-valued problem and hence into the multiobjective problem with the upper bound and the center of the objective function interval. The objective of the problem is considered as the minimization of the worst and the average case, respectively. The solution sets of our interval optimization problems are the efficient solutions of the corresponding multiobjective problem. Therefore, the optimal solutions against the worst and the average case are defined.The paper is organized as follows: in Section2, the multiobjective minimum cost flow problem in the fuzzy environment is formulated. Section 3 proposes the solution procedure for obtaining optimal compromise solution, and the parametric study related to the α-best compromise solution is defined and determined. In Section 4, an example is given for illustration. Finally, some conclusions are reported in Section 5.


## 2. Problem Formulation and Solution Concepts

Consider the following fuzzy multiobjective minimum cost flow (F-MOMCF) problem [29]:(1)F−MOMCFminf˜rx˜,c∑i,j∈Qc˜ijrxij,r=1,2,…,k,subject toX=∑j:i,j∈Qxij−∑k:k,i∈Qxli=bi,for alli∈V,xij∈Uij, for alli,j∈Qxij≥0,for alli,j∈Q,where Q is the set of arcs (i, j), V is the set of nodes, xij is the decision variable representing the flow through arc (i, j), U is the capacity of arc (i, j), c˜ijr is the fuzzy penalty per unit of flow through arc (i, j) in the c˜ijr objective function, r = 1, 2, …, k, and b(i) is the net flow generated at node i, the values of b(i) being positive, zero, or negative which classify node i as a supply node, transshipment node, or demand node, respectively.It is noted that the parameterscijr are vectors of fuzzy numbers [12]. The fuzzy numbers c˜ijr form a convex continuous fuzzy subset of R whose membership functions μc˜ijrcijr are defined by(1)
A continuous mapping fromR to the closed interval [0, 1](2)
μp˜p = 0 for all p ∈ −∞;p1(3)
Strict increase on p ∈p1,p2(4)
μp˜p = 1 for all p ∈ p2,p3(5)
Strict decrease on p ∈p3,p4(6)
μp˜p = 0 for all p ∈ p4,∞Figure1 illustrates the graph of the membership function of a fuzzy number p˜.Figure 1
Representation of the membership functionμpp [12].In this paper, assume that the F-MOMCF problem is stable [30].Definition 1.
(see [12]). The α-level set of fuzzy numbers cijr is defined as the ordinary set(2)Lαcijr=cijr:μijrcijr≥α,r=1,2,…,k;i,j∈Q.
For a certainα, the F-MOMCF problem becomes [15](3)α−MOMECFminfrx,c∑i,j∈Qcijrxij,r=1,2,…,k,subject toX=∑j:i,j∈Qxij−∑k:k,i∈Qxli=bi,for alli∈V,xij∈Uij, for alli,j∈Qxij≥0,for alli,j∈Q,cijr∈Lαc˜ijr.
Since the F-MOMCF problem is stable, theα-MOMCF problem is also stable. It is noted that the parameters cijr are treated as decision variables rather than constraints.Definition 2.
(see [14]). x∗∈X is said to be an α-Pareto optimal solution to the α-MOMCF problem if and only if there does not exist another xij∈X,∈Lαc˜ijr such that f (x, c) ≤ f (x∗, c∗) and f (x, c) ≠f (x∗, c∗), where the corresponding values of parameters c∗are called α-level optimal parameters.
Assume that theα-MOMCF problem is stable [30].Definition 3.
xij°∈X,cijr°∈c˜ijrα, is an α−parametric efficient solution for the α−MOMCF if and only if there is no xij∈M,cijr°∈c˜ijrα, such that ∑i,j∈Qcijrxij∑i,j∈Qcijr°xij°and∑i,j∈Qcijrxij<∑i,j∈Qcijr°xij° for at least one rr=1,K¯, where cijr are the α−level optimal parameters.Theorem 1.
A pointx°∈M is α−fuzzy efficient of F-MOMCF iff for cijr°∈c˜ijrα,x^ is α−parametric efficient of α-MOMCF.Proof.
Necessity: lex∗cijr∈X be a fuzzy efficient solution to the F-MOMCF problem and not an α−parametric efficient solution of the α−MOMCF problem; then, there exist x¯cijr°∈M for cijr°∈c˜ijr such that f˜rx¯,c˜r≤f˜rx∗,c˜r for r and f˜rx¯,c˜r≠f˜rx∗,c˜r for some r. This leads to(4)μc˜=c∈ℝKm×n:f˜1x¯,c˜r°≤f˜1x°,c˜r°,…,f˜r−1x¯,c˜r°≤f˜r−1x°,c˜r°,f˜rx¯,c˜r°≤f˜rx°,c˜r°,f˜r+1x¯,c˜r°≤f˜r+1x°,c˜r°,…,f˜Kx¯,c˜r°≤f˜Kx°,c˜r°≥α,α∈0,1 and with strict inequality holds for at least one r, which contradicts that x°c°∈M is α−fuzzy efficient solution to F-MOMCF; then, x°c°∈M is an α−parametric efficient solution of the α−MOMCF problem.Sufficiency 1.
1Letx°c°∈M be an α−parametric efficient solution of the α−MOMCF problem but not an α−fuzzy efficient solution to the F-MOMCF problem. Then, there exist X¯¯c˜r°∈X′such that(5)μc˜=c∈ℝKm×n:f˜1x¯,c˜r°≤f˜1x°,c˜r°,…,f˜r−1x¯,c˜r°≤f˜r−1x°,c˜r°,f˜rx¯,c˜r°≤f˜rx°,c˜r°,f˜r+1x¯,c˜r°≤f˜r+1x°,c˜r°,…,f˜Kx¯,c˜r°≤f˜Kx°,c˜r°≥α,α∈0,1, and from the continuity and convexity of the membership function, we get(6)f˜1x¯,c˜r°≤f˜1x°,c˜r°,…,f˜r−1x¯,c˜r°≤f˜r−1x°,c˜r°,f˜rx¯,c˜r°≤f˜rx°,c˜r°,f˜r+1x¯,c˜r°≤f˜r+1x°,c˜r°,…,f˜Kx¯,c˜r°≤f˜Kx°,c˜r°,forcijkrp∈c˜ijkrpα,i=1,m¯;j=1,n¯;r=1,K¯. This is a contradiction.
Theα−MOMCF can be solved by using the weighting Tchebycheff problem:(7)minx∈XUmax1≤r≤γrfrx,cijr−fr∗,cijr∈Lαc˜ijr,or equivalently,(8)minz:γrfrx,cijr−fr∗≤z,r=1,2,…,K,x∈X,cijr∈Lαc˜ijr,where γr≥0,r=1,2,…,K,∑r=1Kγr = 1, and fr∗,r=1,2,…,K, are the ideal targets.Remark 1.
Theα−MOMCF can be treated using the weighting problem, i.e., by considering the following problem:(9)minδrfrx,cijr:x∈X,cijr∈Lαc˜ijr,δr≥0,δr≠0,r=1,2,…,K.
It is clear thatx∗,c∗ is an α−Pareto optimal solution of the α-MOMCF if there exists δ∗≥0 such that x∗,c∗ is the unique optimal solution of problem (9) corresponding to the α−level.
The stability of problems (8) and (9) follows from the stability of the α−MOMCF problem.Remark 2.
Problem (8) can also be written as follows:(10)minf1x,cij1−f1∗subject toγrfrx,cijr−fr∗−f1x,cijr+f1∗≤0,r=2,3,…,K,x∈X,cijr∈Lαc˜ijr.


## 3. Solution Procedure

In this section, the steps of the solution method for obtaining theα−best compromise solution corresponding to the α−level which has the minimum combined deviation from the ideal target fr∗, where(11)fr∗=minx∈XU,c,U∈Lαc,Ufrx,cijr,r=1,2,…,K,and the steps are as follows:Step 1: calculate the maximum and minimum of each objective function individually with respect to the given constraints forα=1 and α=0, respectively.Step 2: compute the initial weights from the following relation:(12)γr=f¯r−f¯r∑r=1Kf¯r−f¯r,wheref¯r is the individual maximum and f¯r is the individual minimum.Step 3: the decision maker selects the initial value ofα0<α<1.Step 4: formulate and solve problem (8) to get x∗,c∗.Step 5: determine the termination. Whenfx∗,c∗ is satisfactory to the DM, let x∗,c∗ be the final solution, and go to step 6. Else, return to step 3.Step 6: determineSx∗,c∗ as follows.Let us consider problem (8) as in the following equivalent form:(13)minz:γrfrx,cijr−fr∗≤z,r=1,2,…,K,x∈X,dij1r≤cijr≤dij2r,where dij1r,dij2r∈Lαc˜ijr,i,j∈Q,r=1,2,…,K. The stability of the α−MOMCF problem implies the stability of problem (13). Sx∗,c∗ can be determined by applying the following conditions:(14)ηrcijr∗−dij2r=0,r=1,2,…,K,ζrdij1r−cijr∗=0,r=1,2,…,K,ηr,ζr≥0,r=1,2,…,K.Consider the following three cases.Case 1:ηr>0,r∈I1⊂1,2,…,K;ηr=0,r∉I1.ζr>0.r∈I2⊂1,2,…,K;ζr=0,r∉I2.LetM be the set of all proper subsets of 1,2,…,K. Then, SI1,I2x∗,c∗=d1,d2∈ℝ2K:dij2r=cijr∗,r∈I1,dij2r≥cijr∗,r∉I1,dij1r=cijr∗,r∈I2,dij1r≤cijr∗,r∉I2. Hence,(15)S1x∗,c∗=∪I1,I2SI1,I2x∗,c∗.Case 2ηr;ζr=0. Then,(16)S2x∗,c∗=d1,d2∈ℝ2K:dij2r≥cijr∗,r=1,2,…,K,dij1r≤cijr∗,r=1,2,…,K.Case 3ηr;ζr>0. Then,(17)S3x∗,c∗=d1,d2∈ℝ2K:dij2r=cijr∗,r=1,2,…,K,dij1r=cijr∗,r=1,2,…,K.Thus,(18)Sx∗,c∗=∪p=13Spx∗,c∗.


## 4. Numerical Example

Consider the following F-MOMCF problem with 5 nodes and 7 arcs as in Figure2.(19)minf1˜=1,2,3,5x12⊕3,4,5,6x13⊕5,7,8,13x24⊕9,10,15,16x25⊕7,8,10,11x34⊕9,10,12,14x35⊕2,4,6,8x45,minf2˜=7,8,9,10x12⊕2,3,4,6x13⊕1,2,3,4x24⊕1,2,3,5x25⊕6,7,8,11x34⊕4,6,9,12x35⊕3,4,6,7x45,subject tox∈X=x12+x13=10,x24+x25−x12=0,x34+x35−x13=20,x34+x35−x13=20,x45−x24−x34=−15,−x25−x35−x45=−15,0≤x12≤10,0≤x13≤10,0≤x24≤15,0≤x25≤10,0≤x34≤5,0≤x35≤15,0≤x35≤15,0≤x45≤10.Step 1: solve the problems(20)minx12+3x13+5x24+9x25+7x34+9x35+2x45min7x12+2x13+x24+x25+6x34+4x35+3x45,max5x12+6x13+13x24+16x25+11x34+14x35+8x45,max10x12+6x13+4x24+5x25+11x34+12x35+7x45,subject tox∈X.The individual minimum isf1¯=230andf2¯=170.The individual maximum isf1¯=445andf2¯=375.Also, the ideal targets aref1∗=410andf2∗=190.Step 2: the weights(21)γ1=f¯1−f¯1f¯1−f¯1+f¯2−f¯2=215420=0.511905,γ2=f¯2−f¯2f¯1−f¯1+f¯2−f¯2=205420=0.488095.Step 3: suppose that the decision maker selectsα=0.80.Step 4: the subproblem to be solved is(22)minz,subject to2.6x12+4.5x13+7.8x24+12.5x25+9x34+11.1x35+5x45−1.9535z≤230,8.5x12+3.6x13+2.5x24+2.6x25+7.7x34+7.6x35+4.9x45−2.0488z≤170,x∈X.Figure 2
A network with 5 nodes and 7 arcs [19].Theα−best compromise solution forz=45.1484 is x12∗=10,x24∗=10, x34∗=5,x35∗=15,x13∗=x25∗=x45∗=0,f1=315.5,andf2=262.5. Also, f1˜=230,280,340,445,f2˜=170,225,295,375.Assume that the solution is satisfactory for the DM, and hence,Sx∗,c∗ is determined as(23)η1cijr∗−dij21=0,r=1,2,η1dij1r−cijr∗=0,r=1,2,η1,η2≥0.We haveI1⊆1,2. For I1=∅,η1,η2=0. Then,(24)SI1x∗,c∗=d2∈ℝ2:d1221≥2.6d2421≥7.8,d3421≥9,d3521≥11.1,d1222≥8.5,d2422≥2.5,d3422≥7.7,d3522≥7.6.ForI2=1,η1>0andη2=0. Then,(25)SI2x∗,c∗=d2∈ℝ2:d1221=2.6,d2421=7.8,d3421=9,d3521=11.1,d1222≥8.5,d2422≥2.5,d3422≥7.7,d3522≥7.6.ForI3=2,η1=0andη2>0. Then,(26)SI3x∗,c∗=d2∈ℝ2:d1221≥2.6,d2421≥7.8,d3421≥9,d3521≥11.1,d1222=8.5,d2422=2.5,d3422=7.7,d3522=7.6.ForI4=1,2,η1>0andη2>0. Then,(27)SI4x∗,c∗=d2∈ℝ2:d1221=2.6,d2421=7.8,d3421=9,d3521=11.1,d1222=8.5,d2422=2.5,d3422=7.7,d3522=7.6.Thus,(28)Sx∗,c∗=∪p=14SIpx∗,c∗.


## 5. Conclusions

In this paper, we have introduced fuzzy multiobjective minimum cost flow, where the penalty is characterized by trapezoidal fuzzy numbers. After converting the problem into the corresponding crisp problem, an interactive approach combined with the weighting Tchebycheff problem is applied for solving the problem, and then,Sx∗,c∗ related to the solution is determined. The advantages of the approach are that it elicits information from the decision maker to modify the given constraint set, it gives the optimum penalty, and the computational effort required for obtaining the final solution is reduced. In addition, the proposed method transforms the fuzzy problem into an interval-valued problem and hence into the multiobjective problem which is significant for using in interactive methods to make any comments by related managers and achieving the logical solutions. Also, GAMS software is applied for obtaining the solution.For future research, there are several directions worth investigating. In this paper, the authors assumed the model parameters in the fuzzy environment. However, in real-life situations, the probabilistic nature of parameters may be considered. Also, a more comprehensive model can be built by considering the neutrosophic sets to deal with the uncertainty in model parameters. Further research can build a more sophisticated model by appropriately considering the intuitionistic fuzzy sets.



---

*Source: 6247423-2020-11-17.xml*