Enhancing Possibilistic Fuzzy Goal Programming Approach for Solving Multi Objective Minimum Cost Flow Problems Coefficients

Fuzzy goal programming approach, α −possibly optimal solution, Goal programming, Decision maker, Compromise solution, Parametric analysis.

1. Introduction

The Minimum Cost Flow (MCF) problem is a general form of the network flow problem, which aims to determine the east coast of the shipment of a commodity during a capacitated network to achieve demands at certain nodes from supplies at other nodes. The study of MCF can be investigated to enormous other network problems, for example, maximum flow, assignment, shortest path, transportation, transshipment problems, multi-stage production inventory planning, nurse scheduling, project assignment, mold allocation, college course assignment, and automobile routing [1]-[4]. Hu et al. [5] proposed an algorithm that holds the complementarity slackness at each iteration with the help of a dual approach that is node by updating node potential iteratively; they found an augmenting path.

Multi-objective MCF problems have been studied in the literature [6], [7]. Bazaraa et al. [8] applied the parametric analysis in large-scale linear programming. Steuer [9] decomposed the parametric space of convex combination parametric programming using the parametric analysis. Luhandjula [10] studied the multi-objective linear problem having coefficients represented by possibilistic data. Lee and Moore [11] and Hemaida and Kwak [12] reviewed the Multi-Objective Transportation Problem (MOTP) and applied Goal Programming (GP) to obtain a satisfactory solution. Tamiz et al. [13] and Romero [14] discussed the shortcomings of GP. Many authors applied a fuzzy programming approach to solving MOTP [15]-[22]. Cui et al. [23] proposed a novel general MCF model for optimizing the distribution pattern of evacuation flow and rescue flow on the same network by introducing the conflict cost.

This paper introduces a multi-objective MCF problem with probabilistic variables. The parametric study corresponding to the α −possibly optimal solution is defined and determined without differentiability. The above literature analysis clearly shows that the proposed study is novel, more generalized, and flexible compared to existing relevant literature. It has the distinction due to the inclusion of the following features for the first time in literature:

I. Possibilistic multi-objective MCF.

II. Possibilistic in all of the coefficients of the objective functions.

III. α-pareto optimal solution-based scenario.

IV. The stability set of the first kind without differentiability.

The rest of the paper is outlined as follows.

2. Preliminaries

This section introduces some basic concepts and results related to possibilistic variables and its α −level set, possibilistic distribution, and support.

Definition 1 ([24], [25]). A possibilistic variable u on V is a variable characterized by a possibility distributionμu(v), which means that if u is a variable taking values in V, then μu corresponding to u may be viewed as a fuzzy constraint. Such a distribution is characterized by a possibility distribution function μu: V ⟶ [0, 1], which is associated with each v ∈ V, the degree of compatibility of u with the realization v ∈ V. If V is a Cartesian product of V1, V2, … , Vn, then μu(v1 , v2, … , vn) is an n −ary possibility distribution, i.e.,

μu(v) = (μu1(v1), μu2(v2), … , μun(vn)).

Definition 2. The α −level set of possibilistic variable u is

uα = {v ∈ V: μu(v) ≥ α}.

Definition 3 ([24]). A possibility distribution μu on V is said to be convex if

μu(γv1 + (1 − γ)v2) ≥ min(μu(v1), μu(v2)), for all v1, v2 ∈ V, γ ∈ [0, 1].

Definition 4 ([24]). The support of a possibilistic variable u is

