Maximizing reliability of the capacity vector for multi-source multi-sink stochastic-flow networks subject to an assignment budget

M. R. Hassan

doi:10.3934/jimo.2020020

Article Contents

2021, Volume 17, Issue 3: 1253-1267. Doi: 10.3934/jimo.2020020

This issue Previous Article Side-information-induced reweighted sparse subspace clustering Next Article A goethite process modeling method by Asynchronous Fuzzy Cognitive Network based on an improved constrained chicken swarm optimization algorithm

Maximizing reliability of the capacity vector for multi-source multi-sink stochastic-flow networks subject to an assignment budget

M. R. Hassan^,

Computer Science Branch, Mathematics Department, Faculty of Science, Aswan University, Aswan, Egypt

^* Corresponding author: M. R. Hassan
^* Corresponding author: M. R. Hassan

Received: May 2019

Revised: August 2019

Early access: January 2020

Published: May 2021

Abstract / Introduction Full Text(HTML) Figure(10) / Table(3) Related Papers Cited by

Abstract

Many real-world networks such as freight, power and long distance transportation networks are represented as multi-source multi-sink stochastic flow network. The objective is to transmit flow successfully between the source and the sink nodes. The reliability of the capacity vector of the assigned components is used an indicator to find the best flow strategy on the network. The Components Assignment Problem (CAP) deals with searching the optimal components to a given network subject to one or more constraints. The CAP in multi-source multi-sink stochastic flow networks with multiple commodities has not yet been discussed, so our paper investigates this scenario to maximize the reliability of the capacity vector subject to an assignment budget. The mathematical formulation of the problem is defined, and a proposed solution based on genetic algorithms is developed consisting of two steps. The first searches the set of components with the minimum cost and the second searches the flow vector of this set of components with maximum reliability. We apply the solution approach to three commonly used examples from the literature with two sets of available components to demonstrate its strong performance.

Keywords:

Multi-source multi-sink stochastic-flow networks,
components assignment problem,
reliability of the Capacity Vector.

Mathematics Subject Classification: Primary: 90B25; Secondary: 90B15.

Citation:

Full Text(HTML)

Figure 1. Modified uniform crossover

Download: Full-size image PowerPoint slide

Figure 2. Mutation operation

Download: Full-size image PowerPoint slide

Figure 3. Crossover operation

Download: Full-size image PowerPoint slide

Figure 4. Mutation operation

Download: Full-size image PowerPoint slide

Figure 5. Network with three source and two sink nodes

Download: Full-size image PowerPoint slide

Figure 6. The minimum cost found at each generation

Download: Full-size image PowerPoint slide

Figure 7. Two-source two-sink computer network

Download: Full-size image PowerPoint slide

Figure 8. The minimum cost found at each generation

Download: Full-size image PowerPoint slide

Figure 9. Network with two source and three sink nodes

Download: Full-size image PowerPoint slide

Figure 10. The minimum cost found at each generation

Download: Full-size image PowerPoint slide

Table 1. Component information for the network in Figure 5

p	Capacity					*Cost*
	0	1	2	3	4
1	0.02	0.04	0.14	0.80	0.00	1
2	0.04	0.06	0.10	0.15	0.65	3
3	0.02	0.03	0.05	0.90	0.00	4
4	0.05	0.08	0.87	0.00	0.00	2
5	0.01	0.04	0.10	0.85	0.00	3
6	0.02	0.05	0.15	0.78	0.00	2
7	0.05	0.10	0.85	0.00	0.00	1
8	0.04	0.06	0.15	0.75	0.00	4
9	0.03	0.05	0.12	0.80	0.00	1
10	0.01	0.04	0.05	0.15	0.75	3
11	0.03	0.05	0.07	0.85	0.00	1
12	0.01	0.02	0.07	0.90	0.00	1

| Show Table

DownLoad: CSV

Table 2. The initial population for the network example in Figure 5

