Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
PENENTUAN RUTE TERPENDEK MENUJU KAMPUS MENGGUNAKAN ALGORITMA DYNAMIC PROGRAMMING
Jumadi Email:
[email protected] Jurusan Teknik Informatika, Fakultas Sains dan Teknologi Universitas Islam Negeri Sunan Gunung Djati Jl. A.H. Nasution 105 Cipadung, Cibiru Kota Bandung ABSTRAK Kepadatan kendaraan bermotor, dapat dirasakan pada jalan-jalan di Kota Bandung, terutama di daerah dan jam-jam tertentu. Hal ini, yang mendorong perlu dilakukan penelitian untuk menentukan lintasan terpendek dari daerah Sukamukti Kecamatan Katapang Kabupaten Bandung, menuju ke Kampus UIN di daerah Kecamatan Cibiru Kota Bandung. Seperti yang telah diketahui, bahwa jalan-jalan di Kota Bandung terdapat banyak alternatif jalan dengan karakter masing-masing jalan yang berbeda. Karakter jalan yang ada, diantaranya adalah kepadatan, kondisi fisik jalan dan ukuran lebar jalan. Dengan karakter jalan yang ada, maka dapat diasumsikan bahwa setiap jalan memiliki lama tempuh rata-rata. Nilai rata-rata ini, dijadikan sebagai biaya tempuh jalan tersebut. Dengan menggunakan algoritma Dynamic Programming, dapat diketahui rute terbaik dari Tempat Tinggal menuju Kampus UIN Bandung.
dari teknik ini adalah membagi satu
PENDAHULUAN Sebagai
suatu
programming
konsep,
dynamic
luwes
dibanding
lebih
kebanyakan model dan metode matematik dalam riset operasi. Tidak seperti Linier Programming, dalam masalah dynamic programming matematika
tidak yang
ada
formulasi
baku.
Dynamic
programming merupakan suatu teknik matematika
yang
mengoptimalkan
digunakan proses
untuk
pengambilan
keputusan secara bertahap ganda. Dalam teknik ini, keputusan yang menyangkut suatu
persoalan
dioptimalkan
secara
bertahap dan bukan secara sekaligus. Inti
persoalan atas beberapa bagian persoalan yang dalam dynamic programming disebut sebagai
tahap,
kemudian
dipecahkan.
Keputusan optimal atas seluruh tahap yang kemudian
disebut
sebagai
kebijakan
optimal. Penerapan pendekaan dynamic programming telah dikabarkan mampu untuk menyelesaikan berbagai masalah : alokasi,
muatan
budgeting,
(knapsack),
pengawasan
capital
persediaan,
penentuan jalur terpendek, dan lain-lain. (Nurhidayati, 2010) Dalam
penelitian
Programming
ini,
digunakan
Dynamic untuk 214
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
menentukan rute terpedek dari berbagai
Karakteristik
jalan yang memiliki keterhubungan satu
dengan Program Dinamis:
jalan dengan jalan yang lainnya dan membentuk graph. Daerah yang dijadikan objek penelitian ini, adalah jalan-jalan yang
penyelesaian
persoalan
1. Terdapat sejumlah berhingga pilihan yang mungkin,
menghubungkan Perumahan Taman Bunga
2. Solusi pada setiap tahap dibangun dari
Sukamukti
hasil solusi tahap sebelumnya,
Kecamatan
Katapang
Kabupaten Bandung, dengan Kampus UIN Suanan Gunung Djati di Kecamatan Cibiru Kota Bandung. Secara garis besar jalan yang dihubungkan adalah sebagian jalan-
3. Kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.
jalan yang ada di daerah Bandung Selatan, dengan sebagian jalan-jalan di daerah Bandung Timur, dengan melalui sebagian jalan-jalan yang ada di Bandung Tengah.
Perbedaan
Algoritma
Greedy
dengan
Program Dinamis terletak pada rangkain keputusan. Pada Algoritma Greedy, hanya satu rangkaian keputusan yang dihasilkan.
DASAR TEORI
Sedangkan pada Program Dinamis, lebih
Program Dinamis (dynamic programming)
dari
satu
rangkaian
merupakan metode pemecahan masalah
dipertimbangkan.
keputusan
yang
dengan cara menguraikan solusi menjadi sekumpulan (stage), sedemikian sehingga solusi dari persoalan dapat dipandang dari
Pada
serangkaian
saling
keputusan yang optimal dibuat dengan
berkaitan. Istilah Program Dinamis muncul
menggunakan prinsip optimalitas, yaitu jika
karena kecederungan metode ini dalam
solusi total optimal maka bagian solusi
menganalisa dan mendokumentasikan hasil
sampai tahap ke-k juga optimal.
perhitungan
keputusan
pada
yang
setiap
tahapnya
menggunakan beberapa tabel sehingga perhitungan solusi mudah untuk diketahui secara detail.
program
dinamis,
rangkaian
Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. Ongkos pada tahap k+1 adalah ongkos
215
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
yang dihasilkan pada tahap k ditambah ongkos dari tahap k ke tahap k + 1.
1
ck , k 1
…
2
k
k
…
n
Gambar 1. Prisip Optimalitas (Munir, 2013)
Karakteristik Persoalan Program Dinamis, adalah
4. Ongkos (cost) pada suatu tahap meningkat
1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan. 2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan
dengan
tahap
tersebut. Secara umum, status merupakan
bermacam
kemungkinan masukan yang ada pada tahap tersebut. 3. Hasil diambil
dari keputusan pada
setiap
yang tahap
ditransformasikan dari status yang bersangkutan ke status berikutnya berikutnya.
pada
tahap
secara
(steadily)
teratur dengan
bertambahnya jumlah tahapan. 5. Ongkos
pada
suatu
tahap
bergantung pada ongkos tahaptahap yang sudah berjalan dan ongkos pada tahap tersebut. 6. Keputusan terbaik pada suatu tahap
bersifat
independen
terhadap
keputusan
yang
dilakukan
pada
tahap
sebelumnya. 7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1. 8. Prinsip
optimalitas
berlaku
pada persoalan tersebut. 216
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
tahap k +1 = (ongkos yang dihasilkan pada Ada 2 (dua) pendekatan pada Program Dinamis, yaitu 1. Program Dinamis maju (forward atau updown)
tahap k ) + (ongkos dari tahap k ke tahap k + 1), k = 1, 2, …, n – 1 Sedangkan Program
prinsip
optimalitas
Dinami
pada
mundur
adalah
ongkos pada tahap k =
(ongkos
2. Program Dinamis mundur (backward
yang dihasilkan pada tahap k + 1)
atau bottom-up).
(ongkos dari tahap k + 1 ke tahap k ),
+
k = n, n – 1, …, 1 Misalkan x1, x2, …, xn menyatakan peubah (variable) keputusan yang harus dibuat
Langkah-langkah
masing-masing untuk tahap 1, 2, …, n.
Algoritma
Maka,
sebagai berikut
1. Program dinamis maju. Program
seterusnya
sampai
tahap
struktur
adalah
solusi
2. Definisikan secara rekursif nilai solusi optimal. 3. Hitung nilai solusi optimal secara
x1, x2, …, xn. 2. Program dinamis mundur. Program
Dinamis,
optimal.
n.
Runtunan peubah keputusan adalah
Program
1. Karakteristikkan
dinamis bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan
Pengembangan
maju atau mundur. 4. Konstruksi solusi optimal.
dinamis bergerak mulai dari tahap n, terus mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap 1. Runtunan peubah keputusan adalah xn, xn-1, …, x1.
Pada
prinsipnya
berdasarkan
pada
Progam Graf
Dinamis multitahap
(multistage graph). Tiap simpul di dalam graf tersebut menyatakan status, sedangkan V1, V2, … menyatakan tahap.
Dengan demikian, prinsip optimalitas pada Program Dinamis maju adalah ongkos pada
217
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
V2
V1
V3
V4
V5
2 9 6 3 7
12
10
1
4 8 11
5
Gambar 2. Graph Multitap (Munir, 2013) Pada persoalan Graph Multitahap dikaitkan dengan Program Dinamis, dikenal:
Keterangan:
1. Tahap (k) adalah proses memilih
simpul
a. xk
tujuan
tahap k (k = 2, 3, 4).
berikutnya (Gambar 2, ada 5 b.
tahap). 2. Status (s) yang berhubungan dengan
masing-masing
tahap adalah simpul-simpul
: peubah keputusan pada
c
sxk
: bobot (cost) sisi dari s ke xk
c. fk(s, xk) : total bobot lintasan dari s ke xk d.
fk(s) : nilai minimum dari fk(s, xk)
di dalam graf. Relasi
rekurens
berikut
menyatakan
lintasan terpendek dari status s ke x4 pada
Tujuan
Program
Dinamis
Maju
tahap k:
mendapatkan f4(12) dengan cara mencari f1(s), f2(s), f3(s) terlebih dahulu.
f1 ( s) cx1s (basis)
PEMBAHASAN
f k (s) min{c xk s f k 1 ( xk )} , xk
(rekurens) k = 2, 3, 4
Diketahui perjalanan
dari Sukamukti
menuju kampus UIN Bandung, melaui beberapa alternatif jalan. Alternatif jalan 218
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
yang dapat dilalui dapat dilihat pada
dengan menggunakan Algoritma Dynamic
Gambar 3. Untuk menentukan alternatif
Programming.
jalan dengan lintasan terpendek adalah
Gambar 3. Peta Sukamukti menuju UIN Dalam
penyelesaian
solusi
untuk
proses untuk mendapat solusi optimal pada
menentukan jalur atau lintasan terpendek,
setiap tahapnya. Pada Gambar 4 terdapat 10
telebih dahulu peta jalur-jalur yang ada di
tahap pada peta perjalanan dari Sukamukti
bagi menjadi beberapa bagian. Bagian ini
menuju Kampus UIN Bandung.
merupakan tahapan-tahapan yang akan
219
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
Gambar 4. Pengklasteran Peta Untuk menentukan jalur terbaik yang akan
Pada kondisi S dan tahap n, digunakan Xn*
dilalui dari Sukamukti ke UIN Bandung,
sebagai sembarang nilai yang minimum
ada 2 (dua) hal yang dilakukan.
fn(S,Xn), gunakan fn*(S) sebagai nilai
1. Pilih variabel keputusan Xn (n=1,2,3,4,5,6,7,8,9,10) sebagai daerah yang harus ditempuh pada tahap n. sehingga rute seluruhnya
adalah
X1Sukamukti dan X10UIN
minimum dari fn(S,Xn). Jadi fn*(S)=min fn(S,Xn)=fn(S,Xn*), dengan fn(S,Xn) adalah biaya sekarang pada tahap n, ditambah biaya tahap berikutnya, yaitu tahap n+1 dan seterusnya,
dengan
persamaan
fn(S,Xn)=Cs(Xn)+fn+1*(Xn).
Bandung. 2. Pilih fn(S,Xn) sebagai biaya total untuk kebijakan keseluruhan darai
tahapan
selanjutnya
dengan si penelusur/penjelajah sampai pada kondisi S, siap berangkat ke tahap n, dengan memilih Xn sebagai daerah tujuan berikut.
Pada tahap akhir n=10, maka perjalanannya hanya ditentukan sepenuhnya oleh kondisi S sekarang, yaitu daerah Ujungberung, Panghegar, Gedebage dan tujuan akhir adalah daerah UIN Bandung. Sehingga f10*(S,UIN Bandung)=Cs(UIN Bandung). Pada tahap akhir n=10 hasilnya dapat dilihat pada Tabel 1.
220
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
Tabel 1. Tahap 10 S
f10*(S)
Ujungberung
5
X10 UIN Bandung
Panghegar
4
UIN Bandung
Gedebage
5
UIN Bandung
Tabel 1 menyajikan fakta bahwa penjelajah
penjelajah telah di daerah Arcamanik,
telah sampai di daerah Ujungberung,
Antapani.
Panghegar dan Gedebage. Maka solusi
melalui
feasible-nya adalah X10=UIN Bandung.
Gedebage, dengan biaya pada tahap 9 ini
Perjalanan
dapat
Ujungberung,
adalah
dilakukan
Panghegar
CF(Ujungberung)=5
dan
atau
CF(Panghegar)=4 dan CF(Gedebage)=5. Pada tahap X=9, maka perjalanannya perlu
Pada tahap akhir n=9 hasil perhitungannya
melakukan beberapa perhitungan. Jika si
dapat dilihat pada Tabel 2.
Tabel 2. Tahap 9
S
f8=fS+f9* Ujungberung Panghegar
Gedebage
f9*(S)
X9
Arcamanik
15
18
19
15
Ujungberung
Antapani
24
19
24
19
Panghegar
Proses perhitung pada Tabel 2 adalah
a. Arcamanik, Ujungberung
perjalan ke UIN Bandung melalui daerah
15=10+5
yang disajikan dalam baris melaui daerah
b. Arcamanik,
yang disajikan melaui kolom. Besar biaya
18=10+4+4
yang ada, rinciannya adalah sebagai berikut
c. Arcamanik,
Panghegar
Gedebage
19=10+4+4+5 221
Edisi Juli 2014 Volume VIII No. 1 d. Antapani,
ISSN 1979-8911
Ujungberung
Pada tahap 8, dengan X=8 daerah yang akan
24=15+4+5 e. Antapani,
dihitung
Panghegar
adalah
Antapani,
dengan
memperhatikan nilai minimum pada Tabel 2. Maka jarak dari Cicaheum melalui
19=15+4 f. Antapani,
Gedebage
Arcamnik dan Panghegar diperoleh nilai biaya yang tertera pada Tabel 3. Perjalanan
24=15+4+5
dari Cicaheum melalui Arcamanik 21=6+15 dan Cicaheum melalui Antapani 24=5+19.
Tabel 3. Tahap 8 f7=fS+f8*
S
Arcamanik Antapani
Cicaheum
21
f8*(S)
X8
21
Arcamanik
24
Tahap 7 dengan X=7, terdapat juga jalur
Gedebage. Adapun rician biaya pada tahap
yang menghubungkan daerah X10, yaitu
7 dapat dilihat pada Tabel 7.
Tabel 4. Tahap 7
S
f6=fS+f7* Cicaheum Antapani Gedebage
f7*(S)
X7
Cicadas
26
29
32
26
Cicaheum
Kiaracondong
31
28
27
27
Gedebage
SAMSAT
38
35
20
20
Gedebage
Tahap 6, X=6 dengan mempertimbangkan jarak minum pada tabel-tabel tahap sebelumnya, dapat dilihat pada Tabel 5, Tabel 5. Tahap 6
S
f5=fS+f6* Cicadas
Kiaracondong SAMSAT Gedebage
f6*(S)
X6
222
Edisi Juli 2014 Volume VIII No. 1 Horizon
Buah Batu
Telkom Unv. Dayeuhkolot
ISSN 1979-8911
38
33
32
32
32
41
38
23
23
23
46
43
28
28
28
51
48
33
50
33
SAMSAT, Gedebage SAMSAT, Gedebage SAMSAT, Gedebage SAMSAT
Tahap 5, dengan X=5 dapat ditentukan nilai-nilai seperti tertera pada Tabel 6. Tabel 6. Tahap 5 f4=fS+f5* S
Horizon Buah
PT. INTI
Telkom Dayeuh
Batu
Unv.
kolot
38
45
75
42
f5*(S)
38
X5
Buah Batu
M. Toha
48
33
40
70
33
Buah Batu
Palasari
55
38
35
55
35
Telkom Unv.
Tahap 4, dengan X=6 dapat ditentukan nilai-nilai seperti tertera pada Tabel 7. Tabel 7. Tahap 4
S Cibaduyut
f3=fS+f4* PT. INTI
M. Toha
Palasari
48
40
52
f4*(S) 40
X4 M. Toha
Tahap 3, dengan X=4 dapat ditentukan nilai-nilai seperti tertera pada Tabel 8. Tabel 8. Tahap 3 S
f2=fS+f3*
f3*(S)
X3 223
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
Cibaduyut Kopo
50
50
Cibaduyut
Cangkuang
55
55
Cibaduyut
Tahap 2, dengan X=2 dapat ditentukan nilai-nilai seperti tertera pada Tabel 9. Tabel 9. Tahap 2
S
f1=fS+f2* Kopo
Cangkuang Dayeuhkolot
f2*(S)
X2
Katapang
65
75
90
75
Cangkuang
Sayuran
85
50
70
50
Sayuran
Tahap 1, dengan X=1 dapat ditentukan nilai-nilai seperti tertera pada Tabel 10. Tabel 10. Tahap 1
S Sukamukti
f1=fS+f1* Katapang
Sayuran
80
60
f1*(S)
X1
60
Sayuran
Berdasarkan analisis dengan melakukan perhitungan nilai-nilai yang ada, dapat disimpulakan bahwa rute terpendek adalah Sukamukti-Sayuran-Cangkuang-PalasariTelkom
Unv-SAMSAT-Gedebage-UIN
Bandung. Total nilai yang ada adalah 60. Lintasan terpendek dari Sukamukti menuju UIN Bandung lebih detailnya dapat dilihat pada Gambar 5.
224
Edisi Juli 2014 Volume VIII No. 1
ISSN 1979-8911
Gambar 5. Solusi Jalur TerpendekDaftarPustaka Fathoni, M. Dan Triprabowo, Pencarian
Nurhidayati, F., U., 2010, Penggunaan
Rute Terpendek dengan Menggunakan
Program Dinamik untuk Menentukan
Dynamic Programming, Universitas
Total
Airlangga, Surabaya. Luknanto, D., 2013, Program Dinamik,
Biaya
Minumum
pada
Perencanaan
Produksi
dan
Pengendalian
Persediaan,
Skripsi,
Jurusan TeknikSipil, Fakultas Teknik,
Jurusan Matematika, Fakultas Sains
Universitas Gadjah Mada, Yogyakarta.
danTeknologi,
Universitas
Islam
Negeri Maula Malik Ibrahim, Malang. Munir, R., 2008, Program Dinamis, Bahan Kuliah Strategi Algoritma, Jurusan Teknik Informatika
Informatika, dan
Elektro,
Sekolah Institut
Teknologi Bandung. 225
