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
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 capaci
ty 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.
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 
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.
Ÿ 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.
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
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.
The author would like to thank an anonymous referee for some useful comments.
| [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
This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit
https://creativecommons.org/licenses/by/4.0/
| [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 | ||