No.	The components$ \boldsymbol{(}\mathcal{B} $)	The Flow vector (F)	$ {\boldsymbol{Z}}_{\boldsymbol{obj}}\left(\mathcal{B}\right) $	$ \boldsymbol{R}\boldsymbol{(}{\boldsymbol{X}}_{\boldsymbol{F}}\boldsymbol{(}\mathcal{B}\boldsymbol{)} $
1	2 10 3 12 7 1 8 11 6 9	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	21.0067	0.259087
2	1 7 4 11 6 8 9 10 2 3	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	22.0005	0.288896
3	6 12 8 11 1 10 9 3 2 4	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	22.0164	0.236032
4	12 6 9 7 11 1 3 8 10 2	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	21.0002	0.293038
5	8 5 4 9 7 1 12 6 10 2	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	21.0036	0.269935
6	10 7 12 9 1 5 6 3 2 4	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	21.0002	0.292652
7	1 9 6 10 5 3 11 4 2 12	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	21.0000	0.312330
8	2 1 9 8 12 4 3 6 10 11	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	22.0012	0.282898
9	9 3 12 5 4 1 6 10 2 7	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	21.0002	0.293636
10	2 8 4 1 7 5 11 9 10 3	1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1	23.0000	0.314006

| Show Table

DownLoad: CSV

Table 3. The component information for the network of Figure 7.

p	Capacity
p	0	1	2	3	4	5	6	7	8	9
1	0.001	0.001	0.003	0.004	0.005	0.005	0.006	0.007	0.010	0.015
2	0.001	0.003	0.003	0.004	0.005	0.007	0.007	0.008	0.009	0.010
3	0.002	0.002	0.003	0.006	0.007	0.007	0.010	0.012	0.015	0.017
4	0.001	0.001	0.002	0.003	0.005	0.008	0.010	0.011	0.012	0.015
5	0.001	0.002	0.009	0.012	0.020	0.040	0.050	0.060	0.806	0.000
6	0.001	0.002	0.002	0.005	0.010	0.012	0.015	0.017	0.020	0.025
7	0.001	0.001	0.002	0.005	0.008	0.010	0.012	0.015	0.015	0.017
8	0.001	0.002	0.005	0.005	0.007	0.008	0.010	0.012	0.015	0.015
9	0.001	0.001	0.002	0.002	0.003	0.004	0.005	0.008	0.009	0.010
10	0.002	0.003	0.005	0.006	0.007	0.009	0.012	0.015	0.941	0.000
11	0.002	0.002	0.003	0.005	0.007	0.008	0.010	0.011	0.020	0.030
12	0.001	0.002	0.003	0.005	0.008	0.009	0.010	0.012	0.015	0.040
13	0.001	0.001	0.003	0.005	0.005	0.010	0.011	0.017	0.018	0.020
14	0.001	0.001	0.002	0.002	0.003	0.005	0.007	0.009	0.016	0.021
15	0.001	0.001	0.002	0.003	0.004	0.005	0.007	0.008	0.009	0.011
16	0.001	0.002	0.002	0.004	0.005	0.006	0.007	0.009	0.014	0.017
17	0.001	0.001	0.002	0.002	0.003	0.004	0.005	0.007	0.009	0.011
18	0.001	0.001	0.002	0.002	0.002	0.003	0.003	0.004	0.005	0.007
19	0.001	0.001	0.002	0.003	0.005	0.008	0.009	0.011	0.013	0.014
20	0.002	0.002	0.003	0.006	0.007	0.007	0.010	0.013	0.015	0.020
10	11	12	13	14	15	16	17	18	19	20
0.060	0.150	0.733	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.943	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.919	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.015	0.016	0.020	0.856	0.025	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.891	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.020	0.022	0.025	0.030	0.817	0.000	0.000	0.000	0.000	0.000	0.000
0.016	0.020	0.884	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.011	0.015	0.016	0.017	0.019	0.020	0.857	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.902	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.895	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.025	0.031	0.853	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.024	0.025	0.030	0.035	0.040	0.060	0.719	0.000	0.000	0.000	0.000
0.015	0.017	0.020	0.027	0.870	0.000	0.000	0.000	0.000	0.000	0.000
0.020	0.022	0.025	0.030	0.035	0.040	0.761	0.000	0.000	0.000	0.000
0.015	0.017	0.018	0.019	0.020	0.022	0.844	0.017	0.017	0.000	0.000
0.008	0.009	0.011	0.013	0.014	0.014	0.015	0.000	0.000	0.019	0.020
0.015	0.017	0.020	0.030	0.851	0.000	0.000	0.000	0.000	0.000	0.000
0.915	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
21	22	23	24	25	26	27	28	29	30	31
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.019	0.020	0.023	0.025	0.026	0.740	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	A. Aissou, A. Daamouche and M. R. Hassan, Optimal components assignment problem for stochastic-flow networks, Journal of Computer Science, 15 (2019), 108-117.
[2]	S. G. Chen, An optimal capacity assignment for the robust design problem in capacitated flow networks, Applied Mathematical Modelling, 36 (2012), 5272-5282. doi: 10.1016/j.apm.2011.12.034.
[3]	S. G. Chen, Optimal double-resource assignment for the robust design problem in multistate computer networks, Applied Mathematical Modelling, 38 (2014), 263-277. doi: 10.1016/j.apm.2013.06.020.
[4]	D. W. Coit and A. E. Smith, Penalty guided genetic search for reliability design optimization, Computers and Industrial Engineering, 30 (1996), 895-904.
[5]	B. Dengiz, F. Altiparmak and A. E. Smith, Local search genetic algorithm for optimal design of reliable networks, IEEE Transactions on Evolutionary Computation, 10 (1997), 179-188.
[6]	M. Gen and R. Cheng, Genetic Algorithms and Engineering Optimization, 1$^{st}$ edition, Wiley Series in Engineering, Design, and Automation, 2000.
[7]	M. R. Hassan and H. Abdou, Multi-objective components assignment problem subject to lead-time constraints, Indian Journal of Science and Technology, 11 (2018), 1-9.
[8]	M. R. Hassan, Solving a component assignment problem for a stochastic-flow network under lead-time constraint, Indian Journal of Science and Technology, 8 (2015), 1-5.
[9]	M. R. Hassan, Solving flow allocation problems and optimizing system reliability of multisource multisink stochastic flow network, The International Arab Journal of Information Technology (IAJIT), 13 (2016), 477-483.
[10]	C. C. Hsieh and Y. T. Chen, Reliable and economic resource allocation in an unreliable flow network, Computers and Operations Research, 32 (2005), 613-628.
[11]	C. C. Hsieh and Y. T. Chen, Simple algorithms for updating multi-resource allocations in an unreliable flow network, Computers and Industrial Engineering, 50 (2006), 120-129.
[12]	C. C. Hsieh and M. H. Lin, Reliability-oriented multi-resource allocation in a stochastic-flow network, Reliability Engineering and System Safety, 81 (2003), 155-161.
[13]	Y.-K. Lin and C. T. Yeh, A two-stage approach for a multi-objective component assignment problem for a stochastic-flow network, Engineering Optimization, 45 (2013), 265-285. doi: 10.1080/0305215X.2012.669381.
[14]	Y. K. Lin and C. T. Yeh, System reliability maximization for a computer network by finding the optimal two-class allocation subject to budget, Applied Soft Computing, 36 (2015), 578-588.
[15]	Y. K. Lin and C. T. Yeh, Determining the optimal double-component assignment for a stochastic computer network, Omega, 40 (2012), 120-130.
[16]	Y. K. Lin and C. T. Yeh, Evaluation of optimal network reliability under components-assignments subject to transmission budget, IEEE Transactions on Reliability, 59 (2010), 539-550.
[17]	Y. K. Lin and C. T. Yeh, Maximal network reliability with optimal transmission line assignment for stochastic electric power networks via genetic algorithms, Applied Soft Computing, 11 (2011), 2714-2724.
[18]	Y. K. Lin and C. T. Yeh, Multi-objective optimization for stochastic computer networks using NSGA-Ⅱ and TOPSIS, European Journal of Operational Research, 218 (2012), 735-746. doi: 10.1016/j.ejor.2011.11.028.
[19]	Y. K. Lin and C. T. Yeh, Multistate components assignment problem with optimal network reliability subject to assignment budget, Applied Mathematics and Computation, 217 (2011), 10074-10086. doi: 10.1016/j.amc.2011.05.001.
[20]	Y. K. Lin and C. T. Yeh, Optimal resource assignment to maximize multistate network reliability for a computer network, Computers and Operations Research, 37 (2010), 2229-2238. doi: 10.1016/j.cor.2010.03.013.
[21]	Y. K. Lin and C. T. Yeh, Computer network reliability optimization under double-source assignments subject to transmission budget, Information Sciences, 181 (2011), 582-599.
[22]	Y. K. Lin, C. T. Yeh and P. S. Huang, A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem, Applied Soft Computing, 13 (2013), 3529-3543.
[23]	Q. Liu, H. Z. Xiaoxian and Q. Zhao, Genetic algorithm-based study on flow allocation in a multicommodity stochastic-flow network with unreliable nodes, Eighth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 8 (2007), 576-581.
[24]	Q. Liu, Q. Z. Zhao and W. K. Zang, Study on multi-objective optimization of flow allocation in a multi-commodity stochastic-flow network with unreliable nodes, Journal of Applied Mathematics Computing (JAMC), 28 (2008), 185-198. doi: 10.1007/s12190-008-0093-9.
[25]	M. J. Zuo, Z. Tian and H. Z. Huang, An efficient method for reliability evaluation of multistate networks given all minimal path vectors, IIE Transactions, 39 (2007), 811-817.