# A Novel Maximum Flow Algorithm with Neural Network for Time-Varying Wastage Networks

Authors: Baowen Zhang; Kaiwen Jiang; Wei Huang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

This paper introduces a time-varying wastage maximum flow problem (TWMFP) and proposes a time-flow neural network (TFNN) for solving the TWMFPs. The time-varying wastage maximum flow problem is concerned with finding the maximum flow in a network with time-varying arc capacities and additive flow losses on the arcs. This problem has multiple applications in transportation, communication, and financial network. For example, solving the maximum traffic flow of the transportation network and the maximum profit of the financial network. Unlike traditional neural network algorithms, the proposed TFNN does not require any training by means of its time-flow mechanism. The time-flow mechanism is realized by each active neuron sending pulses to its successor neurons. In order to maximize the network flow, the proposed TFNN can be divided into two parts: path-pulse neural networks (PPNNs) and subnet-flow neural networks (SFNN). PPNN is to generate two subnet sets (viz. with wastage arcs and without), and SFNN is to find the maximum flow value of each subnet. The subnet computing strategy of the proposed algorithm greatly improves the solution accuracy of TWMFPs. Theoretical analysis and experiments have proved the effectiveness of TFNN. The experiment results of the transportation network (viz. New York Road) show that the proposed TFNN has better performance (viz. error rate and computational time) compared to classical algorithms.


---

## Body

## 1. Introduction

The maximum flow problem (MFP) is a classical network optimization problem [1, 2], and it is also a general problem in vehicular networks [3], network optimization [4], social network [5, 6], and other fields. Ford and Fulkerson first solved the maximum flow problem using the labeling algorithm (viz. Ford-Fulkerson (FF) algorithm) [7]. Then, many improved labeling algorithms have been proposed for solving the maximum flow problems [8], such as Edmonds–Karp algorithm [9], and the Cai–Sha algorithm [10]. With the increasing complexity of networks, some intelligent algorithms have been used for solving the MFP, such as the genetic algorithm (GA) [11].The time-varying wastage maximum flow problem is the maximum flow problem with time-varying arc capacities and additive flow losses on the arcs, which can be applied to intelligent transportation [12, 13], communication network [14], financial analysis [15, 16], and other fields. In financial networks, Eboli [17] has described the balance-sheet as a loss flow on the arc. The time-varying maximum flow problem (TMFP) [18, 19] and wastage maximum flow problem (WMFP) [20] have been investigated extensively. Li and Buzdalov et al. [21, 22] proposed their algorithms for solving the TMFPs. Cai [23] and Song [24] have researched different WMFPs. These existing algorithms were improved labeling algorithms [25]. While to the best of our knowledge, a question with regard to find the maximum flow value of time-varying wastage maximum flow problem remains open.In this paper, we propose a novel neural network framework for solving the time-varying wastage maximum flow problem (TWMFP). The TWMFP is the maximum flow problem with time-varying arc capacities and additive flow losses on the arcs. The advantages of the proposed time-flow neural network (TFNN) are summarized as follows: first, different with general neural networks, the proposed TFNN does not require any training based on its time-flow mechanism. Second, compared with classical labeling algorithms, the proposed TFNN greatly improves the calculation speed based on its parallel computing feature. Third, unlike existing maximum flow algorithms, the unique group calculation idea of the proposed TFNN improves the accuracy for solving TWMFPs. In addition, the proposed TFNN can find an accurate solution to the general network maximum flow problems, such as MFP and TMFP.The remainder of this paper is organized as follows: in Section2, some basic concepts of TWMFP are introduced. In Section 3, the TFNN algorithm is developed and an example of a TWMFP is given. In Section 4, the experimental results are reported. And, Section 5 gives a conclusion to this paper.


## 2. Mathematical Formulation

