Article Versions
Export Article
Cite this article
  • Normal Style
  • MLA Style
  • APA Style
  • Chicago Style
Research Article
Open Access Peer-reviewed

The Fuzzy Minimum Cost Flow Problem with the Fuzzy Time-Windows

Nasser A. El-Sherbeny
American Journal of Applied Mathematics and Statistics. 2019, 7(6), 191-195. DOI: 10.12691/ajams-7-6-1
Received October 10, 2019; Revised November 15, 2019; Accepted November 25, 2019

Abstract

The Minimum Cost Flow Problem (MCFP) is a well-known combinatorial optimization and a logical distribution problem. The MCFP is an NP-hard problem with many applications in logistic networks and computer networks. The Fuzzy Minimum Cost Flow Problem with Fuzzy Time-Windows (FMCFPFTW) is an extension of the MCFP. The goal of the problem is to find the minimum amount of the fuzzy flow from the source to the sink that satisfies all constraints of the fuzzy shortest dynamic f-augmenting path with the fuzzy dynamic residual network. We consider a generalized fuzzy version of the MCFP of the fuzzy network. We propose the mathematical model of the FMCFPFTW. Finally, a new algorithm of the FMCFPFTW is presented.

Mathematics Subject Classification: 05C35, 90C27, 65G30, 68R10

1. Introduction

The Minimum Cost Flow Problem (MCFP) is a basic problem in the network flow theory, which is one of the classical combinatorial optimizations and an NP-hard problem with several applications. Over the past 40 years, the MCFP has been an area of research that has attracted many researchers. The MCFP has been studied extensively, see, 1, 2, 8, 9, 18, 23, 24. We consider be a fuzzy network without parallel arcs and loops, where N is a set of nodes and A is a set of arcs. For each node there is an associated of a three integer parameters, a waiting fuzzy cost a node fuzzy capacity and a fuzzy time-windows where, is a non-negative fuzzy time service, see, 3, 16, 19, 20, 24.

