Efficient Design Optimization of Multi-State Flow Network for Multiple Commodities
The network of delivering commodities has been an important design problem in our daily lives and many transportation applications. The delivery performance is evaluated based on the system reliability of delivering commodities from a source node to a sink node in the network. The system reliability is thus maximized to find the optimal routing. However, the design problem is not simple because (1) each path segment has randomly distributed attributes; (2) there are multiple commodities that consume various path capacities; (3) the optimal routing must successfully complete the delivery process within the allowable time constraints. In this paper, we want to focus on the design optimization of the Multi-State Flow Network (MSFN) for multiple commodities. We propose an efficient approach to evaluate the system reliability in the MSFN with respect to randomly distributed path attributes and find the optimal routing subject to the allowable time constraints. The delivery rates, also known as delivery currents, of the path segments are evaluated and the minimal-current arcs are eliminated to reduce the complexity of the MSFN. Accordingly, the correct optimal routing is found and the worst-case reliability is evaluated. It has been shown that the reliability of the optimal routing is at least higher than worst-case measure. Two benchmark examples are utilized to demonstrate the proposed method. The comparisons between the original and the reduced networks show that the proposed method is very efficient.
[1] P. Doulliez and E. Jamoulle, "Transportation Networks with Random
Arc Capacities," Revue Francaise D Automatique Informatique Recherche Operationnelle, vol. 6, no. 3, pp. 45-59, 1972.
[2] T. Aven, "Availability Evaluation of Oil Gas-Production and
Transportation Systems," Reliability Engineering & System Safety, vol.
18, no. 1, pp. 35-44, 1987.
[3] M. A. Samad, "An Efficient Algorithm for Simultaneously Deducing Minimal Paths as Well as Cuts of a Communication-Network,"
Microelectronics and Reliability, vol. 27, no. 3, pp. 437-441, 1987.
[4] T. Aven, "Some Considerations on Reliability Theory and Its
Applications," Reliability Engineering & System Safety, vol. 21, no. 3,
pp. 215-223, 1988.
[5] P. Kubat, "Estimation of Reliability for Communication
Computer-Networks - Simulation Analytic Approach," IEEE
Transactions on Communications, vol. 37, no. 9, pp. 927-933, 1989.
[6] S. T. Soh and S. E. Rai, "Carel: Computer-Aided Reliability Evaluator
for Distributed Computing Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 2, pp. 199-213, 1991.
[7] W. J. Ke and S. D. Wang, "Reliability Evaluation for Distributed
Computing Networks with Imperfect Nodes," IEEE Transactions on
Reliability, vol. 46, no. 3, pp. 342-349, 1997.
[8] C. J. Colbourn, The Combinatorics of Network Reliability, Oxford
University Press, New York, 1987.
[9] J. L. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, 2003.
[10] Y. L. Chen and Y. H. Chin, "The Quickest Path Problem," Computers &
Operations Research, vol. 17, no. 2, pp. 153-161, 1990.
[11] J. B. Rosen, S.-Z. Sun, and G.-L. Xue, "Algorithms for the Quickest
Path Problem and the Enumeration of Quickest Paths," Computers &
Operations Research, vol. 18, no. 6, pp. 579-584, 1991.
[12] G. H. Chen and Y. C. Hung, "On the Quickest Path Problem," Information Processing Letters, vol. 46, no. 3, pp. 125-128, 1993.
[13] G. H. Chen and Y. C. Hung, "Algorithms for the Constrained Quickest
Path Problem and the Enumeration of Quickest Paths," Computers &
Operations Research, vol. 21, no. 2, pp. 113-118, 1994.
[14] E. D. V. Martins and J. L. E. dos Santos, "An Algorithm for the
Quickest Path Problem," Operations Research Letters, vol. 20, no. 4, pp.
195-198, 1997.
[15] M. M. B. Pascoal, M. E. V. Captivo, and J. C. N. Clímaco, "A
Comprehensive Survey on the Quickest Path Problem," Annals of
Operations Research, vol. 147, no. 1, pp. 5-21, 2006.
[16] Y. K. Lin, "Extend the Quickest Path Problem to the System Reliability
Evaluation for a Stochastic-Flow Network," Computers & Operations
Research, vol. 30, no. 4, pp. 567-575, 2003.
[17] Y. K. Lin, "Study on the Multicommodity Reliability of a
Capacitated-Flow Network," Computers & Mathematics with
Applications, vol. 42, no. 1-2, pp. 255-264, 2001.
[18] W. C. Yeh, "A Novel Method for the Network Reliability in Terms of
Capacitated-Minimum-Paths without Knowing Minimum-Paths in
Advance," Journal of the Operational Research Society, vol. 56, no. 10,
pp. 1235-1240, 2005.
[19] W. C. Yeh, "The Extension of Universal Generating Function Method to
Search for All One-to-Many D-Minimal Paths of Acyclic
Multi-State-Arc Flow-Conservation Networks," IEEE Transactions on
Reliability, vol. 57, no. 1, pp. 94-102, 2008.
[20] Y. K. Lin, "Network Reliability of a Time-Based Multistate Network
under Spare Routing with P Minimal Paths," IEEE Transactions on
Reliability, vol. 60, no. 1, pp. 61-69, 2011.
[21] W.-C. Yeh, L.-E. Lin, Y.-C. Chou, and Y.-C. Chen, "Optimal Routing
for Multi-Commodity in Multistate Flow Network with Time
Constraints," International Journal of Systems Science, submitted for
publication.
[22] W. C. Yeh, "A Simple Minimal Path Method for Estimating the
Weighted Multi-Commodity Multistate Unreliable Networks
Reliability," Reliability Engineering & System Safety, vol. 93, no. 1, pp.
125-136, 2008.
[23] J. R. Cogdell, Foundations of Electric Circuits, Prentice Hall, Upper
Saddle River, New Jersey, 1999.
[24] A. Amiri and H. Pirkul, "Routing and Capacity Assignment in Backbone
Communication Networks," Computers & Operations Research, vol. 24,
no. 3, pp. 275-287, 1997.
[1] P. Doulliez and E. Jamoulle, "Transportation Networks with Random
Arc Capacities," Revue Francaise D Automatique Informatique Recherche Operationnelle, vol. 6, no. 3, pp. 45-59, 1972.
[2] T. Aven, "Availability Evaluation of Oil Gas-Production and
Transportation Systems," Reliability Engineering & System Safety, vol.
18, no. 1, pp. 35-44, 1987.
[3] M. A. Samad, "An Efficient Algorithm for Simultaneously Deducing Minimal Paths as Well as Cuts of a Communication-Network,"
Microelectronics and Reliability, vol. 27, no. 3, pp. 437-441, 1987.
[4] T. Aven, "Some Considerations on Reliability Theory and Its
Applications," Reliability Engineering & System Safety, vol. 21, no. 3,
pp. 215-223, 1988.
[5] P. Kubat, "Estimation of Reliability for Communication
Computer-Networks - Simulation Analytic Approach," IEEE
Transactions on Communications, vol. 37, no. 9, pp. 927-933, 1989.
[6] S. T. Soh and S. E. Rai, "Carel: Computer-Aided Reliability Evaluator
for Distributed Computing Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 2, no. 2, pp. 199-213, 1991.
[7] W. J. Ke and S. D. Wang, "Reliability Evaluation for Distributed
Computing Networks with Imperfect Nodes," IEEE Transactions on
Reliability, vol. 46, no. 3, pp. 342-349, 1997.
[8] C. J. Colbourn, The Combinatorics of Network Reliability, Oxford
University Press, New York, 1987.
[9] J. L. Gross and J. Yellen, Handbook of Graph Theory, CRC Press, 2003.
[10] Y. L. Chen and Y. H. Chin, "The Quickest Path Problem," Computers &
Operations Research, vol. 17, no. 2, pp. 153-161, 1990.
[11] J. B. Rosen, S.-Z. Sun, and G.-L. Xue, "Algorithms for the Quickest
Path Problem and the Enumeration of Quickest Paths," Computers &
Operations Research, vol. 18, no. 6, pp. 579-584, 1991.
[12] G. H. Chen and Y. C. Hung, "On the Quickest Path Problem," Information Processing Letters, vol. 46, no. 3, pp. 125-128, 1993.
[13] G. H. Chen and Y. C. Hung, "Algorithms for the Constrained Quickest
Path Problem and the Enumeration of Quickest Paths," Computers &
Operations Research, vol. 21, no. 2, pp. 113-118, 1994.
[14] E. D. V. Martins and J. L. E. dos Santos, "An Algorithm for the
Quickest Path Problem," Operations Research Letters, vol. 20, no. 4, pp.
195-198, 1997.
[15] M. M. B. Pascoal, M. E. V. Captivo, and J. C. N. Clímaco, "A
Comprehensive Survey on the Quickest Path Problem," Annals of
Operations Research, vol. 147, no. 1, pp. 5-21, 2006.
[16] Y. K. Lin, "Extend the Quickest Path Problem to the System Reliability
Evaluation for a Stochastic-Flow Network," Computers & Operations
Research, vol. 30, no. 4, pp. 567-575, 2003.
[17] Y. K. Lin, "Study on the Multicommodity Reliability of a
Capacitated-Flow Network," Computers & Mathematics with
Applications, vol. 42, no. 1-2, pp. 255-264, 2001.
[18] W. C. Yeh, "A Novel Method for the Network Reliability in Terms of
Capacitated-Minimum-Paths without Knowing Minimum-Paths in
Advance," Journal of the Operational Research Society, vol. 56, no. 10,
pp. 1235-1240, 2005.
[19] W. C. Yeh, "The Extension of Universal Generating Function Method to
Search for All One-to-Many D-Minimal Paths of Acyclic
Multi-State-Arc Flow-Conservation Networks," IEEE Transactions on
Reliability, vol. 57, no. 1, pp. 94-102, 2008.
[20] Y. K. Lin, "Network Reliability of a Time-Based Multistate Network
under Spare Routing with P Minimal Paths," IEEE Transactions on
Reliability, vol. 60, no. 1, pp. 61-69, 2011.
[21] W.-C. Yeh, L.-E. Lin, Y.-C. Chou, and Y.-C. Chen, "Optimal Routing
for Multi-Commodity in Multistate Flow Network with Time
Constraints," International Journal of Systems Science, submitted for
publication.
[22] W. C. Yeh, "A Simple Minimal Path Method for Estimating the
Weighted Multi-Commodity Multistate Unreliable Networks
Reliability," Reliability Engineering & System Safety, vol. 93, no. 1, pp.
125-136, 2008.
[23] J. R. Cogdell, Foundations of Electric Circuits, Prentice Hall, Upper
Saddle River, New Jersey, 1999.
[24] A. Amiri and H. Pirkul, "Routing and Capacity Assignment in Backbone
Communication Networks," Computers & Operations Research, vol. 24,
no. 3, pp. 275-287, 1997.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:61509", author = "Yu-Cheng Chou and Po Ting Lin", title = "Efficient Design Optimization of Multi-State Flow Network for Multiple Commodities", abstract = "The network of delivering commodities has been an important design problem in our daily lives and many transportation applications. The delivery performance is evaluated based on the system reliability of delivering commodities from a source node to a sink node in the network. The system reliability is thus maximized to find the optimal routing. However, the design problem is not simple because (1) each path segment has randomly distributed attributes; (2) there are multiple commodities that consume various path capacities; (3) the optimal routing must successfully complete the delivery process within the allowable time constraints. In this paper, we want to focus on the design optimization of the Multi-State Flow Network (MSFN) for multiple commodities. We propose an efficient approach to evaluate the system reliability in the MSFN with respect to randomly distributed path attributes and find the optimal routing subject to the allowable time constraints. The delivery rates, also known as delivery currents, of the path segments are evaluated and the minimal-current arcs are eliminated to reduce the complexity of the MSFN. Accordingly, the correct optimal routing is found and the worst-case reliability is evaluated. It has been shown that the reliability of the optimal routing is at least higher than worst-case measure. Two benchmark examples are utilized to demonstrate the proposed method. The comparisons between the original and the reduced networks show that the proposed method is very efficient.
", keywords = "Multiple Commodities, Multi-State Flow Network (MSFN), Time Constraints, Worst-Case Reliability (WCR)", volume = "6", number = "5", pages = "969-6", }
