Studi Kasus Tentang Jaringan Jalan untuk Menentukan Rute Terpendek Di Kota Semarang

Studi Kasus Tentang Jaringan Jalan untuk Menentukan Rute Terpendek Di Kota Semarang
Jaringan transportasi di kota-kota besar seperti halnya kota Semarang pada umumnya masih mempunyai jaringan yang rumit. Orang akan kebingungan untuk menentukan jalan yang harus dilewati agar sampai tempat tujuan yang belum pernah dikunjunginya dan jalan yang akan dilalui menjadi lebih panjang, sehingga dibutuhkan jalan terpendek untuk sampai ke tempat tujuan. Algoritma Floyd-Warshall merupakan algoritma yang digunakan untuk mencari semua lintasan terpendek antara setiap kemungkinan dua titik yang berbeda. Penelitian ini bertujuan untuk mengetahui hasil program simulasi jaringan jalan di kota Semarang dengan menggunakan algoritma Floyd-Warshall dengan Bahasa pemrograman Visual Basic dan membuktikan bahwa penghitungan manual mempunyai hasil yang sama dengan penghitungan dengan simulasi jaringan jalan di kota Semarang dalam mencari lintasan terpendek pada graf. Penentuan lintasan terpendek pada graf yang direpresentasikan dengan mengambil data jalan di kota Semarang yang dilakukan dari tempat-tempat yang telah ditentukan dengan menggunakan algoritma Floyd-Warshall. Jalan yang akan dilalui jalan yang dapat digunakan kedua arah sehingga dapat digambarkan sebagai graf tidak berarah dan berbobot, bobot yang digunakan adalah panjang jalan antara dua tempat, titik merepresentasikan sebuah tempat yang telah ditentukan sebelumnya, dan sisi sebagai jalan yang dilalui. Simulasi algoritma Floyd-Warshall untuk menangani masalah pencarian lintasan terpendek pada suatu graf merupakan hasil dari perancangan dan pembuatan dengan bahasa pemrograman Visual Basic. Simulasi ini dapat menghasilkan lintasan terpendek dan panjang minimum dari titik awal ke titik tujuan pada graf yang telah direpresentasikan ke dalam program simulasi. Dari data jaringan jalan di kota Semarang yang direpresentasikan, ke dalam bentuk graf setelah diuji coba menggunakan simulasi ternyata mempunyai solusi hasil lintasan dan jarak yang sama dengan perhitungan manual. Dengan demikian, simulasi algoritma Floyd-Warshall dalam menangani masalah lintasan terpendek pada suatu graf menggunakan Visual Basic selesai direalisasikan dan dapat diimplementasikan pada permasalahan sehari-hari yang dapat direpresentasikan dalam bentuk graf dan dicari lintasan terpendeknya.

•                         Lintasan Terpendek
Lintasan terpendek merupakan salah satu dari masalah yang dapat diselesaikan dengan graf. Jika diberikan sebuah graf berbobot, masalah lintasan terpendek adalah bagaimana cara mencari sebuah lintasan pada graf yang dapat meminimalkan jumlah bobot sisi pembentuk lintasan tersebut. Misalkan u dan v dua titik di graf G, lintasan (u,v) di G dengan panjang minimum disebut lintasan terpendek (Budayasa, 2007:47). Ada beberapa macam persoalan lintasan terpendek antara lain:
a.         Lintasan terpendek antara dua buah titik tertentu (a pair shortest path)
b.        Lintasan terpendek antara semua pasangan titik (all pairs shortest path)
c.         Lintasan terpendek dari titik tertentu ke semua titik yang lain.
d.        Lintasan terpendek antara dua buah titik yang melalui beberapa titik tertentu (intermediate shortest path)
Beberapa algoritma yang digunakan untuk menyelesaikan persoalan ini adalah algoritma Dijkstra, algoritma Bellman-Ford, dan algoritma Floyd-Warshall. Setiap algoritma penyelesaian persoalan lintasan terpendek memiliki kriteria masing-masing. Dalam penelitian ini peneliti menggunakan Algoritma Floyd-Warshall untuk pencarian lintasan terpendek.





