Improvement of the methods for determining optimal characteristics of transportation networks
DOI:
https://doi.org/10.15587/1729-4061.2016.85211Keywords:
maximum transport flow, shortest paths, network model, matrix modelAbstract
An improved method of approaching the calculation of maximum flow is developed, which implies applying the method of trees and capacities of tabular processors. The solution can be extended for a problem with several sources and runoffs. This will solve the problem on the optimization of transportation networks with and without limitations in throughput capacity.
We designed an improved method for calculating the shortest path, which is resolved by using the Minty Dijkstra's algorithm. By solving the shortest path problem, we receive the shortest route and a list of vertices that it passes. By having indicators of freight traffic from each vertex to all others, we build a tree of the shortest paths. Going from one vertex to another vertex, we obtain density of traffic in the network without limitation in the throughput capacity.
When the network has a throughput capacity limitation, imposing flows on the network is a bit complicated. In this case, it is necessary to subtract each elementary flow from the existing throughput capacity of the arc, on which it is imposed. For finding the shortest path, it is possible to correct the flows manually.
The process of transforming network models for the process of cargo transportation to the matrix models is presented, through the use of the modified Dijkstra's algorithm. Elements of transportation networks in this case are set in the form of directed graphs. Graphic representation of the results of solving a network traffic problem is given.
References
- Prokudin, G. (2006). Optimization of traffic on a road networkin. Economy and management, 3 (4), 54–59.
- Teodorović, D., Janić, M. (2017). Transportation Systems. Transportation Engineering, 5–62. doi: 10.1016/b978-0-12-803818-5.00002-0
- Cormen, T., Rivest, C., Stein, R. (2006). Section 26.2: The Ford–Fulkerson method. Introduction to Algorithms. Second ed. MIT Press and McGraw–Hill, 651–664.
- Knight, H. (2014). New algorithm can dramatically streamline solutions to the 'max flow' problem. MIT News, 4, 21–26.
- Cancela, H., Mauttone, A., Urquhart, M. E. (2015). Mathematical programming formulations for transit network design. Transportation Research Part B: Methodological, 77, 17–37. doi: 10.1016/j.trb.2015.03.006
- Pu, C., Li, S., Yang, X., Yang, J., Wang, K. (2016). Information transport in multiplex networks. Physica A: Statistical Mechanics and Its Applications, 447, 261–269. doi: 10.1016/j.physa.2015.12.057
- Singh, S., Dubey, G. C., Shrivastava, R. (2016). Various Method to Solve the Optimality for the Transportation Problem. Statistical Mechanics and its Applications, 12, 161–169.
- Wu, J., Guo, X., Sun, H., Wang, B. (2014). Topological Effects and Performance Optimization in Transportation Continuous Network Design. Mathematical Problems in Engineering, 2014, 1–7. doi: 10.1155/2014/490483
- Zou, Y., Zhu, J. (2016). Reachability of higher-order logical control networks via matrix method. Applied Mathematics and Computation, 287-288, 50–59. doi: 10.1016/j.amc.2016.04.013
- Gupta, K., Arora, S. R. (2014). An algorithm for solving a capacitated indefinite quadratic transportation problem with enhanced flow. Yugoslav Journal of Operations Research, 24 (2), 217–236. doi: 10.2298/yjor120823043g
- Prokudin, G., Chupaylenko, A., Dudnik, A., Prokudin, A., Omarov, O. (2016). The conversion process network models of freight transport in the matrix model. Project management, systems analysis and logistics. Science journal, 16 (1), 125–136.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2016 Georgiy Prokudin, Olexiy Chupaylenko, Olexiy Dudnik, Alena Dudnik, Dzhanay Omarov
This work is licensed under a Creative Commons Attribution 4.0 International License.
The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.
A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.
