ANALISIS KEPADATAN ARUS LALU LINTAS JALAN RAYA DENGAN ALGORITMA MAX FLOW MIN CUT : STUDI KASUS RUTE PASAR MINGGU-HARMONI

Jurnal Basis Data, ICT Research Center UNAS Vol.3 No.1 Mei 2008

ISSN 1978-9483

ANALISIS KEPADATAN ARUS LALU LINTAS JALAN RAYA DENGAN ALGORITMA MAX FLOW MIN CUT : STUDI KASUS RUTE PASAR MINGGU-HARMONI Syarif Hidayatullah1, , Winarsih2 1, 2

Jurusan Sistem Informasi, Fakultas Teknologi Komunikasi dan Inf ormatika, Universitas Nasional Jl. Sawo Manila, Pejaten Pasar Minggu No.61, Jakarta 12520 Email: [email protected]

ABSTRAK Masalah yang dapat timbul pada lalu lintas jalan raya adalah masalah kemacetan lalu lintas. Banyak hal yang menyebabkan kemacetan, diantaranya karena banyaknya kendaran yang lewat melebihi kapasitas sistem jalan raya tersebut. Dengan diketahuinya besar arus maksimum yang melalui Pasar Minggu menuju jalan Harmoni dan sebaliknya ini dapat digunakan untuk mengurangi masalah kemacetan yang timbul. Sedangkan masalah arus maksimum pada arus lalu lintas jalan raya dapat diterapkan dengan teori graph. Sebagai alternatif solusi dari kemacetan ini maka digunakan Algotima Max Flow Min Cut dengan dukungan Algoritma Dijkstra. Kata kunci : algoritma, graph, kepadatan arus lalu lintas

ABSTRACT The trouble float to the surface in the traffic is the traffic jam. So much the things caused by traffic jam, among caused so many things the vehicle by way of more traffic capacity system. With be maximum current via Pasar Minggu to Harmony street and the other way it can be used for minimizing the trouble of traffic jam. But the maximum current of traffic jam can be applied by graph theory. As the alternative solution of traffic jam, so we should use algorithm max-flowmin-cut supported by Dijkstra algorithm. Keyword : algoritma, grafik, traffic jam

I.

PENDAHULUAN

Perhubungan dan transportasi merupakan suatu kebutuhan penting masyarakat. Bukan hanya kebutuhan masyarakat modern sekarang ini saja, namun juga kebutuhan sejak zaman dahulu kala. Manusaia membutuhkan sarana angkutan yang memadai agara dapat cepat sampai ke tujuan untuk menyelesaikan berbagai kepentingannya.

9


ISSN 1978-9483

Diantara jenis -jenis alat angkutan yang ada yaitu angkutan darat yang merupakan angkutan jalan raya, angkutan ini paling banyak digunakan. Masalah yang sering ditimbulkan yaitu kemacetan lalu lintas di temapat-tempat tertentu. Arus lalu lintas jalan raya yang melintas diruas kota -kota ini yang menyebabkan kemacetan lalu lintas yang merupakan masalah yang serius, Ini dapat terjadi pada suatu sistem tata kota yang merencanakan adanya kawasan pemukiman dan kawasan perkantoran. Dimana banyak karyawan yang pergi ke kantor dan pelajar yang pergi ke sekolah pada waktu yang bersamaan di pagi hari yang menyebabkan arus lalu lintas menjadi padat sehingga terjadi kemacetan lalu lintas. Begitu pula pada sore harinnya dengan arus yang berlawanan. Dalam hal ini akan difokuskan arus lalu lintas dari kawasan pemukiman Pasar Minggu menuju kawasan perkantoran Harmoni pada pagi hari antara jam 07.00 sampai dengan jam 09.00 WIB. Dan arus lalu lintas dari kawasan perkantoran Harmoni menuju kawasan pemukiman Pasar Minggu pada sore hari antara jam 16.00 sampai 18.00 WIB. Pada permasalahan arus lalu lintas ini akan dibawa ke model graph. Garis menyatakan jalan di dalam kota yang dapat dilalui, titik menyatakan ujung-ujung pertemuan jalan dan bobot dari masing-masing garis menyatakan kapasitas jalan yaitu banyaknya maksimum kendaraan yang melewati jalan persatuan waktu agar aliran di jalan tersebut lancar. Untuk masalah arus lintas ini, diasumsikan bahwa jaringan merupaka jaringan hingga yaitu banyak titik dan garis hingga. Selain itu jaringan hingga mempunyai satu titik sumber dan satu titik tujuan. Agar tidak terjadi kemacetan lalu lintas maka harus diketahui berapa arus maksimum kendaraan yang dapat melalui jaringan persatuan waktu agar lalu lintas lancar. Untuk meyelesaikan masalah ini akan digunakan suatu algoritma. Adapun algoritma yang digunakan adalah algoritma max-flow-min-cut. Algoritma max-flow -min-cut adalah salah satu cara untuk mencari arus maksimum dimana besarnya arus maksimum adalah sama dengan harga minimal dari cut yang memisahkan sumber ke tujuan.