Pada gambar di atas misalkan kota ν1 merupakan kota awal dan kota ν7 merupakan kota tujuan. Dari kota awal sampai kota tujuan dapat dipilih beberapa lintasan sebagai berikut.
ν1 → ν2 → ν3 → ν4 → ν5 → ν7 = 2 + 6 + 3 + 5 + 7 = 23
ν1 → ν2 → ν3 → ν4 → ν6 → ν7 = 2 + 6 + 3 + 6 + 3 = 20
ν1 → ν2 → ν3 → ν4 → ν7 = 2 + 6 + 3 + 6 = 17
ν1 → ν2 → ν3 → ν5 → ν7 = 2 + 6 + 2 + 3 = 13
ν1 → ν2 → ν4 → ν6 → ν7 = 2 + 2 + 6 + 3 = 13
ν1 → ν2 → ν4 → ν5 → ν7 = 2 + 2 + 5 + 7 = 16
ν1 → ν2 → ν4 → ν7 = 2 + 2 + 6 = 10
ν1 → ν2 → ν5 → ν7 = 2 + 3 + 7 = 12
ν1 → ν3 → ν4 → ν5 → ν7 = 4 + 3 + 5 + 7 = 19
ν1 → ν3 → ν4 → ν6 → ν7 = 4 + 3 + 6 + 3 = 16
ν1 → ν3 → ν4 → ν7 = 4 + 3 + 6 = 13
ν1 → ν3 → ν6 → ν7 = 4 + 2 + 3 = 9
Berdasarkan data di atas, lintasan terpendek dari ν1 ke ν7 adalah 9 dengan melewati ν3 dan ν6.

•                         Algoritma Floyd Warshall untuk Graf Berarah
Algoritma yang ditemukan oleh Warshall untuk mencari lintasan terpendek merupakan algoritma algoritma yang sederhana dan mudah implementasinya. Masukan Algoritma Warshall adalah matriks hubung graf berarah berlabel dan keluarannya adalah lintasan terpendek dari semua titik ke semua titik (Siang, 2004). Dalam usaha untuk mencari lintasan terpendek, algoritma Floyd-Warshall memulai iterasi dari titik awalnya kemudian memperpanjang lintasan dengan mengevaluasi titik demi titik hingga mencapai titik tujuan dengan bobot yang seminimum mungkin. Menurut Novandi, sebagaimana dikutip oleh Nur & Setiawan, (2013:21), Algoritma Floyd-Warshall adalah sebuah algoritma analisis graf untuk mencari bobot minimum dari graf berarah. Dalam pengertian lain Algoritma Floyd-Warshall adalah suatu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait. Artinya solusi-solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan solusi lebih dari satu. Algoritma Floyd-Warshall memiliki input graf berbobot (V,E), yang berupa daftar titik (node/verteksV) dan daftar sisi (edge E). Jumlah bobot sisi-sisi pada sebuah lintasan adalah bobot sisi tersebut. Sisi pada E diperbolehkan memiliki bobot negatif, akan tetapi tidak diperbolehkan bagi graf ini untuk memiliki siklus dengan bobot negatif. Algoritma ini menghitung bobot terkecil dari semua sisi yang menghubungkan sebuah pasangan titik dan melakukannya sekaligus untuk semua pasangan titik. Prinsip yang dipegang oleh algoritma Floyd-Warshall adalah prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap (misalnya tahap ke-i) juga optimal.
Algoritma Floyd-Warshall adalah salah satu algoritma dari pemrograman dinamis, yaitu suatu metode yang melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh sebagai suatu keputusan yang saling terkait, artinya solusi-solusi tersebut dibentuk dari solusi yang berasal dari tahap sebelumnya dan ada kemungkinan lebih dari satu solusi. Algoritma Floyd-Warshall juga membandingkan semua kemungkinan lintasan pada graf untuk setiap sisi dari semua titik. Algoritma Floyd-Warshall menerapkan pemrograman dinamis sehingga lebih menjamin keberhasilan penemuan solusi optimum untuk kasus penemuan lintasan terpendek.
Peran pemrograman dinamis yang mencoba untuk memberikan solusi yang memiliki pemikiran terhadap konsekuensi yang ditimbulkan dari pengambilan keputusan dari suatu tahap. Prinsip yang dipegang oleh pemrograman dinamis adalah prinsip optimalitas, yaitu jika solusi total optimal, maka bagian solusi sampai suatu tahap juga optimal.
Algoritma Floyd-Warshall merupakan salah satu jenis algoritma all pair shortest, yaitu mencari lintasan terpendek untuk semua pasangan titik yang ada pada sebuah graf. Input dari algoritma ini berupa graf berbobot dan berarah. Seperti algoritma bellman Ford, algoritma ini juga dapat menghitung sisi yang berbobot negatif. Cara kerja algoritma ini dapat digambarkan dengan menggunakan matriks.

Sumber :
http://lib.unnes.ac.id/22304/