The goal of the time-varying wastage maximum flow problem is to find the maximum flow from the departure node to the destination node within a predetermined period, where arc capacities change over time and flow on the arc may be consumed. Such problems introduced in this paper can be applied to fields such as intelligent transportation and financial analysis. For example, in a transportation network, road congestion during peak periods represents time-varying arc capacities and car accident emergency represents consumption/wastage on the arc.Definition 1.
[Wastage Network (WN)]. LetV be a set of network nodes, A=vi,vj/vi,vj∈V be a set of network arcs, C=cij/vi,vj∈A be a set of arc capacities, and W=wij/vi,vj∈A be a set of arc wastage, then the network G=V,A,C,W is defined as a wastage network.Definition 2.
[Time-Varying Wastage Network (TWN)]. Assume there is a wastage networkG=V,A,C,W, given a piecewise function Cξ=Cijξi/vi,vj∈A,ξi∈Tij stands for a set of arc capacities, where ξ=ξj/ξj=ξi+bij,vi,vj∈A, ξi denotes the depart time of node vi, bij represents the length of arc vi,vj, Tij=tsz,tdz/vi,vj∈A,z=1,…,Z means a set of time windows, tsz and tdz represent the earliest and latest depart times, z and Z denotes the index and number of time windows. Then, network G=V,A,Cξ,W is a time-varying wastage network.
The arc lengths of time-varying wastage networks are set as a predetermined numberδt. The arrival time of the destination node is calculated as follows:(1)ξd=maxξi+bid.Definition 3.
[Feasible Flow]. Given a TWNG=V,A,Cξ,W, then the feasible flow Fijξ of the arc vi,vj can be expressed as follows:(2)Fijξ=fijξ−fijξ∗wij,where(3)fijξ=min∑vg,vi∈AFgiξg,Cijξi.
Considering the particularity of the departure nodevs, then the feasible flow Fsyξ can be calculated by the following equation:(4)Fsyξ=Csyξs−Csyξs∗wsy.Definition 4.
[Model of the TWMFP]. Given a time limitationT0. Follows from (1)–(4), the model of the TWMFP is formulated by the following equation:(5)max∑vr,vd∈AFrdξ,s.t.ξd≤T0,Fijξi≤Cijξi,∑vs,vy∈AFsyξ−∑vr,vd∈AFrdξ≥0,∑vj,vi∈AFjiξ−∑vi,vj∈AFijξ=0,where(6)Fsyξ=Csyξs−Csyξs∗wsy,…Fijξ=fijξ−fijξ∗wij,…Frdξ=frdξ−frdξ∗wrd.(7)frdξ=min∑vx,vr∈AFxrξ,Crdξ.


## 3. Time-Flow Neural Network Algorithm Description

Generally, the labeling algorithms are used to find the solution of maximum flow problems. A disadvantage of these approaches is that they usually obtain large error rate solutions due to the time-varying and wastage in TWMFPs. This paper provides a better way to solve the time-varying wastage maximum flow problem.In this section, the proposed TFNN algorithm will be described at first. And, then the construction of path-pulse neural networks (PPNNs) and subnet-flow neural networks (SFNNs) are depicted. To show the structure and algorithm of TFNN, the description of symbols are shown in Table1.Table 1
Description of the symbols used in TFNN.
SymbolsExplanationPnit1A pulse from neuronn to neuron i at time t1wxiWastage of arcvx,viUniWastage list of the path from neurons to i, where n on the pathTijzThez th time window of arc vi,vjcijzCapacity from neuroni to neuron j at time window TijzBiThe relation neuron of neuronifziThe flow of arcvz,viGoThe set of subnets without wastage arcsGwThe set of subnets with wastage arcsUixPulse information of arcvi,vx


### 3.1. Description of TFNN

The underlying idea of using TFNN to solve TWMFP is that a neuron sends “preflows” (viz. pulses) to its successor neurons when the current neuron received pulses. With this new viewpoint, the proposed TFNN can reach a better solution of TWMFPs. There are two main parts in the design of TFNN, the first part is to find two subnet sets (viz. with wastage arcs and without) by path-pulse neural networks (PPNN), while the second part is to calculate the maximum flow of the subnets based on subnet-flow neural networks (SFNNs). The detailed steps of TFNN are shown in Algorithm 1.Algorithm 1: Time-flow Neural Network (TFNN).
Input: Δt, T0,G.Output: f∗./∗ The maximum flow. ∗/(1)
Sett=0, f∗=0, Go=∅, Gw=∅.(2)
Do(3)
Generate subnet setsGo and Gw from G by PPNN.(4)
Sett=t+Δt.(5)
Untilt>T0./∗ End step2 ∗/(6)
Updatef∗ of all subnets in Go by SFNN.(7)
Updatef∗ of all subnets in Gw by SFNN.(8)
Report the maximum flowf∗.


### 3.2. Description of PPNN

PPNN is used to generate two subnet sets (viz. with and without wastage arcs) through the following parts: first, initialize neurons by Step 1. Second, generate pulses from the departure neurons at every time by Step 3. Third, update all nodes but s at every time by Step 4. Fourth, update subnet sets at every time by Steps 5–10. Finally, output subnet sets. The detailed steps of PPNN are shown in Algorithm 2.Algorithm 2: Path-pulse Neural Networks (PPNN).
Input: Δt,G,t,Go,Gw.Output: Go,Gw./∗ Subnet sets of G. ∗/(1)
Sett1=0,Pnit=∅,Ti=TWi,y=0,wixt=−1(2)
Do(3)
Updatewsxt1,t2, and Psxt2 of s using (13)–(16).(4)
Update all nodesi∈V/s using (8)–(16).(5)
IfOPndt1=0(6)
SetGo=Go∪RPnd.(7)
End If./∗ End step5 ∗/(8)
IfOPndt1>0(9)
SetGw=Gw∪RPnd.(10)
End If./∗ End step8 ∗/(11)
Sett1=t1+Δt(12)
Untilt1>t./∗ End step2 ∗/(13)
Report two subnet setsGo and Gw.All neurons in the PPNN will no longer generate pulses when the time limitation is reached. A general structure of a neuron in PPNN is shown in Figure1.Figure 1
A general structure of PPNN.


