Algoritma Ford-Fulkerson untuk memaksimumkan flow pada penjadwalan jalur kereta api

INDONESIA:

Masalah pengoptimalan penggunaan jalur kereta api dan penjadwalannya sangat penting untuk dikaji. Algoritma Ford-Fulkerson digunakan untuk menentukan flow maksimum pada suatu jaringan yang memiliki satu titik sumber utama (v_s) dan satu titik tujuan utama (v_t), yang mana suatu jaringan memiliki beberapa titik sumber (v_(s_i )) dan beberapa titik tujuan (v_(t_i )). Penelitian ini menganalisis algoritma Ford-Fulkerson untuk memaksimumkan flow penjadwalan jalur kereta api Stasiun Kota Baru Malang pada lima jalur aktif yang digunakan sebagai jalur kedatangan dan keberangkatan kereta api. Jalur tersebut dapat dimaksimumkan nilai flow-nya sehingga penggunaan jalur kereta api dapat ditingkatkan.

Algoritma Ford-Fulkerson adalah membentuk jaringan baru dengan menambahkan satu titik sumber utama (v_s ) dan satu titik tujuan utama (v_t). Kemudian memberi nilai flow awal sebesar nol dan membentuk kapasitas pada setiap busur. Selanjutnya memaksimumkan flow dengan menggunakan algoritma Ford-Fulkerson yaitu melakukan pelabelan titik, menggunakan prosedur balik, dan mencari lintasan peningkatan hingga semua titik yang terlabel telah teramati dan titik tujuan utama tidak terlabel dan kemudian iterasi dihentikan.

Dari hasil analisis diperoleh kesimpulan bahwa pada jalur kereta api Stasiun Kota Baru Malang diperoleh flow maksimum pada seluruh jalur kereta api dengan flow f_19 bernilai 118,34. Penelitian selanjutnya diharapkan dapat mengkaji terkait jaringan jalur kereta api ini, serta dapat dikembangkan untuk pencarian flow maksimum pada jaringan transportasi yang lain.

ENGLISH:

Optimization problems of the use of railway lines and scheduling is very important to be studied. Ford-Fulkerson algorithm is used to determine the maximum flow in a network that has single primary source point (v_s) and one main destination point (v_t), where a network has multiple source points (〖v_s〗_i) and several destination points (〖v_t〗_i). This study analyze the Ford-Fulkerson algorithm to maximize the railroad flow scheduling of Malang Kota Baru station on five active lines used as a point of arrival and departure of trains. The flow of this lane can be maximized so that the use of the railway line could be improved.

Ford-Fulkerson algorithm is establishing a new network by adding one point to the main source (v_s) and a main destination point (v_t). Then giving the value of the initial flow of zero and establish capacity in each arc. Then maximizing the flow using the Ford-Fulkerson algorithm by labeling point, using the reverse procedure, and determining improvement trajectory until all points have been observed and the main destination point are not labeled and then the iteration is stopped.

From the results of the analysis we concluded that on the railway Malang Kota Baru station it is obtained the maximum flow on the entire railway line with flow f_19 is 118,34. Future studies are expected to examine the relevant railway networks, as well as searches can be developed to the maximum flow in the other transport network.