Graphs are excellent mathematical tools applied in many fields such as transportation, communication, informatics, economy,…. A network and a flow network is a useful device to solve many problems in many fields in reality. However, most of the network applications in traditional graphs have only considered the weights of edges and vertexes independently, in which the length of a path is the sum of weights of the edges and the vertexes on the path. However, in many practical problems, weights at a vertex are not the same for all paths passing the vertex, but depend on the edges coming to and leaving the vertex. For example, the transit time on the transport network depends on the direction of transportation: turn right, turn left or go straight, even some directions are forbidden. Furthermore, on a network, there are many types of commodities, each of which are at different costs. Types of commodities share the capacity of edges and vertexes. Therefore, it is necessary to study a network with multiple commodities at multiple costs. The article builds a model of extended multi-commodity multi-cost network in order to modelise practical problems more exactly and effectively. The maximal concurent multi-commodity multi-cost flow limited cost problems, that are modelized by implicit linear programming problems. On the basis of duality theory in linear programming, an effective polynomial approximation algorithm is developed.
| Published in | American Journal of Applied Mathematics (Volume 8, Issue 3) |
| DOI | 10.11648/j.ajam.20200803.11 |
| Page(s) | 74-82 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2020. Published by Science Publishing Group |
Network, Graph, Multi-cost Multi-commodity Flow, Linear Optimization, Approximation
| [1] | Naveen Garg and Jochen Könemann, “Faster and Simpler Algorithms for Multi-Commodity Flow and Other Fractional Packing Problems”, SIAM J. Comput, Canada, 37 (2), 2007, pp. 630-652. |
| [2] | Xiaolong Ma and Jie Zhou, “ An Extended Shortest Path Problem with Switch Cost Between Arcs”, Proceedings of the International MultiConference of Engineers and Computer Scientists 2008, Vol IIMECS 2008, 19-21 March, 2008, Hong Kong. |
| [3] | Ellis L. Johnson, George L. Nemhauser; Joel S. Sokol, and Pamela H. Vance, “Shortest Paths and Multi-Commodity Network Flows,” A Thesis Presented to the Academic Faculty, pp. 41-73, 2003. |
| [4] | Xiaolong Ma and Jie Zhou, “An extended shorted path problem with switch cost between arcs,” Proceedings of the international multiconference of engineers and computer scientists, Hong Kong, IMECS, 2008. |
| [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 Multi-Commodity flow problems,” In Proceedings, ACMSIAM Symposium on Discrete Algorithms, vol. 4, no. 1, 2002. |
| [7] | Aleksander, “Faster Approximation Schemes for Fractional Multi-Commodity Flow Problems via Dynamic Graph Algorithms,” Massachusetts Institute of Technology, 2009. |
| [8] | Tran Quoc Chien, “Linear multi-channel traffic network”, Ministry of Science and Technology, code B2010DN-03-52. |
| [9] | Tran Quoc Chien and Tran Thi My Dung, “ Application of the shortest path finding algorithm to find the maximum flow of goods”, Journal of Science & Technology, University of Danang, 3 (44) 2011. |
| [10] | Tran Quoc Chien, “Application of the shortest multi-path finding algorithm to find the maximum simultaneous flow of goods simultaneously”, Journal of Science & Technology, University of Danang, 4 (53) 2012. |
| [11] | Tran Quoc Chien, “Application of the shortest multi-path finding algorithm to find the maximal simultaneous flow of goods simultaneously the minimum cost”, Journal of Science & Technology, Da Nang University, 5 (54) 2012. |
| [12] | Tran Quoc Chien, “The algorithm finds the shortest path in the general graph”, Journal of Science & Technology, University of Da Nang, 12 (61) / 2012, pp. 16-21. |
| [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, pp. 522-527. |
| [14] | Tran Quoc Chien, “Applying the algorithm to find the fastest way to find the maximum linear and simultaneous minimum cost on an extended transportation network”, Journal of Science & Technology, University of Da Nang. 10 (71) 2013, pp. 85-91. |
| [15] | Tran Ngoc Viet; Tran Quoc Chien; and Le Manh Thanh, “The Revised Ford-Fulkerson Algorithm Finding Maximal Flows on Extended Networks,” International Journal of Computer Technology and Applications, vol. 5, no. 4, 2014, pp. 1438-1442. |
| [16] | Viet Tran Ngoc; Chien Tran Quoc; and Tau Nguyen Van, “Improving Computing Performance for Algorithm Finding Maximal Flows on Extended Mixed Networks,” Journal of Information and Computing Science, England, UK, vol. 10, no. 1, 2015, pp. 075-080. |
| [17] | Xiangming Yao, Baomin Han, Baomin Han, Hui Ren, “Simulation-Based Dynamic Passenger Flow Assignment Modelling for a Schedule-Based Transit Network;” Discrete Dynamics in Nature and Society- Hindawi, 2017. |
| [18] | Ziliaskopoulos, A. K, “A linear rogramming model for the single destination system optimum dynamic traffic assignment problem,” Transportation Science, vol. 34, no. 1, 2000. |
| [19] | Nagarney A, “Mathematical Models of Transportation and Networks,” Mathematical Models in Economics, 2007. |
| [20] | Schulz, A. S., N. E. Stier-Moses, “On the performance of user equilibria in traffic networks,” Proc. 14th Annual ACM-SIAM Sympos on Discrete Algorithms (SODA). SIAM, Philadelphia, PA, 2003. |
| [21] | Tran Ngoc Viet, Tran Quoc Chien, Nguyen Mau Tue, “Optimized Linear Multiplexing Algorithm on Expanded Transport Networks”, Journal of Science & Technology, University of Da Nang. 3 (76) 2014, pp. 121-124. |
| [22] | Tran Ngoc Viet, Tran Quoc Chien, Nguyen Mau Tue, “The problem of linear multi-channel traffic flow in traffic network”, Proceedings of the 7th National Conference on Fundamental and Applied Information Technology Research (FAIR'7), ISBN: 978-604-913-300-8, pp. 31-39. |
| [23] | Tran Quoc Chien, Ho Van Hung, “Extended linear Multi-Commodity multi-cost network and maximal flow finding problem”, Proceedings of the 7th National Conference on Fundamental and Applied Information Technology Research (FAIR'10), ISBN: 978-604-913-614-6, pp. 385-395. |
| [24] | Tran Quoc Chien, Ho Van Hung, “ Applying algorithm finding shortest path in the multiple-weighted graphs to find maximal flow in extended linear multicomodity multi-cost network”, EAI Endorsed Transactions on Industrial Networks and Intelligent Systems, 12.2017, Volume 4, Issue 11, pp. 1-6. |
| [25] | Tran Quoc Chien, Ho Van Hung, “Extended Linear Multi-Commodity Multi-Cost Network and Maximal Flow Limited Cost Problems”, The International Journal of Computer Networks & Communications (IJCNC), Volue 10, No. 1, January 2018, pp. 79-93. (SCOPUS). |
| [26] | Ho Van Hung, Tran Quoc Chien, “Implement and Test Algorithm finding Maximal Flow Limited Cost in extended multicomodity multi-cost network”, The International Journal of Computer Techniques (IJCT), Volume 6 Issue 3, May – June 2019, pp. 1-9. |
| [27] | Ho Van Hung, Tran Quoc Chien, “Extended Linear Multi-Commodity Multi-Cost Network and Maximal Concurent Flow Problems”, The International Journal of Mobile Netwwork Communications & Telematics (IJMNCT), Vol. 9, No. 1, February 2019, pp 1-14. |
| [28] | Ho Van Hung, Tran Quoc Chien, “Installing Algorithm to find Maximal Concurent Flow in Multi-cost Multi-Commodity Extended”, International Journal of Innovative Science and Research Technology (IJISRT), Volue 4, Issue 12, December 2019, pp 1110-1119. |
APA Style
Ho Van Hung, Tran Quoc Chien. (2020). Maximal Concurent Limited Cost Flow Problems on Extended Multi-commodity Multi-cost Network. American Journal of Applied Mathematics, 8(3), 74-82. https://doi.org/10.11648/j.ajam.20200803.11
ACS Style
Ho Van Hung; Tran Quoc Chien. Maximal Concurent Limited Cost Flow Problems on Extended Multi-commodity Multi-cost Network. Am. J. Appl. Math. 2020, 8(3), 74-82. doi: 10.11648/j.ajam.20200803.11
AMA Style
Ho Van Hung, Tran Quoc Chien. Maximal Concurent Limited Cost Flow Problems on Extended Multi-commodity Multi-cost Network. Am J Appl Math. 2020;8(3):74-82. doi: 10.11648/j.ajam.20200803.11
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ajam.20200803.11,
author = {Ho Van Hung and Tran Quoc Chien},
title = {Maximal Concurent Limited Cost Flow Problems on Extended Multi-commodity Multi-cost Network},
journal = {American Journal of Applied Mathematics},
volume = {8},
number = {3},
pages = {74-82},
doi = {10.11648/j.ajam.20200803.11},
url = {https://doi.org/10.11648/j.ajam.20200803.11},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajam.20200803.11},
abstract = {Graphs are excellent mathematical tools applied in many fields such as transportation, communication, informatics, economy,…. A network and a flow network is a useful device to solve many problems in many fields in reality. However, most of the network applications in traditional graphs have only considered the weights of edges and vertexes independently, in which the length of a path is the sum of weights of the edges and the vertexes on the path. However, in many practical problems, weights at a vertex are not the same for all paths passing the vertex, but depend on the edges coming to and leaving the vertex. For example, the transit time on the transport network depends on the direction of transportation: turn right, turn left or go straight, even some directions are forbidden. Furthermore, on a network, there are many types of commodities, each of which are at different costs. Types of commodities share the capacity of edges and vertexes. Therefore, it is necessary to study a network with multiple commodities at multiple costs. The article builds a model of extended multi-commodity multi-cost network in order to modelise practical problems more exactly and effectively. The maximal concurent multi-commodity multi-cost flow limited cost problems, that are modelized by implicit linear programming problems. On the basis of duality theory in linear programming, an effective polynomial approximation algorithm is developed.},
year = {2020}
}
TY - JOUR T1 - Maximal Concurent Limited Cost Flow Problems on Extended Multi-commodity Multi-cost Network AU - Ho Van Hung AU - Tran Quoc Chien Y1 - 2020/04/29 PY - 2020 N1 - https://doi.org/10.11648/j.ajam.20200803.11 DO - 10.11648/j.ajam.20200803.11 T2 - American Journal of Applied Mathematics JF - American Journal of Applied Mathematics JO - American Journal of Applied Mathematics SP - 74 EP - 82 PB - Science Publishing Group SN - 2330-006X UR - https://doi.org/10.11648/j.ajam.20200803.11 AB - Graphs are excellent mathematical tools applied in many fields such as transportation, communication, informatics, economy,…. A network and a flow network is a useful device to solve many problems in many fields in reality. However, most of the network applications in traditional graphs have only considered the weights of edges and vertexes independently, in which the length of a path is the sum of weights of the edges and the vertexes on the path. However, in many practical problems, weights at a vertex are not the same for all paths passing the vertex, but depend on the edges coming to and leaving the vertex. For example, the transit time on the transport network depends on the direction of transportation: turn right, turn left or go straight, even some directions are forbidden. Furthermore, on a network, there are many types of commodities, each of which are at different costs. Types of commodities share the capacity of edges and vertexes. Therefore, it is necessary to study a network with multiple commodities at multiple costs. The article builds a model of extended multi-commodity multi-cost network in order to modelise practical problems more exactly and effectively. The maximal concurent multi-commodity multi-cost flow limited cost problems, that are modelized by implicit linear programming problems. On the basis of duality theory in linear programming, an effective polynomial approximation algorithm is developed. VL - 8 IS - 3 ER -
Email: