Efficient Design Optimization of Multi-State Flow Network for Multiple Commodities

Authors: Yu-Cheng Chou, Po Ting Lin

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)

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079288

References:

[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.