# Maximal Flow of Transportation Network in Medan City Using Ford-Fulkerson Algorithm

• Faridawaty Marpaung Mathematics Departement Universitas Negeri Medan, Jalan Williem Iskandar Pasar V, Medan North Sumatera Indonesia
• Arnita Arnita Mathematics Departement Universitas Negeri Medan, Jalan Williem Iskandar Pasar V, Medan North Sumatera Indonesia
• Nila Sari Mathematics Departement Universitas Negeri Medan, Jalan Williem Iskandar Pasar V, Medan North Sumatera Indonesia
Keywords: Traffic Congestion, Transport Network, Maximal Flow and Ford-Fulkerson Algorithm.

### Abstract

Transportation is a major component of living, government, and social systems. Tsocio-demographic conditions influence the performance. In this study has a purpose as an investigation of an event that measures the maximal capacity of the road as a way to overcome congestion. Searching for the maximal flow based upon the graph formed using the Ford-Fulkerson Algorithm with numerous stages, namely determining the possible pathway through the source point to the main point arranged in numerous iterations by analyzing the graph formed. Then the initialization process is given by zero flow from each side of the graph, then the search for maximal flow is obtained after doing as many as 16 iterations. The residual flow results from subtracting the total number of flows by the number of flows at each iteration. The iteration will stop if no more augmenting pathway is found. Cuts will occur if the amount of flow equals the amount of capacity. Research data is in the form of public transportations in Medan and routes. The data was obtained directly from the archives of the Transportation Service in Medan City. The search for the maximal flow of the transportation network is carried out by observing the public transportation route in the city of Medan, namely the public transportation route through Jalan Jamin Ginting to Jl. Various types of public transportation traverse Williem Iskandar. Based upon the research, the maximal capacity can be exceeded through the transportation network. There are 5 types of public transportations. The pathway through City Hall - Jl. Putri Hijau and the pathway through Jl. Perintis Kemerdekaanâ€“Jl. HM. Yamin has exceeded capacity because the types of public transportation that pass through the two roads are 15 and 9. However, the other lanes are still low, so it should divert some types of public transportation overload to empty roads.