#### 3.2.1. Input

The input part is used to receive pulses from its predecessor neurons.


#### 3.2.2. Pulse Receiver

The pulse receiver part is used to filter the received pulses and consists ofPnit1, y and time window Ti. Time window Ti is initialized by Algorithm 2 (PPNN). Pnit1 is explained as follows:(8)Pnit1=Uni,if the input has received pulse,∅,if the input does not received pulse,where(9)Uni=wsit,ifn=s,wsat0,…,wnit,ifn≠s.y is explained as follows:(10)y=g1Pnit1=1,ifPnit1≠∅,0,ifPnit1=∅.where Pnit1≠∅ means at least one pulse has reached at t1.If the current neuron is the destination neurond, the neuron no longer generates pulses and output the path RPndt1 and the wastage OPndt1. Their expressions are shown as follows:(11)RPndt1=<∅>,ifPndt1=∅;<s,t,…,d,t1>,ifPndt1=wsit,…,wndt1,(12)OPndt1=−1,ifPnit1=∅,∑wijt∈Pndt1wijt,ifPnit1≠∅.


#### 3.2.3. Neuron State

The neuron state part is used to select the time window and consists ofwixt1, x=f,…,h. wixt1 is explained in the following equation:(13)wixt1=g2Wi=wix,ift1∈Tixz,−1,ift1∉Tixz.


#### 3.2.4. Pulse Sender

The pulse sender part is used to calculate the parameter and generates pulses and consists oft2 and Pixt2, x=f,…,h. The expression of them are shown as follows:(14)t2=t1+Δt,(15)Pixt2=g3Pnit1,wixt1,t2=Uix,if the output has sent pulse;∅,if the output does not send pulse,where(16)Uix=wsx,ifi=s,t1∈Tixz;wsat0,…,wnit,wixt1,ifi≠s,t1∈Tixz.


#### 3.2.5. Output

The output part is used to send the pulse to its successor neurons.


### 3.3. Description of SFNN

SFNN is used to find the maximum flow of subnets through the following parts: first, initialize neurons by Step 1. Second, update all nodes,fp,cij,fijt,Bi, and f∗ by Steps 2–7. Third, update D by Steps 8–10. Final, output the maximum flow. The detailed steps of SFNN are shown in Algorithm 3.Algorithm 3: Subnet-flow Neural Networks (SFNNs).
Input: f∗,G′.Output: f∗.(1)
Setj=0,Mi=0,Bi=−1,Pni=∅,Ini=0,fnit=0,F=fnit/vn,vi∈A, Bs=s,C=C′.(2)
Do(3)
SetD=0,p=∅,fp=0.(4)
Update all nodes using (17)–(25).(5)
Setp=QPnd,wp=∑i,j∈pwij,fp=FPnd∗1−wp(6)
Setcij=cij−fp,fijt=fp,Bi=−1 where i,j∈p.(7)
Setf∗=f∗+fp.(8)
IfMi of all nodes are not equal to 0.(9)
SetD=1.(10)
End If./∗ End step8 ∗/(11)
UntilD==1./∗ End step2 ∗/(12)
Reportf∗.Each neuron in SFNN will reserve the first pulse received in an iteration. A general structure of a neuron in subnet-flow neural networks is shown in Figure2.Figure 2
A general structure of SFNN.


#### 3.3.1. Input

The input part is used to receive pulses coming from its relational neurons.


#### 3.3.2. Pulse Receiver

The pulse receiver part is used to filter the received pulses and consists ofPni, j, B, F, and C. The value of B, F, and C are calculated by the SFNN Algorithm. Pni is shown as follows:(17)Pni=Uni,if the input has received pulse;∅,if the input does not received pulse,where(18)Uni=Isi,ifn=s;Isa,…,Ini,ifn≠s.j is explained as follows:(19)j=g4Pni=1,ifPni≠∅;0,otherwise.The value ofPni not equals ∅ means at least one pulse has reached at current neuron i at t.If current neuroni is the destination neuron d, the neuron no longer generates pulses and output the path QPnd and the path flow FPnd. Their expressions are shown as follows:(20)QPnd=<∅>,ifPnd=∅;s,…,d,ifPnd=Isa,…,Ind,(21)FPnd=0,ifPnd=∅;minIij|Iij∈Pnd,ifPnd≠∅.


