| Peer-Reviewed

Maximal Concurent Limited Cost Flow Problems on Extended Multi-commodity Multi-cost Network

Received: 1 April 2020     Accepted: 20 April 2020     Published: 29 April 2020
Views:       Downloads:
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.

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

Keywords

Network, Graph, Multi-cost Multi-commodity Flow, Linear Optimization, Approximation

References
[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.
Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    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}
    }
    

    Copy | Download

  • 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  - 

    Copy | Download

Author Information
  • Faculty of Information Technology, Quangnam University, Tamky, Vietnam

  • The University of Education, University of Danang, Danang, Vietnam

  • Sections