For each arc there is an associated of a three integer parameters, a positive fuzzy transit time a fuzzy transit cost and a positive fuzzy capacity limit All these parameters are functions of the fuzzy time service The source node s and a sink node has a fuzzy time-windows respectively, see 13, 14, 21, 22. The fuzzy flow must arrive at node before a fuzzy time if it arrives before it just a fuzzy waiting time before treating the fuzzy flow at the node (a fuzzy waiting time see 4, 5, 6, 7, 18.

The problem is to determine how given the amount of the fuzzy flow can be sent from one node s to another node The fuzzy minimum cost on a fuzzy shortest dynamic f-augmenting path of the fuzzy dynamic residual network, subject to the fuzzy capacity limits on the arcs, see 10, 11, 15, 17.

Traditionally, this problem is considered as a static one, where it is assumed that it takes a zero time to traverse the arc. All attributes of the fuzzy network, including a fuzzy cost to send a fuzzy flow on the arc, the fuzzy capacity of the arc, are a fuzzy time-invariant. A more realistic model is to consider the fuzzy time needed to traverse an arc. For each arc there is a fuzzy transit time For each node there is a fuzzy time-windows subject to the condition that the schedule remains optimal for any fuzzy service time By the shortest dynamic f-augmenting path with a fuzzy dynamic residual network. The new version of the problem becomes so-called the Fuzzy Minimum Cost Flow Problem with Fuzzy Time-Windows (FMCFPFTW).

The reminder of this paper consists of six sections including organized Introduction. Section 2 presents some basic concepts, definitions, a fuzzy time-varying, a fuzzy time-windows and the fuzzy shortest dynamic f-augmenting path with a fuzzy dynamic residual network. In Section 3, we presented the fuzzy dynamic residual network with the fuzzy time-varying and fuzzy time-windows. In Section 4, we propose, the mathematical formulation model of the FMCFPFTW. In Section 5, we presented an algorithm of the FMCFPFTW of the fuzzy network. Finally, the conclusion is given in Section 6.

2. Some Basic Concepts and Definitions

Let be a fuzzy network without parallel arcs and loops, where N is a set of nodes and A is a set of arcs. All parameters of the fuzzy network are functions of a fuzzy service time where Each node has a fuzzy time-windows More specifically, is a fuzzy capacity of the arc is a fuzzy capacity of each node during the period from to A fuzzy transit time is needed to send a fuzzy flow through the arc at a fuzzy time

The fuzzy cost of a transmitting one unit of a fuzzy flow through the arc at a fuzzy time is keeping one unit of the fuzzy flow that a waiting at the node for the closed interval duration We assume that and are the fuzzy integers and two particular nodes s and are the source and the sink nodes of the fuzzy network with a fuzzy time-windows respectively.

We consider and be a fuzzy flow value of the arc during the period The fuzzy flow value is a fuzzy waiting at the node during the closed period The total fuzzy flow value under a schedule which specifies, how to send a fuzzy flow from the source node s to the sink node within the fuzzy time-windows and a fuzzy time limit then,

(1)

The FMCFPFTW is to find a feasible schedule send to a given fuzzy flow from s to within the fuzzy time limit and minimize the total fuzzy cost satisfy all constraints.

A fuzzy time-varying and a fuzzy time-windows are an essential ingredient which we must consider in our model. Consequently, some important concepts and procedures will have to be re-defined and re-constructed, to consider the existence of the dynamic fuzzy time. Without ambiguity, in the following, we will assume that the length of the arc is equal to the fuzzy cost use the interchangeably of terminologies a fuzzy cost and a fuzzy length by the fuzzy shortest path, the fuzzy cheapest path. Further, we denote be a directed fuzzy path from s to connecting to the nodes where and are a fuzzy arrival time, a fuzzy waiting time, and a fuzzy departure time respectively at the node with a fuzzy time The fuzzy path has a fuzzy service time if the total fuzzy time required to traverse this path where,

Definition 2.1 Let be a classic network where N is a limited set of nodes and A is a set of arcs. Each arc has an integral number and where l is a capacity of each node, b is a transit time of each arc, is a cost of the transmitting one unit of the flow and is a cost of each node. A time-window is defined by, for each node has time-windows and respectively, see, Figure 1.

Definition 2.2 13 Let be a non-empty set, The fuzzy set is the set of ordered pairs where is the membership function of the fuzzy set The fuzzy travel time between two places along with the most likely fuzzy time; For example, the fuzzy time to travel from node to node is between and but must possibly it is This sort of knowledge lets us construct 3-point fuzzy travel times.

Definition 2.3 12 Every node is assigned by the expert to one of two predetermined groups; a classical fuzzy time-windows and a fuzzy time-windows of a normal node. In an extreme case, a fuzzy time-window is tighter than the classical counterpart. The shown characteristics of the fuzzy time-windows are suggested to the shipper who can modify them. We consider the FMCFPFTW; the new optimization fuzzy model is presented by the fuzzy capacities calculating and the crisp equivalents of the fuzzy chance constraints.

Definition 2.4 The fuzzy path is said to be a fuzzy dynamic f-augmenting path from s to with a fuzzy time-varying and a fuzz time-windows with, if it satisfies:

(2)
(3)
(4)
(5)

for and then there is no fuzzy waiting time

Definition 2.5 Let be a fuzzy dynamic f-augmenting path from s to of the fuzzy time-varying and the fuzzy time-windows, with then the fuzzy capacity of the path is defined as where;

(6)

In this work, the algorithm to be developed will search, successively, the fuzzy shortest paths from the source node s to the sink node of the fuzzy dynamic residual network. The fuzzy transmit as much as possible of the fuzzy flow along the fuzzy paths, satisfy all constraints. In 20, we will need to the fuzzy network updating of the procedure to keep the needed information on the current fuzzy dynamic flow, which is to be introduced below. In our fuzzy network to updating of the procedure, we create, initially, a new fuzzy network to replace the original one.

Definition 2.6 For every arc we create an artificial arc, denoted by It's a fuzzy transit time a fuzzy transit cost and the fuzzy capacity where, then;

For

(7)
(8)
(9)

For every node we define as the fuzzy capacity within which a fuzzy flow can be waiting at from a fuzzy time to and as the fuzzy cost from a fuzzy flow to stay at from a fuzzy time to Initially, let and,

(10)

No fuzzy flow can be sent along any artificial arcs in the fuzzy network as defined above since the fuzzy capacities of these arcs are a set to zero. Hence, this new fuzzy network is equivalence to the original one, and so we will still denote it by

3. The Fuzzy Dynamic Residual Network with Fuzzy Time-Varying and Fuzzy Time-Windows

Let be a fuzzy dynamic f-augmenting path from s to and be a fuzzy flow value send along which satisfies For and for each node then the update of the fuzzy capacity of the arc is given by:

Ÿ If is not an artificial arc. Let,

(11)
(12)

Ÿ If is an artificial arc. Let

(13)
(14)

For the update of the fuzzy capacity node is given by:

Ÿ If the fuzzy waiting time at node is positive ( Let

(15)
(16)

The fuzzy network generated by the fuzzy network updating the procedure above is said to be a fuzzy dynamic residual network of the fuzzy time-varying and the fuzzy time-windows. The optimization problem in the original fuzzy network of the fuzzy dynamic residual network with a fuzzy time-varying and a fuzzy time-windows is equivalent to the sense that there is a one-to-one correspondence between their feasible solutions.

In the original fuzzy network, we assume that all fuzzy transit times Thus, the first fuzzy dynamic f-augmenting path will only contain the arcs with positive fuzzy transit times and a positive fuzzy waiting time But in a fuzzy dynamic residual network of the fuzzy time-varying and fuzzy time-windows, a fuzzy transit time associated with an artificial arc is negative number, and a fuzzy flow can be stored at the node for a negative waiting time. Therefore, a fuzzy dynamic f-augmenting path can be found in the fuzzy dynamic residual network with a fuzzy time-varying and a fuzzy time-window may contain some arcs of the negative transit times and negative waiting time (

Definition 3.1 Let and where a negative waiting time ( the fuzzy path is said to be a fuzzy f-augmenting path from s to If for then, for each node it satisfies:

(17)
(18)
(19)

if is an artificial arc

(20)

if where for

For a node with a fuzzy time-varying and a fuzzy time-windows, the fuzzy cost of the fuzzy shortest dynamic f-incrementing path from s to with the fuzzy time is said to be infinity if;

Ÿ there is no a fuzzy path from s to or

Ÿ all the fuzzy paths from s to either have a fuzzy time greater than or a violate some other constraints and thus infeasible.

4. A Mathematical Model of the FMCFPFTW

Ÿ A mathematical model of the FMCFPFTW is given by the following:

(21)

Subject to:

(22)
(23)
(24)
(25)

Equation (21) is the objective function that minimizes the total fuzzy cost. Equation (22) is a fuzzy flow value departure from the source node s and arrival to the sink node with the traveling fuzzy time Equation (23) is fuzzy flow conservation. Equations (24) and (25) are the fuzzy capacity constraints on the arcs and nodes respectively. All constraints are satisfying a fuzzy time-varying and a fuzzy time-windows constraint.

5. An Algorithm of the FMCFPFTW

Let be a fuzzy network of the fuzzy time-varying and a fuzzy time-windows with nonzero fuzzy transit times, an arbitrary fuzzy costs and no negative cycles. We will develop an algorithm to find the fuzzy shortest dynamic f-augmenting path from s to with the fuzzy time at most where no fuzzy waiting time is permitted at any node. We will develop a procedure, called a fuzzy shortest dynamic f-augmenting path of the fuzzy time-varying and a fuzz time-window searching the process for the zero-fuzzy waiting time, which contains a two different searching operation:

Ÿ the first is a forward-searching,

Ÿ the second is a backward-searching.

Both operations are designed by using a fuzzy dynamic programming method, and the forward-searching is to deal with positive fuzzy transit times while the backward searching will deal a negative transit time.

Definition 5.1 Let be a fuzzy dynamic f-augmenting path with the fuzzy time-varying and a fuzzy time-windows from s to a fuzzy service time A section is defined as a sub-path of where all the fuzzy transit times have the same sign. A section of is said to be positive if it's a fuzzy transit times are all positive.

A fuzzy dynamic f-augmenting path with a fuzzy time-varying and a fuzzy time-window consists of a several positive and a negative section alternatively. The number of these sections is said to be the alternating number of

Definition 5.2 Let is the fuzzy length of the fuzzy shortest dynamic f-augmenting path with the fuzzy time-varying and a fuzzy time-windows from the source node s to the node of a fuzzy time exactly with the alternating number at most k.

Since there are no negative cycles in the fuzzy network a fuzzy shortest dynamic f-augmenting path cannot contain more than n nodes and each node cannot be visited more than once at any fuzzy time Therefore, cannot contain more than sections. In other words, is the fuzzy length of the fuzzy shortest dynamic f-augmenting path with the fuzzy time-varying and fuzzy time-windows from s to of the fuzzy time exactly when

We now describe the procedure to solve the sub-problem, in which and denote the set of all positive and negative arcs, respectively.

We will present an algorithm of the FMCFPFTW, our algorithm satisfies a fuzzy time-varying and a fuzzy time-windows constraint without a fuzzy waiting time of the fuzzy shortest dynamic f-augmenting path.

i) The first: An algorithm of the fuzzy shortest dynamic f-augmenting path of a fuzzy dynamic residual network:

Begin

Initialize:

Sort all values for and for all arcs

Sort all values for and for all arcs

Do

For all do

Case 1: i is an odd number:

For do

For every do the forward-searching operation:

Case 2: i is an even number:

For do

For every do the backward-searching operation:

While there exists at least one

Let

End

ii) The second: An algorithm of the FMCFPFTW:

Begin

For do

Call the first algorithm;

If then call the algorithm UP-NET; (there is an f-augmenting path with the fuzzy time-varying and the fuzzy time-windows of the fuzzy flow value so update a fuzzy network)

Else stop; (no feasible solution to send all v units of the fuzzy flow from s to within the fuzzy time

If then stop;

End

6. Conclusion

This paper presents a new version of the Minimum Cost Flow Problem (MCFP), a new version is the Fuzzy Minimum Cost Flow Problem with the Fuzzy Time-Windows (FMCFPFTW). We consider a generalized fuzzy version of the MCFP. The objective is to find an optimal schedule to send a fuzzy flow from the source to the sink satisfies all constraints of the fuzzy shortest dynamic f-augmenting path of the fuzzy dynamic residual network The fuzzy flow must arrive at the sink before a fuzzy nonnegative deadline Also, we propose a mathematical formulation model of the MFCFFPFTW. Finally, an algorithm of the FMCFPFTW is presented.

Acknowledgements

The author would like to thank an anonymous referee for some useful comments.

References

[1]  R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.
In article      
 
[2]  R. Ahuja, V. Goldberg, B. Orlin and E. Tarjan (1992). Finding minimum cost flows by double scaling, Mathematical Programming, 53, 243-266.
In article      View Article
 
[3]  Y. Agarwal, K. Mathur, and H. Salki (1989). A set-partitioning-based exact algorithm for the vehicle routing problem. Networks, (19), 731-749.
In article      View Article
 
[4]  G. Busacker and J. Gowen, A procedure for determining a family of minimum cost network flow patterns, Technical Report 15, Operation Research, Johns Hopkins University, 1961.
In article      View Article
 
[5]  X. Cai, T. Kloks (1997). Time-varying shortest path problem with constraints, Networks, 29 (3), 141-149.
In article      View Article
 
[6]  N. Christofides, and N. Beasley, (1984). The period routing problem, Networks, (14), 237-241.
In article      View Article
 
[7]  W. Chiang, and R. Russell, (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, (63), 3-27.
In article      View Article
 
[8]  G. Clarke, and W. Wright, (1964). Scheduling of vehicles from a central depot to the number of delivery points, Operations Research, (12), 568-581.
In article      View Article
 
[9]  G. Crainic, and G. Laporte, Fleet management and logistics. Kluwer Academic Publishers, 2000.
In article      
 
[10]  Y. Dumes, J. Desrosiers, and F. Soumis (1991). The pickup and delivery problem with time windows, European Journal of Operation Research, (54), 7-21.
In article      View Article
 
[11]  J. Edmonds and R. Karp, (1972). Theoretical improvements in algorithmic efficiency for network flow problems, Journal of ACM, 248-264.
In article      View Article
 
[12]  N. El-Sherbeny (2002), Resolution of a vehicle routing problem with a multi-objective simulated annealing method, Ph.D. dissertation, Faculty of Science, Mons University, Mons, Belgium.
In article      
 
[13]  N. El-Sherbeny, (2017). Algorithm of fuzzy maximum flow problem with fuzzy time-windows in the hyper network, International Journal of Pure and Applied Mathematics, 116, No. 4, 863-874.
In article      
 
[14]  N. El-Sherbeny, (2011). Imprecision and flexible constraints in fuzzy vehicle routing problem, American Journal of Mathematical and Management Sciences, 31, 55-71.
In article      View Article
 
[15]  L. Ford and D. Fulkerson, (1956). Maximal flow through a network, Canadian Journal of Mathematics, 8, 399-404.
In article      View Article
 
[16]  V. Goldberg and E. Tarjan, (1990). Solving minimum cost flow problem by successive approximation, Mathematics of Operation Research, 15, 430-466.
In article      View Article
 
[17]  T. Havens, J. Bezdek, and C. Leckie, A soft modularity function for detecting fuzzy communities in social networks, IEEE Transactions on Fuzzy Systems, 21, No. 16, 1170-1175, (2013).
In article      View Article
 
[18]  L. Ford, D. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, 1962.
In article      
 
[19]  Y. Koskosidis, W. Powell, and M. Solomon, (1992). An optimization-based heuristic for vehicle routing and scheduling with soft time windows constraints. Transportation, Science, (26), 57-69.
In article      View Article
 
[20]  A. Landeghem, (1988). A bi-criteria heuristic for the vehicle routing problem with time windows. European Journal of Operational Research, (36), 217-226.
In article      View Article
 
[21]  D. Lozovanu, S. Pickl, (2004). A special dynamic programming technique for multiobjective discrete control and for dynamic games on graph-based methods, CTWO4 Workshop on Graphs and Combinatorial Optimization, Milano, 184-188.
In article      
 
[22]  K. Sullivan, and J. Smith, (2014). Exact algorithms for solving a Euclidean maximum flow network interdiction problem, Networks, 64, No. 2, 109-124.
In article      View Article
 
[23]  C. Reeves. Modern heuristic techniques for combinatorial problems. Mc-Greenhill. 1995.
In article      
 
[24]  D. Tuyttens, J. Teghem, N. El-Sherbeny, (2004). A multiobjective vehicle routing problem solved by simulated annealing, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, Germany, 535, 133-152.
In article      View Article
 

Published with license by Science and Education Publishing, Copyright © 2019 Nasser A. El-Sherbeny

Creative CommonsThis work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Cite this article:

Normal Style
Nasser A. El-Sherbeny. The Fuzzy Minimum Cost Flow Problem with the Fuzzy Time-Windows. American Journal of Applied Mathematics and Statistics. Vol. 7, No. 6, 2019, pp 191-195. http://pubs.sciepub.com/ajams/7/6/1
MLA Style
El-Sherbeny, Nasser A.. "The Fuzzy Minimum Cost Flow Problem with the Fuzzy Time-Windows." American Journal of Applied Mathematics and Statistics 7.6 (2019): 191-195.
APA Style
El-Sherbeny, N. A. (2019). The Fuzzy Minimum Cost Flow Problem with the Fuzzy Time-Windows. American Journal of Applied Mathematics and Statistics, 7(6), 191-195.
Chicago Style
El-Sherbeny, Nasser A.. "The Fuzzy Minimum Cost Flow Problem with the Fuzzy Time-Windows." American Journal of Applied Mathematics and Statistics 7, no. 6 (2019): 191-195.
Share
[1]  R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice Hall, Englewood Cliffs, NJ, 1993.
In article      
 
[2]  R. Ahuja, V. Goldberg, B. Orlin and E. Tarjan (1992). Finding minimum cost flows by double scaling, Mathematical Programming, 53, 243-266.
In article      View Article
 
[3]  Y. Agarwal, K. Mathur, and H. Salki (1989). A set-partitioning-based exact algorithm for the vehicle routing problem. Networks, (19), 731-749.
In article      View Article
 
[4]  G. Busacker and J. Gowen, A procedure for determining a family of minimum cost network flow patterns, Technical Report 15, Operation Research, Johns Hopkins University, 1961.
In article      View Article
 
[5]  X. Cai, T. Kloks (1997). Time-varying shortest path problem with constraints, Networks, 29 (3), 141-149.
In article      View Article
 
[6]  N. Christofides, and N. Beasley, (1984). The period routing problem, Networks, (14), 237-241.
In article      View Article
 
[7]  W. Chiang, and R. Russell, (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of Operations Research, (63), 3-27.
In article      View Article
 
[8]  G. Clarke, and W. Wright, (1964). Scheduling of vehicles from a central depot to the number of delivery points, Operations Research, (12), 568-581.
In article      View Article
 
[9]  G. Crainic, and G. Laporte, Fleet management and logistics. Kluwer Academic Publishers, 2000.
In article      
 
[10]  Y. Dumes, J. Desrosiers, and F. Soumis (1991). The pickup and delivery problem with time windows, European Journal of Operation Research, (54), 7-21.
In article      View Article
 
[11]  J. Edmonds and R. Karp, (1972). Theoretical improvements in algorithmic efficiency for network flow problems, Journal of ACM, 248-264.
In article      View Article
 
[12]  N. El-Sherbeny (2002), Resolution of a vehicle routing problem with a multi-objective simulated annealing method, Ph.D. dissertation, Faculty of Science, Mons University, Mons, Belgium.
In article      
 
[13]  N. El-Sherbeny, (2017). Algorithm of fuzzy maximum flow problem with fuzzy time-windows in the hyper network, International Journal of Pure and Applied Mathematics, 116, No. 4, 863-874.
In article      
 
[14]  N. El-Sherbeny, (2011). Imprecision and flexible constraints in fuzzy vehicle routing problem, American Journal of Mathematical and Management Sciences, 31, 55-71.
In article      View Article
 
[15]  L. Ford and D. Fulkerson, (1956). Maximal flow through a network, Canadian Journal of Mathematics, 8, 399-404.
In article      View Article
 
[16]  V. Goldberg and E. Tarjan, (1990). Solving minimum cost flow problem by successive approximation, Mathematics of Operation Research, 15, 430-466.
In article      View Article
 
[17]  T. Havens, J. Bezdek, and C. Leckie, A soft modularity function for detecting fuzzy communities in social networks, IEEE Transactions on Fuzzy Systems, 21, No. 16, 1170-1175, (2013).
In article      View Article
 
[18]  L. Ford, D. Fulkerson, Flows in Networks, Princeton University Press, Princeton, NJ, 1962.
In article      
 
[19]  Y. Koskosidis, W. Powell, and M. Solomon, (1992). An optimization-based heuristic for vehicle routing and scheduling with soft time windows constraints. Transportation, Science, (26), 57-69.
In article      View Article
 
[20]  A. Landeghem, (1988). A bi-criteria heuristic for the vehicle routing problem with time windows. European Journal of Operational Research, (36), 217-226.
In article      View Article
 
[21]  D. Lozovanu, S. Pickl, (2004). A special dynamic programming technique for multiobjective discrete control and for dynamic games on graph-based methods, CTWO4 Workshop on Graphs and Combinatorial Optimization, Milano, 184-188.
In article      
 
[22]  K. Sullivan, and J. Smith, (2014). Exact algorithms for solving a Euclidean maximum flow network interdiction problem, Networks, 64, No. 2, 109-124.
In article      View Article
 
[23]  C. Reeves. Modern heuristic techniques for combinatorial problems. Mc-Greenhill. 1995.
In article      
 
[24]  D. Tuyttens, J. Teghem, N. El-Sherbeny, (2004). A multiobjective vehicle routing problem solved by simulated annealing, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, Germany, 535, 133-152.
In article      View Article