#### 3.3.3. Neuron State

The neuron state part is used to record whether the current neuron has received a pulse and consists ofMi. It is explained as follows:(22)Mi=g5B=Mi+1,ifBx=−1;Mi,otherwise.where x∈VRi. The value of Mi is initialized as 0.


#### 3.3.4. Pulse Generator

The pulse generator part is used to calculate the parameter for sending pulses. This part consists ofIix, x=e,…,h. Iix is shown as follows:(23)Iix=g6F,C,B=cixz−fixt,iffixt<cixz,Bx=−1;fzit,iffzit>0,Bz=−1,0,otherwise.


#### 3.3.5. Pulse Sender

The pulse sender part is used to generate pulses and consists ofPix, x=e,…,h. Pix is explained as follows:(24)Pix=g7Pni,Iix=Uix,if the output has sent pulse;∅,if the output does not send pulse,where(25)Uix=Iix,ifi=s;Isa,…,Ini,Iix,ifi≠s.


#### 3.3.6. Output

The output part is used to send pulses to its relational neurons.


### 3.4. An Example

The detailed steps of TFNN for solving the TWMFPs are illustrated by an example. The topology and description of a time-varying wastage network are described as shown in Figure3 and Table 2. The time limitation is T0=3.Figure 3
An example of TFNN.Table 2
Description of a time-varying wastage network.
NodeArcTime windowCapacityWastagess⟶i0,11001,350ii⟶j0,3100i⟶d0,3100.5jj⟶d0,3100The proposed TFNN can solve this problem by the following steps:First, find two subnet sets (viz. with wastage arcsGw and without Go).Go=Path1,t=0, where Vo=s,i,j,d,Wo=0,0,0,Co=10,10,10.Gw=Path2,t=0,and1, where Vw=s,i,d,Ww=0,0.5,Cw=10,10 at t=0,Cw=5,10 at t=1.Second, calculate the maximum flow of the subnet.The flow ofGo is equal to f1=10−10∗0=10. Then, the capacity of arc s,i with depart time t=0 is adjusted to 0. The flow of Path2 with depart time t=0 is equal to 0. Therefore, the flow of Gw is equal to f2=5−5∗0.5=2.5.To sum up, the maximum flow isf∗=f1+f2=12.5.


### 3.5. Time Complexity

Theorem 1.
[Time Complexity of TFNN]. Given a TWNG, n represents the nodes number in G, m denotes the arcs number in G, T0 represents the time limitation, Δt means a unit time. Then, TFNN solves the time-varying wastage maximum flow problem in o43mn2intT0/Δt2 time, where int denotes the top of the integral function.Proof.
The overall PPNN consists of two parts. The time complexity of the first part (viz. Steps 1–5) depends on the PPNN algorithm and the second part (viz. Steps 6–8) depends on the SFNN algorithm.
For the PPNN algorithm, there is one loop and the worst time complexity is equal too5+T0/Δt3+12n+2=o5T0/Δt12n+5. Based on the time complexity of PPNN, the time complexity of the first part of TFNN is equal to o4+T0/Δt5+T0/Δt12n+5+1.
For the SFNN algorithm, there is one loop and the worst time complexity is equal too7+T0/Δt3+9n+2+m+2=o7+T0/Δt9n+m+7. According to the number of subnetworks is less then n, the time complexity of the second part of TFNN is equal to o2n7+T0/Δt9n+m+7.
To sum up, the time complexity of TFNN is equal too4+T0/Δt5+T0/Δt12n+5+1+2n7+T0/Δt9n+m+7=o4+14n+18n2+2mn+14nT0/Δt+12n+5T0/Δt2. Because there are at least two nodes (viz. n≥2) and one arc (viz. m≥1) in a network, we have. o4+14n+18n2+2mn+14nT0/Δt+12n+5T0/Δt2≤o18n2+40n+2mn+9T0/Δt2≤o43mn2T0/Δt2.
According toΔt≥1, the time complexity of TFNN can be simplified as follows: o43mn2T0/Δt2<=okmn2T02, here k denotes a constant.
Theorem1 is proven.


## 3.1. Description of TFNN

