On solving maximum and quickest interval-valued flows over time

Abstract

Network flows over time (also called Dynamic Network Flows) are considered as generalized form of standard (static) networks by adding an element of time. The factor of transit time on the arcs which specify the amount of time it takes for one unit of the flows to pass through a particular arc, make these networks different to traditional form of networks. While in most of network flow problems, transit times and capacities are given constant, stochastic or Fuzzy numbers, in this paper we suppose that transit times, capacities and consequently flows on arcs fall within specific ranges expressed as compact intervals. This vagueness in transit times, capacities and flows could arise in a number of ways: 1) when determining the exact capacity or transit time quantities is hard and there may happen errors in determining them which intervals reflect the measurement errors; 2) when it is impossible or even it is not needed to produce neither a distribution nor fuzzy functions but transit times, capacities and flows lie within specific ranges, or vary in time within these ranges. While determining the exact time for traveling in specific path in network transportation system is extremely difficult or almost impossible, determination of interval which can describe the range of required time for travelling in the network would be easy and fully operational. Our contribution in this paper is producing maximum flow and quickest s - t flow algorithms, first to network flows over time with interval-valued capacities and then to T-length bounded network flows over time with interval-valued transit times and capacities.

Keywords

Maximum flows over time interval-valued transit times interval-valued capacities temporally repeated flows

1 Introduction

Ford and Fulkerson [14, 15] for the first time in the 1960’s introduced flows over time (also called dynamic flows) by including transit time of an arc in the network model. They considered the problem of sending maximum flow from the source node s to the sink node t and showed that this problem can be solved efficiently by one minimum cost flow computation on the given network, where transit times of arcs are interpreted as arc costs. Since then a fair amount of study has been devoted to this topic, for example see the survey of Aronson [3] and Powell et al. [27]. Anderson et al. [2] studied the maximum flow over time problem in a network with zero transit times and time-varying transit times and storage capacities for the case where time is modeled as a continuum. They generalized the Max Flow-Min Cut theorem to the continuous-time model. This result was later extended by Philpott [26] to arbitrary transit times on the arcs. Fonoberova and Lozovanu [13] on the other hand, proposed an algorithm to solve the dynamic maximum flow problem in which capacities are depended on time.

Alonso and Fall [1] using a linear programming formulation of flows over time with piecewise constant capacity and transit times, presented an algorithm to solve a deterministic form of a routing problem in delay tolerant networking. Hashemi et al. [19] introduced two algorithms for dynamic network flow problems in the continuous model, based on a discretization approach. Their algorithms lead to approximate interior solutions and converge to optimum solutions.

Koch et al. [21] deployed measure theory in order to introduce a general model of network flows over time combining both discrete and continuous aspects in only one model. They also generalized the concept of cuts to their case and extend the famous Max Flow-Min Cut theorem to the setting.

Fleischer and Tardos [12] proved a close correspondence between discrete and continuous flows over time when cost, capacities, supplies and demands are independent of time and transit times on arcs are integral. A problem closely related to one considered by Ford and Fulkerson is the quickest s - t flow problem which can be solved in polynomial time by incorporating the algorithm of Ford and Fulkerson into binary search frame work. Burkard et al. [4] using Megiddo’s method of parametric search presented a faster algorithm for the quickest s - t flow problem.

But in most real-world situations, the model’s coefficients like transits times or capacities are not exactly known because relevant data is inexistent or scarce, difficult to obtain or estimate, the system is subject to changes, etc. Therefore, appropriate mathematical programming models for decision support must take explicitly into account. Moreover, fuzzy and stochastic approaches are frequently used to describe and treat imprecise and uncertain elements present in a real decision problem. In fuzzy programming problems, it is assumed that the membership functions of fuzzy sets are known. Also, in stochastic programming problems, it is assumed that the probability distributions of coefficients (viewed as random variables) are known. Ebrahimnejad et al. [6] used the bounded primal simplex algorithm for solving minimum cost flow problem (MCFP) with fuzzy costs which is a fundamental problem in networks and is widely applied in transportation, communication and computer network. After that Ebrahimnejad and Nasseri [7] generalized the network simplex algorithm for solving the same problem. Ghatee et al. [16] transformed the MCFP with fuzzy link costs into multi-objective MCFP. Also, Ghatee and Hashemi [17] deal with fuzzy quantities and relations in multi-objective minimum cost flow problem. In addition, Nasseri and Ebrahimnejad [25] used the fuzzy variable linear programming problems (FVLPs) for solving the flexible minimum cost flow problem. Moreover, Ebrahimnejad and Verdegay [8] and Ebrahimnejad [9], respectively applied the fuzzy bounded primal and dual simplex algorithms for solving maximum flow problem with fuzzy arc capacities and bounded transportation problem with fuzzy demands and supplies as two applications of bounded FVLPs. Ebrahimnejad [10] proposed a simplified method for solving transportation problem with generalized fuzzy numbers as an important network structured linear programming problem. Also, a two-step method has proposed for solving fuzzy transportation problem where all of the parameters are represented by non-negative triangular fuzzy numbers in [11].

In real world applications, however, it is not always easy to specify the membership function or the probability distribution in an inexact environment. Thus, in some of the cases, the use of an interval coefficient may serve the purpose better [20 , 29–32]. Interval programming just assumes that information about the range of variation of some (or all) of the parameters is available, which allows to specify a model with interval coefficients. Sengupta and pal [29] presented an algorithm for the shortest path problem when the connected arcs in a transportation network were represented as interval numbers. Using Hukuhara difference, Diamond [5] developed interval-valued version of the Max Flow-Min Cut theorem and Karp-Edmonds algorithm for networks with fuzzy capacities and flows. Although the Hukuhara difference is unique, but it doesn’t always exist, so aim to overcome this situation, Stefanini [30] produced a generalization of Hukuhara difference for interval and fuzzy arithmetic. Moreover Stefanini and Bede [31] introduced generalizations of the Hukuhara differentiability to the case of interval valued functions. They also studied interval differential equations and produced a practical algorithm to solve interval differential equations. Our main approach in this paper is generalizing Ford and Fulkerson’s maximum flow algorithm, first to network flows over time with interval-valued capacities and then to network flows over time with interval-valued transit times andcapacities.

The rest of the paper is organized as fallows. Section 2 gives the necessary definitions and symbolic representations for interval arithmetic. In Section 3, starting with static interval-valued flows, we generalize the concept of flows over time to interval-valued one and then produce an algorithm for the maximum flows over time with interval-valued capacities. Section 4, extends the maximum interval-valued flows over time to the case in which the capacities and transit times are interval-valued, and then gives two algorithms to obtain the quickest and maximum interval-valued flow in T-length bounded networks. Finally, Section 5 concludes the paper.

2 Interval arithmetic and order operations

As a coefficient, an interval signifies the extent of tolerance or a region that the parameter can possibly take. In reality, inexactness of this kind can be cited in countless situations. Here, all lower case letters denote real numbers and the upper case letters denote the interval numbers or the closed intervals on the real line R. An interval number A = [l_A, r_A] is the set of real numbers x such that l_A ≤ x ≤ r_A.

Let I denote the class of nonempty compact intervals on [0, ∞] and A, B ∈ I such that A = [l_A, r_A] and B = [l_B, r_B] then we have:

[l_A, r_A] is nonnegative if l_A ≥ 0, r_A ≥ 0 and it is positive if l_A ≥ 0 , r_A > 0 . $\begin{matrix} 1) A + B = [l_{A} + l_{B}, r_{A} + r_{B}] \end{matrix}$ $\begin{matrix} 2) A * B = [min (l_{A} l_{B}, l_{A} r_{B}, r_{A} l_{B}, r_{A} r_{B}), \\ max (l_{A} l_{B}, l_{A} r_{B}, r_{A} l_{B}, r_{A} r_{B})] \end{matrix}$ which can be simplified to A * B = [l_Al_B, r_Ar_B] because in this paper all intervals are defined on [0, ∞].

3) A ≤ B if l_A ≤ l_B and r_A ≤ r_B.

4) The generalized Hukuhara difference of two sets A, B ∈ I (gH-difference for short) is defined as follows ([26]): $A \underset{g}{⊖} B = C \Leftrightarrow {\begin{matrix} (a) A = B + C \\ or \\ (b) B = A + (- 1) C \end{matrix}$ (1)Take note that - C = (-1) C ={ - c : c ∈ C } but in general C+ (-1) C ≠ { 0 }, i.e. the opposite of C is not the inverse of Cin Minkowski addition (unless C ={ c } is a singleton).

Proposition 1. ([30]): The gH-difference $C = A \underset{g}{⊖} B$ of two intervals A = [l_A, r_A] and B = [l_B, r_B] always exists and we have: $[l_{A}, r_{A}] \underset{g}{⊖} [l_{B}, r_{B}] = [l_{C}, r_{C}]$ (2)in which $\begin{matrix} l_{C} = min {l_{A} - l_{B}, r_{A} - r_{B}} \\ r_{C} = max {l_{A} - l_{B}, r_{A} - r_{B}} \end{matrix}$

Conditions (a) and (b) in (1) are satisfied simultaneously if and only if the two intervals have the same length and l_c = r_c.

Note: All differences used in this paper aregH-difference.

Definition 1. In this paper the integral of interval-valued function f : [a, b] → I with f (x) = [f^- (x) , f⁺ (x)] is defined: $\int_{a}^{b} f (x) dx = [\int_{a}^{b} f^{-} (x) dx, \int_{a}^{b} f^{+} (x) dx]$ (3)

3 Maximum interval-valued flows over time with integral transit times

In this section we first give several basic definitions from graph theory and present some basic notations and then work on the main subject of the section.

A directed graph N = (V, A) consists of a finite nonempty set V of nodes and a set A of arcs whose elements are ordered pairs of distinct nodes. A directed network is a directed graph whose nodes and/or arcs have associated numerical values (typically costs, capacities, transit times, and/or supplies and demands). As usual, we let n denotes the number of nodes and m denotes the number of arcs in N.

For two (not necessarily distinct) nodes u and v in a directed graph N = (V, A), a u - v walk W in N is a sequence of nodes in N, beginning at u and ending at v like W = (u = v₀, v₁, …, v_k = v) where (v_i, v_i+1) ∈ A for 0 ≤ i ≤ k. A walk in which no node is repeated is a (directed) path. A u - v walk is closed if u = v. A closed walk of length at least 2 in which no node is repeated except for the initial and terminal nodes is a (directed) cycle. In this paper we use terms graph, network, path and cycle instead of directed graph, directed network, directed path and directed cycle for short.

Let S ⊆ V be a set of terminals in network N = (V, A) which can be portioned into a subset of sources S⁺ and sinks S^-. Every source node v ∈ S⁺ has a supply D_v ≥ 0 and every sink v ∈ S^- has a demand D_v ≤ 0 such that ∑_v∈SD_v = 0. In this paper we consider the case with only one source s ∈ V and one sink t ∈ V. In this case, we suppose D_s = - D_t = d. A static flow x on N assigns every arc e a non-negative flow value x_e such that the following flow conservation constraints are obeyed: $\sum_{e \in δ^{+} (v)} x_{e} - \sum_{e \in δ^{-} (v)} x_{e} = 0, for all v \in V ∖ S$ (4)

Here δ⁺ (v) and δ^- (v) denote the set of arcs e leaving node v and entering node v, respectively.

The static flow x satisfies the supplies and demands if: $\sum_{e \in δ^{+} (v)} x_{e} - \sum_{e \in δ^{-} (v)} x_{e} = D_{v} for all v \in S$ (5)

For the case of a single source s and a single sink t which we use the term s - t flow:

An s - t flow x satisfying supply D_s = - D_t = d has value d which we show with |x| = d.

A flow x is called feasible if it obeys the capacity constraints x_e ≤ u_e for all e ∈ A in which u_e is a positive capacity for arc e.

The cost of a static flow x is defined as

c (x) = \sum_{e \in A} c_{e} x_{e}

(6)

Now, we review the concepts such as network flows over time and temporally repeated flows in order to formulate the maximum flow over time problem. Consider network N = (V, A) in which each arc e ∈ A has an associated nonnegative integral transit time τ_e and a positive capacity u_e. A flow over time f on N with time horizon T is given by Lebesgue-measurable function f_e : [0, T] → R⁺ where f_e (θ) determines the rate of flow per unit entering arc e at time θ. Suppose that we have an s - t flow over time. In the model without intermediate storage which is desired in this paper, for all ξ ∈ [0, T) and v∈ V ∖ { s, t } we require that: $\int_{0}^{ξ} (\sum_{e \in δ^{+} (v)} f_{e} (θ) - \sum_{e \in δ^{-} (v)} f_{e} (θ - τ_{e})) d θ = 0$ (7)

Note that here f_e (θ - τ_e) determines the rate of flow entering arc e at time θ - τ_e which arrives to v; the tail of arc e which is an intermediate node, at time θ.

Moreover an s - t flow over time should satisfy the supply D_s = - D_t = d in which: $\int_{0}^{T} (\sum_{e \in δ^{+} (s)} f_{e} (θ) - \sum_{e \in δ^{-} (s)} f_{e} (θ - τ_{e})) d θ = D_{s}$ (8)

Let x be a feasible static flow in N with path decomposition (x_p) _p∈P and value |x| = ∑_p∈Px_p such that the transit time τ_p at every path p ∈ P is bounded from above by T. For every path p ∈ P the temporally repeated flow f sends flow at constant rate x_p into path p ∈ P starting at time zero, ending at time T - τ_p. The value of a temporally repeated s - t flow f which we show with |f| is given by |f| = T|x| - ∑_e∈Aτ_ex_e; because according to the definition of temporally repeated flows: $\begin{matrix} | f | = \sum_{p \in P} (T - τ_{p}) x_{p} = T \sum_{p \in P} x_{p} - \sum_{p \in P} τ_{p} x_{p} = \\ = T | x | - \sum_{e \in A} τ_{e} \sum_{p \in P : e \in A} x_{p} = T | x | - \sum_{e \in A} τ_{e} x_{e} \end{matrix}$ (9)

We are in a position to formulate the maximum flow over time problem. In the maximum flow over time problem it is aimed to determine an s - t flow over time f that send as much flow as possible from the source node s to the sink node t within a given time horizon T. Ford and Fulkerson considered this problem in the setting of discrete flows over time. They proved that the problem can be solved efficiently by transforming it to a static minimum cost flow problem in a related graph. Fleischer and Tardos [12] showed that this algorithm directly extends to continuous flows over time. Since we are going to generalize this algorithm for the case with interval data, we give a short description of it. The algorithm of Ford and Fulkerson computes a temporally repeated s - t flow of maximum value. Recall that the value of a temporally repeated flow f with underlying static flow x is given by T|x| - ∑_e∈Aτ_ex_e. This suggests the following static flow formulation: $\begin{matrix} max T | x | - \sum_{e \in A} τ_{e} x_{e} \\ s . t . \\ x is a static s - t flow in N \end{matrix}$

Any solution to this problem defines a temporally repeated flow with time horizon T.

Optimality of x with respect to the objective function implies that transit time τ_p of any path p ∈ P is bounded by T (A network in which transit time of any path p ∈ P is bounded by T is called T-length bounded network). Furthermore, Ford and Fulkerson [14] proved that a maximum temporally repeated flow with time horizon T is a maximum flow over time with time horizon T.

3.1 Static interval-valued s - t flows

A static interval-valued s - t flow x = [l_x, r_x] assigns every arc e a non-negative interval-valued flow [l_{x
_e}, r_{x
_e}]; the set of real numbers x_e such that l_{x
_e} ≤ x_e ≤ r_{x
_e}, such that the flow conservation constraints $\sum_{e \in δ^{+} (v)} [l_{x_{e}}, r_{x_{e}}] \underset{g}{⊖} \sum_{e \in δ^{-} (v)} [l_{x_{e}}, r_{x_{e}}] = [0, 0]$ for all v ∈ V ∖ S are obeyed. Again δ⁺ (v) and δ^- (v) denote the set of arcs e leaving node v and entering node v, respectively. In addition interval-valued outflow of node s should be more than interval-valued inflow of it and then s has a supply as $[l_{D_{s}}, r_{D_{s}}] = \sum_{e \in δ^{+} (s)} [l_{x_{e}}, r_{x_{e}}] \underset{g}{⊖} \sum_{e \in δ^{-} (s)} [l_{x_{e}}, r_{x_{e}}]$ (10)

Similarly inflow of node t should be more than outflow of it and then t has a demand $[r_{D_{t}}, l_{D_{t}}] = \sum_{e \in δ^{-} (t)} [l_{x_{e}}, r_{x_{e}}] \underset{g}{⊖} \sum_{e \in δ^{+} (t)} [l_{x_{e}}, r_{x_{e}}]$ (11)

An interval-valued s - t flow x = [l_x, r_x] satisfying supply [l_{D
_s}, r_{D
_s}] = [- r_{D
_t}, - l_{D
_t}] = [l_d, r_d] has value |x| = [l_d, r_d]. Consequently the cost of a static interval-valued flow x = [l_x, r_x] is defined as $C (x) = \sum_{e \in A} c_{e} [l_{x_{e}}, r_{x_{e}}]$ (12)

Finally an interval-valued flow x = [l_x, r_x] is called feasible if it obeys the capacity constraints [l_{x
_e}, r_{x
_e}] ≤ [l_{u
_e}, r_{u
_e}] for all e ∈ A.

For example consider a two-sided street which has two lines in each side but sometimes because of some traffical reasons it changes to three or even four lines just in one side. In this case the upper bound for number of lines in this side of the street is a number between two and four, means [2, 4], then every interval-valued flow in this street should satisfy the constraint [l_x, r_x] ≤ [2, 4].

Theorem 1. (Interval-valued Flow Decomposition Theorem): Every interval-valued path and cycle flow has a unique representation as nonnegative interval-valued arc flows. Inversely, every nonnegative interval-valued arc flow x can be represented as an interval-valued path and cycle flow (though not necessarily uniquely) with the following properties:

Every directed path with positive interval-valued flow connects a source node to a sink node.

At most n + m paths and cycles have nonzero interval-valued flow; out of these, at most m cycles have nonzero flow.

Proof. Suppose that P denotes the collection of all interval-valued paths and W the collection of all interval-valued cycles in network N. Let [l_f(p), r_f(p)] is an interval-valued flow on path p ∈ P and [l_f(w), r_f(w)] is an interval-valued flow on cycle w ∈ W. Now the interval-valued flow [l_{x
_e}, r_{x
_e}] on arc e ∈ A equals the sum of the interval-valued flows [l_f(p), r_f(p)] and [l_f(w), r_f(w)] for all paths p and cycles w that contains arc e. Thus each interval-valued path and cycle flow determines arc flows uniquely.

Now we establish the converse assertions. We give an algorithmic proof to show how to decompose any interval-valued arc flow x into an interval-valued path and cycle flow.

Suppose that i₀ is a source node. Then some arc (i₀, i₁) carries a positive interval-valued flow. If i₁ is a sink node, we stop; otherwise, the flow conservation constraint of node i₁ implies that some other arc (i₁, i₂) carries interval-valued positive flow. We repeat this argument until we encounter a sink node or we revisit a previously examined node. Note that one of these two cases will occur within n steps. In the former case we obtain a directed path p from source node i₀ to some sink node i_k, and in the latter case we obtain a directed cycle w. In either case the path or the cycle consists solely of arcs with positive interval-valued flow. If we obtain a directed path, we let l_f(p) = min{ l_{D
_{i
₀}}, l_{D
_{i
_k}}, min { l_{x
_ij} : (i, j) ∈ p }} and r_f(p) = l_f(p) + k in which $\begin{matrix} k = min {(r_{D_{i_{0}}} - l_{D_{i_{0}}}), (r_{D_{i_{k}}} - l_{D_{i_{k}}}), \\ , \min {(r_{x_{ij}} - l_{x_{ij}}) : (i, j) \in p}} \end{matrix}$

Then redefine: $\begin{matrix} [l_{D_{i_{0}}}, r_{D_{i_{0}}}] = [l_{D_{i_{0}}}, r_{D_{i_{0}}}] \underset{g}{⊖} [l_{f (p)}, r_{f (p)}], \\ [l_{D_{i_{k}}}, r_{D_{i_{k}}}] = [l_{D_{i_{k}}}, r_{D_{i_{k}}}] \underset{g}{⊖} [l_{f (p)}, r_{f (p)}] \end{matrix}$

Also, for each arc (i, j) in p define: $[l_{x_{ij}}, r_{x_{ij}}] = [l_{x_{ij}}, r_{x_{ij}}] \underset{g}{⊖} [l_{f (p)}, r_{f (p)}]$

If we obtain a directed cycle w, we let l_f(w) = min{ l_{x
_ij} : (i, j) ∈ w }, r_f(w) = l_f(w) + k in which k = min{ (r_{x
_ij} - l_{x
_ij}) : (i, j) ∈ w } and redefine $[l_{x_{ij}}, r_{x_{ij}}] = [l_{x_{ij}}, r_{x_{ij}}] \underset{g}{⊖} [l_{f (w)}, r_{f (w)}]$ for each (i, j) in w. We repeat this process with the redefined problem until flow conservation constraint for all v ∈ V ∖ S are obeyed. Then we select any node with at least one outgoing arc with a positive interval-valued flow as the starting node, and repeat the procedure, which in this case must find a directed cycle. We terminate when [l_{x
_e}, r_{x
_e}] = [0, 0] for the redefined problem and all e ∈ A. Clearly, the original flow is the sum of flows on the paths and cycles identified by this method.

Notice that if in an obtained path (cycle) l_f(p) = k = 0 (l_f(w) = k = 0) then we should change the path (cycle) in a way that either l_f(p) > 0 or k > 0. It is obvious that always there is a path (cycle) with a desired property; otherwise, suppose that l_f(p) = k = 0 (l_f(w) = k = 0) for all p ∈ P(w ∈ W). On the other word suppose that there is at least an arc on every path (cycle), say (i, j) with [l_{x
_ij}, r_{x
_ij}] = [0, 0].

Let p = (s = i₀, i₁, … i_k, i_k+1, … i_l = t) be an arbitrary path and (i_k, i_k+1) be a first arc on the path with zero interval-valued flow. If i_k ∉ S⁺, then i_k is an intermediate node, and interval-valued flow on the former arc on the path i.e. (i_k-1, i_k) should be positive. Flow conservation constraint on node i_k guarantees that there is another outward arc like $(i_{k}, i_{k + 1}^{'})$ with positive flow. Pursuing the same argument for node $i_{k + 1}^{'}$ and repeating the process we will either revisit a node on the path or meet a sink node which in the former case we have a cycle with l_f(w) > 0 or k > 0 and in the latter case a path with l_f(p) > 0 or k > 0 which is a contradiction.

If i_k ∈ S⁺ then there should be some outward arc that carry a positive interval-valued flow. By pursuing the same argument in this case we will also come to contradiction. Now observe that each time we identify a directed path, we reduce the supply/demand of some terminal to zero or the flow on some arc to zero; and each time we identify a directed cycle, we reduce the flow on some arc to zero. Consequently, the path and cycle representation of the given interval-valued flow x contains at most m + n directed paths an cycles, and at most m of these are directed cycles. □

Example 1. Consider the network shown in Fig. 1(a). The interval-valued arc flow shown in the Fig. 1(b) sends [4, 9] units of flow from node s to node t.

If we apply Theorem 1, we can decompose the given interval-valued arc flow into interval-valued path-flows as follow:

$\begin{matrix} p_{1} = (s, 1, 2, 4, 5, t), [l_{x_{p_{1}}}, r_{x_{p_{1}}}] = [1, 1] \\ p_{2} = (s, 1, 4, 5, t), [l_{x_{p_{2}}}, r_{x_{p_{2}}}] = [1, 1] \\ p_{3} = (s, 2, 5, t), [l_{x_{p_{3}}}, r_{x_{p_{3}}}] = [1, 2] \\ p_{4} = (s, 3, t), [l_{x_{p_{4}}}, r_{x_{p_{4}}}] = [0, 2] \\ p_{5} = (s, 3, 2, 4, t), [l_{x_{p_{5}}}, r_{x_{p_{5}}}] = [1, 1] \\ p_{6} = (s, 1, 4, t), [l_{x_{p_{6}}}, r_{x_{p_{6}}}] = [0, 1] \\ p_{7} = (s, 1, 2, 4, t), [l_{x_{p_{7}}}, r_{x_{p_{7}}}] = [0, 1] \end{matrix}$

3.2 Interval-valued network flows over time

Consider network N = (V, A) in which each arc e ∈ A has an associated nonnegative integral transit time τ_e and a positive interval-valued capacity [l_{u
_e}, r_{u
_e}]. An interval-valued flow over time [l_f, r_f] on N with time horizon T is given by Lebesgue-measurable function f_e : [0, T] → I in which I denotes the class of nonempty compact intervals on [0, ∞] and [l_{f_e(θ)}, r_{f_e(θ)}] determines the uncertain rate of flow per unit entering arc e at time θ. Although, transit times are fixed, but flow on arc e progresses at uncertain rate. In particular, the interval-valued flow [l_{f_e(θ)}, r_{f_e(θ)}] entering arc e at time θ arrives to the tail of the arc at time θ + τ_e. Thus, in order to obey the time horizon T, we require that [l_{f_e(θ)}, r_{f_e(θ)}] = [0, 0] for θ ∈ [T - τ_e, T).

Suppose that we have an interval-valued s - t flow over time. In the model without intermediate storage which is desired in this paper, for all ξ ∈ [0, T) and v∈ V ∖ { s, t } we require that: $\begin{matrix} \int_{0}^{ξ} (\sum_{e \in δ^{+} (v)} l_{f_{e} (θ)} - \sum_{e \in δ^{-} (v)} l_{f_{e} (θ - τ_{e})}) d θ = 0 \\ and \int_{0}^{ξ} (\sum_{e \in δ^{+} (v)} r_{f_{e} (θ)} - \sum_{e \in δ^{-} (v)} r_{f_{e} (θ - τ_{e})}) d θ = 0 \end{matrix}$ (13)

This implies $\begin{matrix} [(\int_{0}^{ξ} (\sum_{e \in δ^{+} (v)} l_{f_{e} (θ)} - \sum_{e \in δ^{-} (v)} l_{f_{e} (θ - τ_{e})}) d θ), \\ , (\int_{0}^{ξ} (\sum_{e \in δ^{+} (v)} r_{f_{e} (θ)} - \sum_{e \in δ^{-} (v)} r_{f_{e} (θ - τ_{e})}) d θ)] = [0, 0] then, \\ \int_{0}^{ξ} [(\sum_{e \in δ^{+} (v)} l_{f_{e} (θ)} - \sum_{e \in δ^{-} (v)} l_{f_{e} (θ - τ_{e})}), \\ , (\sum_{e \in δ^{+} (v)} r_{f_{e} (θ)} - \sum_{e \in δ^{-} (v)} r_{f_{e} (θ - τ_{e})})] d θ = [0, 0] then, \\ \int_{0}^{ξ} ([\sum_{e \in δ^{+} (v)} l_{f_{e} (θ)}, \sum_{e \in δ^{+} (v)} r_{f_{e} (θ)}] \underset{g}{⊖} \\ [\sum_{e \in δ^{-} (v)} l_{f_{e} (θ - τ_{e})}, \sum_{e \in δ^{-} (v)} r_{f_{e} (θ - τ_{e})}]) d θ = [0, 0] thus, \end{matrix}$ $\begin{matrix} \int_{0}^{ξ} (\sum_{e \in δ^{+} (v)} [l_{f_{e} (θ)}, r_{f_{e} (θ)}] \underset{g}{⊖} \\ \sum_{e \in δ^{-} (v)} [l_{f_{e} (θ - τ_{e})}, r_{f_{e} (θ - τ_{e})}]) d θ = [0, 0] . \end{matrix}$ (14)

Moreover an interval-valued s - t flow over time should satisfy the supply $[l_{D_{s}}, r_{D_{s}}] = [- r_{D_{t}}, - l_{D_{t}}] = [l_{d}, r_{d}]$ (15)in which: $\begin{matrix} [l_{D_{s}}, r_{D_{s}}] = \int_{0}^{T} (\sum_{e \in δ^{+} (s)} [l_{f_{e} (θ)}, r_{f_{e} (θ)}] \underset{g}{⊖} \\ \sum_{e \in δ^{-} (s)} [l_{f_{e} (θ - τ_{e})}, r_{f_{e} (θ - τ_{e})}]) d θ and \\ [l_{D_{t}}, r_{D_{t}}] = \int_{0}^{T} (\sum_{e \in δ^{-} (t)} [l_{f_{e} (θ - τ_{e})}, r_{f_{e} (θ - τ_{e})}] \underset{g}{⊖} \\ \sum_{e \in δ^{+} (t)} [l_{f_{e} (θ)}, r_{f_{e} (θ)}]) d θ . \end{matrix}$

3.3 Temporally repeated interval-valued flows

Let [l_x, r_x] be a feasible interval-valued static flow in N with path decomposition [l_f(p), r_f(p)] _p∈P such that the transit time τ_p of every path p ∈ P is bounded from above by T. For every path p ∈ P, the temporally repeated interval-valued flow [l_f, r_f] sends flow at uncertain rate [l_f(p), r_f(p)] into path p ∈ P starting at time zero, ending at time T - τ_p.

The value of a temporally repeated interval-valued s - t flow [l_f, r_f] is given by $\begin{matrix} [l_{| f |}, r_{| f |}] = \sum_{p \in P} (T - τ_{p}) [l_{x_{p}}, r_{x_{p}}] \\ = \sum_{p \in P} [(T - τ_{p}) l_{x_{p}}, (T - τ_{p}) r_{x_{p}}] \\ = [\sum_{p \in P} (T - τ_{p}) l_{x_{p}}, \sum_{p \in P} (T - τ_{p}) r_{x_{p}}] \\ = [(T \sum_{p \in P} l_{x_{p}} - \sum_{p \in P} τ_{p} l_{x_{p}}), (T \sum_{p \in P} r_{x_{p}} - \sum_{p \in P} τ_{p} r_{x_{p}})] \\ = [T | l_{x} | - \sum_{p \in P} (\sum_{e \in p} τ_{e}) l_{x_{p}}, T | r_{x} | - \sum_{p \in P} (\sum_{e \in p} τ_{e}) r_{x_{p}}] \\ = [T | l_{x} | - \sum_{e \in A} τ_{e} (\sum_{e \in p, e \in A} l_{x_{p}}), T | r_{x} | - \sum_{e \in A} τ_{e} (\sum_{e \in p, e \in A} r_{x_{p}})] \\ = [T | l_{x} | - \sum_{e \in A} τ_{e} l_{x_{e}}, T | r_{x} | - \sum_{e \in A} τ_{e} r_{x_{e}}] then, \end{matrix}$ (16) $[l_{| f |}, r_{| f |}] = [T | l_{x} | - \sum_{e \in A} τ_{e} l_{x_{e}}, T | r_{x} | - \sum_{e \in A} τ_{e} r_{x_{e}}]$ (17)

Then if we want to have a temporally repeated interval-valued flow with maximum value, we must maximize the objective value in (17) and consequently T|l_x| - ∑_e∈Aτ_el_{x
_e} and T|r_x| - ∑_e∈Aτ_er_{x
_e}.

3.4 Maximum interval-valued flow over time

Inspired by algorithm of Ford and Fulkerson we produce an algorithm for maximum interval-valued flow over time as follow:

Let N = (V, A) be a network flow with interval-valued capacities u_e = [l_{u
_e}, r_{u
_e}] _e∈A and time horizon T, then:

Step 1: First solve the following static problem: $\begin{matrix} P_{L} : \\ max T | \underset{\sim}{x} | - \sum_{e \in A} τ_{e} \underset{\sim_{e}}{x} \\ s . t . \\ \underset{\sim}{x} is a static flow in N such that \underset{\sim_{e}}{x} \leq l_{u_{e}} for all e \in A \end{matrix}$

Let $x_{\sim}^{*}$ be an optimal solution of P_L, solve the next following static problem: $\begin{matrix} P_{R} : \\ max T | \tilde{x} | - \sum_{e \in A} τ_{e} {\tilde{x}}_{e} \\ s . t . \\ \tilde{x} is a static flow in N such that \underset{\sim_{e}^{*}}{x} \leq {\tilde{x}}_{e} \leq r_{u_{e}} for all e \in A \end{matrix}$

Now, if we name the optimal solutions of the problems P_L and P_R, say $x_{\sim}^{*}$ and ${\tilde{x}}^{*}$ as $l_{x}^{*}$ and $r_{x}^{*}$ , respectively, then ${[l_{x_{e}}^{*}, r_{x_{e}}^{*}]}_{e \in A}$ will be an optimal solution for the static network flow N = (V, A) with interval-valued capacities.

Step 2: Decompose ${[l_{x_{e}}^{*}, r_{x_{e}}^{*}]}_{e \in A}$ into interval-valued flows $[l_{x_{p}}^{*}, r_{x_{p}}^{*}]$ on paths p ∈ P and start to send ${[l_{x_{p}}^{*}, r_{x_{p}}^{*}]}_{p \in P}$ starting at time zero, ending at T - τ_p. The resulting temporally repeated interval-valued flow is a maximum interval-valued flow over time with time horizon T.

Lemma 1. Let $[l_{x}^{*}, r_{x}^{*}]$ be an optimal solution generated by solving problems P_L and P_R and also ${[l_{x_{p}}^{*}, r_{x_{p}}^{*}]}_{p \in P}$ be a path decomposition of $[l_{x}^{*}, r_{x}^{*}]$ (we can assume without loose of generality that no cycles are needed in the flow decomposition; otherwise we can decrease flow on cycle without decreasing the objective value). Then, transit time of any path p ∈ P is bounded by T.

Proof. The objective value in (17), divided to two distinct problems P_L and P_R, can be rewritten as (16). Assume that there is a path p ∈ P with τ_p > T. By decreasing the amount of flow on path p, the objective value can be increased which is a contradiction to the optimality of $[l_{x}^{*}, r_{x}^{*}]$ .■

4 Interval-valued T-length bounded network flows over time with interval-valued capacities and transit times

Now consider network N = (V, A) in which each arc e ∈ A has an associated nonnegative interval-valued transit time [l_{τ
_e}, r_{τ
_e}] and a positive interval-valued capacity [l_{u
_e}, r_{u
_e}]. An interval-valued flow over time [l_f, r_f] on N with time horizon T = [T, T] is defined similar to Section 3.2. In this case both transit times and capacities are uncertain throughout, so that flow on arc e progresses at uncertain rate, as before. In particular, the interval-valued flow [l_{f_e(θ)}, r_{f_e(θ)}] entering arc e = (u, v) at time θ arrives at v at uncertain time [θ + l_{τ
_e}, θ + r_{τ
_e}]. Thus, in order to obey the time horizon T = [T, T], we require that [l_{f_e(θ)}, r_{f_e(θ)}] = [0, 0] for θ ∈ [T - r_{τ
_e}, T). As before Let we have a single source s and a single sink t in the network and intermediate storage is not desired. We also require that for all ξ ∈ [0, T) and v∈ V ∖ { s, t } flow conservation constraints and needed supply satisfied (see Section 3.2)

4.1 Temporally repeated interval-valued flows with interval-valued transit times

As before, let [l_x, r_x] be a feasible interval-valued static flow in N with path decomposition [l_f(p), r_f(p)] _p∈P such that the transit time [l_{τ
_p}, r_{τ
_p}] of every path p ∈ P is bounded from above by T = [T, T]. Note that in this section we have considered that all paths are T-length bounded. For every path p ∈ P, the temporally repeated interval-valued flow [l_f, r_f] sends flow at uncertain rate [l_f(p), r_f(p)] into path p ∈ P starting at time zero, ending at uncertain time [T - r_{τ
_p}, T - l_{τ
_p}].

The value of a temporally repeated interval-valued s - t flow [l_f, r_f] is given by $\begin{matrix} [l_{| f |}, r_{| f |}] & = \sum_{p \in P} [T - r_{τ_{p}}, T - l_{τ_{p}}] * [l_{x_{p}}, r_{x_{p}}] \\ = \sum_{p \in P} [min {(T - r_{τ_{p}}) l_{x_{p}}, (T - r_{τ_{p}}) r_{x_{p}}, \\ (T - l_{τ_{p}}) l_{x_{p}}, (T - l_{τ_{p}}) r_{x_{p}}}, \\ max {(T - r_{τ_{p}}) l_{x_{p}}, (T - r_{τ_{p}}) r_{x_{p}}, \\ (T - l_{τ_{p}}) l_{x_{p}}, (T - l_{τ_{p}}) r_{x_{p}}}] = (I) \end{matrix}$ (18)

Now since 0 ≤ l_{x
_p} ≤ r_{x
_p}, 0 ≤ l_{τ
_p} ≤ r_{τ
_p} and both T - l_{τ
_p} and T - r_{τ
_p} are nonnegative for all p ∈ P then: $\begin{matrix} (I) = \sum_{p \in P} [(T - r_{τ_{p}}) l_{x_{p}}, (T - l_{τ_{p}}) r_{x_{p}}] \\ = [\sum_{p \in P} (T - r_{τ_{p}}) l_{x_{p}}, \sum_{p \in P} (T - l_{τ_{p}}) r_{x_{p}}] \\ = [T \sum_{p \in P} l_{x_{p}} - \sum_{p \in P} (\sum_{e \in p} r_{τ_{e}}) l_{x_{p}}, T \sum_{p \in P} r_{x_{p}} - \sum_{p \in P} (\sum_{e \in p} l_{τ_{e}}) r_{x_{p}}] \\ = [T | l_{x} | - \sum_{e \in A} r_{τ_{e}} (\sum_{p \in P, e \in p} l_{x_{p}}), T | r_{x} | - \sum_{e \in A} l_{τ_{e}} (\sum_{p \in P, e \in p} r_{x_{p}})] \\ = [T | l_{x} | - \sum_{e \in A} r_{τ_{e}} l_{x_{e}}, T | r_{x} | - \sum_{e \in A} l_{τ_{e}} r_{x_{e}}] thus, \end{matrix}$ (19) $[l_{| f |}, r_{| f |}] = [T | l_{x} | - \sum_{e \in A} r_{τ_{e}} l_{x_{e}}, T | r_{x} | - \sum_{e \in A} l_{τ_{e}} r_{x_{e}}]$ (20)

Then if we want to have temporally repeated interval-valued flow with maximum value, we must maximize T|l_x| - ∑_e∈Ar_{τ
_e}l_{x
_e} and T|r_x| - ∑_e∈Al_{τ
_e}r_{x
_e}.

4.2 Maximum interval-valued flow over time with interval-valued transit times

As before, we produce an algorithm for maximum interval-valued flow over time with interval-valued transit times as follow:

Let N = (V, A) be a network flow with time horizon T, interval-valued transit times and capacities [l_{τ
_e}, r_{τ
_e}] _e∈A and u_e = [l_{u
_e}, r_{u
_e}] _e∈A respectively, then:

Step 1: First solve the following static problem: $\begin{matrix} P_{L}^{I} : \\ max T | \underset{\sim}{x} | - \sum_{e \in A} r_{τ_{e}} \underset{\sim_{e}}{x} \\ s . t . \\ \underset{\sim}{x} is a static flow in N such that \underset{\sim_{e}}{x} \leq l_{u_{e}} for all e \in A \end{matrix}$

Then let $x_{\sim}^{*}$ be an optimal solution of $P_{L}^{I}$ and solve the next following static problem: $\begin{matrix} P_{R}^{I} : \\ max T | \tilde{x} | - \sum_{e \in A} l_{τ_{e}} {\tilde{x}}_{e} \\ s . t . \\ \tilde{x} is a static flow in N such that x_{\sim}^{*_{e}} \leq {\tilde{x}}_{e} \leq r_{u_{e}} for all e \in A . \end{matrix}$

Now if we name the optimal solutions of the problems $P_{L}^{I}$ and $P_{R}^{I}$ , say $x_{\sim}^{*}$ and ${\tilde{x}}^{*}$ as $l_{x}^{*}$ and $r_{x}^{*}$ , respectively, then ${[l_{x_{e}}^{*}, r_{x_{e}}^{*}]}_{e \in A}$ will be an optimal solution for the mentioned static network flow with interval-valued capacities.

Step 2: Decompose ${[l_{x_{e}}^{*}, r_{x_{e}}^{*}]}_{e \in A}$ into interval-valued flows $[l_{x_{p}}^{*}, r_{x_{p}}^{*}]$ on paths p ∈ P and start to send ${[l_{x_{p}}^{*}, r_{x_{p}}^{*}]}_{p \in P}$ Starting at time zero, ending at uncertain interval-valued time [T - r_{τ
_p}, T - l_{τ
_p}]. The resulting temporally repeated interval-valued flow is a maximum interval-valued flow over time with time horizon T = [T, T] (see Theorem 2 at the end of this subsection).

Theorem 2. A maximum temporally repeated interval-valued flow with time horizon T when capacities (both capacities and transit times) are interval-valued is a maximum interval-valued flow over time with time horizon T.

Proof is obvious because we divide the objective value of a temporally repeated interval-valued flow into two problems P_L and P_R ( $P_{L}^{I}$ and $P_{R}^{I}$ ).

Moreover a solution to problems P_L and P_R ( $P_{L}^{I}$ and $P_{R}^{I}$ ) can be obtained by adding the arc (t, s) to the original graph with transit time -T and computing the minimum cost circulation in N with transit times interpreted as costs. For example by applying the minimum mean cycle-cancelling algorithm of Goldberg and Tarjan [18] this can be solved in strongly polynomial time.

To see a complexity survey of minimum cost circulation; refer to the book of Schrijver [28].

4.3 Numerical example

Now we produce a numerical example which is solved using the proposed algorithm in Section 4.2 and the obtained results are discussed.

Example 2. Consider the network shown in Fig. 1(a). Interval-valued capacities are given in the Fig. 1(a), let T = [12, 12], $\begin{matrix} [l_{τ_{s 1}}, r_{τ_{s 1}}] = [1, 2], [l_{τ_{s 2}}, r_{τ_{s 2}}] = [2, 3], \\ [l_{τ_{s 3}}, r_{τ_{s 3}}] = [1, 3], [l_{τ_{12}}, r_{τ_{12}}] = [2, 4], \\ [l_{τ_{32}}, r_{τ_{32}}] = [1, 2], [l_{τ_{25}}, r_{τ_{25}}] = [1, 2], \\ [l_{τ_{24}}, r_{τ_{24}}] = [0, 1], [l_{τ_{14}}, r_{τ_{14}}] = [3, 5], \\ [l_{τ_{35}}, r_{τ_{35}}] = [1, 3], [l_{τ_{3 t}}, r_{τ_{3 t}}] = [2, 3], \\ [l_{τ_{5 t}}, r_{τ_{5 t}}] = [1, 1], [l_{τ_{4 t}}, r_{τ_{4 t}}] = [1, 2], \\ [l_{τ_{45}}, r_{τ_{45}}] = [1, 2] . \end{matrix}$

Note that all paths at the given network are 12-length bounded. We are going to send maximum interval-valued flow over time from node s to node t within time horizon T = [12, 12] applying the algorithm produced in Section 4.2.

In Step 1 we solve the following static problem: $\begin{matrix} P_{L}^{I} : \\ max Z_{L} = 12 | \underset{\sim}{x} | - 2 x_{s 1} - 3 x_{s 2} - 3 x_{s 3} - 4 x_{12} - 2 x_{32} - 2 x_{25} \\ - x_{24} - 5 x_{14} - 3 x_{35} - 3 x_{3 t} - 2 x_{5 t} - 2 x_{4 t} - 2 x_{45} \\ s . t . \\ x_{s 2} + x_{12} + x_{32} = x_{24} + x_{25}, x_{s 1} = x_{12} + x_{14} \\ x_{s 3} = x_{32} + x_{35} + x_{3 t}, x_{14} + x_{24} = x_{4 t} + x_{45} \\ x_{25} + x_{35} + x_{45} = x_{5 t}, | \underset{\sim}{x} | = x_{s 1} + x_{s 2} + x_{s 3} \\ 0 \leq x_{s 1} \leq 3, 0 \leq x_{s 2} \leq 1, 0 \leq x_{s 3} \leq 2, 0 \leq x_{14} \leq 1 \\ 0 \leq x_{14} \leq 1, 0 \leq x_{12} \leq 1, 0 \leq x_{32} \leq 1, 0 \leq x_{25} \leq 2 \\ 0 \leq x_{24} \leq 3, 0 \leq x_{45} \leq 2, 0 \leq x_{35} \leq 1, 0 \leq x_{3 t} \leq 1 \\ 0 \leq x_{5 t} \leq 4, 0 \leq x_{4 t} \leq 2 \end{matrix}$ (21)

Using the standard simplex algorithm to solve problem (21) leads to the following optimal solution and optimal objective value: $\begin{matrix} Z_{L} = 21, | \underset{\sim}{x} | = 5, \\ x_{s 1} = 2, x_{s 2} = 1, x_{s 3} = 2, x_{12} = 1, x_{32} = 0, x_{25} = 1, x_{24} = 1, \\ x_{14} = 1, x_{35} = 1, x_{3 t} = 1, x_{5 t} = 2, x_{4 t} = 2, x_{45} = 0 \end{matrix}$ Now we solve the following static problem: $\begin{matrix} P_{R}^{I} : \\ max Z_{R} = 12 | \tilde{x} | - x_{s 1} - 2 x_{s 2} - x_{s 3} - 2 x_{12} - x_{32} - x_{25} \\ - 0 x_{24} - 3 x_{14} - x_{35} - 2 x_{3 t} - 2 x_{5 t} - x_{4 t} - x_{45} \\ s . t . \\ x_{s 2} + x_{12} + x_{32} = x_{24} + x_{25}, x_{s 1} = x_{12} + x_{14} \\ x_{s 3} = x_{32} + x_{35} + x_{3 t}, x_{14} + x_{24} = x_{4 t} + x_{45} \\ x_{25} + x_{35} + x_{45} = x_{5 t}, | \tilde{x} | = x_{s 1} + x_{s 2} + x_{s 3} \\ 2 \leq x_{s 1} \leq 5, 1 \leq x_{s 2} \leq 3, 2 \leq x_{s 3} \leq 3, 1 \leq x_{14} \leq 2 \\ 1 \leq x_{12} \leq 2, 0 \leq x_{32} \leq 2, 2 \leq x_{25} \leq 2, 0 \leq x_{24} \leq 3 \\ 0 \leq x_{45} \leq 2, 1 \leq x_{35} \leq 1, 1 \leq x_{3 t} \leq 3, 3 \leq x_{5 t} \leq 6 \\ 1 \leq x_{4 t} \leq 4 \end{matrix}$ (22)

The optimal solution and optimal value of objective function of problem (22) are achieved asfollows: $\begin{matrix} Z_{L} = 77, | \tilde{x} | = 10, x_{s 1} = 4, \\ x_{s 2} = 3, x_{s 3} = 3, x_{12} = 2, x_{32} = 0, x_{25} = 2, x_{24} = 3, \\ x_{14} = 2, x_{35} = 1, x_{3 t} = 2, x_{5 t} = 4, x_{4 t} = 4, x_{45} = 1 \end{matrix}$

Optimal solutions of the problems (21) and (22) compose optimal interval-valued solution of the static network flow with interval-valued capacities shown in Fig. 1(a) as follow: $\begin{matrix} [l_{x_{s 1}}^{*}, r_{x_{s 1}}^{*}] = [2, 4], [l_{x_{s 2}}^{*}, r_{x_{s 2}}^{*}] = [1, 3], [l_{x_{s 3}}^{*}, r_{x_{s 3}}^{*}] = [2, 3], \\ [l_{x_{12}}^{*}, r_{x_{12}}^{*}] = [1, 2], [l_{x_{32}}^{*}, r_{x_{32}}^{*}] = [0, 0], [l_{x_{24}}^{*}, r_{x_{24}}^{*}] = [1, 2], \\ [l_{x_{25}}^{*}, r_{x_{25}}^{*}] = [1, 3], [l_{x_{14}}^{*}, r_{x_{14}}^{*}] = [1, 2], [l_{x_{35}}^{*}, r_{x_{35}}^{*}] = [1, 1], \\ [l_{x_{3 t}}^{*}, r_{x_{3 t}}^{*}] = [1, 2], [l_{x_{5 t}}^{*}, r_{x_{5 t}}^{*}] = [2, 4], [l_{x_{4 t}}^{*}, r_{x_{4 t}}^{*}] = [2, 4], \\ [l_{x_{45}}^{*}, r_{x_{45}}^{*}] = [0, 1] \end{matrix}$

In Step 2 we decompose the outcome static interval-valued flows into interval-valued flows onpaths: $\begin{matrix} p_{1} = (s, 1, 4, t), [l_{τ_{p_{1}}}, r_{τ_{p_{1}}}] = [5, 9], [l_{x_{p 1}}, r_{x_{p 1}}] = [1, 2] \\ p_{2} = (s, 1, 2, 4, t), [l_{τ_{p_{2}}}, r_{τ_{p_{2}}}] = [4, 9], [l_{x_{p 2}}, r_{x_{p 2}}] = [1, 2] \\ p_{3} = (s, 2, 5, t), [l_{τ_{p_{3}}}, r_{τ_{p_{3}}}] = [5, 7], [l_{x_{p 3}}, r_{x_{p 3}}] = [1, 3] \\ p_{4} = (s, 3, t), [l_{τ_{p_{4}}}, r_{τ_{p_{4}}}] = [3, 6], [l_{x_{p 4}}, r_{x_{p 4}}] = [1, 2] \\ p_{5} = (s, 3, 5, t), [l_{τ_{p 5}}, r_{τ_{p_{5}}}] = [4, 8], [l_{x_{p 5}}, r_{x_{p 5}}] = [1, 1] \end{matrix}$

Now we start to send ${[l_{x_{p}}^{*}, r_{x_{p}}^{*}]}_{p \in P}$ Starting at time zero, ending at [T - r_{τ
_p}, T - l_{τ
_p}]: $\begin{matrix} [1, 2] * [3, 7] + [1, 3] * [5, 7] + [1, 2] * [3, 8] \\ + [1, 2] * [6, 9] + [1, 1] * [4, 8] = [21, 77] \end{matrix}$

This means that at most [21, 77] unit of interval-valued flow over time can be sent within time horizon [12, 12].

4.4 Quickest interval-valued flow over time

Here we want to produce an algorithm which determines an interval-valued s - t flow over time that satisfies demand [l_D, r_D] within minimum time [l_T, r_T].

Algorithm is very easy; Apply binary search to determine the time horizon T. In each step, solve the problems P_L and P_R ( $P_{L}^{I}$ and $P_{R}^{I}$ for the case with interval-valued transit times on T-length bounded network) separately for the current value of T. Repeat this approach separately to meet demands and in which and for the given ɛ. The resulted $[\underset{\sim}{T}, \tilde{T}]$ is the quickest time horizon in which the demand which is sufficiently close to, and falls in [l_D, r_D] is satisfied.

According to Fleischer and Tardos [12] if demands and transit times are integral in P_L and P_R ( $P_{L}^{I}$ and $P_{R}^{I}$ ), the mentioned binary search algorithm finds the optimal time horizons $\underset{\sim}{T}$ and $\tilde{T}$ in polynomial time.

5 Conclusions

In this paper we considered a network flow over time in which transit times, capacities and consequently flow on arcs fall within compact intervals. In fact, sometimes determining the exact quantity of capacities and transit times are either hard, with probable errors or even unwanted. In these cases considering transit times, capacities and flows laid within specific ranges, or vary in time within these ranges may help. In this paper, thanks to Ford and Fulkerson algorithm for the maximum flow over time, we produced interval-valued maximum flow and quickest s - t flow algorithms to network flows over time with interval-valued capacities and transit times. As we mentioned before, the algorithm proposed at section 4 works on T-length bounded networks which is a restriction, then a future work would be producing an algorithm without this restriction.

Footnotes

Acknowledgments

The authors would like to thank the anonymous reviewers and the editor for their insightful comments and suggestions. Moreover, the first and second authors greatly appreciate the office of vice chancellor for research of Islamic Azad University, Parand Branch and Qaemshahr Branch, respectively, for financially supports.

References

Alonso

and Fall

, A linear programming formulation of flows over time with piecewise constant capacity and transit times. Technical Report IRB-TR-03-007, Intel Research, 2003.

Anderson

E.J.

, Nash

and Philpott

A.B.

, A class of continuous network flow problems, Mathematics of Operations Research 7 (1982), 501–514.

Aronson

J.E.

, A survey of dynamic network flows, Annals of Operations Research 20 (1989), 1–66.

Burkard

R.E.

, Dlaska

and Klinz

, The quickest flow problem, ZOR- Methods and Models of Operations Research 37 (1993), 31–58.

Diamond

, A fuzzy Max Flow-Min Cut theorem, Fuzzy Sets and Systems 119 (2001), 139–148.

Ebrahimnejad

, Nasseri

S.H.

and Mansourzadeh

S.M.

, Bounded primal simplex algorithm for bounded linear programming with fuzzy cost coefficients, International Journal of Operations Research and Information Systems 2(1) (2011), 96–120.

Ebrahimnejad

and Nasseri

S.H.

, Extension of network primal simplex algorithm for solving minimum cost network flow problem with fuzzy costs based on ranking functions, Annals of Fuzzy Mathematics and Informatics 4(1) (2012), 9–24.

Ebrahimnejad

and Verdegay

J.L.

, On solving bounded fuzzy variable linear program and its applications, Journal of Intelligent and Fuzzy Systems 27(5) (2014), 2265–2228.

Ebrahimnejad

, A duality approach for solving bounded linear programming problems with fuzzy variables based on ranking functions and its application in bounded transportation problems, International Journal of Systems Science 46(11) (2015), 2048–2060.

10.

Ebrahimnejad

, A simplified new approach for solving fuzzy transportation problems with generalized trapezoidal fuzzy numbers, Applied Soft Computing 19 (2014), 171–176.

11.

Ebrahimnejad

, An improved approach for solving fuzzy transportation problem with triangular fuzzy numbers, Journal of Intelligent and Fuzzy Systems (2015). DOI: 10.3233/IFS-151625

12.

Fleischer

L.K.

and Tardos

, Efficient continuous-time dynamic network flow algorithms, Operations Research Letters 23 (1998), 71–80.

13.

Fonoberova

and Lozovanu

, The maximum flow in dynamic networks, Computer Science Journal of Moldova 12 (2004), 387–396.

14.

Ford

L.R.

and Fulkerson

D.R.

, Constructing maximal dynamic flows from static flows, Operations Research 6 (1985), 419–433.

15.

Ford

L.R.

and Fulkerson

D.R.

, Flows in Networks, Princeton University Press, Princeton, 1962.

16.

Ghatee

, Hashemi

S.M.

, Zarepisheh

and Khorram

, Preemptive priority-based algorithms for fuzzy minimal cost flow problem: An application in hazardous materials transportation, Computers & Industrial Engineering 57 (2009), 341–354.

17.

Ghatee

and Hashemi

S.M.

, Application of fuzzy minimum cost flow problems to network design under uncertainty, Fuzzy Sets and Systems 160 (2009), 3263–3289.

18.

Goldberg

A.V.

and Tarjan

R.E.

, Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM 36 (1989), 873–886.

19.

Hashemi

S.M.

, Nasrabadi

and Skutella

, On solving continuous-time dynamic network flows. Technical Report 13-2008, TU Berlin, 2008.

20.

Jayswal

, Stancu-Minasian

and Ahmad

, On sufficiency and duality for a class of interval-valued programming problems, Applied Mathematics and Computation 218 (2011), 4119–4127.

21.

Koch

, Nasrabadi

and Skutella

, Continuous and discrete flows over time: A general model based on measure theory. Technical Report 16-2009, TU Berlin, 2009.

22.

, Luo

and Deng

, Necessary and sufficient conditions of some strong optimal solutions to the interval linear programming, Linear Algebra and its Applications 439 (2013), 3241–3255.

23.

H.W.

, Cao

M.F.

, Wang

, Fan

and He

, Numerical solutions comparison for interval linear programming problems based on coverage and validity rates, Applied Mathematical Modelling 38 (2014), 1092–1100.

24.

Luo

and Li

, Strong optimal solutions of interval linear programming, Linear Algebra and its Applications 439 (2013), 2479–2493.

25.

Nasseri

S.H.

and Ebrahimnejad

, A fuzzy primal simplex algorithm and its application for solving flexible linear programming problems, European J Industrial Engineering 4(3) (2010), 372–389.

26.

Philpott

A.B.

, Continuous-time flow in networks, Mathematics of Operations Research 15 (1990), 640–661.

27.

Powell

W.B.

, Jaillet

, Odoni

, Stochastic and dynamic networks and routing, In Ball

M.O.

, Magnanti

T.L.

, Monma

C.L.

and Nemhauser

G.L.

, editors, Handbooks in Operations Research and Management Science: Networks. Elsevier Science Publishers B.V., 1995.

28.

Schrijver

, Combinatorial Optimization Springer, Berlin, Heidelberg, 2003.

29.

Sengupta

and Pal

T.K.

, Solving the shortest path problem with interval arcs, Fuzzy Optimization and Decision Making 5 (2006), 71–89.

30.

Stefanini

, A generalization of Hukuhara difference for interval and fuzzy arithmetic, in Dubois

, et al. (Eds), Soft Methods for Handling Variability and Imprecision, Advances in Soft Computing 48, Springer, 2008.

31.

Stefanini

and Bede

, Generalized Hukuhara Differentiability of Interval-valued Functions and Interval Differential Equations, Working Papers 0803, University of Urbino Carlo Bo, Department of Economics, revised, 2008.

32.

Wang

and Huang

, Violation analysis on two-step method for interval linear programming, Information Sciences 281 (2014), 85–96.