Improvement of the methods for determining optimal characteristics of transportation networks

Authors

DOI:

https://doi.org/10.15587/1729-4061.2016.85211

Keywords:

maximum transport flow, shortest paths, network model, matrix model

Abstract

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.

Author Biographies

Georgiy Prokudin, National Transport University Suvorova str., 1, Kyiv, Ukraine, 01010

Doctor of Technical Sciences, Professor, Нead of Department

Department international transportation and customs control

Olexiy Chupaylenko, National Transport University Suvorova str., 1, Kyiv, Ukraine, 01010

PhD, Associate Professor

Department of international transportation and customs control

Olexiy Dudnik, National Transport University Suvorova str., 1, Kyiv, Ukraine, 01010

PhD, Associate Professor

Department of international transportation and customs control

Alena Dudnik, National Transport University Suvorova str., 1, Kyiv, Ukraine, 01010

Assistant

Department of transport systems and road safety

Dzhanay Omarov, National Transport University Suvorova str., 1, Kyiv, Ukraine, 01010

Postgraduate student

Department of international transportation and customs control

References

  1. Prokudin, G. (2006). Optimization of traffic on a road networkin. Economy and management, 3 (4), 54–59.
  2. Teodorović, D., Janić, M. (2017). Transportation Systems. Transportation Engineering, 5–62. doi: 10.1016/b978-0-12-803818-5.00002-0
  3. 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.
  4. Knight, H. (2014). New algorithm can dramatically streamline solutions to the 'max flow' problem. MIT News, 4, 21–26.
  5. 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
  6. 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
  7. 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.
  8. 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
  9. 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
  10. 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
  11. 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

2016-12-19

How to Cite

Prokudin, G., Chupaylenko, O., Dudnik, O., Dudnik, A., & Omarov, D. (2016). Improvement of the methods for determining optimal characteristics of transportation networks. Eastern-European Journal of Enterprise Technologies, 6(3 (84), 54–61. https://doi.org/10.15587/1729-4061.2016.85211

Issue

Section

Control processes