The underlying idea of using TFNN to solve TWMFP is that a neuron sends “preflows” (viz. pulses) to its successor neurons when the current neuron received pulses. With this new viewpoint, the proposed TFNN can reach a better solution of TWMFPs. There are two main parts in the design of TFNN, the first part is to find two subnet sets (viz. with wastage arcs and without) by path-pulse neural networks (PPNN), while the second part is to calculate the maximum flow of the subnets based on subnet-flow neural networks (SFNNs). The detailed steps of TFNN are shown in Algorithm 1.Algorithm 1: Time-flow Neural Network (TFNN).
Input: Δt, T0,G.Output: f∗./∗ The maximum flow. ∗/(1)
Sett=0, f∗=0, Go=∅, Gw=∅.(2)
Do(3)
Generate subnet setsGo and Gw from G by PPNN.(4)
Sett=t+Δt.(5)
Untilt>T0./∗ End step2 ∗/(6)
Updatef∗ of all subnets in Go by SFNN.(7)
Updatef∗ of all subnets in Gw by SFNN.(8)
Report the maximum flowf∗.


## 3.2. Description of PPNN

PPNN is used to generate two subnet sets (viz. with and without wastage arcs) through the following parts: first, initialize neurons by Step 1. Second, generate pulses from the departure neurons at every time by Step 3. Third, update all nodes but s at every time by Step 4. Fourth, update subnet sets at every time by Steps 5–10. Finally, output subnet sets. The detailed steps of PPNN are shown in Algorithm 2.Algorithm 2: Path-pulse Neural Networks (PPNN).
Input: Δt,G,t,Go,Gw.Output: Go,Gw./∗ Subnet sets of G. ∗/(1)
Sett1=0,Pnit=∅,Ti=TWi,y=0,wixt=−1(2)
Do(3)
Updatewsxt1,t2, and Psxt2 of s using (13)–(16).(4)
Update all nodesi∈V/s using (8)–(16).(5)
IfOPndt1=0(6)
SetGo=Go∪RPnd.(7)
End If./∗ End step5 ∗/(8)
IfOPndt1>0(9)
SetGw=Gw∪RPnd.(10)
End If./∗ End step8 ∗/(11)
Sett1=t1+Δt(12)
Untilt1>t./∗ End step2 ∗/(13)
Report two subnet setsGo and Gw.All neurons in the PPNN will no longer generate pulses when the time limitation is reached. A general structure of a neuron in PPNN is shown in Figure1.Figure 1
A general structure of PPNN.


### 3.2.1. Input

The input part is used to receive pulses from its predecessor neurons.


### 3.2.2. Pulse Receiver

The pulse receiver part is used to filter the received pulses and consists ofPnit1, y and time window Ti. Time window Ti is initialized by Algorithm 2 (PPNN). Pnit1 is explained as follows:(8)Pnit1=Uni,if the input has received pulse,∅,if the input does not received pulse,where(9)Uni=wsit,ifn=s,wsat0,…,wnit,ifn≠s.y is explained as follows:(10)y=g1Pnit1=1,ifPnit1≠∅,0,ifPnit1=∅.where Pnit1≠∅ means at least one pulse has reached at t1.If the current neuron is the destination neurond, the neuron no longer generates pulses and output the path RPndt1 and the wastage OPndt1. Their expressions are shown as follows:(11)RPndt1=<∅>,ifPndt1=∅;<s,t,…,d,t1>,ifPndt1=wsit,…,wndt1,(12)OPndt1=−1,ifPnit1=∅,∑wijt∈Pndt1wijt,ifPnit1≠∅.


### 3.2.3. Neuron State

The neuron state part is used to select the time window and consists ofwixt1, x=f,…,h. wixt1 is explained in the following equation:(13)wixt1=g2Wi=wix,ift1∈Tixz,−1,ift1∉Tixz.


### 3.2.4. Pulse Sender

The pulse sender part is used to calculate the parameter and generates pulses and consists oft2 and Pixt2, x=f,…,h. The expression of them are shown as follows:(14)t2=t1+Δt,(15)Pixt2=g3Pnit1,wixt1,t2=Uix,if the output has sent pulse;∅,if the output does not send pulse,where(16)Uix=wsx,ifi=s,t1∈Tixz;wsat0,…,wnit,wixt1,ifi≠s,t1∈Tixz.


### 3.2.5. Output

The output part is used to send the pulse to its successor neurons.


## 3.2.1. Input

The input part is used to receive pulses from its predecessor neurons.


## 3.2.2. Pulse Receiver

