由於現代生活之品質，十分仰賴網路所提供之服務，例如電力網路、電腦網路與物流網路等，因此網路可靠度(network reliability)顯得極為重要。在真實世界中，網路上的每條傳輸邊基於全部失效、部分失效或維修保養等因素，使得每條傳輸邊具有多種狀態，故這些網路應被視為隨機流量網路(stochastic-flow network)，因而網路可靠度被定義為該網路可以滿足需求端需求量之機率。從品管之角度來看，網路可靠度最佳化(network reliability optimization)為許多組織所追逐的目標，本論文即以隨機流量網路的可靠度最佳化為主軸，探討三種議題：1. 隨機電力網路之可靠度最佳化；2. 隨機電腦網路之可靠度最佳化；以及3. 隨機物流網路之可靠度最佳化。就此三個議題，分別建立最佳化問題之數學模式以及隨機流量網路模型，並以此為根據，分別發展以基因演算法(genetic algorithm)為基礎之最佳化演算法，其中每一演算法皆結合最小路徑(minimal paths)或最小割集(minimal cuts)特性之一與遞迴不交和法(Recursive Sum of Disjoint Products)。最後於每一議題中，藉由實例之應用以彰顯所提出之演算法相較於其他演算法有較佳之計算效率。冀望本論文之貢獻能使得網路可靠度最佳化之領域更趨完善，並且在實務上能作為業界執行最佳化決策之參考指標。

Our modern life relies on the service provided from the networks, such as electric power networks, computer networks, logistics networks, etc, and thus the reliability of network is very important. Many real-world networks should be regarded as stochastic-flow networks. That is, each arc has multiple states due to complete failure, partial failure, maintenance, etc. Therefore, network reliability is defined as the probability that the network can transmit a given unit of demand from a source node to a sink node. From the viewpoint of quality management, network reliability optimization is essential and pursued by numerous organizations. This dissertation focuses on three issues related to network reliability optimization for stochastic-flow networks: (i) network reliability optimization for stochastic electric power networks, (ii) network reliability optimization for stochastic computer networks, and (iii) network reliability optimization for stochastic logistics networks. In the three issues, the problem formulations and stochastic-flow network models are respectively constructed. Subsequently, three optimization algorithms, all of which integrate genetic algorithm, either minimal paths or minimal cuts, and Recursive Sum of Disjoint Products, are developed to solve the three problems, respectively. Furthermore, several experiments related to practical networks are displayed to demonstrate the proposed algorithms’ computational efficiency while comparing with several algorithms.

