Maximal concurrent minimal cost flow problems on extended multicost multicommodity networks
##plugins.themes.academic_pro.article.main##
Author

Ho Van Hung, Tran Quoc Chien
Từ khóa:
Tóm tắt
The graph is a great mathematical tool, which has been effectively applied to many fields such as economy, informatics, communication, transportation, etc. It can be seen that in an ordinary graph the weights of edges and vertexes are taken into account independently where the length of a path is the sum of weights of the edges and the vertexes on this path. Nevertheless, in many practical problems, weights at vertexes are not equal for all paths going through these vertexes, but are depending on coming and leaving edges. Moreover, on a network, the capacities of edges and vertexes are shared by many goods with different costs. Therefore, it is necessary to study networks with multiple weights. Models of extended multicost multicommodity networks can be applied to modelize many practical problems more exactly and effectively. The presented article studies the maximal concurrent minimal cost flow problems on multicost and multicommodity networks, which are modelized as optimization problems. On the base of the algorithm to find maximal concurrent flow and the algorithm to find maximal concurrent limited cost flow, an effective polynomial approximate procedure is developed to find a good solution.
Tài liệu tham khảo

[1] Xiaolong Ma and Jie Zhou, “An Extended Shortest Path Problem with Switch Cost Between Arcs”, IIMECS 2008, 1921 March, 2008, Hong Kong.
[2] Naveen Garg and Jochen Könemann, “Faster and Simpler Algorithms for MultiCommodity Flow and Other Fractional Packing Problems”, SIAM Journal. Comput, Canada, 37(2), 2007, pp. 630652.
[3] Ellis L. Johnson, Geo L. Nemhauser; Joel S. Sokol, and Pamela H. Vance, “Shortest Paths and MultiCommodity Network Flows”, A Thesis Presented to the Academic Faculty, 2003, pp. 4173.
[4] Xiaolong Ma and Jie Zhou, “An extended shorted path problem with switch cost between arcs”, IMECS 2008, Hong Kong.
[5] L. K. Fleischer, “Approximating fractional Multi  Commodity flow independent of the number of commodities”, SIAM J. Discrete Math., vol.13, no.4, 2000.
[6] G. Karakostas, “Faster approximation schemes for fractional MultiCommodity flow problems”, In Proceedings, ACMSIAM Symposium on Discrete Algorithms, vol.4, no.1, 2002.
[7] Aleksander, “Faster Approximation Schemes for Fractional MultiCommodity Flow Problems via Dynamic Graph Algorithms” Massachusetts Institute of Technology, 2009.
[8] Tran Quoc Chien, “Linear multichannel traffic network”, Ministry of Science and Technology, code B2010DN0352.
[9] Tran Quoc Chien and Tran Thi My Dung, “Application of the shortest path finding algorithm to find the maximum flow of goods”, The University of Danang  Journal of Science and Technology, 3 (44) 2011.
[10] Tran Quoc Chien, “Application of the shortest multipath finding algorithm to find the maximum simultaneous flow of goods simultaneously”, The University of Danang  Journal of Science and Technology, 4 (53) 2012.
[11] Tran Quoc Chien, “Application of the shortest multipath finding algorithm to find the maximal simultaneous flow of goods simultaneously the minimum cost”, The University of Danang  Journal of Science and Technology, 5 (54) 2012.
[12] Tran Ngoc Viet, Tran Quoc Chien, Nguyen Mau Tue, “Optimized Linear Multiplexing Algorithm on Expanded Transport Networks”, The University of Danang  Journal of Science and Technology. 3 (76) 2014, pp.121124.
[13] Tran Quoc Chien; Nguyen Mau Tue; and Tran Ngoc Viet, “The algorithm finds the shortest path on the extended graph”. Proceeding of the 6th National Conference on Fundamental and Applied Information Technology (FAIR), Viet Nam, 2017. pp.522527.
[14] Xiangming Yao, Baomin Han, Baomin Han, Hui Ren, “SimulationBased Dynamic Passenger Flow Assignment Modelling for a ScheduleBased Transit Network”, Discrete Dynamics in Nature and Society Hindawi, 2017.
[15] Samani A and Wang M, MaxStream: “SDNbased flow maximization for video streaming with QoSenhancement”, In: IEEE 43rd conference on local computer networks (LCN), 2018, pp. 287–290.
[16] Wright M, Gomes G, Horowitz R and Kurzhanskiy A, “On node models for highdimensional road networks”, Transp Res Part B: Methodol 105, 2017, pp.212–234.
[17] Mohammadi M, Jula P and Tavakkoli Moghaddam R, “Design of a reliable multimodal multicommodity model for hazardous materials transportation under uncertainty”. Eur J Oper Res 257(3), 2017, pp.792–809.
[18] Xu X, Zhang Y and Lu J, “Routing optimization of small satellite networks based on multicommodity flow”, In: International conference on machine learning and intelligent communications. Springer, Cham, 2017, pp.355–363.
[19] Fortz B, Gouveia L, JoyceMoniz M, “Models for the piecewise linear unsplittable multicommodity fow problems”, Eur J Oper Res 261(1), 2017, pp. 30–42
[20] Balma A, Salem S, Mrad M and Ladhari T, “Strong Multicommodity flow formulations for the asymmetric traveling salesman problem”, Eur J Oper Res 27, 2018, pp. 72–79.
[21] Vahdani B, Veysmoradi D, Shekari N and Mousavi S, “Multiobjective, multiperiod locationroutingmodel to distribute relief after earthquake by considering emergency roadway repair”, Neural ComputAppl 30(3), 2018, pp.835–854.
[22] Lu Y, Benlic U and Wu Q, “A population algorithm based on randomized tabu thresholding for themulticommodity pickupanddelivery traveling salesman problem”, Comput Oper Res 101, 2019, pp.285–297.
[23] Tran Quoc Chien, Ho Van Hung, “Extended linear MultiCommodity multicost network and maximal flow finding problem”, Proceedings of the 7th National Conference on Fundamental and Applied Information Technology Research (FAIR'10), ISBN: 9786049136146, pp.385395.
[24] Tran Quoc Chien, Ho Van Hung, “Applying algorithm finding shortest path in the multipleweighted graphs to find maximal flow in extended linear multicomodity multicost network”, EAI Endorsed Transactions on Industrial Networks and Intelligent Systems, 2017, Volume 4, Issue 11, pp.16.
[25] Tran Quoc Chien, Ho Van Hung, “Extended Linear MultiCommodity MultiCost Network and Maximal Flow Limited Cost Problems”, The International Journal of Computer Networks & Communications (IJCNC), Volue 10, No. 1, January 2018, pp.7993. (SCOPUS).
[26] Ho Van Hung, Tran Quoc Chien, “Implement and Test Algorithm finding Maximal Flow Limited Cost in extended multicomodity multicost network”, The International Journal of Computer Techniques (IJCT), Volume 6 Issue 3, May – June 2019, pp.19.
[27] Ho Van Hung, Tran Quoc Chien, “Extended Linear MultiCommodity MultiCost Network and Maximal Concurrent Flow Problems”, The International Journal of Mobile Netwwork Communications & Telematics (IJMNCT), Vol.9, No.1, February 2019, pp 114.
[28] Ho Van Hung, Tran Quoc Chien, “Installing Algorithm to find Maximal Concurrent Flow in Multicost Multicommodity Extended”, International Journal of Innovative Science and Research Technology (IJISRT), Volue 4, Issue 12, December 2019, pp 11101119.
[29] Ho Van Hung, Tran Quoc Chien, Maximal Concurrent Limited Cost Flow Problems on Extended Linear MultiCommodity MultiCost Networks, American Journal of Applied Mathematics, Vol. 8, No. 3, 2020, pp 7482.
[30] Ho Van Hung, Tran Quoc Chien, Implement Algorithm Finding Maximal Concurrent Limited Cost Flow on Extended Multicommodity Multicost Network, IOSR Journal of Computer Engineering (IOSRJCE), 22.2 (2020), pp 3444.