The pulse receiver part is used to filter the received pulses and consists ofPnit1, y and time window Ti. Time window Ti is initialized by Algorithm 2 (PPNN). Pnit1 is explained as follows:(8)Pnit1=Uni,if the input has received pulse,∅,if the input does not received pulse,where(9)Uni=wsit,ifn=s,wsat0,…,wnit,ifn≠s.y is explained as follows:(10)y=g1Pnit1=1,ifPnit1≠∅,0,ifPnit1=∅.where Pnit1≠∅ means at least one pulse has reached at t1.If the current neuron is the destination neurond, the neuron no longer generates pulses and output the path RPndt1 and the wastage OPndt1. Their expressions are shown as follows:(11)RPndt1=<∅>,ifPndt1=∅;<s,t,…,d,t1>,ifPndt1=wsit,…,wndt1,(12)OPndt1=−1,ifPnit1=∅,∑wijt∈Pndt1wijt,ifPnit1≠∅.


## 3.2.3. Neuron State

The neuron state part is used to select the time window and consists ofwixt1, x=f,…,h. wixt1 is explained in the following equation:(13)wixt1=g2Wi=wix,ift1∈Tixz,−1,ift1∉Tixz.


## 3.2.4. Pulse Sender

The pulse sender part is used to calculate the parameter and generates pulses and consists oft2 and Pixt2, x=f,…,h. The expression of them are shown as follows:(14)t2=t1+Δt,(15)Pixt2=g3Pnit1,wixt1,t2=Uix,if the output has sent pulse;∅,if the output does not send pulse,where(16)Uix=wsx,ifi=s,t1∈Tixz;wsat0,…,wnit,wixt1,ifi≠s,t1∈Tixz.


## 3.2.5. Output

The output part is used to send the pulse to its successor neurons.


## 3.3. Description of SFNN

SFNN is used to find the maximum flow of subnets through the following parts: first, initialize neurons by Step 1. Second, update all nodes,fp,cij,fijt,Bi, and f∗ by Steps 2–7. Third, update D by Steps 8–10. Final, output the maximum flow. The detailed steps of SFNN are shown in Algorithm 3.Algorithm 3: Subnet-flow Neural Networks (SFNNs).
Input: f∗,G′.Output: f∗.(1)
Setj=0,Mi=0,Bi=−1,Pni=∅,Ini=0,fnit=0,F=fnit/vn,vi∈A, Bs=s,C=C′.(2)
Do(3)
SetD=0,p=∅,fp=0.(4)
Update all nodes using (17)–(25).(5)
Setp=QPnd,wp=∑i,j∈pwij,fp=FPnd∗1−wp(6)
Setcij=cij−fp,fijt=fp,Bi=−1 where i,j∈p.(7)
Setf∗=f∗+fp.(8)
IfMi of all nodes are not equal to 0.(9)
SetD=1.(10)
End If./∗ End step8 ∗/(11)
UntilD==1./∗ End step2 ∗/(12)
Reportf∗.Each neuron in SFNN will reserve the first pulse received in an iteration. A general structure of a neuron in subnet-flow neural networks is shown in Figure2.Figure 2
A general structure of SFNN.


### 3.3.1. Input

The input part is used to receive pulses coming from its relational neurons.


### 3.3.2. Pulse Receiver

The pulse receiver part is used to filter the received pulses and consists ofPni, j, B, F, and C. The value of B, F, and C are calculated by the SFNN Algorithm. Pni is shown as follows:(17)Pni=Uni,if the input has received pulse;∅,if the input does not received pulse,where(18)Uni=Isi,ifn=s;Isa,…,Ini,ifn≠s.j is explained as follows:(19)j=g4Pni=1,ifPni≠∅;0,otherwise.The value ofPni not equals ∅ means at least one pulse has reached at current neuron i at t.If current neuroni is the destination neuron d, the neuron no longer generates pulses and output the path QPnd and the path flow FPnd. Their expressions are shown as follows:(20)QPnd=<∅>,ifPnd=∅;s,…,d,ifPnd=Isa,…,Ind,(21)FPnd=0,ifPnd=∅;minIij|Iij∈Pnd,ifPnd≠∅.


### 3.3.3. Neuron State

The neuron state part is used to record whether the current neuron has received a pulse and consists ofMi. It is explained as follows:(22)Mi=g5B=Mi+1,ifBx=−1;Mi,otherwise.where x∈VRi. The value of Mi is initialized as 0.


### 3.3.4. Pulse Generator

The pulse generator part is used to calculate the parameter for sending pulses. This part consists ofIix, x=e,…,h. Iix is shown as follows:(23)Iix=g6F,C,B=cixz−fixt,iffixt<cixz,Bx=−1;fzit,iffzit>0,Bz=−1,0,otherwise.


### 3.3.5. Pulse Sender

The pulse sender part is used to generate pulses and consists ofPix, x=e,…,h. Pix is explained as follows:(24)Pix=g7Pni,Iix=Uix,if the output has sent pulse;∅,if the output does not send pulse,where(25)Uix=Iix,ifi=s;Isa,…,Ini,Iix,ifi≠s.