Amiri, A. and Pirkul, H., “Routing and capacity assignment in backbone communication networks”, Computers and Operations Research, Vol. 24, pp. 275–287 (1997).
Aven, T., “Reliability evaluation of multistate systems with multistate components”, IEEE Transactions on Reliability, Vol. 34, pp. 473–479 (1985).
Ball, M. O., “Computing network reliability”, Operations Research, Vol. 27, pp. 823–838 (1979).
Ball, M. O., Hagstrom, J., and Provan, J. S., “Threshold reliability of networks with small failure sets”, Networks, Vol. 25, pp. 101–115 (1995).
Bolduc, M. C., Renaud, J., and Boctor, F., “A heuristic for the routing and carrier selection problem”, European Journal of Operational Research, Vol. 183, pp. 926–932 (2007).
Cadini, F., Zio, E., and Petrescu, C. A., “Optimal expansion of an existing electrical power transmission network by multi–objective genetic algorithms”, Reliability Engineering and System Safety, Vol. 95, pp. 173–181 (2010).
Chen, D. J., Hol, W. C., Chen, R. S., and Chen, D. T. K. “A heuristic algorithm for the reliability–oriented file assignment in a distributed computing system”, Computers and Mathematics with Applications, Vol. 29, pp. 85–104 (1995).
Cheng, S. T. “Topological optimization of a reliable communication network”, IEEE Transactions on Reliability, Vol. 47, pp. 225–233 (1998).
Chu, P. C. and Beasley, J. E., “A genetic algorithm for the generalized assignment problem”, Computers and Operations Research, Vol. 24, pp. 17–23 (1997).
Coit, D. W. and Smith, A. E., “Penalty guided genetic search for reliability design optimization”, Computers and Industrial Engineering, Vol. 30, pp. 895–904 (1996).
Coit, D. W. and Smith, A. E., “Reliability optimization of series–parallel systems using genetic algorithm”, IEEE Transactions on Reliability, Vol. 45, pp. 254–266 (1996).
Colbourn, C. J., The Combinatorics of Network Reliability, Oxford University, New York (1987).
Crucitti, P., Latora, V., and Marchiori, M., “A topological analysis of the Italian electric power grid”, Physica A: Statistical Mechanics and its Applications, Vol. 338, pp. 92–97 (2004).
Doullize, P. and Jamoulle, E., “Transportation networks with random arc capacities”, RAIRO, Vol. 3, pp. 45–60 (1972).
Ford, L. R. and Fulkerson, D. R., Flows in networks, Princeton University, NJ (1962).
Goldberg, D., Genetic Algorithms in Search, Optimization and Machine Learning, Addison–Wesley, Massachusetts (1989).
Grefenstette, J. J., “Optimization of control parameters for genetic algorithms”, IEEE Transactions on Systems, Man and Cybernetics, Vol. 16, pp.122–128 (1986).
Guo, Y., Lim, A., Rodrigues, B., and Zhu, Y., “Carrier assignment models in transportation procurement”, Journal of the Operational Research Society, Vol. 57, pp. 1472–1481 (2006).
Harper, P. R., De Senna, V., Vieira, I. T., and Shahani, A. K., “A genetic algorithm for the project assignment problem”, Computers and Operations Research, Vol. 32, pp. 1255–1265 (2005).
Holland, J. H., Adaption in Natural and Artificial Systems, University of Michigan, Ann Arbor (1975).
Hsieh, C. C. and Chen, Y. T., “Reliable and economic resource allocation in an unreliable flow network”, Computer and Operations Research, Vol. 32, pp. 613–628 (2005a).
Hsieh, C. C. and Chen, Y. T., “Resource allocation decisions under various demands and cost requirements in an unreliable flow network”, Computer and Operations Research, Vol. 32, pp. 2771–2784 (2005b).
Hsieh, C. C. and Lin, M. H., “Reliability–oriented multi–resource allocation in a stochastic–flow network”, Reliability Engineering and System Safety, Vol. 81, pp. 155–161 (2003).
Hsieh, C. C. and Lin, M. H., “Simple algorithms for updating multi–resource allocations in an unreliable flow network”, Computers and Industrial Engineering, Vol. 50, pp. 120–129 (2006).
Hudson, J. C. and Kapur, K. C., “Reliability bounds for multistate systems with multistate components”, Operations Research, Vol. 33 pp. 153–160 (1985).
Jain, S. P. and Gopal, K., “A heuristic method of link reliability assignment for maximal reliability”, Microelectronics Reliability, Vol. 30, pp. 673–679 (1990).
Jane, C. C. and Laih, Y. W., “Algorithms to determine the threshold reliability of flow networks”, IIE Transactions, Vol. 36, pp. 469–479 (2004).
Jane, C. C. and Yuan, J., “A sum of disjoint products algorithm for reliability evaluation of flow networks”, European Journal of Operational Research, Vol. 131, pp. 664–675 (2001).
Kiu, S. W. and McAllister, D. F., “Reliability optimization of computer–communication networks”, IEEE Transactions on Reliability, Vol. 37, pp. 475–483 (1988).
Kumar, A., Pathak, R. M., and Gupta, Y. P., “Genetic–algorithm–based reliability optimization for computer network expansion”, IEEE Transactions on Reliability, Vol. 41, pp. 63–72 (1995a).
Kumar, A., Pathak, R. M., Gupta, Y. P., and Parsaei, H. R., “A genetic algorithm for distributed system topology design”, Computers and Industrial Engineering, Vol. 28, pp. 659–670 (1995b).
Kuo, S., Lu, S., and Yeh, F., “Determining terminal pair reliability based on edge expansion diagrams using OBDD”, IEEE Transactions on Reliability, Vol. 48, pp. 234–246 (1999).
Lisnianski, A. and Levitin, G., Multi–state system reliability: assessment, optimization and application, Vol. 6, World Scientific, Singapore (2003).
Levitin, G., “Reliability evaluation for acyclic consecutively connected networks with multistate elements”, Reliability Engineering and System Safety, Vol. 73, pp. 137–143 (2001).
Levitin, G., “Optimal reliability enhancement for multi–state transmission networks with fixed transmission time”, Reliability Engineering and System Safety, Vol. 76, pp. 287–299 (2002).
Levitin, G. and Lisnianski, A., “A new approach to solving problems of multi–state system reliability optimization”, Quality Reliability Engineering International, Vol. 17, pp. 93–104 (2001).
Li, Y., Yang, Y., Zhou, L., and Zhu, R., “Observations on using problem–specific genetic algorithm for multiprocessor real–time task scheduling”, International Journal of Innovative Computing, Information and Control, Vol. 5, pp. 2531–2540 (2009).
Liao, Z. and Rittscher, J., “Integration of supplier selection, procurement lot sizing and carrier selection under dynamic demand conditions”, International Journal of Production Economics, Vol. 107, pp. 502–510 (2007).
Lin, Y. K., “A simple algorithm for reliability evaluation of a stochastic–flow network with node failure”, Computer and Operations Research, Vol. 28, pp. 1277–1285 (2001a).
Lin, Y. K., “Study on the multicommodity reliability of a capacitated–flow network”, Computers and Mathematics with Applications, Vol. 42, pp. 255–264 (2001b).
Lin, Y. K., “Using minimal cuts to evaluate the system reliability of a stochastic–flow network with failures at nodes and arcs”, Reliability Engineering and System Safety, Vol. 75, pp. 41–46 (2002).
Lin, Y. K., “Reliability of a stochastic–flow network with unreliable branches & nodes under budget constraints”, IEEE Transactions on Reliability, Vol. 53, pp. 381–387 (2004).
Lin, Y. K., “Reliability evaluation for an information network with node failure under cost constraint”, IEEE Transactions on Systems, Man and Cybernetics – Part A: Systems and Humans, Vol. 37, pp. 180–188 (2007a).
Lin, Y. K., “On a multicommodity stochastic–flow network with unreliable nodes subject to budget constraint”, European Journal of Operational Research, Vol. 176, pp. 347–360 (2007b).
Lin, F. T. and Tsai, T. R., “A two–stage genetic algorithm for solving the transportation problem with fuzzy demands and fuzzy supplies”, International Journal of Innovative Computing, Information and Control, Vol. 5, pp. 4775–4785 (2009).
Liu, Q., Zhang, H., Ma, X., and Zhao, Q., “Genetic algorithm–based study on flow allocation in a multicommodity stochastic–flow network with unreliable nodes”, Proceedings of The 8th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, Tsinan, pp. 576–581 (2007).
Liu, Q., Zhao, Q., and Zang, W., “Study on multi–objective optimization of flow allocation in a multi–commodity stochastic–flow network with unreliable nodes”, Journal of Applied Mathematics and Computing, Vol. 28, pp. 185–198 (2008).
Man, K. F., Tang, K. S., and Kwong, S., “Genetic algorithms: concepts and applications”, IEEE Transactions on Industrial Electronics, Vol. 43, pp. 519–534 (1996).
Min, H., “A personal–computer assisted decision support system for private versus common carrier selection”, Transportation Research Part E: Logistics and Transportation Review, Vol. 34, pp. 229–241 (1998).
Mitchell, M., An Introduction to Genetic Algorithms, MIT, Massachusetts (1996).
Mohammaditbar, D. and Teimoury, E., “Integrated freight transportation carrier selection and network flow assignment: methodology and case study”, Journal of Applied Sciences, Vol. 8, pp. 2928–2938 (2008).
Murphy, P., Daley, J., and Hall, P., “Carrier selection: do shippers and carriers agree, or not?”, Transportation Research Part E: Logistics and Transportation Review, Vol. 33, pp. 61–72 (1997).
Painton, L. and Campbell, J., “Genetic algorithms in optimization of system reliability”, IEEE Transactions on Reliability, Vol. 44, pp. 172–178 (1995).
Pierre, S. and Legault, G., “A genetic algorithm for designing distributed computer network topologies”, IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics, Vol. 28, pp. 249–258 (1998).
Provan, J. S. and Ball, M. O., “Computing network reliability in time polynomial in the number of cuts”, Operations Research, Vol. 32, pp. 516–526 (1984).
Ramírez–Rosado, T. J. and Bernal–Agustín, J. L., “Reliability and costs optimization for distribution networks expansion using an evolutionary algorithm”, IEEE Transactions on Power systems, Vol. 16 pp. 111–118 (2001).
Ramirez–Marquez, J. E. and Rocco S., C. M., “Stochastic network interdiction optimization via capacitated network reliability modeling and probabilistic solution discovery”, Reliability Engineering and System Safety, Vol. 94, pp. 913–921 (2009).
Ramirez–Marquez, J. E., Rocco S., C. M., and Levitin, G., “Optimal protection of general source–sink networks via evolutionary techniques”, Reliability Engineering and System Safety, Vol. 94, pp. 1676–1684 (2009).
Rueger, W. J., “Reliability analysis of networks with capacity constraints and failure at branches & nodes, IEEE Transactions on Reliability, Vol. 35, pp. 523–528 (1986).
Schaffer, J. D., Caruana, R. A., Eshelman, L. J., and Das R., “A study of control parameters affecting online performance of genetic algorithms for function optimization”, Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann, Los Altos, CA, pp. 51–60 (1989).
Soh, S. and Rai, S., “An efficient cutset approach for evaluating communication–network reliability with heterogeneous link–capacities”, IEEE Transactions on Reliability, Vol. 54, pp. 133–144 (2005).
Srinivas, M. and Lalit, M. P., “Genetic algorithm: a survey”, IEEE Computer, Vol. 27, pp. 18–20 (1994).
Syswerda, G., “Uniform crossover in genetic algorithm”, Proceedings of the 3rd International Conference on Genetic Algorithms, Morgan Kaufmann, Los Altos, CA, pp. 2–9 (1989).
Toroslu, I. H. and Arslanoglu, Y., “Genetic algorithm for the assignment problem with multiple objectives”, Information Sciences, Vol. 177, pp. 787–803 (2007).
Wang, Y. Z., “An application of genetic algorithm methods for teacher assignment problems”, Expert Systems with Applications, Vol. 22, pp. 295–302 (2002).
Wilson, J. M., “A genetic algorithm for the generalized assignment problem”, Journal of the Operational Research Society, Vol. 48, pp. 804–809 (1997).
Xu, W., He, S., Song, R., and Li, J., “Reliability based assignment in stochastic–flow freight network”, Applied Mathematics and Computation, Vol. 211, pp. 85–94 (2009).
Xue, J., “On multistate system analysis”, IEEE Transactions on Reliability, Vol. 34, pp. 329–337 (1985).
Yao, M. J. and Chu, W. M., “A genetic algorithm for determining optimal replenishment cycles to minimize maximum warehouse space requirements”, Omega, Vol. 36, pp. 619–631 (2008).
Zacharia, P., Menti, A., and Zacharias, Th., “Genetic algorithm–based optimal design of shunt compensators in the presence of harmonics”, Electric Power Systems Research, Vol. 78, pp. 728–735 (2008).
Zuo, M. J., Tian, Z., and Huang, H. Z., “An efficient method for reliability evaluation of multistate networks given all minimal path vectors”, IIE Transactions, Vol. 39, pp. 811–817 (2007).