II. TINJAUAN PUSTAKA 2.1. Definisi Graph Definisi Graph G yang menyatakan oleh G=(V,E) terdiri dari dua himpunan, himpunan E boleh kosong dan himpunan V tidak boleh kosong yaitu : 1. Himpunan titik V dimana V={V1,V2,….,Vn} 2. Himpunan garis E dimana E={e1,e2,…,em} Sedemikian sehingga setiap garis ekivalen berhubungan dengan pasangan tak terurut (Vi,Vj). 2.2. Jaringan Arus Definisi 1 : Suatu pasangan terurut N=(D,C) disebut suatu jaringan transportasi (network flow) jika D=(V,E) adalah graph berarah yang terhubung dan tidak mengandung loop dan C adalah fungsi dari garis (V i,V j) yang menunjukkan suatu besaran misalnya : - Sejumlah barang yang dapat diangkut dari titik Vi ke titik Vj. - Jumlah penumpang yang dapat diangkut dari kota ke kota lain. - Jumlah arus listrik ya ng dialairkan dari suatu tempat ke tempat lain. Definisi 2 : Jika pada jaringan N=(D,C) terdapat : - Titik Vs dengan derajat kedalamannya nol - Titik Vm dengan derajat keluarnya nol. Maka suatu arus dari Vs ke Vm dalam suatu jaringan adalah fungsi F yang non negatif pada E, sehingga : 10


ISSN 1978-9483

a. 0 ≤ f(x,v 1) ≤ C(x,v1 ) , ∀(x,v1)∈E W jika x = v s   b. Σ f(x,v1)- Σf(v 1,x) = 0 jika x ≠ v s dan x ≠ v m  − W jika x = v m  Titik vs disebut sumber, titk vm disebut Tujuan dan x disebut titik antara W disebut nilai suatu jaringan dengan arus yang memenuhi syarat(a) dan (b) disebut jaringan arus. Dari syarat a terlihat bahwa arus pada suatu busur selalui dibatasi oleh kapasitas dari garis. Dari syarat b terlihat bahwa arus yang keluar dari sumber sama dengan arus yang masuk ke tujuan. Dan arus yang masuk ke suatu titik (selain sumber dan tujuan) sama dengan arus yang keluar dari titik tersebut. Suatu garis (vi ,vj ) disebut ”jenuh” jika f(vi ,vj ) = C(vi ,vj) dan disebut ”tidak jenuh” jika f(vi ,vj) ≤ C(vi ,vj).

C=40 f=30 Vs C=20 f=15

a

C=20 f=20

C=10 f=10

b

e C=30 f=10

C=20 f=15

d

C=30 f=30 Vm C=40 f=15

Gambar 2.1 Diagram garis-garis arus

Dari gambar 2.1 dapat dinyatakan bahwa : f(a,e)=C(a,e), f(a,d)=C(a,d) , f(e,vm)=C(e, vm) maka (a,e),(a,d),(e,vm) adalah garis-garis yang jenuh dan sisanya garis-garis tidak jenuh, karena f(vs,a)
vj ∈ P

Nilai maksimum kapasitas dari semua cut disebut minimum cut . Perhatikan gambar 2.2. merupakan contoh dari cut : S={ (vs ,d), (vs ,b), (b,a), (a,b), (a,vm ) } dengan P ={ vs,a} dan P ={b,c,vm }. Sedangkan kapasitas dari cut : C(P, P )=C(vs,d)+C(vs ,b)+C(a,b)+C(a,vm ) = 5+1+5+2 = 13

11


ISSN 1978-9483

a C=2

C=4 Vs

C=6 b

C=5

C=5 C=4 C=1

Vm C=1

d