### 3.3.6. Output

The output part is used to send pulses to its relational neurons.


## 3.3.1. Input

The input part is used to receive pulses coming from its relational neurons.


## 3.3.2. Pulse Receiver

The pulse receiver part is used to filter the received pulses and consists ofPni, j, B, F, and C. The value of B, F, and C are calculated by the SFNN Algorithm. Pni is shown as follows:(17)Pni=Uni,if the input has received pulse;∅,if the input does not received pulse,where(18)Uni=Isi,ifn=s;Isa,…,Ini,ifn≠s.j is explained as follows:(19)j=g4Pni=1,ifPni≠∅;0,otherwise.The value ofPni not equals ∅ means at least one pulse has reached at current neuron i at t.If current neuroni is the destination neuron d, the neuron no longer generates pulses and output the path QPnd and the path flow FPnd. Their expressions are shown as follows:(20)QPnd=<∅>,ifPnd=∅;s,…,d,ifPnd=Isa,…,Ind,(21)FPnd=0,ifPnd=∅;minIij|Iij∈Pnd,ifPnd≠∅.


## 3.3.3. Neuron State

The neuron state part is used to record whether the current neuron has received a pulse and consists ofMi. It is explained as follows:(22)Mi=g5B=Mi+1,ifBx=−1;Mi,otherwise.where x∈VRi. The value of Mi is initialized as 0.


## 3.3.4. Pulse Generator

The pulse generator part is used to calculate the parameter for sending pulses. This part consists ofIix, x=e,…,h. Iix is shown as follows:(23)Iix=g6F,C,B=cixz−fixt,iffixt<cixz,Bx=−1;fzit,iffzit>0,Bz=−1,0,otherwise.


## 3.3.5. Pulse Sender

The pulse sender part is used to generate pulses and consists ofPix, x=e,…,h. Pix is explained as follows:(24)Pix=g7Pni,Iix=Uix,if the output has sent pulse;∅,if the output does not send pulse,where(25)Uix=Iix,ifi=s;Isa,…,Ini,Iix,ifi≠s.


## 3.3.6. Output

The output part is used to send pulses to its relational neurons.


## 3.4. An Example

The detailed steps of TFNN for solving the TWMFPs are illustrated by an example. The topology and description of a time-varying wastage network are described as shown in Figure3 and Table 2. The time limitation is T0=3.Figure 3
An example of TFNN.Table 2
Description of a time-varying wastage network.
NodeArcTime windowCapacityWastagess⟶i0,11001,350ii⟶j0,3100i⟶d0,3100.5jj⟶d0,3100The proposed TFNN can solve this problem by the following steps:First, find two subnet sets (viz. with wastage arcsGw and without Go).Go=Path1,t=0, where Vo=s,i,j,d,Wo=0,0,0,Co=10,10,10.Gw=Path2,t=0,and1, where Vw=s,i,d,Ww=0,0.5,Cw=10,10 at t=0,Cw=5,10 at t=1.Second, calculate the maximum flow of the subnet.The flow ofGo is equal to f1=10−10∗0=10. Then, the capacity of arc s,i with depart time t=0 is adjusted to 0. The flow of Path2 with depart time t=0 is equal to 0. Therefore, the flow of Gw is equal to f2=5−5∗0.5=2.5.To sum up, the maximum flow isf∗=f1+f2=12.5.


## 3.5. Time Complexity

Theorem 1.
[Time Complexity of TFNN]. Given a TWNG, n represents the nodes number in G, m denotes the arcs number in G, T0 represents the time limitation, Δt means a unit time. Then, TFNN solves the time-varying wastage maximum flow problem in o43mn2intT0/Δt2 time, where int denotes the top of the integral function.Proof.
The overall PPNN consists of two parts. The time complexity of the first part (viz. Steps 1–5) depends on the PPNN algorithm and the second part (viz. Steps 6–8) depends on the SFNN algorithm.
For the PPNN algorithm, there is one loop and the worst time complexity is equal too5+T0/Δt3+12n+2=o5T0/Δt12n+5. Based on the time complexity of PPNN, the time complexity of the first part of TFNN is equal to o4+T0/Δt5+T0/Δt12n+5+1.
For the SFNN algorithm, there is one loop and the worst time complexity is equal too7+T0/Δt3+9n+2+m+2=o7+T0/Δt9n+m+7. According to the number of subnetworks is less then n, the time complexity of the second part of TFNN is equal to o2n7+T0/Δt9n+m+7.
To sum up, the time complexity of TFNN is equal too4+T0/Δt5+T0/Δt12n+5+1+2n7+T0/Δt9n+m+7=o4+14n+18n2+2mn+14nT0/Δt+12n+5T0/Δt2. Because there are at least two nodes (viz. n≥2) and one arc (viz. m≥1) in a network, we have. o4+14n+18n2+2mn+14nT0/Δt+12n+5T0/Δt2≤o18n2+40n+2mn+9T0/Δt2≤o43mn2T0/Δt2.
According toΔt≥1, the time complexity of TFNN can be simplified as follows: o43mn2T0/Δt2<=okmn2T02, here k denotes a constant.
Theorem1 is proven.