Supp (u) = {v ∈ V: sup μu(v) > 0, for all δ > 0}, where Nδ(y) = {v ∈ V ∈: ‖v − y‖ <

v∈Nδ(y)

3. Problem Statement and Solution Concepts

Consider the following possibilistic multi-objective MCF problem.

(Poss MOMCF) min F ̃r(x, c ̃r) = ∑(i,j)∈M c ̃ij r xij , r = 1, 2, … , K,

∑ xij − ∑ xli = b(i), for all i ∈ V, x ∈ X = { j: (i,j)∈M k:(k,i)∈M } xij ∈ Uij, for all (i, j) ∈ M, xij ≥ 0, for all (i, j) ∈ M, where M: The set of arcs (i, j), V: The set of nodes, xij: The decision variable representing the flow through the arc (i, j), Uij = [lij, uij]: Capacity of arc (i, j), c ̃ij r : The possibilistic penalty per unit of flow through the arc (i, j) in the c ̃ij r objective function r = 1, 2, … , K, b(i): The net flow generated at node i, the values of b(i) being positive, zero, or negative classifies node i as a supply node, transshipment node, or demand node, respectively.

It is noted that the parameters c ̃ij K is vectors of possibilistic variables on ℝ, which is characterized by possibility distributions μc ̃ . It is assumed that all possibility distributions in the Poss MOMCF problem are convex cones having compact supports and u0 = supp(u).

Definition 5. x∗ ∈ is an α −possibly efficient solution for Poss MOMCF if there is no x ∈ G such that

F1(x, c ̃1) ≤ F1(x ̂, c ̃1), F2(x, c ̃2) ≤ F2(x ̂, c ̃2),

Poss ( … , Fr−1(x, c ̃r−1) ≤ Fr−1(x ̂, c ̃r−1), Fr(x, c ̃r) ≤ Fr(x ̂, c ̃r), ) ≥ α. (1)

Fr+1(x, c ̃r+1) ≤ Fr+1(x ̂, c ̃r+1), … , FK(x, c ̃K) ≤ FK(x ̂, c ̃K) Based on the extension principle, we have F1(x, c ̃1) ≤ F1(x ̂, c ̃1), F2(x, c ̃2) ≤ F2(x ̂, c ̃2), Poss ( … , Fr−1(x, c ̃r−1) ≤ Fr−1(x ̂, c ̃r−1), Fr(x, c ̃r) ≤ Fr(x ̂, c ̃r), ) Fr+1(x, c ̃r+1) ≤ Fr+1(x ̂, c ̃r+1), … , FK(x, c ̃K) ≤ FK(x ̂, c ̃K)

μc ̃1(c1), μc ̃2(c2), … , μc ̃r−1(cr−1), = Sup min ( r r+1 K ), (c1, c2,…, cK)∈E μc ̃r(c ), μc ̃r+1(c ), … , μc ̃K(c ) where

(c1, c2, … , cK): F1(x, c ̃1) ≤ F1(x ̂, c ̃1), F2(x, c ̃2) ≤ F2(x ̂, c ̃2),

E = { … , Fr−1(x, c ̃r−1) ≤ Fr−1(x ̂, c ̃r−1), Fr(x, c ̃r) ≤ Fr(x ̂, c ̃r), }. (3)

Fr+1(x, c ̃r+1) ≤ Fr+1(x ̂, c ̃r+1), … , FK(x, c ̃K) ≤ FK(x ̂, c ̃K) μc ̃r,r = 1, 2, … , K are arcs K(i, j) possibly distributions.

4. Characterization of −Possibly Efficient Solution for Poss MOMCF Problem

For investigating the α −possibly efficient solutions for the Poss MOMCF problem, let us consider the α −parametric multi-objective MCF problem (α −PMOMCF) min Fr(x, cr) = ∑(i,j)∈M cij r xij , r = 1, 2, … , K,

( ) (4)

∑ xij − ∑ xli = b i , for all i ∈ V, x ∈ X = { j: (i,j)∈M k:(k,i)∈M } xij ∈ Uij, for all (i, j) ∈ M, xij ≥ 0, for all (i, j) ∈ M, cij r ∈ (c ̃ij r ) ,

r r r

where, (c ̃ij)α is the α −cut of the possibilistic variable cij. Based on the convexity assumption μc ̃r ij(cij), (i, j) is arc, r = 1, K are real intervals denoted by [(cij r−)α, (cij r+)α ]. Let φr α be the set of arcs (i, j) with cij r ∈ [(cij r−)α, (cij r+)α ] , r = 1, K. The α −PMOMCF problem can be rewritten as min Fr(x, cr) = ∑(i,j)∈M cij r xij , r = 1, 2, … , K,

s. t. (5)

x ∈ X, and cr ∈ φr α, r = 1, K.

Problem (5) can be rewritten as min Fr(x, cr) = ∑(i,j)∈M(cij r−(τ) + τ cij r−(τ))xij , r = 1, 2, … , K, s. t. (6)

x ∈ X, and cr ∈ φr α, r = 1, K, τ ∈ [0,1].

Definition 6. x∗ ∈ G is an α −parametric efficient solution for α −PMOMCF problem if there is no x ∈ G and cr ∈ φr α such that Fr(x, cr) ≤ Fr(x∗, cr); ∀r = 1, K and Fr(x, cr) < Fr(x∗, cr) holds for at least one r. Definition 7 ([26]). A feasible vector Y° ∈ X is said to be α −parametric compromise solution of α −PMOMCF if and only if Y° ∈ H and F(Y) ≤ ⋀Y∈X F(Y), where ⋀ stands for the minimum, and H is the set of α −parametric efficient solutions.

Definition 8 ([15]). If the α −parametric compromise solution satisfies the decision makers' preference, the solution is called α −preferred parametric compromise solution.

Theorem 1. x∗ ∈ G is an α −possibly efficient solution for the Poss MOMCF problem if and only if α −parametric efficient solution for α −PMOMCF problem.

Proof: (see [24]).

5. Fuzzy Goal Programming Approach for Solving Problem (5)

Based on the three concepts of fuzzy goals (G), fuzzy constraints (C), and fuzzy decision (D) introduced by Bellman and Zadeh [27], the fuzzy decision is defined as

D = C ∩ G. (7)

Then

μD(x) = min(μC(x), μG(x)). (8)

With the membership Function (8), let us describe the fuzzy goals for the problem under study. The linear membership function (MP) [28] is given by 0, Fr(x, cr) ≤ Lr,

r Ur− Fr(x,cr) r

μr( Fr(x, c )) = { Ur−Lr , Lr < Fr(x, c ) < Ur, (9)

1, Fr(x, cr) ≥ Ur, where, Lr, and Ur are the lower and upper bounds of Fr(x, cr), Lr ≠ Ur, and can be calculated as

Lr = min x Fr(x, cr), and Ur = max x Fr(x, cr), r = 1, 2, … , K. (10)

By applying the fuzzy Decision (8) and membership Function (9), α −PMOMCF can be rewritten as

max min (μr( Fr(x, cr))),

r=1,K

s. t. (11)

x ∈ X, and cr ∈ φr α, r = 1, K.

Problem (11) can be converted into well-defined linear programming using the auxiliary variable as

max ϑ (12) ϑ ≤ μr( Fr(x, cr)), r = 1, K, x ∈ X, and cr ∈ φr α, r = 1, K.

In order to formulate Problem (12) as a GP [29], we introduce the negative and positive deviational variables.

Fr(x, cr) − vr + + vr − = Gr, r = 1, K, (13)

where, Gr is the aspiration level of the objective function r. Now, Problem (12) is reformulated as a mixed integer GP problem as max ϑ

ϑ ≤ μr( Fr(x, cr)), r = 1, K,

r r (14)

x ∈ X, and c ∈ φα, r = 1, K, Fr(x, cr) − vr + + vr − = Gr, vr −, vr + ≥ 0, r = 1, K , 0 ≤ ϑ ≤ 1.

6. Solution Procedure

In this section, a solution procedure for solving the Poss MOMCF problem can be summarized in the following steps:

Step 1. Consider the Poss MOMCF problem.

Step 2. Solve each one of the objective function and continue this process K times. If all the resulting solutions are equal, select one of them and go to Step 5.

Step 3. Define the membership function of every one of the objectives and also the aspiration level.

Step 4. Construct Problem (13), then solve it using any computer package (Say, GAMS).

Step 5. Stop and then determine the stability set of the first kind S(x°, c°) as

ωij (cij r − (cij r+) ) = 0, for all arc (i, j), r = 1, K, φij ((cij r−) − cij r ) = 0, for all arc (i, j), r = 1, K.

7. Numerical Example

Consider the following problem:

min F1(x, c1) = ∑(i,j)∈M c ̃ij 1 xij,

min F2(x, c2) = ∑ c ̃ij 2 xij,

(i,j)∈M

(15)

x12 + x13 = 10, x45 − x24 − x34 = −15, −x25 − x35 − x45 = −15, x12 ∈ [0, 20], x13 ∈ [0, 10], x24 ∈ [0, 20], x25 ∈ [0,10], x34 ∈ [0, 30], x35 ∈ [0,25], x45 ∈ [0, 50].

The possibilistic variables c ̃ij 1, and c ̃ij 2 are represented by a possibility distributions μc ̃1 ij(. ), and μc ̃2 ij(. ) In Fig. 1 and Fig. 2. The supports of the possibilistic variables c ̃ij 1, and c ̃ij 2 are[3,12], and [2, 10]. Hence, for the parametric functions0 ≤ τ ≤ 1, the supports are Supp (a ̃1) = 1 + 4ϑ, μa ̃1(1) = μa ̃1(5) = 0, Supp (a ̃2) = 10 − 4ϑ, μa ̃2(10) = μa ̃2(6) = 0.

Supp (c ̃12 1 ) = 3 + 4τ, μc ̃1 12(3) = μc ̃1 12(7) = 0, Supp (c ̃13 1 ) = 6 − 2τ, μc ̃1 13(4) = μc ̃1 13(6) = 0, Supp (c ̃24 1 ) = 5 + 4τ, μc ̃1 24(5) = μc ̃1 24(9) = 0, Supp (c ̃25 1 ) = 7 + τ, μc ̃1 13(7) = μc ̃1 13(8) = 0, Supp (c ̃34 1 ) = 9 + 2τ, μc ̃1 34(9) = μc ̃1 34(11) = 0, Supp (c ̃35 1 ) = 10 + 2τ, μc ̃1 35(10) = μc ̃1 35(12) = 0, Supp (c ̃45 1 ) = 1 + τ, μc ̃1 45(1) = μc ̃1 45(2) = 0, Supp (c ̃12 2 ) = 13 − 4τ, μc ̃2 12(13) = μc ̃2 12(9) = 0, Supp (c ̃13 2 ) = 4 + 4τ, μc ̃2 13(4) = μc ̃2 13(8) = 0, Supp (c ̃24 2 ) = 7 − 4τ, μc ̃2 24(7) = μc ̃2 24(3) = 0, Supp (c ̃25 2 ) = 4 + 4τ, μc ̃2 25(4) = μc ̃2 25(8) = 0, Supp (c ̃34 2 ) = 7 − 2τ, μc ̃2 34(5) = μc ̃2 34(7) = 0, Supp (c ̃35 2 ) = 4 + 2τ, μc ̃2 35(4) = μc ̃2 35(6) = 0, Supp (c ̃45 2 ) = 10 − 4τ, μc ̃2 45(6) = μc ̃2 45(10) = 0.

Min F1(τ) =(3 + 4τ)x12 + (6 − 2τ)x13 + (5 + 4τ)x24 + (7 + τ)x25 + (9 + 2τ)x34 +(10 + 2τ)x35 + (1 + τ)x45, Min F2(τ) =(13 − 4τ)x12 + (4 + 4τ)x13 + (7 − 4τ)x24 + (4 + 4τ)x25 + (7 − 2τ)x34 +(4 + 2τ)x35 + (10 − 4τ)x45,

x12 + x13 = 10,

(16)

x45 − x24 − x34 = −15, −x25 − x35 − x45 = −15, x12 ∈ [0, 20], x13 ∈ [0, 10], x24 ∈ [0, 20], x25 ∈ [0,10],

x34 ∈ [0, 30], x35 ∈ [0,25], x45 ∈ [0, 50], and ∈ [0,1].

L1 = 265, U1 = 375, L2 = 250, U1 = 425,

At τ =0, the GP for the problem becomes max ϑ

3x12 + 6x13 + 5x24 + 7x25 + 9x34 + 10x35 + x45 + ϑ110 ≤ 375,

(17)

13x12 + 4x13 + 7x24 + 4x25 + 7x34 + 4x35 + 10x45 + ϑ175 ≤ 425, x12 + x13 = 10, x45 − x24 − x34 = −15, −x25 − x35 − x45 = −15, x12 ∈ [0, 20], x13 ∈ [0, 10], x24 ∈ [0, 20], x25 ∈ [0,10],

x34 ∈ [0, 30], x35 ∈ [0,25], x45 ∈ [0, 50],

3x12 + 6x13 + 5x24 + 7x25 + 9x34 + 10x35 + x45 − v1 + + v1 − = 265, 13x12 + 4x13 + 7x24 + 4x25 + 7x34 + 4x35 + 10x45 − v2 + + v2 − = 250,

v1 +, v1 −, v2 +, v2 − = and ϑ ∈ [0,1].

Using the GINO software, the optimal compromise solution is

x12 ° = x24 ° = 8.56, x13 ° = 1.44, x25 ° = x45 ° = 0, x34 ° = 6.44, x35 ° = 15, v1 + = 20.11,

v1 − = v2 − = 0, v2 + = 32, ϑ° = 0.82.

° ° ° ° ° ° ° 1° 2°

To determine the stability set S (x12, x24, x13, x25, x45 , x34, x35, cij , cij ),

ω1 12(3 − (c12 1+)0) = 0, ω1 13(6 − (c13 1+)0) = 0, ω1 24(5 − (c24 1+)0) = 0, ω1 25 (7 − (c25 1+) ) = 0,

ω1 34(9 − (c34 1+)0) = 0, ω1 35 (10 − (c35 1+) ) = 0, ω1 45 (1 − (c45 1+) ) = 0, ω12 2 (13 − (c12 2+)0) = 0,

ω13 2 (4 − (c13 2+)0) = 0, ω2 24(7 − (c24 2+)0) = 0, ω2 25 (4 − (c25 2+) ) = 0, ω2 34(7 − (c34 2+)0) = 0, ω2 35 (4 − (c35 2+)0) = 0, ω2 45 (10 − (c45 2+)0) = 0,

ω1 12, ω1 13, ω1 24, ω1 25, ω1 34, ω1 35, ω1 45, ω12 2 , ω13 2 , ω2 24, ω2 25, ω2 34, ω2 35, ω2 45 ≥ 0.

We get I1 ⊆ {1, 2}.

For I1 = ∅, ω1 12, ω1 13, ω1 24, ω1 25, ω1 34, ω1 35, ω1 45, ω12 2 , ω13 2 , ω2 24, ω2 25, ω2 34, ω2 35, ω2 45 = 0. Then

° ° ° ° ° ° ° 1° 2°

SI1 (x12, x24, x13, x25, x45 , x34, x35, cij , cij ) cij r : (c12 1+)0 ≥ 3, (c13 1+)0 ≥ 6, (c24 1+)0 ≥ 5, (c25 1+) ≥ 7, (c34 1+)0 ≥ 9, (c35 1+) ≥ 10, (c45 1+) ≥ 1, (c12 2+)0 ≥ 13, = 0 0 0 .

(c13 2+)0 ≥ 4, (c24 2+)0 ≥ 7, (c25 2+) ≥ 4, (c34 2+)0 ≥ 7, (c35 2+) ≥ 4, (c45 2+) ≥ 10

0 0 0

For I2 = {1}, ω1 12, ω1 13, ω1 24, ω1 25, ω1 34, ω1 35, ω1 45 > 0; ω12 2 , ω13 2 , ω2 24, ω2 25, ω2 34, ω2 35, ω2 45 = 0. Then

° ° ° ° ° ° ° 1° 2°

SI2 (x12, x24, x13, x25, x45 , x34, x35, cij , cij ) cij r : (c12 1+)0 = 3, (c13 1+)0 = 6, (c24 1+)0 = 5, (c25 1+) = 7, (c34 1+)0 = 9, (c35 1+) = 10, (c45 1+) = 1, (c12 2+)0 ≥ 13, = 0 0 0 .

(c13 2+)0 ≥ 4, (c24 2+)0 ≥ 7, (c25 2+) ≥ 4, (c34 2+)0 ≥ 7, (c35 2+) ≥ 4, (c45 2+) ≥ 10

0 0 0

For I3 = {2}, ω1 12, ω1 13, ω1 24, ω1 25, ω1 34, ω1 35, ω1 45 = 0; ω12 2 , ω13 2 , ω2 24, ω2 25, ω2 34, ω2 35, ω2 45 > 0. Then ° ° ° ° ° ° ° 1° 2°

SI3 (x12, x24, x13, x25, x45 , x34, x35, cij , cij ) cij r : (c12 1+)0 ≥ 3, (c13 1+)0 ≥ 6, (c24 1+)0 ≥ 5, (c25 1+) ≥ 7, (c34 1+)0 ≥ 9, (c35 1+) ≥ 10, (c45 1+) ≥ 1, (c12 2+)0 = 13, = 0 0 0 .

(c13 2+)0 = 4, (c24 2+)0 = 7, (c25 2+) = 4, (c34 2+)0 = 7, (c35 2+) = 4, (c45 2+) = 10

0 0 0

For I4 = {1,2}, ω1 12, ω1 13, ω1 24, ω1 25, ω1 34, ω1 35, ω1 45 > 0; ω12 2 , ω13 2 , ω2 24, ω2 25, ω2 34, ω2 35, ω2 45 > 0. Then

° ° ° ° ° ° ° 1° 2°

SI4 (x12, x24, x13, x25, x45 , x34, x35, cij , cij ) = cij r : (c12 1+)0 = 3, (c13 1+)0 = 6, (c24 1+)0 = 5, (c25 1+) = 7, (c34 1+)0 = 9, (c35 1+) = 10, (c45 1+) = 1, (c12 2+)0 = 13, 0 0 0 .

(c13 2+)0 = 4, (c24 2+)0 = 7, (c25 2+) = 4, (c34 2+)0 = 7, (c35 2+) = 4, (c45 2+) = 10

0 0 0

Hence

° ° ° ° ° ° ° 1° 2°

S (x12, x24, x13, x25, x45 , x34, x35, cij , cij )

° ° ° ° ° ° ° 1° 2°

= ⋃ SIp (x12, x24, x13, x25, x45 , x34, x35, cij , cij ).

8. Discussion

In this section, the proposed study is compared with some existing relevant literature to carve out the advantageous aspect of the proposed research. Table 1 presents this comparison under specific parameters. It's evident that the result obtained by the proposed approach is less than that obtained by Alharbi et al. [30].

9. Conclusion

This paper introduces a multi-objective MCF problem with possibilistic variables. A fuzzy GP approach has been applied to the possibilistic MCF problem. The advantage of this approach is the utilization to allow conflicting goals and permit the consideration of the decision environment. The GAMS software has been applied to obtain the solution. The parametric study corresponding to the α −possibly optimal solution is defined and determined without differentiability. Future work may include extending this study to other fuzzy-like structures (i. e., interval-valued fuzzy set, Neutrosophic set, Pythagorean fuzzy set, Spherical fuzzy set, etc., with more discussion and suggestive comments.

Author Contribution

H.A. K. research design, conceptualization, and validation. S. A. E. data gathering, computing, and editing. The authors have read and agreed to the published version of the manuscript.

Funding

The authors declare thatno external funding or support was received for the research.

Data Availability

All data supporting the reported findings in this research paper are provided within the manuscript.

Conflicts of Interest

The authors declare no conflicts of interest.