Gambar 2.2 Diagram cut garis -garis arus. 2.4. Teorema Max-Flow-Min-Cut Pada jaringan transportasi N, nilai arus maksimum dari vs ke vm sama dengan nilai minimum kapasitas dari semua cut dalam N terhadap vs dan vm . 2.5. Algoritma Max-Flow-Min-Cut Algoritma ini digunakan untuk memecahkan masalah arus maksimum dengan dukungan teorema max-flow-min-cut. Berdasarkan teorema ini akan dicari cut minimal yang harganya juga merupakan arus maksimum yang dicari. Karena dipakainya konsep dual, sedangkan yang dapat ditentukan dualnya adalah graph planar, maka algoritma ini dapat dijalankan pada graph planar. Algoritma max-flow-min -cut dapat dicari dengan beberapa tahap : Tahap 1: Buat jaringan dual G *=(V *,E *). Cara membuatnya yaitu dengan menempatkan sebuah titik dari V* pada setiap daerah G, Khusus untuk daerah luar dari G, ditempatkan dua titik dual, sebut a dan z, seberang menyebrang aliran jaringan G tersebut. Garis dari dual dibuat menghubungkan titik dual serta memotong garis batas daerah yang bersangkutan. Bobot garis dual adalah sama dengan bobot garis batas. Tahap 2: Mencari jalur terpendek antara titik a dan z didalam G* dan gunakan algoritma Dijkstra. Tahap 3: Tentukan cutest K dalam graph G yang sesuai dengan jalur terpendek didalam graph dual G*. Tahap 4: Jika ej∈K maka tetapkan fj=cj. Jumlah dari aliran ini adalah harus maksimum dan sama dengan panjang jalur terpendek. Panjang jalur terpendek inilah yang merupakan harga dari cut minimal dan sekaligus merupakan harga arus maksimum yang dicari. 2.6. Algoritma Dijkstra Algoritma ini digunakan untuk mencari rute (jalur) terpendek dari sumber titik s ke tujuan titik t. Dalam setiap langkah dalam algoritma, beberapa titik diberi label tetap dan lainnya diberi label sementara. Langkap-langkap algoritma Dijkstra adalah sebagai berikut : Langkah 1 : Titik sumber diberi label tetap 0 atau d(s)=0 dan titik diberi label sementara ∞. Langkah 2 : Setiap titik vj yang belum diberi label tetap mendapatkan label sementara yang baru dimana bobotnya diberikan sebagai berikut: Label sementara titik vj=min{label lama vj ,(label lama vi + dij). Dimana vi adalah titik terakhir yang diberi label tetap dalam iterasi sebelumnya dan dij adalah jarak dari garis yang menghubungkan antara titik vi dan vj jika titik vi dan vj tidak ada garis yang menghubungkan maka dij = ∞. Langkah 3 : Mencari label sementara yang minimum diantara semua label sementara dan label sementara yang minimum tersebut menjadi tetap. 12


ISSN 1978-9483

Langkah 4 : Ulangi langkah 2 dan langkah 3 sampai titik tujuan hingga mendapatkan label tetap.

III. PEMBAHASAN KASUS RUTE PASAR MINGGU - HARMONI Arus lalu lintas yang diamati pada masalah ini yaitu pagi hari untuk pada waktu para karyawan yang ditinggal di Pasar Minggu akan bekerja ke kantor di kawasan Harmoni antara jam 07.00 sampai dengan jam 09.00 WIB. Dan arus lalu lintas pada sore hari saat para karyawan yang bekerja di Harmoni akan pulang ke rumah di kawasan Pasar Minggu antara jam 16.00 sampai 18.00 WIB. Bobot dan garis menunjukkan kapasitas jalan per 15 menit. Jalan yang digunakan yaitu jalanjalan besar dan jika terdapat dua jalan yang mempunyai dua jalur yaitu jalur cepat dan jalur lambat maka dalam hal ini digunakan jalur lambat. 3.1. Data Hasil Pengamatan A. Keadaan Pertama : pada pagi hari antara jam 07.00 WIB s/d jam 09.00 dari kawasan pemukiman Pasar Minggu menuju kawasan Perkantoran Harmoni terdapat kapasitas pada masing-masing jalan seperti tabel 3.1. berikut ini : Tabel 3.1. Kapasitas kendaraan dari kawasan Pasar Minggu menuju Perkantoran Harmoni. Aliran Kendaraan di Jalan Pasar Minggu Dewi Sartika MT Haryono Gatot Subroto(Patra Jasa) Gatot Suroto(Balai Sidang) Otista Diponegoro Supomo Dr.Saharjo Imam Bonjol Sudirman Ks Tubun S.Parman Kyai Tapa KH.Hasyim Ashari Thamrin Kebon Sirih Abdul Muis Medan Merdeka Kramat Gunung Sahari Veteran

Kapasitas Kendaraan 369 551 422 334 479 648 331 396 486 348 614 371 661 483 383 207 340 316 573 117 447 631

B. Keadaan kedua : pada pagi sore antara jam 16.00 WIB s/d jam 18.00 dari kawasan perkatoran Harmoni menuju kawasan Pasar Minggu terdapat kapasitas pada masing-masing jalan seperti tabel 3.2. berikut ini : 13


ISSN 1978-9483

Tabel 3.2. Kapasitas kendaraan dari kawasan Perkantoran Harmoni menuju Pasar Minggu Aliran Kendaraan di Jalan KH.Hasyim Ashari Kyai Tapa Abdul Muis Kebon Sirih Ks Tubun Medan Merdeka Thamrin Imam Bonjol Sudirman Diponegoro Dr.Saharjo Supomo Ir.Juanda Gunung Sahari Kramat Matraman Otista MT.Haryono Dewi Sartika Gatot Subroto(Patra Jasa) Gatot Suroto(Balai Sidang) Pasar Minggu

Kapasitas Kendaraan 585 617 316 306 315 979 279 107 344 240 365 301 681 652 192 136 542 528 337 341 702 270

3.2. Pembahasan Arus lalu lintas ini dibua t kedalam model graph. Garis menyatakan jalan didalam kota yang dapat dilalui, titik menyatakan ujung-ujung pertemuan jalan dan bobot masing-masing garis menyatakan kapasitas jalan yaitu banyaknya maksimal kendaraan yang melewati jalan persatuan waktu agar aliran di jalan tersebut lancar. Keadaan Pertama : Kapasitas kendaraan pada pagi hari antara jam 07.00 WIB s/d jam 09.00 dari kawasan pemukiman Pasar Minggu menuju kawasan Perkantoran Harmoni perhatikan Graph pada gambar 1. Untuk pemecahan masalah ini digunakan algoritma max-flow-min-cut melalui beberapa tahapan seperti berikut : Tahap 1: Buat jaringan dual G*=(V * ,E*). Cara membuatnya yaitu dengan menempatkan sebuah titik dari V* pada setiap daerah G, Khusus untuk daerah luar dari G, ditem patkan dua titik dual, sebut a dan z, seberang menyebrang aliran jaringan G tersebut. Garis dari dual dibuat menghubungkan titik dual serta memotong garis batas daerah yang bersangkutan. Bobot garis dual adalah sama dengan bobot garis batas. Dapat dilihat pada gambar 3. Tahap 2: Mencari jalur terpendek antara titik a dan z didalam G* dan gunakan algoritma Dijkstra. Diperoleh jalur terpendek dari a ke z adalah 796 dengan rute yang ditempuh aàcàfàz. Pemberian label tetap dapat dilihat pada gambar 1. Tahap 3: Tentukan cutest K dalam graph G (gambar 1) yang sesuai dengan jalur terpendek didalam graph dual G*(gambar 2),K=(e ac,e cf,efx ) 14


ISSN 1978-9483

Tahap 4: Jika ej∈K maka tetapkan fj=cj , fa=348, f c=331, f f=117 Jumlahnya = 796, Maka jumlah dari aliran ini adalah arus maksimum dan sama dengan panjang jalur terpendek. Hasil Iterasi dengan menggunakan algoritma max-flow -min -cut diperoleh seperti tabel 3. berikut ini : Tabel 3. Hasil iterasi algoritma max-flow-min-cut dari bobot titik a,b,c,d,e,f,g,h dan z. Iterasi a b C d e f g H z 1 # 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ # # 0 369 348 334 476 ∞ ∞ ∞ ∞ 551 648 3 # # # # 0 369 348 334 479 679 ∞ ∞ ∞ 551 348 648 648 4 # # # # # 0 369 348 334 479 679 ∞ ∞ ∞ 551 348 648 648 5 # # # # # # 0 369 348 334 479 679 819 850 ∞ 551 348 648 648 6 # # # # # # # 0 369 348 334 479 679 819 850 796 551 348 1126 648 1310 648 Keadaan kedua : Kapasitas kendaraan pada pagi hari antara jam 16.00 WIB s/d jam 18.00 dari kawasan perkatoran Harmoni menuju kawasan Pasar Min ggu perhatikan Graph pada gambar 3. Untuk pemecahan masalah ini digunakan algoritma max-flow-min-cut melalui beberapa tahapan seperti berikut : Tahap 1: Buat jaringan dual G*=(V * ,E*). Cara membuatnya yaitu dengan menempatkan sebuah titik dari V* pada setiap daerah G, Khusus untuk daerah luar dari G, ditempatkan dua titik dual, sebut p dan y, seberang menyebrang aliran jaringan G tersebut. Garis dari dual dibuat menghubungkan titik dual serta memotong garis batas daerah yang bersangkutan. Bobot garis dual adalah sama dengan bobot garis batas. Dapat dilihat pada gambar 3. Tahap 2: Mencari jalur terpendek antara titik p dan y didalam G* dengan gunakan algoritma Dijkstra. Diperoleh jalur terpendek dari p ke y adalah 532 dengan rute yang ditempuh pàsàwày. Pemberian label tetap dapat dilihat pada gambar 3. 15


ISSN 1978-9483

Tahap 3: Tentukan cutest K dalam graph G (gambar 3) yang sesuai dengan jalur terpendek didalam graph dual G*(gambar 4),K=(e ac,e cf,efx ) Tahap 4: Jika ej∈K maka tetapkan fj=cj, fp=192, fs=204, fw= 136 Jumlahnya = 532, Maka jumlah dari aliran ini adalah arus maksimum dan sama dengan panjang jalur terpendek. Hasil iterasi dengan menggunakan algoritma max-flow-min -cut diperoleh seperti tabel 4. berikut ini : Tabel 4. Hasil iterasi algoritma max-flow-min-cut dari bobot titik a,b,c,d,e,f,g,h dan z Iterasi p q R s t u w X y 1 # 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ # # 0 401 192 ∞ ∞ ∞ ∞ ∞ ∞ 585 652 617 681 2 # # # 0 401 1171 192 471 299 396 ∞ ∞ 585 652 617 681 3 # # # # 0 401 1171 192 471 299 396 924 640 585 652 617 681 4 # # # # 0 401 1171 192 471 299 396 924 532 585 652 640 617 681 5 # # # # # 0 401 1171 192 471 299 396 924 532 585 652 640 617 681

6

# 0

401 585 617

1171

# 192 652 681

# 471

# 299

# 396

924

# 532

V. KESIMPULAN 1. Arus maksimum pada arus lalu lintas dari kawasan Pasar Minggu ke kawasan perkantoran Jalan Harmoni dengan menggunakan algoritma max-flow-min-cut menghasilkan arus maksimum 16


ISSN 1978-9483

pada pagi hari antara jam 07.00 WIB sampai dengan jam 09.00 WIB per 15 menit sebanyak 796 kendaraan, dengan rute aàcàfàz dimana aàc=348, càf=331 dan fàz=117. 2. Arus maksimum pada arus lalu lintas dari kawasan perkantoran Jalan Harmoni ke kawasan Pasar Minggu dengan menggunakan algoritma max-flow -min-cut menghasilkan arus maksimum pada pagi hari antara jam 16.00 WIB sampai dengan jam 18.00 WIB per 15 menit sebanyak 532 kendaraan, dengan rute pàsàwày dimana pàs=192, sàw=304 dan wày=136. Beradanya kendaraan yang banyaknya lebih besar dari arus maksimum tersebut, dapat menimbulkan kemacetan lalu lintas.

DAFTAR PUSTAKA [1] Chachra, Vinod., 1979, Applications of Graph Theory Algorithms, North Holland, New York. [2] Deo, Narsingh., 1987, Graph Theory with Applications to Engineering and Computer Science, Prentice Hall of India Private Limited, New Delhi. [3] Rubiyanti, Sri., 1986, Arus Maksimum pada Jaringan Transportasi, FMIPA-UI, Jakarta. [4] Slamet, Sumantri dan Hendrik Makaliwe, 1991, Matematika Kombinatorik , PT.Elex Media Komputindo, Jakarta [5] Soemin. Agus dan Suryadi Harmanto, 1986, Suatu Aplikasi Graph pada Masalah Perhubungan, Matematika dan Komputer Univesitas Gunadarma. [6] Tarliah, Tjutju dan Ahmad Dimyati,1992, Operations Research : Model-model Pengambilan Keputusan , PT.Sinar Baru Algens indo.

17

ANALISIS KEPADATAN ARUS LALU LINTAS JALAN RAYA DENGAN ALGORITMA MAX FLOW MIN CUT : STUDI KASUS RUTE PASAR MINGGU-HARMONI

Recommend Documents