## 4. Experiments

A large transportation network (viz. New York Road) is used to test the performance of the proposed TFNN algorithm. Time-varying and wastage components are added to some arcs in the network. The Ford–Fulkerson (FF) [26], genetic algorithm (GA) [22], Edmonds–Karp (EK) [10], and the Cai–Sha (CS) algorithm [11] will be used for experimental comparison with the proposed TFNN. There are 100 generations and 50 populations preset in the genetic algorithm [27].The error rate and computational time of these algorithms are compared as follows: the percentage deviation of the mean value (PDM) and the percentage deviation of the best value (PDB) are used as performance indexes (PI) to illustrate the error rate (ER) of different algorithms. PDM and PDB, respectively, are the mean and best value of ER for a set of networks. ER can be calculated asER=Fm−Fa/Fm∗100%, where Fm is the maximum flow among these algorithms and Fa is the flow value of each algorithm.We used 1000-node, 3000-node, and 5000-node networks for experiments and analyzed the error rate and computational time of the results. Table 3 reports the experimental results of TFNN, FF, GA, EK, and CS algorithms. Compared with other algorithms, the proposed TFNN always can find the best solutions in all cases. The error rate of other algorithms increases with the increase of nodes number. The PDM of other algorithms on Data3 all exceed 17.48% and the PDM of FF and EK are 27.45% and 31.61%, while TFNN is 0.00%. This is because both of FF and EK fail to take into time-varying components. GA adopts a random search mechanism. CS algorithm always finds the shortest path first, it reduces the solution accuracy. These results show that the proposed TFNN has better performance than existing algorithms (including FF, GA, EK, and CS). The tendency of the error rate of FF, GA, EK, CS, and the proposed TFNN algorithms are shown in Figure 4(a).Table 3
Comparative results of the TFNN and other algorithms.
DatasetNodesArcsPIFFGAEKCSTFNNData110002067PDM (%)9.9117.1598.4915.0670.00PDB (%)7.2615.5907.0133.9600.00Time (ms)49.13177652.0357.4160.25Data230006106PDM (%)16.4013.2617.5210.050.00PDB (%)13.5110.9413.198.1080.00Time (ms)304.853574317.49436.53240.93Data3500010095PDM (%)27.4525.8831.6117.480.00PDB (%)23.0823.5728.1915.380.00Time (ms)955.646346915.961213.96582.21Figure 4
Experimental results of FF, GA, EK, CS, and TFNN with different datasets. (a) PDM. (b) Computational time.
(a)(b)The calculation times of TFNN, FF, GA, EK, and CS algorithms are shown in Table3. The computational time of the proposed TFNN is relatively short than other algorithms. First, GA requires more time to find a solution due to its pure random search mechanism. Second, as the number of nodes increases, the calculation time of TFNN is gradually better than the other three algorithms. The reason is that the complexity of the CS algorithm largely depends on the number of nodes, while the FF and EK algorithm will take more time to iterate as the number of nodes increases. The tendency of computational time of FF, GA, EK, CS, and the proposed TFNN algorithms are described in Figure 4(b).


## 5. Conclusions

In this research, we introduce the time-varying wastage maximum flow problem and propose the Time-flow Neural Network to solve the TWMFPs. The proposed TFNN does not require any training by means of a time-flow mechanism. Experimental results show that the proposed TFNN has better performance than traditional algorithms (including FF, EK, and CS) and intelligent algorithm (such as GA). The main advantages of TFNN are shown as follows.First, compared with existing maximum flow algorithms, TFNN has higher accuracy when solving the TWMFPs. The proposed TFNN can obtain a larger flow due to its group calculation idea. The experiment results show that the error rate of TFNN is lower (17.48% lower than CS and 31.61% lower than EK) on a large network (5000 nodes and 10095 arcs).Second, TFNN has a higher calculation speed based on its parallel computing feature. The experiment results show that the computational time of TFNN is 52% shorter than CS on a large network (5000 nodes and 10095 arcs).In future research, more constraints can be considered when solving the time-varying wastage maximum flow problems. And, the neural network framework should be improved for the maximum flow problems under uncertain environments.



---

*Source: 3782761-2022-09-30.xml*