Algoritma ford-fulkerson untuk memaksimumkan flow pada penjadwalan jalur kereta api

Andriany, Hardiana Devita (2016) Algoritma ford-fulkerson untuk memaksimumkan flow pada penjadwalan jalur kereta api. Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

[img]
Preview
Text (Fulltext)
11610023.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (6MB) | Preview

Abstract

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.

Item Type: Thesis (Undergraduate)
Supervisor: Irawan, Wahyu Hengky and Kusumastuti, Ari
Keywords: Algoritma Ford-Fulkerson; flow maksimum; jaringan; jaringan bipartisi; Ford-Fulkerson algorithm; maximum flow; network; bipartite network
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: Imam Rohmanu
Date Deposited: 21 Mar 2017 12:47
Last Modified: 21 Mar 2017 12:47
URI: http://etheses.uin-malang.ac.id/id/eprint/5756

Actions (login required)

View Item View Item