Academic literature on the topic 'Maximum flow problem; augmenting path; and Ford and Fulkerson algorithm'

This paper, presents an efficient algorithm that solves such a large class of optimization problems. Ford-Fulkerson determines the maximum flow in a network by iteratively augmenting flow paths until no further improvement is possible. On the other hand, Dijkstra's algorithm excels in finding the shortest path in a weighted graph, making it suitable for minimizing costs in network traversal. However, this paper simultaneously optimizes both objectives (flow and cost) dependently in unique iterations by considering all constraints and objectives holistically. The aim of this work is to develop efficient algorithms that can handle complex optimization problems in transportation, network design, and other fields, ultimately improving resource utilization and minimizing costs as its crucial for enhancing decision-making processes, improving efficiency in resource utilization, and achieving cost savings in diverse applications ranging from transportation networks to production planning. This paper deals about formulating the linear programming for the optimizations problems and finding the maximum amount of flow that can be sent from a source node to a sink node while minimizing the total cost of sending that flow by using simplex method (Two phase method). Through computational experiments and case studies, everybody demonstrate the effectiveness and efficiency of the proposed approach in solving real-world network flow problems. Our method yields efficient algorithms with in smallest numbers of iterations and time that enable the optimal allocation of resources within networks, achieving both maximum flow and minimum cost simultaneously.

The maximum flow problem is popular with many researchers as it plays a significant role in many areas. This problem is about obtaining the maximum flow where there is one source and sink in the network flow. In solving maximum flow problems, many algorithms are applied such as the most used are the Ford-Fulkerson Algorithm and the Edmonds-Karp Algorithm. The goal of this study is to identify the gaps of these two algorithms and sufficiently provide an analysis and comparison of their time complexity, simplicity, and effectiveness to solve the augmentation path in the maximum flow problem. The Ford-Fulkerson and Edmonds-Karp algorithms performed well and sufficiently to solve the augmentation path in the maximum flow problem. However, both algorithms consist of different gaps like having slow time complexity and difficulty in implementation and execution.
 Keywords: Maximum Flow Problem, Augmentation Path, Ford Fulkerson Algorithm, Network Flow, Edmonds-Karp Algorithm

In this paper, the well-known Ford-Fulkerson algorithm in graph theory is used to determine the maximum flow in a road traffic network. Road traffic congestion is a major urban transport problem that occurs when the volume of traffic exceeds the capacity of existing road facilities. The manifestation of traffic congestion is due to the ownership of a high number of vehicles at the expense of road traffic infrastructure and the high growth of the urban population. Only one road connects the city center of Kinshasa, which concentrates the main activities of the inhabitants, to the international airport of Ndjili. Whether you are a pedestrian, a car driver or a public transport user, you cannot escape the traffic jams that refuse to leave Kinshasa. Even motorbike taxis cannot escape. Yet the grade separations built on Lumumba Boulevard in Debonhomme, at the Marché de la Liberté and at Pascal are all open to traffic. Built to facilitate the flow of traffic between the city center (Gombe) and N'djili International Airport, these elephantine structures serve little purpose. In this study, the identification of the maximum flow and bottleneck path along the Lumumba Boulevard between Debonhomme and Ndjili International Airport in the Tshangu district of Kinshasa was carried out. All possible routes from the different sources to the different wells were established. It emerged from this study that the optimal solutions would be the construction of secondary roads and improvement of the road facilities to minimize the problem of traffic congestion.

Ford and Fulkerson introduce the maximum dynamic flow problems with fixed transit times on the arcs and developed the first well known algorithm that sends maximum flow from the source to the sink by augmenting along s-t paths and prove the maximum amount of flow is equal to the total capacity of the arcs in minimum cut. In flows over time with fixed transit time on the arc, the time it takes to traverse an arc does not depend on the current flow situation on the arc. But in real situation, the flow units travelling on the same arc at the same time do not necessarily experience the same pace, i.e., flow units are in general not entering and leaving an arc in the same order. In this paper, we discuss the time expanded graph for load-dependent and inflow[1]dependent transit times. We also discuss the discrete and continuous time flow, earliest arrival flow and quickest transhipment problem.