Kata Kunci: Program Dinamis, Optimalisasi, Angkutan umum, Transportasi jarak jauh, Biaya perjalanan, Waktu Perjalanan Contoh-contoh yang diambil dalam makalah ini juga mungkin bukan kondisi aktual, beberapa hanya perkiraan penulis, tetapi cukup menggambarkan kondisi yang sebenarnya (misal: jarak Jl. Ganesha-Jl. Tamansari tentu saja lebih dekat daripada jarak Jl. Ganesha-Jl. Dipati Ukur).
Dalam makalah ini penulis ingin mencari bagaimana cara seseorang menemukan jalan yang optimal dari suatu tempat ke tempat lain, baik dari segi waktu, biaya, tingkat kenyamanan, ataupun kombinasi dari ketiga aspek itu.
2. ALGORITMA PROGRAM DINAMIS
Program dinamis merupakan suatu cara penyelesaian masalah dengan menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Pada penyelesaian metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.
Program dinamis mempunyai karakteristik sebagai berikut:
1. Persoalan dapat dibagi menjadi beberapa tahap, 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. Jumlah status bisa berhingga atau tidak berhingga.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah
tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap 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.
Secara umum, ada empat langkah yang dilakukan dalam mengembangkan algoritma program dinamis:
1. Karakteristikkan struktur solusi optimal.
2. Definisikan secara rekursif nilai solusi optimal.
3. Hitung nilai solusi optimal.
4. Konstruksi solusi optimal.
Dalam menyelesaikan persoalan dengan program dinamis, orang dapat menggunakan duan pendekatan
berbeda, yaitu maju (forward atau up-down) dan mundur (backward atau bottom-up). Misalkan x1, x2, x3, …, xn menyatakan peubah keputusan yang harus dibuat masing-masing untuk tahap 1, 2, 3, …, n, maka,
a. Program dinamis maju. Program dinamis bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan
seterusnya sampai tahap n. Runtunan peubah keputusan adalah x1, x2, x3, …, xn.
b. Program dinamis mundur. Program dinamis bergerak mulai dari tahap n, terus mundur ke tahap n-1, n-2, sampai ke tahap 1. Runtunan peubah keputusan adalah xn, xn-1, xn-2, …, x1.
3. METODE PENYELESAIAN MASALAH
Seperti yang telah dipaparkan sebelumnya, masalah pencarian jalur transportasi jarak jauh terbaik ini akan diselesaikan menggunakan algoritma program dinamis yang sudah dijelaskan pada bab sebelumnya.
Untuk mempermudah pemecahan masalah, pendekatan yang dipakai adalah program dinamik mundur, dengan dua pemecahan masalah yang berbeda: optimalisasi waktu dan optimalisasi biaya. Sebagai permulaan, kita menentukan titik awal dan titik akhir perjalanan yang akan ditempuh. Kita anggap awal perjalanan (x0) adalah kampus ITB, yaitu Jalan Ganesha 10, sedangkan akhir perjalanan (xn) adalah Bandara Soekarno-Hatta Jakarta. Dari titik awal dan titik akhir, kita membuat daftar angkutan yang berada di antara x0 dan xn, dengan spesifikasi seperti yang tertera pada tabel 1. Pada tabel di atas, d1 dihitung dari x0 dan d2 dihitung dari xn. Jumlah angkutan umum dibatasi, karena akan sangat banyak jika ditulis semua. Aspek kenyamanan diabaikan terlebih dahulu. Setelah semua kemungkinan transport dibuat, asumsikan manusia hanya sanggup berjalan sampai 500 m untuk setiap pemberhentian, sehingga setiap transport yang mempunyai d1 lebih dari 500 m dieliminasi, saat menentukan solusi lokal.
Tahap yang digunakan dalam fungsi ini mungkin saja sangat banyak sampai tak berhingga, sehingga tahap untuk fungsi ini harus dibatasi, karena akan mempermudah kerja memori yang harus membangkitkan data-data transportasi setiap kali rekursif.
3.1 Optimalisasi Waktu Perjalanan
Menentukan solusi untuk optimalisasi waktu perjalanan merupakan sebuah operasi rekursif dengan notasi sebagai berikut:
fn (s) = txn (basis)
fk (s) = min {txn + fk+kx (xk)} (rekurens)
Sedangkan untuk setiap tahap yang dilakukan dilakukan pembangkitan daftar angkutan yang tersedia (sama seperti tabel 2)
Jika operasi rekursif didefinisikan sebagai optimizeTime(k) dan operasi pembangkitan data didefinisikan sebagai generate(k) maka fungsi optimizeTime(k) adalah sebagai berikut:
Generate(k)
if (k <= 500) then {basis}
return (t(x)+walk(k))
else {rekurens}
return (min(t(x)+walk(k-k(x))
+optimizeTime(k-k(x))))
Pada notasi di atas, k adalah jarak dari x (tempat tersebut) sampai tempat akhir (xn). Fungsi tersebut akan mencapai basisnya saat k kurang dari atau sama dengan 500 m, yaitu anggapan manusia tidak butuh alat transportasi, namun waktu berjalannya juga ditambahkan pada waktu total.
3.2 Optimalisasi Biaya Perjalanan
Optimalisasi biaya perjalanan pada prinsipnya hampir sama dengan optimalisasi waktu perjalanan, namun semua operasi yang berhubungan dengan waktu diganti dengan biaya.
Menentukan solusi untuk optimalisasi biaya perjalanan merupakan sebuah operasi rekursif dengan notasi sebagai berikut:
fn (s) = cxn (basis)
fk (s) = min {cxn + fk+kx (xk)} (rekurens)
Sedangkan untuk setiap tahap yang dilakukan dilakukan pembangkitan daftar angkutan yang tersedia (sama seperti tabel 2) Jika operasi rekursif didefinisikan sebagai optimizeCost(k) dan operasi pembangkitan data didefinisikan sebagai generate(k) maka fungsi optimizeCost(k) adalah sebagai berikut:
Generate(k)
if (k <= 500) then {basis}
return (c(x))
else {rekurens}
return (min(c(x)+optimizeCost(k-k(x))))
Pada notasi di atas, k adalah jarak dari x (tempat tersebut) sampai tempat akhir (xn). Fungsi tersebut akan mencapai basisnya saat k kurang dari atau sama dengan 500 m, yaitu anggapan manusia tidak butuh alat transportasi. Pada bagian ini, waktu untuk berjalan sama sekali tidak diperhitungkan, karena murni menghitung biaya perjalanan saja.
4. KESIMPULAN
Algoritma program dinamis sudah lumrah dipakai untuk suatu persoalan optimalisasi. Dalam kasus ini, algoritma program dinamis sudah cukup dapat menyelesaikan persoalan pemilihan jalur transportasi jarak jauh, namun yang perlu diperhatikan adalah banyaknya jumlah dan jenis angkutan yang sangat banyak dari suatu tempat ke tempat lain di dunia. Untuk optimalisasi biaya atau waktu saja, hanya satu aspek yang dilihat (biaya atau waktu), namun jika melihat kedua aspek tersebut bersamaan, ditambah aspek kenyamanan, algoritma yang dibuat akan lebih kompleks lagi.
