Shortest Path Problems

oleh : Dicky Rahardiantoro


Jaringan (Network) adalah suatu susunan garis edar (path) yang menghubungkan berbagai titik, di mana satu barang atau lebih bergerak dari satu titik ke titik lain atau setiap orang akrab dengan berbegai jaringan seperti system jalan tol, jaringan telepon, jaringan rel kereta api, dan jaringan televisi.

Network model sangatlah aplikatif untuk diterapkan ke banyak permasalahan pengambilan keputusan yang dapat dimodelkan sebagai model optimasi jaringan dan penyelesaian problem yang efisien dan efektif.

Jaringan diilustrasikan sebagai diagram yang terdiri dari dua komponen penting : simpul (nodes) dan cabang (branches). Simpul melambangkan titik-titik persimpangan. Cabang menghubungkan simpul-simpul tersebut dan mencerminkan arus satu titik ke titik lain dalam jaringan tersebut. Simpul-simpul dalam diagram jaringan dilambangkan dengan lingkaran dan cabang dilambangkan dengan garis yang menghubungkan simpul-simpul tersebut.

Jaringan yang ditunjukkan pada gambar di atas memiiki empat simpul dan empat cabang. Simpul yang melambangkan Atlanta disebut sebagai titik awal (origin) dan tiga simpul sisanya dapat merupakan tujuan, tergantung dariapa yang ingin kita tentukan dari jaringan tersebut. Nilai-nilai yang tertera pada tiap cabang dapat menunjukkan tentang informasi jarak, lamanya waktu, atau biaya yang diberikan pada masing-masing cabang.

Pada prinsipnya, tujuan dari pemodelan jaringan adalah untuk memperoleh solusi jarak terpendek, waktu tersingkat dan biaya terendah di antara titik-titik dalam jaringan.



MASALAH RUTE TERPENDEK

Masalah rute terpendek (Shortest Path Problems) berguna untuk menentukan jarak tersingkat antara titik awal dan beberapa titik tujuan. Sebagai contoh, sebuah perusahaan jasa pengangkutan barang disewa untuk memindahkan furnitur dan perlengkapan kantor milik Istec Corporation ke markas besarnya yang baru. Untuk memindahkan barang-barang tersebut, perusahaan jasa yang disewa dapat melalui beberapa jalur antar kota sebagaimana yang digambarkan pada diagram jaringan berikut ini.



Agar perjalanan lebih efisien, maka jalur manakah yang jarak tempuhnya lebih pendek ?

Shorthes Route Algorithm

Langkah-1, berilah node-1 label permanen [0,S]. Angka pertama pada permanen label tersebut menunjukkan jarak antar node, sedangkan angka kedua menunjukkan nomer node sebelumnya. Node-1 tidak memiliki node pendahulu (node sebelumnya) sehingga label S menunjukkan bahwa ia adalah node awal.

Langkah-2, hitunglah tentatif label (d,n) terhadap semua node yang dapat dicapai langsung dari node 1. Label d menunjukkan jarak suatu node dengan node sebelumnya dan n adalah node sebelumnya.

Langkah-3, identifikasi seluruh node dengan tentatif label yang menunjukkan jarak paling kecil dengan node sebelumnya. Katakanlah node tersebut sebagai node-k, maka ubahlah tentatif label pada node-k tersebut menjadi permanen label dengan menggunakan simbol [ , ]. Jika semua node telah memiliki permanen label maka beralihlah ke langkah ke-5

Langkah-4, berilah tentatif label (t,k) pada node yang dapat dicapai langsung dari node-k. Label t menunjukkan jarak kumulatif sedangkan k adalah node sebelumnya yang telah memiliki permanen label. Bila suatu node telah memiliki tentatif label maka gunakan tentatif label yang memiliki jarak terpendek

Langkah-5, lakukan langkah-langkah di atas sampai seluruh tetatif label pada tiap node memiliki jarak paling pendek dengan node sebelumnya, sehingga tentatif label tersebut menjadi permanen label

Penerapan Shortest Route Algorithm pada proses pemindahan barang-barang Istec Corporation ke kantor barunya.

Label [0,S] diberikan pada node-1. Node 2, 3 dan 4 adalah node yang dapat dicapai langsung dari node-1. Masing-masing diberi tetatif label (100,1) , (50,1) dan (40,1).

Karena node-4 memiliki jarak paling pendek dari node-1 maka tentatif label node-4 berubah menjadi permanen label [40,1].


Node 3 dan 6 adalah node yang dapat dicapai langsung dari node-4 yang telah memiliki permanen label. Total jarak node 4 ke node 3 adalah sebesar 60 dan total jarak node 4 ke node 6 adalah 140, sehingga node 6 diberi tentatif label (140,4) dan node 3 diberi tambahan 1 tentatif label (60,4).

Node 3 memiliki 2 tentatif label, yaitu : (50,1) dan (60,4), padahal tiap node hanya boleh memiliki 1 tentatif label. Sehingga tentatif label yang dipilih untuk node-3 adalah (50,1).

Karena tidak ada lagi jalur yang dapat ditempuh menuju node-3 selain dari node-1 dan node-4, maka tentatif label (50,1) sudah menunjukkan jarak terpendek, sehinga tentatif label tersebut dapat diubah menjadi permanen label [50,1].


Untuk mencapai node-2 hanya terdapat satu jalur yaitu melalui node 1 sehingga tentatif label pada node-2 dapat diubah menjadi permanen label [100,1].

Node-5 dapat dicapai oleh node-2 dan node-3, sehingga node-5 dapat memiliki tentatif label (200,2) dan (150,3). Tentatif label yang dipilih untuk node-5 adalah (150,3). Karena tidak terdapat lagi suatu node yang dapat mencapai node-5 dengan jarak yang lebih pendek dari 150 maka tentatif label berubah menjadi permanen label [150,3].



Lakukan proses tersebut sampai seluruh node memiliki tentatif label dan seluruh tentatif label dapat berubah menjadi permanen label. Pada iterasi akhir diperoleh hasil sebagai berikut :


Hasil tersebut menunjukkan bahwa untuk mencapai node-13 jarak terpendeknya adalah melalui node-10, 7, 5, 3, 1. Artinya perjalanan dari node-1 (kantor lama) ke node-13 (kantor baru) hendaknya dapat melalui rute 1 – 3 – 5 – 7 – 10 – 13 dengan jarak total sebesar 430 miles.





3 komentar:

Sem Firdaus said...

visit back gan . . .

Sem Firdaus said...

visit back gan

Starbio Ternak untuk Sapi , Kambing dan Kerbau said...

saya senang berkunjung ke blog anda
banyak info info menarik nya

Post a Comment

Tanggapan, pesan atau pertanyaan hendaknya disertai dengan identitas (minimal mengisi NAMA dgn men-select bagian Comment as dengan "Name/URL"). Terima kasih

(c) DickyRahardi.Com™, 2006