Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
GAGASAN KONSEP KONEKTIVITAS MAKSIMAL KASUS JARINGAN JALAN LUAR KOTA Hitapriya Suprayitno1, Indrasurya B. Mochtar, Achmad Wicaksono Jurusan Teknik Sipil. Institut Teknologi Sepuluh Nopember (ITS). Surabaya Email:
[email protected]
ABSTRAK Salah satu komponen Kualitas Jaringan Transportasi adalah Konektivitas Maksimal. Konektivitas Maksimal terjadi bila semua titik didalam jaringan sudah terhubung satu dengan yang lain dan tidak mungkin dibuat hubungan baru. Konektivitas Maksimal bisa dianalisa dengan menggunakan Graf dari Teori Graf. Taaffe, didalam bidang Ilmu Geografi pernah merumuskan hal ini. Untuk kasus Jaringan Planar, rumusan yang telah dibuat tersebut dirasa tidak tepat. Oleh karena itu diperlukan sebuah perumusan baru. Penelitian ini ditujukan untuk menyusun perumusan Konektivitas Maksimal bagi Kasus Jaringan Planar Tak Berarah Tak Berbobot. Perumusan dilakukan dengan melakukan percobaan terhadap beberapa alternatif bentuk jaringan planar. Identifikasi Konektivitas Maksimal didapatkan berdasar pengamatan visual. Rumusan Definisi Konektivitas Maksimal disusun berdasarkan percobaan ini. Rumusan Definisi Konektivitas Maksimal telah berhasil disusun. Nilai Konektivitas Maksimal adalah Nilai Konektivitas Maksimal Absolut dikurangi dengan Jumlah Ruas Berlebih (Ruas Redundant). Kondisi Konektivitas Absolut tercapai bila setiap Titik didalam Jaringan terhubung secara langsung dengan seluruh Titik yang lain didalam Jaringan. Tergantung dari bentuk Tata Letak Titik Jaringan, pada Kondisi Konektivitas Maksimal Absolut bisa terjadi Ruas-Ruas Redundant. Rumusan ini berbeda dari rumusan yang telah disusun oleh Taaffe. Kata kunci: jaringan transportasi, konektivitas maksimal, graf.
PENDAHULUAN Suatu upaya awal untuk menyusun Ukuran Kualitas Konektivitas Jaringan Transportasi berbasis Teori Graf telah berhasil disusun di Amerika Serikat didalam kalangan Ilmu Geografi. Percobaan ini telah menghasilkan beberapa Ukuran Kualitas Konektivitas Jaringan berikut ini : Konektivitas Minimal, Konektivitas Maksimal, Indeks Gama serta Tipe Jaringan (Taffee, Gauthier & Kelly – 1996). Sebuah percobaan pemakaian konsep ini untuk kasus jaringan jalan sudah pernah dilakukan. Hasil percobaan menunjukkan bahwa Rumusan Konektivitas Maksimal Taaffe masih agak primitif dan masih kurang benar (Suprayitno – 2008). Oleh karena itu diperlukan suatu upaya untuk memperbaiki Konsep Konektivitas Maksimal tersebut. Beberapa referensi mengenai Teori Graf sudah berhasil dikumpulkan. Referensireferensi yang ada tidak mengandung pembahasan mengenai konsep konektivitas maksimal tersebut (Bondy & Murty – 1982; Chevalier & Hirsch – 1980; Dimyati & Dimyati – 1994; Goujet & Nicolas – 1988, Suprayitno - 2008). Tulisan ini membahas upaya penulis untuk menyusun Gagasan Konsep dan Perhitungan Konektivitas Maksimal berbasis Konektivitas Maksimal Absolut.
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Catatan : Pada tulisan ini digunakan istilah “graf” dan “jaringan”. Istilah “graf” digunakan untuk menyebutkan sebuah jaringan didalam konteks Teori Graf, sedangkan istilahnya satunya digunakan untuk menyebutkan jaringan secara umum yang bukan berada dalam konteks Teori Graf. TINJAUAN PUSTAKA Teori Graf Teori Graf adalah terjemahan dalam Bahasa Indonesia oleh penulis dari istilah Graph Theory dalam Bahasa Inggris atau Theori de Gaphe dalam Bahasa Perancis. Teori Graf adalah salah satu Cabang Ilmu Matematika yang membahas segala sesuatu tentang Graf (Bondy & Murty – 1982; Chevalier & Hirsch – 1980; Dimyati & Dimyati – 1994; Goujet & Nicolas - 1988). Graf dalam Teori Graf didefinisikan sebagai sebuah kumpulan titik (vertex) dan busur (edge). Setiap busur berujung pada dua buah titik. Akan tetapi, tidak setiap titik harus terhubung oleh busur dengan titik yang lain. Pada Teori Graf posisi relatif antar titik dan antar busur tidak penting atau dengan kata lain tidak diperhitungkan. Dengan demikian sebuah Graf bisa direpresentasikan secara grafis dalam beberapa bentuk visual grafis yang berbeda (Bondy & Murty – 1982; Chevalier & Hirsch – 1980; Goujet & Nicolas - 1988). Secara umum Graf bisa direpresentasikan dalam bentuk Formulasi Matematis sebagai berikut. Sebuah Graf G adalah sebuah triple berurutan {V(G), E(G), G} yang mengandung satu himpunan titik terisi V(G), satu himpunan busur E(G) dan sejumlah fungsi kejadian (incidence function) G yang merepresentasikan dua titik ujung sebuah busur. Bila e adalah sebuah busur yang menghubungkan titik u dengan titik v, maka G(e) = uv (Bondy & Murty – 1982). Suatu Graf bisa direpresentasikan melalui 4 bentuk representasi utama : secara matematis, secara grafis, dengan menggunakan Matrik Kejadian (Incidence Matrix) atau dengan menggunakan Matrik Hubungan (Adjacency Matrix) (Bondy & Murty – 1982). Istilah ”pohon” merupakan terjemahan penulis dari istilah ”tree” dalam Graph Theory. Berikut ini disampaikan definisi Pohon Graf dalam Bahasa Inggris : ”A tree is a connected acyclic graph. An acyclic graph is one that contains no cycle” . Terkait dengan hal ini terdapat dua buah Teorema penting. Kedua teorema tersebut disampaikan dalam Bahasa Inggris sebagai berikut (Bondy & Murty – 1982). Teorema 1. ”In a tree, any two vertices are connected by a unique path”. Teorema 2. ”If G is a tree, then = – 1”. Konsep Konektivitas Maksimal Taaffe – Jaringan Planar Didunia Ilmu Geografi di Amerika Serikat telah dikembangkan Konsep Konektivitas Jaringan Transportasi berbasis Teori Graf. Konsep tersebut, pada tulisan ini, disebut sebagai Konsep Konektivitas Taaffee. Didalam Konsep ini dikenal adanya beberapa konsep karakteristik konektivitas jaringan : Konektivitas Minimal, Konektivitas Maksimal, Indeks Gamma, Tipe Bentuk Jaringan. Konsep tersebut disusun masing-masing untuk kasus Jaringan Planar dan kasus Jaringan Non Planar (Taaffe, Gauthier & O’Kelly – 1996). Rumus Konektivitas Minimal dan Maksimal untuk Kasus Jaringan Planar disampaikan sebagai berikut (Taaffe, Gauthier & O’Kelly – 1996). Kmin = (T – 1)
ISBN : 978-979-99735-9-7 B-10-2
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Kmax = dimana : Kmin : Kmaks : T
3 (T - 2) nilai konektivitas minimal nilai konektivitas maksimal : jumlah titik
Penelitian Terdahulu Penelitian awal penyusunan Metoda Penilaian Jaringan Jalan dengan menggunakan Konsep Konektivitas Graf Taaffe telah dilakukan. Penelitian ini menghasilkan dua macam Nilai Indeks Kualitas Jaringan, yang keduanya diperlukan untuk menilai Kualitas Jaringan. Hasil penelitian menunjukkan bahwa Teori Graf dan Konsep Konektivitas Taaffe mengandung kelemahan, keduanya tidak bisa merepresentasikan Karakteristik Jaringan Jalan secara baik. Salah satu kesimpulan penting lain adalah bahwa rumusan Konektivitas Maksimal masih kurang tepat (Suprayitno – 2008). KONSEP KONEKTIVITAS MAKSIMAL BARU Kritik Konsep Konektivitas Maksimal Taaffe – Jaringan Planar Konsep Konektivitas Taaffe disusun dengan mengadopsi Konsep Teori Graf secara langsung, tanpa melakukan penyesuaian terhadap Karakteristik Utama sebuah Jaringan Transportasi. Konsep ini mencampur-adukan pengertian planar pada Graf dan planar pada Jaringan Jalan. Jaringan Jalan oleh konsep ini digolongkan sebagai Jaringan Planar, sehingga segala ketentuan tentang Jaringan Planar pada Teori Graf dianggap berlaku pada Jaringan Jalan. Konsep Konektivitas Maksimal pada Jaringan Jalan diturunkan langsung dari Konsep Graf Planar. Oleh karena itu pada kasus Konsep Konektivitas Maksimal Jaringan Transportasi Planar terdapat beberapa kelemahan sebagai berikut. Jaringan Transportasi Planar bukan berarti Tidak Boleh Berpotongan Konsep ini disusun dengan anggapan, seperti halnya pada Teori Graf, bahwa Ruas pada Jaringan Planar tidak boleh saling berpotongan. Pada kenyataannya, pada Kasus Jaringan Jalan, Ruas-Ruas Planar boleh saling berpotongan.
Jaringan Jalan
Teori Graf
Gambar 1. Jaringan Planar Boleh dan Tidak Boleh Berpotongan
ISBN : 978-979-99735-9-7 B-10-3
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Busur Redundant tidak diEliminasi Disebabkan oleh prinsip penyusunan konsepnya, pada Konsep Taaffe bisa terjadi Busur Redundant. Busur ini tidak diEliminasi, sehingga pada Jaringan Tinjauan bisa terjadi kelebihan Busur. Penjelasan mengenai hal ini bisa disampaikan melalu Gambar 2 sebagai berikut. Pada Gambar 2 terdapat 2 Jaringan dengan Jumlah dan Tata Letak Titik yang sama persis. Pada kasus Teori Graf keberadaan Busur Merah dianggap wajar. Sedangkan pada Kasus Jaringan Jalan Busur Merah ini harus dihilangkan karena hampir berimpit dengan dua ruas yang berdekatan.
Teori Graf
Jaringan Jalan
Gambar 2. Busur Redundant Tidak diEliminasi dan diEliminasi
Tata Letak Titik Tidak Diperhitungkan Dalam Teori Graf, Titik tidak mempunyai koordinat. Sebaliknya pada Jaringan Jalan, Koordinat Titik merupakan salah satu karakteristik penting bagi sebuah Jaringan. Hal ini bisa digambarkan melalui Gambar 3 sebagai berikut. Pada Teori Graf, karena Titik dianggap tidak mempunyai koordinat, maka Jaringan 1 dianggap sama dengan Jaringan 2. Sedangkan pada Jaringan Jalan, karena Koordinat Titik mutlak harus ada, maka Jaringan 1 sama sekali tidak sama dengan Jaringan 2.
Jaringan 1
Jaringan 2 Gambar 3. Tata Letak Titik Harus Diperhitungkan
Konsep Konektivitas Maksimal Baru Konektivitas Maksimal Baru diturunkan dari Reduksi terhadap Konektivitas Maksimal Absolut. Reduksi Ruas perlu dilakukan karena pada Jaringan terdapat ruasruas yang terasa berlebih. Keterangan mengenai hal ini akan disampaikan pada beberapa uraian dibawah ini. Dengan demikian Konektivitas Maksimal bisa dirumuskan sebagai berikut. Kmaks = Kmaks-abs - Rredundant
ISBN : 978-979-99735-9-7 B-10-4
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
dimana Kmaks Kmaks-abs Rredundant
: :
: nilai konektivitas maksimal nilai konektivitas maksimal absolut jumlah ruas berlebih
Konektivitas Maksimal Absolut Konektivitas Maksimal Absolut adalah nilai Konektivitas Maksimal yang tertinggi yang bisa dicapai oleh suatu Jaringan Titik dengan mengabaikan seluruh kendala konektivitas jaringan yang melekat pada jaringan yang ditinjau. Kendala yang dimaksud bisa berupa sifat planar atau non planar jaringan, koordinat titik, jarak langsung antar titik dan kendala yang lain. Dengan demikian Konektivitas Absolut terjadi bila setiap titik didalam jaringan terhubung secara langsung ke semua titik sisanya. Dengan demikian Rumus Konektivitas Maksimal Absolut yang diusulkan berbentuk seperti sebagai berikut. Kmaks,abs = T (T - 1) / 2 dimana : Kmaks,abs : nilai konektivitas maksimal absolut T : jumlah titik didalam jaringan Contoh sebuah Jaringan dengan kondisi Konektivitas Maksimal Absolut disampaikan pada Gambar 4 sebagai berikut. Dengan Jumlah Titik Jaringan sama dengan 5, maka setiap titik didalam jaringan terhubung oleh 4 buah ruas.
Gambar 4. Contoh Jaringan dengan kondisi Konektivitas Maksimal Absolut
Ruas Redundant Kalau diperhatikan dengan baik Gambar 4 diatas, tampak terlihat adanya ruasruas yang berlebihan, atau ruas-ruas redundant. Tiga buah ruas yang diberi warna merah terasa berlebihan (Gambar 5). Ketiga ruas ini sangat dekat dan hampir berimpit dengan dua ruas penghubung titik antara. Pada dunia Jaringan Jalan, ruas langsung yang sangat dekat dengan dua ruas penghubung titik antara tidak pernah dibangun. Oleh karena itu ketiga ruas merah ini tidak perlu diadakan. Ketiga ruas merah ini disebut sebagai Ruas Redundant atau Ruas Berlebih. Gambaran tentang Ruas Redundant ini disampaikan pada Gambar 5 Ruas Redundant pada Jaringan sebagai berikut.
ISBN : 978-979-99735-9-7 B-10-5
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Gambar 5. Ruas Redundant pada Jaringan
Konektivitas Maksimum Mengingat penjelasan tentang R redundant diatas tersebut, bisa disimpulkan bahwa Nilai Konektivitas Maksimum merupakan Nilai Konektivitas Maksimum Absolut dikurangi oleh Jumlah Ruas Redundant. Oleh karena itu Nilai Konektivitas Maksimum bisa dirumuskan sebagai berikut. Kmaks = Kmaks-abs – Rred dimana : Kmaks = Nilai Konektivitas Maksimum Kmaks-abs = Nilai Konektivitas Maksimum Absolut Rred = Jumlah Ruas Redundant. Gambaran suatu Kondisi Konektivitas Maksimum disampaikan melalui Gambar 6 Jaringan dengan Konektivitas Maksimum sebagai berikut. Pada Jaringan ini ketiga Ruas Berlebih telah dihapuskan.
Gambar 6. Jaringan dengan Konektivitas Maksimum
Ruas Redundant Sesuai dengan uraian pada sub-bab diatas, Ruas Redundant atau Ruas Berlebih bisa didefinisikan sebagai berikut. Ruas Redundant atau Ruas Berlebih adalah sebuah ruas yang menghubungkan dua buah titik dan ruas tersebut hampir berimpit dengan dua buah ruas yang menghubungkan kedua titik tersebut dengan sebuh titik antara kedua titik utama tersebut. Gambaran Ruas Redundant atau Ruas Berlebih disampaikan pada Gambar 7 Ruas Redundant sebagai berikut.
ISBN : 978-979-99735-9-7 B-10-6
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Gambar 7. Contoh Ruas Redundant atau Ruas Berlebih
UJI COBA KONSEP KONEKTIVITAS MAKSIMAL Kasus Uji Coba Konsep Konektivitas Maksimal baru diatas perlu unutk diuji kebenarannya. Untuk itu perlu dilakukan pengujian konsep dengan menggunakan Kasus Uji Coba tertentu. Kasus Uji Coba yang akan digunakan berupa sebuah Jaringan dengan 6 buah titik dan 8 ruas. Kasus Uji Coba disampaikan pada Gambar 8 sebagai berikut.
Gambar 8. Kasus Uji Coba
Perhitungan Nilai Konektivitas Maksimal Absolut Nilai Konektivitas Maksimal Absolut bisa dihitung dengan menggunakan Rumus yang sudah didefinisikan didepan. Kmaks-abs = T (T - 1) / 2 = 6 (6 – 1 ) / 2 = 15 Gambaran Jaringan pada kondisi Konektivitas Maksimum Absolut disampaikan pada Gambar 9 sebagai berikut.
ISBN : 978-979-99735-9-7 B-10-7
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Gambar 9. Jaringan pada kondisi Kmaks-abs
Perhitungan R Redundant Identifikasi Ruas Berlebih atau Ruas Redundant dilakukan secara visual. Setiap ruas yang posisinya hampir berimpit dengan 2 ruas penghubung titik antara dikatagorikan sebagai Ruas Redundant. Pada Jaringan Uji Coba bisa ditemui 3 buah Ruas Redundant. Gambaran Ruas Redundant disampaikan pada Gambar 10 sebagai berikut.
Gambar 10.Ruas Redundant
Perhitungan K Maksimal Selanjutnya Konektivitas Maksimal bisa dihitung dengan menggunakan Rumus Perhitungan yang sudah didefinisikan diatas. Kmaks = Kmaks-abs – Rred = 15 – 3 = 12 Gambaran Konektivitas Maksimal disampaikan pada Gambar 11 Konektivitas Maksimal sebagai berikut. Pada Gambar 8 bisa dilihat bahwa Jaringan berada pada kondisi Konektivitas Maksimal dan Jumlah Ruas adalah 12.
ISBN : 978-979-99735-9-7 B-10-8
Prosiding Seminar Nasional Manajemen Teknologi XI Program Studi MMT-ITS, Surabaya 6 Pebruari 2010
Gambar 11. Konektivitas Maksimal
KESIMPULAN Penelitian ini, yang merupakan bagian dari Penyusunan Disertasi tentang Penyusunan Metoda Penilaian Kualitas Jaringan Jalan, telah menghasilkan beberapa kesimpulan pokok sebagai berikut : Konsep Konektivitas Taaffe terbukti tidak tepat untuk digunakan bagi Analisis Jaringan Jalan. Konsep Konektivitas Maksimal baru telah berhasil dirumuskan sebagai berikut : Kmaks = Kmaks-abs - Rred
DAFTAR PUSTAKA Bondy, J.A. & Murty, U.S.R. (1982). Graph Theory with Applications. Fifth Printing. North-Holland. New York. Chevalier, A. & Hirsch, G. (1980). Méthodes Quantitative pour le Management : Finance, Marketing, Production. Entreprise Moderne d’Édition. Paris. Dimyati, T.T. & Dimyati A. (1994). Operation Research – Model-Model Pengambilan Keputusan. Sinar Baru Algesindo, Bandung. Goujet, C. & Nicolas, C. (1986). Mathématiques Apliquées – Probabilités, Initiation à la Recherche Operationnelle. Troisième Édition. Masson. Paris. Suprayitno, Hitapriya (2008). “Penggunaan Konsep Konektivitas Teori Graf sebagai Pijakan bagi Upaya Penyusunan Metoda Penilaian Kualitas Jaringan Jalan Primer”. Seminar Nasional Teknologi Infrastruktur Perkotaan, Surabaya, 12 Juli 2008. Program Diploma Teknik Sipil, Institut Teknologi Sepuluh Nopember (ITS). Surabaya. Taaffe, E.J., Gauthier, H.L. & O’Kelly, M.E. (1996). Geography of Transportation. Second Edition. Prentice Hall. New Jersey.
ISBN : 978-979-99735-9-7 B-10-9