BAB III METODOLOGI DAN PERBANDINGAN METODA

BAB III METODOLOGI DAN PERBANDINGAN METODA


Melalui penjelasan konsep jaringan graph, dalam menelusuri rute menuntut adanya penggunaan metoda yang tepat. Merunut pada tinjauan pustaka, setidaknya akan digunakan dua metoda yang berbeda dalam menyelesaikan masalah. Penyertaan contoh kasus yang berbeda-beda ditujukan untuk menyeleksi metoda terpilih yang memiliki kesesuaian dengan permasalahan. Namun sebelum beranjak ke dalam perbandingan metoda, kerangka tahapan metodologi dijelaskan untuk menjaring keseluruhan proses pengerjaan kasus perutean ini. 3.1

METODOLOGI Metodologi ini menjelaskan langkah demi langkah setiap tahapan yang dilakukan dalam studi. Dalam menyelesaikan permasalahan penentuan rute dapat digunakan diagram alur metodologi dan berikut penjelasannya: 1. Identifikasi Permasalahan Permasalahan yang ingin diselesaikan adalah menentukan rute moda transportasi pada suatu wilayah kajian dengan batasan yang ada. Studi pustaka akan membantu dalam mengetahui permasalahan penentuan jaringan rute yang telah dilakukan oleh orang lain. 2. Penentuan Wilayah Kajian Wilayah kajian yang akan dibahas merupakan wilayah kepulauan. Pusat kegiatan dari masing-masing subwilayah kajian direpresentasikan melalui pelabuhan yang beroperasi. Sehingga hasil yang diharapkan adalah hubungan antar pelabuhan tersebut, yaitu dalam bentuk rute.

Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-1


3. Identifikasi Moda dan Muatan Moda transportasi yang dipilih mengikuti pertimbangan disesuaikan dengan kondisi wilayah kajian. Sehingga dalam kajian tersebut, muatan yang diperhitungkan sesuai dengan moda transportasinya. 4. Identifikasi Model Jaringan dan Data Untuk mempermudah dalam penyelesaian maka digunakan teori graph. Selain itu,

data-data

yang

ada

berkaitan

dengan

permasalahan

juga

ikut

dipertimbangkan. 5. Perumusan Fungsi Objektif dan Batasan Fungsi objektif dan batasan dirumuskan berdasarkan permasalahan dan tujuan yang akan dicapai. 6. Pemilihan metoda dan aplikasi program Setelah menentukan model optimasi, maka pertimbangan selanjutnya adalah penentuan metoda yang tepat disertai pengembangan ke dalam aplikasi program. Untuk memahami penjelasan, alur kerja metodologi ditampilkan pada Gambar 3.1.

Studi Pustaka

Identifikasi Permasalahan Pemilihan Wilayah Kajian

Identifikasi Moda Dan Data yang Digunakan

Identifikasi Model Jaringan DalamGraph Perumusan Permasalahan Metoda A

Metoda B

Pemilihan Metoda Dan Aplikasi Program Gambar 3. 1. Metodologi pengerjaan Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-2


Mengikuti skema tahapan di atas, pemilihan metoda di akhir tahapan menjadi fokus perhatian dalam bab ini. Dikarenakan sulit mencari kecocokan metoda penyelesaian untuk menangani persoalan jaringan yang dihadapi. Namun, sebelum menginjak ke dalam proses pemilihan tersebut, terminologi selanjutnya diberikan sebagai acuan yang dipakai dalam proses perbandingan hingga pengerjaan di wilayah kajian. 3.2

DESKRIPSI MASALAH DAN TERMINOLOGI Berawal dari konsep jaringan graph, node-node pada kasus mewakili pusat kegiatan wilayah. Masalah merupakan mengobservasi hubungan node-node yang terbentuk menghubungkan source dan target. Dengan ketentuan bentukan rute yang terjadi, harus melalui batasan dan sesuai tujuan yang akan dicapai pada wilayah kajian. Untuk wilayah kajian yang diilustrasikan sebagai graph dibawah dapat berupa wilayah perkotaan atau kepulauan. Dalam contoh kasus ini, wilayah studi yang dipakai adalah wilayah kepulauan. Sehingga moda transportasi yang dipakai harus sesuai dengan kebutuhan dari wilayah kajian tersebut, seperti kapal laut, kapal feri, atau pesawat terbang. Dalam gambar graph dibawah, terdapat informasi keinginan pergerakan dari suatu pusat kegiatan (centroid) yang diilustrasikan dengan tanda segitiga. Dimana keinginan pergerakan pada suatu centroid akan melewati arc yang tidak berbobot dan berkumpul di node-node, yang akan menjadi beban pada ruas. Setelah mengetahui kondisi dari wilayah kajian dan permasalahannya maka tahap selanjutnya adalah menetapkan asumsi-asumsi batasan masalah (pergerakan moda) dan mengidentifikasi data-data yang relevan serta variabel yang dicari, kemudian dianalogikan dengan baik pada model jaringan graph. Asumsi arah pergerakan moda transportasi yang dipakai adalah satu arah. Dimana pergerakan yang terjadi adalah berurutan ke depan dari kodifikasi yang diberikan pada Gambar 3.2. Contoh pergerakan yang dipakai menjadi asumsi adalah dari node s ke node 1 lalu node 2 kemudian node t, dan tidak berlaku untuk pergerakan dari node s ke node 3 lalu node 2 kemudian node 1 dan ke node t. Asumsi tersebut dipakai untuk menyederhanakan kompleksitas permasalahan jaringan sehingga mudah dipahami. Hal tersebut menjadi dasar pergerakan dalam penyelesaian permasalahan penentuan rute untuk berbagai kasus pada subbab selanjutnya.


III-3


B

D

a ij

1

A

3

t

s

E

2 C

Gambar 3. 2. Gambar jaringan dalam graph 3.2.1 Terminologi Jaringan Berikut Tetapan Variabelnya Rs…t

: Menunjukkan rute, merupakan kumpulan ruas yang menghubungkan node (source dan target) oleh satu moda. Contoh rute Rs13 t, maka ruas yang terbentuk adalah as1, a13 , dan a3t.

node

: Mewakili pusat kegiatan, yang dapat menunjukkan keinginan pergerakan, supply, atau permintaan (demand) dari node tersebut. Dengan notasi s-t menunjukkan source dan target dan i-j adalah komponen node bebasnya.

aij

: Garis berarah (arc) menghubungkan dua node, merepresentasikan biaya, jarak, pendapatan, muatan penumpang dan kendaraan, dan sebagainya.

Tod

: Keinginan pergerakan dari centroid (pusat kegiatan/zona) o (origin) ke d (destination), bisa berupa penumpang maupun kendaraan.

Tpod

: Keinginan pergerakan penumpang dari centroid o ke d (pnp/hari).

Tkod

: Keinginan pergerakan kendaraan dari centroid o ke d (smp/hari).

daij

: Jarak pada arc ij (km).

dxy

: Jumlah jarak dari tiap ruas aij yang dilalui node x ke node y (km).

Mpaij

: Muatan penumpang pada arc ij .

Mkaij

: Muatan kendaraan pada arc ij.


III-4


Caij

: Biaya pada arc ij.

Paij

: Pendapatan pada arc ij.

Kaij

: Keuntungan pada arc ij.

Uaij

: Kapasitas muatan pada arc ij.

Upaij

: Kapasitas penumpang pada arc ij.

Ukaij

: Kapasitas kendaraan di arc ij.

MDpaij : Nilai pada arc ij dengan rumusan Mpaij dikalikan dengan jarak daij MDkaij : Nilai pada arc ij dengan rumusan Mkaij dikalikan dengan jarak daij Korelasi antara muatan dan keinginan pergerakan (Tod) diberikan sebagai berikut. Maij odij Tod a

o

(3.1)

d

(Berlaku untuk pergerakan penumpang maupun kendaraan)

odij  a

1 jika ruas aij digunakan oleh rute antara o dan d 0 jika sebaliknya

odij a

: proporsi keinginanan pergerakan dari centroid o ke centroid d yang menggunakan rute dan ruas aij (hubungan yang terbentuk dari sekumpulan centroid untuk suatu ruas), (Tamin, 2000).

Persamaan untuk muatan penumpang-km disetiap ruas MDpaij = Mpaij x daij

(3.2), dimana M p aij oda T p od o

d

Persamaan untuk muatan kendaraan-km disetiap ruas MDkaij = Mkaij x daij

(3.3), dimana M k aij oda T o

p

od

d

Komponen tetapan variabel yang akan digunakan. Tp

: Tarif penumpang (rp/km-pnp)

Bo

: Biaya operasional (rp/km)


III-5


Tk

: Tarif kendaraan (rp/km-smp)

Bt

: Biaya tetap (rp/hari)

Bp

: Biaya dikenakan untuk satu node

Np

: Jumlah node dikunjungi

Hubungan rumusan biaya, pendapatan, dan keuntungan yang terbentuk.







Pa ij  M p aij * T p * da ij  M k a ij * Tk * da ij : pendapatan pada ruas ij

(3.4)

Ca ij  B o * daij   Bp *N p 

: meliputi operasional pergerakan aij (3.5)

Ka ij Pa ij Ca ij

: selisih antara pedapatan dan biaya. (3.6)

Pemaparan terminologi di atas berfungsi sebagai pijakan dasar untuk memahami pengerjaan contoh kasus yang ada. Contoh kasus meliputi minimasi jarak, maksimasi muatan, dan keuntungan. Perbedaan masalah tersebut menjadikan penanganannya berbeda bergantung pada metoda penyelesaiannya. Sehingga perlu adanya pembagian kajian khusus untuk setiap metoda mencakup perumusan dan notasi khususnya. 3.2.2 Kajian Algoritma Djikstra  Minimasi Jarak d si min{ d si , d sj da ji }

dsi

(3.7)

: Menunjukkan nilai jumlah jarak dari tiap ruas aij yang dilalui node s ke node i.

dsj

: Menunjukkan nilai jumlah jarak dari tiap ruas aij yang dilalui node s ke node j.

Keseluruhan variabel rumusan berada dalam kondisi dinamis sesuai prinsip pengupdatean setiap ruas. Artinya nilai variabel pada ruas dapat berubah sesuai proses iterasi. Kasus maksimasi muatan dan keuntungan mengacu hasil kasus yang pertama. Prinsipnya dengan memberikan beban muatan dan keuntungan pada setiap


III-6


ruas dari rute yang telah diperoleh. Pengembangan dilakukan mengingat algoritma Djikstra tidak memiliki rumusan baku untuk kedua kasus tersebut. 3.2.3 Kajian Algoritma Genetik  Minimasi Jarak FOD k da ij i

(3.8)

j

Merupakan fungsi objektif dari total jarak untuk satu rutenya pada kromosom k  Maksimasi Muatan FOM k MDa ij i

(3.9)

j

Merupakan fungsi objektif dari total muatan-jarak pada kromosom k  Maksimasi Keuntungan FOK k Kaij B t i

(3.10)

j

Merupakan fungsi objektif dari total keuntungan pada kromosom k Untuk permasalahan maksimasi muatan dan keuntungan diatas tidak memakai batasan kapasitas pada tiap ruasnya (Uaij ). Sehingga akan dicoba memperhitungkan kapasitas (Uaij ) tiap ruas pada permasalahan yang sama. Dalam pengerjaannya, algoritma genetika mengadopsi istilah biologi karena dasar pengoperasiannya memakai prinsip genetika (Leonardo, 2003), diantaranya yang digunakan adalah: Kromosom : Menyatakan suatu rute yang terkodifikasi dalam kode biner pada gen. Gen

: Komponen kromosom yang menyatakan suatu node dikunjungi.

Populasi

: Merupakan kumpulan kromosom.

Seleksi

: Proses pemilihan kromosom unggul berdasar nilai fitnessnya.

Crossover

: Operasi genetika yang bercara kerja menukarkan sejumlah gen antar pasangannya bergantung titik potong dan dipengaruhi crossover rate.


III-7


Mutasi

: Operasi genetika bekerja dengan prinsip mengganti nilai gen pada kromosom secara acak dipengaruhi mutation rate.

Komponen yang mengikuti proses operasi genetikanya, antara lain: fk

: Nilai fitness dari kromosom k pada suatu populasi. Memiliki bentuk tergantung kasus yang dihadapi. a. Minimasi Jarak

1 fk  FOD k 1

(3.11)

b. Maksimasi Muatan

f k FOM k FOK k

(3.12)

∑fk

: Jumlah fitness dari kromosom k pada suatu populasi. a. Minimasi Jarak

f

k

FODk

k

FOM k FOK k

k

b. Maksimasi Muatan

f k

P[k]

: Nilai probabilitas pada kromosom k

C[k]

: Kumulatif probabilitas pada kromosom k

R[k]

: Bilangan acak pada kromosom k, dimana k = 1, 2, 3 ...k

CP[p]

: Posisi cutting point pada pasangan p (cross over), dimana p = 1, 2, 3 ...p

MP

: Posisi gen termutasi.

Di setiap tahapannya, algoritma genetika sering menggunakan bilangan acak untuk membantu proses operasinya. Contohnya penentuan cutting point dan mutation point. Dengan penjabaran masalah dan tujuan yang berbeda-beda tersebut, mengarahkan ke dalam perbandingan metoda yang akan digunakan. Hal ini dimaksudkan untuk menunjukkan kelebihan metoda terpilih yang akan digunakan dalam kasus kajian.


III-8


3.3

PERBANDINGAN METODA DALAM PENENTUAN RUTE Perbandingan metoda dilakukan melalui penelusuran rute dengan tujuan yang berbeda-beda. Mulai minimasi jarak, maksimasi muatan, hingga keuntungan. Pengarahan seperti pada Gambar 3.3 diberikan untuk menjelaskan secara bertahap. Sehingga diharapkan pengantar ini dapat memberikan pemahaman saat pengerjaan pada wilayah kajian menggunakan metoda terpilih, algoritma genetika.

Permasalahan

Tujuan

Metoda Dipakai Algoritma Djikstra

Minimasi Jarak Algoritma Genetik

Penentuan Rute Dari Suatu Jaringan

Mengacu 3 Rute Algoritma Djikstra Maksimasi Muatan Algoritma Genetik Mengacu 3 Rute Algoritma Djikstra Maksimasi Keuntungan Algoritma Genetik

Gambar 3. 3. Tujuan dan metoda yang dipakai Dengan demikian informasi yang dibutuhkan bergantung dari permasalahan yang ditangani. Minimasi biaya hanya membutuhkan informasi jarak (biaya), maksimasi pendapatan berupa muatan, dan keuntungan berupa selisih dari keduanya. Metoda yang akan digunakan adalah algoritma Djikstra dan algoritma genetika. Ilustrasi masalah ke dalam bentuk graph dimaksudkan untuk memberikan gambaran komponen terminologi dalam jaringan. Namun, sebelum memasuki contoh kasus, konsep dasar kedua metoda akan dijelaskan terlebih dahulu pada subbab selanjutnya.


III-9


3.3.1 Metoda Algoritma Djikstra Algoritma Djikstra mempunyai dasar yang baik dalam menyelesaikan permasalahan jarak terpendek. Jika terdapat node yang berdekatan dengan node s (source) pada jaringan dan mempunyai jarak terpendek, maka node tersebut diberi tanda. Node t (target) adalah node tujuan, kemudian node-node (i) yang berdekatan tadi ditelusuri. Node tertanda merupakan node dengan jarak terpendek dan dinamakan node j. Untuk menghubungkan node-node tersebut, dibentuk dari node s ke node i dengan jarak terpendek pada arc ij untuk semua node i yang diberi tanda. Jarak terpendek didapat dengan mengikuti langkah-langkah berikut. Langkah 1. Pertama notasikan semua arc dan node sebagai node yang belum diberi tanda. Beri tanda dsi kepada tiap node i untuk menandakan panjang dari ruas node s ke node i. Dengan notasi dss = 0 untuk semua i ≠s. Kemudian notasikan j pada akhir sebagai node yang diberi tanda. Untuk node s, maka j = s. Langkah 2 Untuk tiap node i yang belum diberi tanda, definisikan dsi pada persamaan (3.7) sebagai berikut: d si min{ d si , d sj da ji } pencarian node berikutnya dari node j adalah sebagai node yang mendapat pengaruh dari node j. Jika dsi =  untuk semua node i yang belum diberi tanda, kemudian hentikan proses pengerjaan jika tidak ada ruas dari node s ke node yang belum diberi tanda. Lalu beri tanda pada node yang belum diberi tanda dengan nilai dsi yang terkecil. Selain itu beri tanda juga arc yang mengarah ke node i dari node diberi tanda yang mencerminkan nilai dari dsi . Kemudian j = i. Langkah 3 Jika akhir node t sudah diberi tanda, maka jarak terpendek dari node s ke node t telah ditemukan. Jika node t belum diberi tanda maka ulangi kembali langkah 2.


III-10


3.3.2 Metoda Algoritma Genetika Algoritma genetika melakukan pencarian dalam beberapa area lokal dengan daerah kerja suatu populasi atau generasi. Algoritma genetika menggunakan aturan iterasi probabilistik pada operasi genetikanya dalam menentukan solusi. Pengembangan dilakukan melalui penyandian permasalahan ke dalam kromosom. Kombinasi terbentuk setelah kromosom melalui operasi genetika. Sistem pencarian dilakukan melalui iterasi pada tahapan selanjutnya yang dilakukan secara simultan/bersamaan dimana setiap individu mewakili solusi potensial dari masalah. Ilustrasi algoritma genetika dalam mencari solusi diperlihatkan pada di bawah ini.

S

X3 Xn X1

X2

Xn = Solusi H(Xn)= Kumpulan Solusi Evaluasi Fungsi Objektif dan Fitness Operator Genetika Mempertahankan solusi yang baik dan mencari solusi-solusi lain sesuai dengan batasan yang ditetapkan. Populasi Berikutnya Evaluasi Fungsi Objektif dan Fitness

Tidak Jumlah Populasi Maksimum? Ya Solusi Terbaik

Gambar 3. 4 Ilustrasi metoda algoritma genetika Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-11


Sedangkan penerapan metoda algoritma genetika dalam permasalahan pencarian rute dapat terlihat pada prosedur yang harus dijalankan terlampir pada Gambar 3.5.

Penentuan Fungsi Objektif Kodifikasi Solusi

Inisialisasi Populasi

Evaluasi Fungsi Objektif dan Fitness

Seleksi Kromosom

Generasi selanjutnya

Crossover (Pindah Silang) Mutasi

Tidak

Ya Generasi Yang Bisa Diterima

Solusi Optimum

Gambar 3. 5 Diagram alir algoritma genetika permasalahan Sumber: (Hermawanto, 2007)

Permasalahan jaringan pada subbab selanjutnya akan diselesaikan menggunakan Simple Genetic Algorithm. Sehingga hanya menerapkan dasar-dasar metoda algoritma genetika yang sederhana dalam menyelesaikan permasalahan. Oleh karena itu, diambil beberapa tahapan algoritma genetika sederhana, yaitu: 1. Menentukan fungsi objektif permasalahan Merupakan perumusan fungsi objektif sebagai parameter yang diukur dari solusi.


III-12


2. Kodifikasi masalah dan pembentukan kromosom. Encoding bergantung pada masalah yang akan dipecahkan, dan salah satu yang begitu umum dikenal adalah pengkodean dengan kode biner. 3. Inisialisasi Populasi Pembentukan populasi yang terdiri dari sejumlah kromosom yang telah ditentukan. Populasi inilah yang nantinya mengalami proses genetika. 4. Evaluasi kromosom Merupakan dasar untuk proses seleksi. Diawali dari konversi kromosom ke parameter fungsi yang kemudian dievaluasi dan dilanjutkan penentuan fitness fungsi objektif. 5. Seleksi Kromosom Proses seleksi ini merupakan proses duplikasi saja dan tidak akan menghilangkan sifat kromosom yang lama. Hal ini dilakukan dalam proses algoritma genetika untuk menjaga sifat-sifat yang baik sehingga sifat-sifat yang baik itu tidak akan hilang begitu saja. Proses seleksi dilakukan dengan cara membuat kromosom yang mempunyai fungsi objektif baik mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas yang tinggi. Pada proses ini digunakan metoda seleksi Roulette Wheel. Pertama-tama induk dipilih berdasarkan fitness mereka. Semakin baik sebuah kromosom, semakin besar kemungkinan untuk dipilih. Seperti sebuah roulette wheel dimana diletakkan semua kromosom dalam suatu populasi, setiap kromosom memiliki luas daerah menurut fungsi fitnessnya. Kemudian dilakukan undian untuk melakukan seleksi. Kromosom dengan fitness yang lebih baik memiliki kemungkinan lebih besar untuk terpilih.


III-13


6. Crossover (pindah silang) Operator ini bekerja pada dua buah kromosom pada saat bersamaan dan menghasilkan kromosom baru dengan menggabungkan kedua kromosom tersebut. Jumlah kromosom dalam populasi yang mengalami crossover ditentukan oleh paramater yang disebut dengan crossover rate. Nilai crossover rate yang tinggi akan memungkinkan pencapaian alternatif solusi yang lebih bervariasi dan mengurangi kemungkinan menghasilkan nilai optimum yang tidak dikehendaki. Metoda crossover yang dipakai adalah one-cutting point atau satu titik potong. Proses pindah silang dengan satu titik potong mudah digunakan, dimana untuk melakukan proses pindah silang ini adalah dengan cara menentukan satu titik potong secara acak, kemudian menukar potongan kromosom sisi sebelah kanan dari orang tua pertama dan potongan kromosom sisi sebelah kanan orang tua kedua. Dengan cara ini akan dihasilkan dua kromosom baru hasil pindah silang. 7. Mutasi Proses mutasi merupakan salah satu dari operator genetika yang akan menghasilkan atau tidak perubahan secara acak pada satu kromosom. Jumlah gen dalam kromosom pada suatu populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan nilai mutasi atau mutation rate. Apabila nilai mutasi terlalu kecil, maka kromosom-kromosom yang berguna mungkin tidak akan muncul dalam populasi, tetapi apabila terlalu tinggi maka kromosom baru akan kehilangan sifat-sifat yang mungkin saja merupakan sifat yang unggul dari orangtuanya. 8.

Pemasukan populasi baru kedalam populasi berikutnya, dari populasi tersebut dipakai sebagai populasi baru dalam iterasi selanjutnya.

9.

Iterasi dilakukan sampai didapat hasil yang optimal, yaitu dengan melihat konvergensi nilai-nilai yang didapatkan sesuai dengan batasan optimasi fungsi obyektif awal yang diinginkan.


III-14


Permasalahan untuk berbagai tujuan pada subbab selanjutnya, akan diselesaikan menggunakan metoda algoritma genetika dengan penetapan parameter genetika, yaitu: Populasi

: 4 Kromosom

Panjang Kromosom

: 5 Gen/kromosom

Crossover rate

: 60%

Mutasi rate

: 3%

3.3.3 Minimasi Jarak Pada kasus minimasi jarak direpresentasikan dengan graph seperti Gambar 3.6 berikut, dimana tiap ruas identik dengan aij yang merepresentasikan jarak atau biaya tiap arc. Tujuan dicapai ketika node s (source) terhubung ke t (target) melalui ruas dari node-node yang ada, dalam kondisi jarak yang minimal. Jarak minimal didefinisikan sebagai total jarak ruas yang dilalui. Shortest path problem melibatkan pencarian ruas dari node s ke t yang mempunyai kemungkinan jarak terkecil.

B

D da13 = 2 1

3

das1 = 3 A

da3t = 1

da1t = 6

das3 = 6

t

s

da23 = 2

da12 = 2

E

da2t = 4

das2 = 4 2 C

Gambar 3. 6 Gambar jaringan beserta informasi jarak Untuk informasi data jarak antar ruas disajikan pada Tabel 3.1 sebagai berikut:


III-15


Tabel 3. 1 Data Jarak, daij s s 1 2 3 t

1 3

2 4 2

3 6 2 2

t 20 6 4 1

Untuk menyelesaikan permasalahan jaringan diatas akan digunakan dua metoda yaitu metoda algoritma Djikstra dan metoda algoritma genetika, yang akan dijelaskan dibawah ini:  Algoritma Djikstra Untuk Minimasi Jarak Tahapan pengerjaan untuk kasus jaringan pada Gambar 3.6 dengan algoritma Djikstra adalah sebagai berikut: Langkah 1. Notasikan hanya node s yang diberi tanda, dss = 0, dan jarak dsi =  untuk semua i ≠s dan j = s. Langkah 2. Hitung jarak pada node selanjutnya yang berhubungan dengan node j menggunakan persamaan (3.7). d si min{ d si , d sj da ji } ds1 = min{ds1, dss + das1} = min { , 0 +3} = 3 ds2 = min{ds2, dss + das2} = min { , 0 +4} = 4 ds3 = min{ds3, dss + das3} = min { , 0 +6} = 6 Jarak minimal pada node yang belum diberi tanda adalah ds1 = 3, node 1 adalah diberi tanda dan juga as1 . Jarak terpendek ditetapkan terdiri dari as1 dan nilai j = 1. Untuk iterasi pertama diperlihatkan pada Gambar 3.7


III-16


1 das1 = 3 s

Gambar 3. 7 Iterasi pertama algoritma Djikstra Rute 1 Langkah 3. node t belum diberi tanda, maka ulangi langkah 2. Langkah 2. ds2 = min{ds2, ds1 + da12} = min {4, 3 +2} = 4 ds3 = min{ds3, ds1 + da13} = min {6, 3 +2} = 5 dst = min{dst , ds1 + da 1t} = min { , 3 +6} = 9 Jarak minimal pada node yang belum diberi tanda adalah ds2 = 4, node 2 adalah diberi tanda dan begitu juga dengan as2. Nilai j = 2. Untuk iterasi kedua diperlihatkan pada Gambar 3.8 1 da s1 = 3 s da s2 = 4

2

Gambar 3. 8 Iterasi kedua algoritma Djikstra Rute 1 Langkah 3 node t belum diberi tanda, maka ulangi langkah 2. Langkah 2 ds3 = min{ds3, ds2 + da23} = min {5, 4 +2} = 5 dst = min{dst , ds2 + da 2t} = min {9, 4 +4} = 8 Jarak minimal pada node yang belum diberi tanda adalah d s3 = 5, node 3 diberi tanda dan begitu juga dengan a13. Nilai j = 3. Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-17


Untuk iterasi ketiga diperlihatkan pada Gambar 3.9

da 13 = 2

1

da s1 = 3

3

s da s2 = 4

2

Gambar 3. 9 Iterasi ketiga algoritma Djikstra Rute 1 Langkah 3 node t belum diberi tanda, maka ulangi langkah 2. Langkah 2 dst = min{dst , ds3 + da 3t} = min {8, 5 +1} = 6 Node t akhirnya diberi tanda, juga a3t. Untuk iterasi keempat diperlihatkan pada Gambar 3.10

da s1 = 3

da 13 = 2

1

3

da 3t = 1

s t da s2 = 4

2

Gambar 3. 10 Iterasi keempat algoritma Djikstra Rute 1 Dari langkah-langkah pengerjaan diatas, didapatkan rute terpendek Rs13t pada as1, a 13, dan a3t . dengan panjang rute 3 + 2 + 1 = 6.  Algoritma Genetika untuk Minimasi Jarak Berikut merupakan tahapan yang dilakukan untuk mencapai solusi permasalahan dari penetapan parameter genetika sebelumnya:


III-18


1. Kodifikasi masalah dan Inisialisasi Populasi Pengisian set populasi dengan membangkitkan bilangan acak pada gen masing-masing kromosom seperti yang disajikan pada Tabel 3.3. Kodifikasi dilakukan dengan menggunakan bilangan biner. Untuk node yang mempunyai bilangan biner 1 maka node tersebut dikunjungi oleh moda transportasi, dan bilangan biner 0 untuk sebaliknya. Awal pergerakan dimulai dari node s dan berakhir di node t. Tabel 3. 2 Contoh pengisian Kromosom dengan Bilangan Acak Rute\node Pergerakan Rute

s 1

1 1

2 0

3 1

t 1

Dari Tabel 3.2, memberikan arti moda transportasi memulai pergerakan dari node s kemudian ke node 1 lalu node 3 dan berakhir di node t. Tabel 3. 3 Inisialisasi Kasus Minimasi Jarak Nama\no de Kromos om 1 Kromos om 2 Kromos om 3 Kromos om 4

s 1 1 1 1

1 1 1 1 1

2 1 1 0 0

3 1 0 0 0

t 1 1 1 1

2. Evaluasi kromosom Fungsi objektif didapat melalui penerjemahan kromosom ke dalam rumusan dan fitness melalui satu dibagi dengan nilai fungsi objektif ditambah satu. Rute yang dibentuk oleh bilangan biner 1 pada node-node tersebut mewakili suatu fungsi pada setiap ruasnya. Hal tersebut tergantung pada fungsi tujuan yang ingin dicapai, seperti permasalahan maksimasi atau minimasi baik untuk jarak (daij ), biaya (Caij ), muatan (Maij ), pendapatan (Paij ), atau keuntungan (Kaij ). Berikut contoh perhitungan fungsi objektif (FODk) pada kromosom 1 dengan mengacu persamaan (3.8) yang disajikan di Tabel 3.4,


III-19


Rute terbentuk Rs123t = as1 + a12 + a23 + a3t as1

= das1

= 3 km

a12

= da12

= 2 km

a23

= da23

= 2 km

a3t

= da3t

= 1 km

maka FOD rute Rs123t = das1 + da12 + da23 + da3t = 3 + 2 + 2 +1 = 8 km. Kemudian dihitung nilai fitness pada masing-masing kromosom, dikarenakan tujuan dari permasalahan rute ini merupakan minimasi, maka digunakan persamaan (3.11) yaitu rumus fitness, fk =

1 , FODk merupakan (FOD k 1)

fungsi objektif pada kromosom k. Untuk menghindari pembagian dengan angka 0 maka nilai fungsi objektif dijumlahkan angka 1. Fitness f1 =

1 = 1/ (8 + 1) = 0.11, berikut merupakan tabel ( FOD k 1)

pengerjaan fungsi objektif dari minimasi jarak. Tabel 3. 4 Evaluasi Fungsi Objektif Kasus Minimasi Jarak Nama\no de Kromos om 1 Kromos om 2 Kromos om 3 Kromos om 4

s 1 1 1 1

1 1 1 1 0

2

3 1 1 0 0

t 1 0 0 1

1 1 1 1

FODk 8 9 9 7 Σfk

fk 0,11 0,10 0,10 0,13 0,44

3. Seleksi Kromosom Proses seleksi dilakukan dengan cara membuat kromosom yang mempunyai fitness kecil mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas yang tinggi. Untuk itu dapat digunakan rumus probabilitas pada persamaan (3.13),

P[k] = fk / ∑fk


(3.13) III-20


Untuk contoh kromosom 1, P[1] = f 1 / ∑fk = 0,11 / 0.44 = 0.25. Kemudian untuk nilai probabilitas P[k] dari masing-masing kromosom dikumulatifkan, lalu digunakan untuk proses seleksi dengan bantuan bilangan acak. Setelah dihitung kumulatif probabilitasnya C[k] maka proses seleksi menggunakan roulete-wheel dapat dilakukan. Prosesnya adalah dengan membangkitkan bilangan acak R[k] dalam range 0-1. Jika R[k] < C[1] maka pilih kromosom 1 sebagai induk, selain itu pilih kromosom ke-k sebagai induk dengan syarat C[k-1] < R[k] < C[k]. Roulete wheel diputar sebanyak jumlah populasi (bangkitkan bilangan acak R[k]) dan pada tiap putaran, maka dipilih satu kromosom untuk populasi baru. Untuk contoh kromosom 2, P[2] = 0,23 sehingga C[2] = P[1] + P[2] = 0,25 + 0,23 = 0,48 dengan R[2] = 0,711. Angka acak kedua R[2] adalah lebih besar dari C[1] dan lebih kecil daripada C[3] maka pilih kromosom 3 sebagai kromosom pada populasi baru, dari bilangan acak yang telah dibangkitkan diatas maka populasi kromosom baru hasil proses seleksi dapat dilihat pada Tabel 3.5: Tabel 3. 5 Seleksi Kromosom Kasus Minimasi Jarak Nama\no de Kromos om 1 Kromos om 2 Kromos om 3 Kromos om 4

s 1 1 1 1

1 1 1 1 0

2 1 1 0 0

3 1 0 0 1

t 1 1 1 1

P C R 0,25 0,255 0,815 0,23 0,484 0,711 0,23 0,713 0,931 0,29 1 0,595

Seleksi Kromos om 4 Kromos om 3 Kromos om 4 Kromos om 3

s 1 1 1 1

1 0 1 0 1

2 0 0 0 0

3 1 0 1 0

4. Crossover (pindah silang) Setelah proses seleksi maka proses selanjutnya adalah proses crossover. Metoda yang digunakan salah satunya adalah one-cutting point, yaitu memilih secara acak satu posisi dalam kromosom induk kemudian saling menukar gen. Kromosom yang dijadikan induk dipilih secara acak dan jumlah kromosom yang mengalami crossover dipengaruhi oleh parameter crossover rate. Pada tahap ini digunakan crossover rate adalah sebesar 60%, maka diharapkan


III-21

t 1 1 1 1


dalam satu generasi ada 60% kromosom (semua kromosom) dari satu populasi mengalami proses crossover. Prosesnya adalah sebagai berikut: Jumlah kromosom yang mengalami crossover = crossover rate x jumlah kromosom = 0.6 x 4 = 2.4 ≈2 kromosom. Untuk penentuan kromosomnya digunakan bilangan acak. Demikian juga pasangan kromosom yang akan crossover dipilih dengan menggunakan bilangan acak. Bangkitkan bilangan acak (dengan nilai R[k], kromosom 1-4) pada dua slot untuk menentukan kromosom crossover. Lalu pasangan kromosom ditentukan dengan bilangan acak berupa kromosom crossover, seperti yang terlihat pada Tabel 3.6. Tabel 3. 6 Bilangan Acak Pasangan Crossover Kasus Minimasi Jarak Kromosom 1 x Kromos om 4

Setelah melakukan pemilihan induk proses selanjutnya adalah menentukan posisi crossover seperti pada Tabel 3.7. Tahap ini dilakukan dengan cara membangkitkan bilangan acak dengan batasan 1 sampai (panjang kromosom – 1), dalam kasus ini bilangan acak yang dibangkitkan adalah 1 – 3. Misalkan didapatkan posisi crossover adalah 1 maka kromosom induk akan dipotong mulai gen ke 1 ke kanan kemudian potongan gen tersebut saling ditukarkan antar induk. Posisi cutting-point crossover dipilih menggunakan bilangan acak 1-3 sebanyak jumlah crossover yang terjadi, yaitu CP[1] = 3. Tabel 3. 7 Proses Crossover Kasus Minimasi Jarak Nama\Node Kromosom1 INDUK Kromosom4

s 1 1

1 0 1

2 0 0

3 1 0

t 1 1

Kromosom1 Kromosom4

1 1

0 1

0 0

0 1

1 1

ANAK

Kemudian dari hasil diatas dirangkum menjadi Tabel 3.8 dibawah ini:


III-22


Tabel 3. 8 Hasil Crossover Kasus Minimasi Jarak Nama\node Kromosom Kromosom Kromosom Kromosom

1 2 3 4

s 1 1 1 1

1 0 1 0 1

2 0 0 0 0

3 0 1 1 0

t FODk 1 20 1 6 1 7 1 9

5. Mutasi Jumlah mutasi ditentukan dengan mengalikan mutation rate dan total gen dalam satu populasi. Dengan demikian, didapat hasil = mutation rate x jumlah kromosom x jumlah gen dalam kromosom = 0,03 x 4 x 5 = 0,6 ≈1 (satu) gen termutasi. Mutasi

dilakukan

pada

kromosom

yang dipilih dengan

membangkitkan bilangan acak lokasi kromosom, contoh kasus ini dengan bilangan acak dipilih kromosom 1. Untuk menentukan posisi gen yang termutasi dipilih dengan membangkitkan bilangan acak lokasi gen termutasi atau MP (mutation point). Interval MP adalah 2 hingga n – 1 dari total gen, dimaksudkan untuk menghindari node awal dan akhir termutasi karena mencerminkan pergerakan source ke target. Pada kasus ini, posisi gen termutasi (MP) dipilih dengan bantuan bilangan acak sehingga didapat MP = 3 di kromosom 1. Besarnya nilai mutasi rate menyebabkan jumlah gen termutasi semakin banyak. Namun bila jumlah gen termutasi lebih dari satu maka gen termutasi pada masing-masing kromosom terpilih berjumlah maksimal satu gen. Pembatasan dilakukan agar dalam proses mutasi, satu kromosom hanya terkena satu gen termutasi. Solusi dan populasi setelah proses mutasi disajikan pada Tabel 3.9. Tabel 3. 9 Hasil Mutasi dan Rute Terbaik Kasus Minimasi Jarak Nama\node Kromosom1 Kromosom2 Kromosom3 Kromosom4

s 1 1 1 1

1 0 1 0 1

2 1 0 0 0

3 0 1 1 0

t FODk 1 8 1 6 1 7 1 9


Termutasi Solusi

III-23


Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.11 dibawah ini: da 13 = 2 da s1 = 3

3

1

da 3t = 1 t

s 2

Gambar 3. 11 Hasil pengerjaan algoritma genetika Sebagai perbandingan dengan algoritma Djikstra, maka untuk iterasi keempat algoritma Djikstra diperlihatkan pada Gambar 3.12.

3

2

1

3

1 t

s 4

2

Gambar 3. 12 Iterasi keempat algoritma Djikstra Rute 1 Dari langkah-langkah pengerjaan diatas menggunakan algoritma Djikstra dan algoritma genetika, didapatkan rute terpendek yang sama pada as1 , a13, dan a3t dengan panjang rute 3 + 2 + 1 = 6, seperti pada Tabel 3.10. Tabel 3. 10 Rute Terbaik Kasus Minimasi Jarak

Rute

Algoritma Djikstra Algoritma Genetika Rs13t Rs13t

FODk

6 km

6 km

Dengan demikian, penentuan rute dengan menggunakan kedua algoritma diatas didapat hasil yang sama, yaitu rute Rs13t .


III-24


3.3.4 Maksimasi Muatan Tanpa Batasan Kapasitas Tiap Ruas Dengan kasus yang berbeda, yaitu memaksimasi muatan diharapkan dapat diselesaikan dengan baik menggunakan kedua metoda. Konsep graph masih dipakai dalam pengerjaan masalah ini, seperti pada Gambar 3.13 dibawah. Dimana tiap arc telah diidentikkan dengan aij yang merepresentasikan muatan dari tiap-tiap arc. Tujuan yang akan dicapai adalah bagaimana menghubungkan node s (source) ke node t (target) melalui ruas yang dibentuk oleh node-node yang ada, dimana tercapai keadaan jumlah muatan yang maksimal. Muatan maksimal yang dicari didefinisikan sebagai jumlah dari muatan disetiap ruas yang dilalui. Permasalahan maksimasi muatan melibatkan pencarian path dari s ke t yang mempunyai kemungkinan jumlah muatan terbesar.

p

B

k

T BC dan T BC Tp BD dan T kBD p k T BE dan T BE

T pDE dan T kDE

D

1

3

A

t

s p T AB T pAC p T AD TpAE

E

k

dan T AB dan T kAC k dan T AD dan T kAE

2 p

C

k

T CD dan T CD Tp CE dan T kCE

Gambar 3. 13 Contoh jaringan maksimasi muatan Untuk informasi keinginan pergerakan dapat dilihat pada Tabel 3.11 dan Tabel 3.12 sebagai berikut: Tabel 3. 11 Data Tpod Penumpang A A B C D E

B 20

C 15 20

D 10 10 5

E 5 5 10 5

Tabel 3. 12 Data Tkod Kendaraan A A B

B

C

D

E

10

7 10

5 5

2 2

2

5 2

C D E


III-25


Untuk kasus jaringan graph pada Gambar 3.13, besar muatan ditiap ruas dipengaruhi oleh keinginan pergerakan (T od) dari centroid asal dan sebelumnya serta centroid pada node lain yang ikut membentuk rute. Oleh karena itu, sangat penting untuk mengetahui rute yang dibentuk terlebih dahulu dari sekumpulan node. Rute yang terbentuk tersebut belum tentu menghubungkan semua node, bisa hanya beberapa node saja. Hal tersebut membuat muatan pada tiap ruas sangat tergantung dari pemilihan rute. Sehingga dengan demikian dapat diketahui keinginan pergerakan (Tod) dari centroid melalui node yang terlibat pada tiap ruas. Selain itu, pada setiap ruas terdapat batasan kapasitas (Uaij) muatan yang diijinkan. Hal tersebut tergantung pada jenis moda dan kapasitas moda. Tetapi untuk kasus pada subbab ini, hal tersebut diabaikan untuk lebih memahami cara penyelesaian. Permasalahan dengan mempertimbangkan kapasitas muatan tiap ruas akan dibahas pada subbab 3.3.6. Untuk menyelesaikan permasalahan jaringan diatas akan digunakan dua metoda yaitu metoda algoritma Djikstra dan metoda algoritma genetika, yang akan dijelaskan dibawah ini:  Metoda Algoritma Djikstra Untuk Maksimasi Muatan Algoritma Djikstra mempunyai dasar yang baik dalam menyelesaikan permasalahan jarak terpendek. Tetapi untuk muatan dengan memperhitungkan keinginan pergerakan (Tod) belum bisa digunakan karena nilai muatan pada aij yang berubahubah sesuai dengan node yang diberi tanda pada prosedur algoritma ini. Selain itu permasalahan yang ditemukan adalah ketika node i yang akan ditinjau terhadap node j, maka muatan sebelumnya perlu ditambahkan dengan keinginan pergerakan (Tod) sesuai dengan node i tersebut. Dengan keterbatasan tersebut, maka dipakai beberapa tahapan berikut: a. Menentukan 3 rute terbaik dari permasalahan minimasi jarak dengan algoritma Djikstra diatas. b. Membebankan keinginan pergerakan (Tod) pada masing-masing rute diatas.


III-26


c. Dari ketiga rute diatas, dipilih rute yang mempunyai nilai muatan terbanyak. Kemudian ketiga tahapan diatas diaplikasikan sebagai berikut: a. Menentukan 3 Rute Terbaik Dengan Fungsi Tujuan Minimasi Jarak Setelah rute terbaik pertama terbentuk seperti pada Gambar 3.14 dengan menggunakan algoritma Djikstra, maka rute selanjutnya dicari dengan memperbarui nilai jarak setelah rute terbaik pertama didapat. Hal ini dilakukan agar ruas pada rute terbaik tidak terbentuk lagi. Untuk rute Rs13t, ruas as1 diberi nilai jarak yang besar agar rute tersebut tidak terbentuk kembali. da 13 = 2

1

3

da s1 = 3 6

da 3t = 1 6

2

s

2

4

t

2

4

Gambar 3. 14. Rute 1 dari permasalahan jaringan Dengan demikian, ruas as1 diberikan nilai 10 untuk menentukan rute terpendek kedua dari node s ke node t. 2

1

3 1

da s1 = 10 6

6

2

s 4

2 2

t 4

Gambar 3. 15. Permasalahan jaringan untuk rute 2

Pengerjaan rute kedua terbaik untuk kasus jaringan pada Gambar 3.15 dengan algoritma Djikstra Langkah 1. Notasikan hanya node s yang diberi tanda, dss = 0, dan jarak dsi =  untuk semua i ≠s dan j = s.


III-27


Langkah 2. Hitung jarak pada node selanjutnya yang berhubungan dengan node j menggunakan persamaan (3.7). ds1 = min{ds1, dss + das1} = min { , 0 +10} = 10 ds2 = min{ds2, dss + das2} = min { , 0 +4} = 4 ds3 = min{ds3, dss + das3} = min { , 0 +6} = 6 Jarak minimal pada node yang belum diberi tanda adalah ds2 = 4, node 2 adalah diberi tanda dan juga as 2. Jarak terpendek ditetapkan terdiri dari as2 dan nilai j = 2. Untuk iterasi pertama diperlihatkan pada Gambar 3.16

s da s2 = 4 2

Gambar 3. 16 Iterasi pertama algoritma Djikstra Rute 2 Langkah 3.node t belum diberi tanda, maka ulangi langkah 2. Langkah 2. ds3 = min{ds3, ds2 + da23} = min {6, 4 +2} = 6 dst = min{dst , ds2 + da2t } = min { , 4 +4} = 8 Jarak minimal pada node yang belum diberi tanda adalah ds3 = 6, node 3 adalah diberi tanda dan begitu juga dengan a23. Nilai j = 3. Untuk iterasi kedua diperlihatkan pada Gambar 3.17 3 da 23 = 2

s da s2 = 4

2

Gambar 3. 17 Iterasi kedua algoritma Djikstra Rute 2 Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-28


Langkah 3 node t belum diberi tanda, maka ulangi langkah 2. Langkah 2 dst = min{dst , ds3 + da3t } = min {8, 6 +1} = 7 Node t akhirnya diberi tanda, juga a3t. Untuk iterasi keempat diperlihatkan pada Gambar 3.18

3

1

1

2

t

s 4

2

Gambar 3. 18 Iterasi ketiga algoritma Djikstra Rute 2 Dari langkah-langkah pengerjaan diatas, didapatkan rute terpendek Rs23t pada as1, a23, dan a3t. dengan panjang rute = 4 + 2 + 1 = 7. Setelah rute terbaik pertama dan kedua terbentuk seperti pada Gambar 3.19 dengan menggunakan algoritma Djikstra, maka rute selanjutnya dicari dengan memperbarui nilai jarak setelah rute terbaik pertama dan kedua didapat. Hal ini dilakukan agar ruas pada rute terbaik tidak terbentuk lagi. Untuk rute Rs13t dan rute Rs23t, ruas as2 dan ruas as1 diberi nilai jarak yang besar agar rute tersebut tidak terbentuk kembali. 2

1 3

3 1

6 2

2

s 4

2

6 t 4

Gambar 3. 19. Rute 1 dan 2 dari permasalahan jaringan Dengan demikian, ruas as2 diberikan nilai 10 untuk menentukan rute terpendek ketiga dari node s ke node t. Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-29

BAB III METODOLOGI DAN PERBANDINGAN METODA 2

1 10

3 1

6

6

2

s 4

2

t

2

4

Gambar 3. 20. Permasalahan jaringan untuk rute 3

Pengerjaan rute ketiga terbaik untuk kasus jaringan pada Gambar 3.20 dengan Algoritma Djikstra Langkah 1. Notasikan hanya node s yang diberi tanda, dss = 0, dan jarak dsi =  untuk semua i ≠s dan j = s. Langkah 2. Hitung jarak pada node selanjutnya yang berhubungan dengan node j menggunakan persamaan (3.7). ds1 = min{ds1, dss + das1} = min { , 0 +10} = 10 ds2 = min{ds2, dss + das2} = min { , 0 +10} = 10 ds3 = min{ds3, dss + das3} = min { , 0 +6} = 6 Jarak minimal pada node yang belum diberi tanda adalah ds3 = 6, node 3 adalah diberi tanda dan juga as3 . Jarak terpendek ditetapkan terdiri dari as3 dan nilai j = 3. Untuk iterasi pertama diperlihatkan pada Gambar 3.21

2 6 s

Gambar 3. 21 Iterasi pertama algoritma Djikstra rute 3

Langkah 3.node t belum diberi tanda, maka ulangi langkah 2.


III-30


Langkah 2. dst = min{dst , ds3 + da3t } = min { , 6 +1} = 7 Jarak minimal pada node yang belum diberi tanda adalah d(t) = 7, node t adalah diberi tanda dan begitu juga dengan a3t. Untuk iterasi kedua diperlihatkan pada Gambar 3.22.

Pa ij

3

s

1 t

Gambar 3. 22 Iterasi kedua algoritma Djikstra rute 3 Dari langkah-langkah pengerjaan diatas, didapatkan rute terpendek Rs3t pada as3 dan a3t. dengan panjang rute 6 + 1 = 7. Dengan menggunakan metoda algoritma Djikstra pada permasalahan menentukan rute dengan fungsi tujuan meminimasi jarak, didapat tiga alternatif rute terpendek yaitu pada Tabel 3.13 dibawah ini: Tabel 3. 13 Tiga Rute Terbaik Hasil Algoritma Djikstra Rute\Jarak Total Jarak Rute Rs13t 6 km Rute Rs23t 7 km Rute Rs3t 7 km

Dari ketiga rute diatas, dengan pengerjaan algoritma Djikstra maka rute yang paling pendek adalah Rs13t. b. Pembebanan Keinginan Pergerakan (Tod ) Pada Tiga Rute Terbaik Sebelumnya untuk kasus maksimasi muatan ini, perlu ditekankan untuk menentukan muatan pada masing-masing ruas, ikut melibatkan keinginan pergerakan (Tod) dari centroid. Oleh karena itu, penentuan kemungkinan rute perlu ditetapkan untuk Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-31


menentukan besar keinginan pergerakan yang nantinya akan dibebankan pada muatan setiap ruas pada rute. Rute-rute terbaik yang didapat dari algoritma Djikstra digunakan untuk dibebani dengan keinginan pergerakan yang terlibat pada rute yang bersangkutan. Rumus muatan pada persamaan (3.1) diatas dikalikan dengan jarak (daij) pada masing-masing ruas agar mempunyai satuan dan arti yang jelas. Persamaan diatas berlaku untuk kendaraan dan penumpang. Persamaan (3.2) untuk muatan penumpang-km disetiap ruas: p p ij MDpaij = Mpaij x daij , dimana M aij od T od a

o

d

Persamaan (3.3) untuk muatan kendaraan-km disetiap ruas: M k a ij odij T k od a

MDkaij = Mkaij x daij , dimana

o

d

Kemudian keinginan pergerakan (Tod) baik penumpang (Tpod) maupun kendaraan (Tkod) dibebankan ke dalam ruas, seperti berikut: Muatan Penumpang - Rute Rs13t

= as1 + a13 + a3t

Mpas1 = Tp AB + TpAD + TpAE

= 20 + 10 + 5

= 35 orang

Mpa13 = Tp AD + TpAE + TpBD + TpBE = 10 + 5 + 10 + 5

= 30 orang

Mpa3t = TpAE + TpBE + TpDE

= 15 orang

=5+5+5

Sedangkan untuk muatan penumpang-km, yaitu sebagai berikut MDpas1 = Mp as1 x das1

= 35 x 3 = 105 orang-km

MDpa13 = Mp a13 x da13

= 30 x 2 = 60 orang-km

MDpa3t = Mpa3t x da3t

= 15 x 1 = 15 orang-km

untuk muatan penumpang-km total dari rute Rs13t = 105 + 60 + 15 = 180 orang-km - Rute Rs23t

= as2 + a23 + a3t

Mpas2 = T pAC + TpAD + TpAE

= 30 orang


III-32


Mpa23 = Tp AD + TpAE + TpCD + TpCE

= 30 orang

Mpa3t = TpAE + TpCE + TpDE

= 20 orang


= 30 x 4 = 120 orang-km


= 30 x 2 = 60 orang-km


= 20 x 1 = 20 orang-km


= as3 + a3t

Mpas3 = Tp AD + TpAE = 15 orang Mpa3t = TpAE + TpDE = 10 orang Sedangkan untuk muatan penumpang-km, yaitu sebagai berikut MDpas2 = Mp as2 x das2

= 15 x 6 = 90 orang-km


= 10 x 1 = 10 orang-km

untuk muatan penumpang-km total dari rute Rs23t = 90 + 10 = 100 orang-km Selain itu hasil pembebanan dari tiga rute diatas dapat dilihat pada Tabel 3.14 berikut: Tabel 3. 14 Tiga Rute Terbaik Maksimasi Muatan Penumpang

1

Rute Rs13t

Total (orang-km) 180

2

Rs23t

200

3

R s3t

100

No


III-33


Dari hasil pembebanan diatas, maka dapat disimpulkan dengan rute terpendek Rs23t didapat jumlah muatan penumpang-km sebesar yaitu 200 orang-km, seperti pada Gambar 3.23. 3

Ma3t = 20 s

Ma s2 = 120

Ma 23 = 60

t

2

Gambar 3. 23 Maksimasi muatan penumpang algoritma Djikstra dengan hasil rute R s23t Muatan Kendaraan - Rute Rs13t

= as1 + a13 + a3t

Mkas1 = Tk AB + TkAD + TkAE = 10 + 5 + 2

= 17 knd

Mka13 = Tk AD + TkAE + TkBD + TkBE = 5 + 2 + 5 + 2 Mka3t = T kAE + TkBE + TkDE = 2 + 2 + 2

= 14 knd

= 6 knd

Sedangkan untuk muatan kendaraan-km, yaitu sebagai berikut MDkas1 = Mk as1 x das1

= 17 x 3 = 51 knd-km

MDka13 = Mk a13 x da13

= 14 x 2 = 28 knd-km

MDka3t = Mka3t x da3t

= 6 x 1 = 6 knd-km

untuk muatan kendaraan-km total dari rute Rs13t = 51 + 28 + 6 = 85 knd-km - Rute Rs23t

= as2 + a23 + a3t

Mkas2 = T kAC + TkAD + TkAE

=7+5+2

Mka23 = Tk AD + TkAE + TkCD + TkCE

= 14 knd

= 5 + 2 + 2 + 5 = 14 knd

Mka3t = T kAE + TkCE + TkDE = 2 + 5 + 2

= 9 knd

Sedangkan untuk muatan kendaraan-km, yaitu sebagai berikut


III-34


MDkas2 = Mk as2 x das2

= 14 x 4 = 56 knd-km


= 14 x 2 = 28 knd-km


= 9 x 1 = 9 knd-km

untuk muatan kendaraan-km total dari rute Rs 23t = 56 + 28 + 9 = 93 knd-km - Rute Rs3t

= as3 + a3t

Mkas3 = Tk AD + TkAE = 5 + 2

= 7 knd

Mka3t = T kAE + TkDE = 2 + 2

= 4 knd


= 7 x 6 = 42 knd-km


= 4 x 1 = 4 knd-km

untuk muatan kendaraan-km total dari rute Rs 23t = 42 + 4 = 46 knd-km Selain itu hasil pembebanan dari tiga rute diatas dapat dilihat pada Tabel 3.15 berikut: Tabel 3. 15 Tiga Rute Terbaik Maksimasi Muatan Kendaraan

1

Rute Rs13t

Total (knd-km) 85

2

Rs23t

93

3

Rs3t

46

No

Dari hasil pembebanan diatas, maka dapat disimpulkan dengan rute terpendek Rs23t didapat jumlah muatan yang besar yaitu 93 kendaraan-km, seperti pada Gambar 3.24.


III-35


3

Ma3t = 9 s

Mas2 = 56

Ma 23 = 28

t

2

Gambar 3. 24 Hasil maksimasi muatan kendaraan algoritma Djikstra dengan rute Rs23t  Algoritma Genetika untuk Maksimasi Muatan Untuk data yang dipakai adalah informasi keinginan pergerakan (Tod) pada Tabel 3.11 untuk muatan penumpang dan Tabel 3.12 untuk muatan kendaraan. Berikut merupakan tahapan yang dilakukan untuk mencapai solusi permasalahan dari maksimasi muatan: Muatan Penumpang 1. Kodifikasi Masalah dan Inisialisasi Populasi Pengisian set populasi dengan membangkitkan bilangan pada gen kromosom, seperti pada Tabel 3.16. Tabel 3. 16 Inisialisasi Populasi Kasus Maksimasi Muatan Nama\Node Kromosom1 Kromosom2 Kromosom3 Kromosom4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

2. Evaluasi kromosom Merupakan fungsi objektif dari masing-masing kromosom (rute/solusi) dengan menjumlahkan nilai muatan pada masing-masing ruas pada rute yang dipilih. Kemudian untuk nilai fitness (fk) digunakan dari fungsi objektif muatan (FOM k) pada persamaan (3.9) dan (3.12) karena merupakan fungsi maksimasi. Berikut contoh perhitungan fungsi objektif (FOMk ) pada kromosom 1 beserta hasil fungsi objektif semua kromosom di Tabel 3.17. Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-36


Rute terbentuk Rs13t = as1 + a13 + a3t Mpas1 = Tp AB + TpAD + TpAE = 20 + 10 + 5 = 35 orang Mpa13 = Tp AD + TpAE + TpBD + TpBE = 10 + 5 + 10 + 5 = 30 orang Mpa3t = T pAE + TpBE + TpDE = 5 + 5 + 5 = 15 orang Sedangkan untuk muatan penumpang-km, yaitu sebagai berikut MDpas1 = Mp as1 x das1 = 35 x 3 = 105 orang-km MDpa13 = Mp a13 x da13 = 30 x 2 = 60 orang-km MDpa3t = M pa3t x da3t = 15 x 1 = 15 orang-km Sehingga untuk FOM rute R s13t = MDpas1 + MDpa13 + MDpa3t = 105 + 60 + 15 = 180 orang-km. Tabel 3. 17 Evaluasi Fungsi Objektif Kasus Maksimasi Muatan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t FOMk = fk 1 180 1 290 1 135 1 100 Σf k 705

3. Seleksi Kromosom Didapat dengan menghadapkan nilai random dengan kumulatif probabilitas. Kondisi yang berlaku adalah ketika R[k] < C[1] maka kromosom 1 dipilih sebagai induk, kromosom ke-k dipilih sebagai induk dengan syarat C[k-1] < R[k] < C[k]. Kromosom pada tahap ini diperlihatkan pada Tabel 3.18 sebagai berikut:


III-37


Tabel 3. 18 Seleksi Kromosom Kasus Maksimasi Muatan Nama\Node Kromos om 1 Kromos om 2 Kromos om 3 Kromos om 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

P 0,26 0,41 0,19 0,14

C 0,255 0,667 0,858 1,000

R 0,095 0,442 0,137 0,595


s 1 1 1 1

1 1 1 1 1

2 0 1 0 1

4. Crossover (pindah silang) Jumlah kromosom yang mengalami crossover = Crossover rate x jumlah kromosom = 0.6 x 4 = 2.4 ≈ 2 kromosom. Lalu pasangan kromosom ditentukan dengan bilangan acak berupa kromosom crossover, seperti yang terlihat pada Tabel 3.19. Tabel 3. 19 Bilangan Acak Pasangan Crossover Kasus Maksimasi Muatan Kromos om 3 x Kromos om 4

Tahapan cross over dilakukan dengan menentukan letak cutting point yang juga melalui bilangan acak dan menukarkan gen yang terpotong tersebut. Proses crossover disajikan pada Tabel 3.20 dengan CP[1] = 3, berikut dengan hasil crossover pada Tabel 3.21. Tabel 3. 20 Proses Crossover Kasus Maksimasi Muatan Nama\Node Kromosom 3 INDUK Kromosom 4

s 1 2 3 t 1 1 0 1 1 1 1 1 0 1

Kromosom 3 Kromosom 4

1 1 0 0 1 1 1 1 1 1

ANAK

Tabel 3. 21 Hasil Crossover Kasus Maksimasi Muatan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 1

2 0 1 0 1

3 1 0 0 1

t 1 1 1 1

FOMk 180 290 135 395


III-38

3 1 0 1 0

t 1 1 1 1


5. Mutasi Jumlah gen termutasi

= panjang gen x mutation rate = 20 x 0,03 = 0,6 ~ 1

gen. Dengan bilangan acak, kromosom dan mutation point ditentukan (yaitu MP = 3 pada kromosom 1), maka hasil mutasi diperlihatkan pada Tabel 3.22. Tabel 3. 22 Hasil Mutasi Kasus Maksimasi Muatan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 1

2 1 1 0 1

3 1 0 0 1

t 1 1 1 1

FOMk Termutasi

395 290 135 395

Solusi

Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.25 dibawah ini: 1

3

p

M as1=50 Mp a12=65

s

Mp a3t=25

Mp a23=45

t

2

Gambar 3. 25. Hasil maksimasi muatan penumpang-km dengan algoritma genetika Muatan Kendaraan Untuk muatan kendaraan, cara pengerjaannya tidak jauh berbeda dengan muatan penumpang, hanya pada nilai muatan ditiap ruas yang berbeda. Oleh karena itu, untuk muatan kendaraan disajikan hasil akhir dari proses algoritma genetika seperti pada Tabel 3.23 dibawah ini: Tabel 3. 23 Hasil Mutasi untuk Maksimasi Muatan Kendaraan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 1

2 1 1 0 1

3 1 0 0 1

t 1 1 1 1

FOMk 187 135 60 187


Termutasi

Solusi

III-39


Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.26 dibawah ini: 1

3

k

M as1=24 k

k

M a12 =31

s

k

M a3t=11

M a23 =21

t

2

Gambar 3. 26. Hasil maksimasi muatan kendaraan-km dengan algoritma genetika Dari kedua metoda diatas, hasil yang didapat berbeda seperti yang disajikan pada Tabel 3.24 dan Tabel 3.25 berikut, baik untuk kasus muatan penumpang maupun kendaraan. Tabel 3. 24 Hasil Perbandingan Metoda Kasus Maksimasi Muatan Penumpang

Rute FOMk

Algoritma Djikstra Algoritma Genetika Rs23t Rs123t 200

395

Tabel 3. 25 Hasil Perbandingan Metoda Kasus Maksimasi Muatan Kendaraan

Rute FOMk


187

Untuk kedua muatan baik penumpang maupun kendaraan, didapat rute dan nilai muatan yang berbeda jauh. Hal tersebut dikarenakan pada algoritma Djikstra hanya berdasarkan rute terpendek. Dimana dengan rute terpendek belum tentu nilai muatan yang didapat maksimal, walaupun jarak yang didapat relatif pendek. Sedangkan algoritma genetika menelusuri semua alternatif dengan bantuan operator genetika sehingga terbentuk rute yang maksimal.


III-40


3.3.5 Maksimasi Keuntungan Tanpa Batasan Kapasitas Tiap Ruas Untuk kasus maksimasi keuntungan akan dibantu dengan ilustrasi graph pada Gambar 3.27 dibawah, dimana tiap ruas telah diidentikkan dengan aij yang merepresentasikan keuntungan dari tiap-tiap arc. Tujuan yang akan dicapai adalah bagaimana menghubungkan node s (source) ke node t (target) melalui ruas yang dibentuk oleh node-node yang ada secara kedepan (keinginan pergerakan, Tod, tidak boleh kembali ke node sebelumnya/lebih kecil), dimana tercapai keadaan jumlah keuntungan yang maksimal. Keuntungan maksimal yang dicari didefinisikan sebagai jumlah dari keuntungan disetiap ruas yang dilalui. Permasalahan maksimasi keuntungan melibatkan pencarian path dari s ke t yang mempunyai kemungkinan jumlah keuntungan terbesar.

T pBC dan T kBC p k T BD dan T BD p k T BE dan T BE

D B da13 = 2

1

A

das1 = 3

t das2 = 4

da12 = 2

dan T

k DE

da3t = 1

da23 = 2

s

T pAB dan T kAB p k T AC dan T AC p T AD dan T kAD p k T AE dan T AE

p DE

3

da1t = 6

das3 = 6

T

E

da2t = 4 2 C

p

k

T CD dan T CD Tp CE dan TkCE

Gambar 3. 27. Contoh permasalahan jaringan untuk maksimasi keuntungan Sedangkan data yang dipakai adalah informasi keinginan pergerakan (Tod) pada Tabel 3.11 untuk muatan penumpang dan Tabel 3.12 untuk muatan kendaraan. Dari penjelasan terminologi pada subbab sebelumnya, telah dijelaskan informasiinformasi yang dibutuhkan, yaitu: Tp

: 2 (rp/org/km)

Bo

: 30 (rp/km)


III-41


Tk

: 4 (rp/knd/km)

Bt

: 100 (rp/kapal)

Bp

: 75 (rp)

Hubungan rumusan biaya, pendapatan, dan keuntungan yang didapat dari rute terbentuk dihitung menggunakan persamaan (3.4), (3.5), dan (3.6). Untuk menyelesaikan permasalahan jaringan diatas akan digunakan dua metoda yaitu metoda algoritma Djikstra dan metoda algoritma genetika.  Metoda Algoritma Djikstra Untuk Maksimasi Keuntungan Dari penjelasan diatas mengenai maksimasi muatan dengan algoritma Djikstra, maka begitu

juga

dengan

maksimasi

keuntungan,

mengalami

kesulitan

dalam

penyelesaiannya. Hal ini disebabkan dalam keuntungan terlibat variabel pendapatan (Paij ) dan biaya (Caij ). Dalam pendapatan bergantung dari muatan (Maij ), begitu juga dengan biaya yaitu terhadap jarak (daij ). Dengan keterbatasan tersebut, maka dipakai beberapa tahapan seperti dalam kasus maksimasi muatan berikut: a. Menentukan 3 rute terbaik dari permasalahan minimasi jarak pada subbab diatas. b. Kemudian pendapatan dan biaya dihitung pada masing-masing rute diatas berdasarkan informasi jarak dan muatan. c. Dari ketiga rute diatas, dipilih rute yang mempunyai nilai keuntungan terbanyak. Dari rute terbaik pada Tabel 3.14 dan informasi jarak dan muatan dari subbab sebelumnya maka dapat dihitung keuntungan tiap rute, yang disajikan sebagai berikut: Keuntungan Rute Rs13t Pendapatan





Pa ij  M p a ij * T p * da ij  M k aij * T k * da ij




III-42


Pas1

= (35 * 2 * 3) + ( 17 * 4 * 3)

= 210 + 204

= Rp. 414,-

Pa13

= (30 * 2 * 2) + ( 14 * 4 * 2)

= 120 + 112

= Rp. 232,-

Pa3t

= (15 * 2 * 1) + ( 6 * 4 * 1)

= 30 + 24

= Rp. 54,-

Biaya


Cas1

= ( 30 * 3 ) + ( 75 * 1) = Rp. 165,-

Ca13

= ( 30 * 2 ) + ( 75 * 1) = Rp. 135,-

Ca3t

= ( 30 * 1 ) + ( 75 * 1) = Rp. 105,-

Keuntungan Ka ij Pa ij Ca ij

Kas1

= Rp. 414 – Rp. 165

= Rp. 249,-

Ka13

= Rp. 232 – Rp. 135

= Rp. 97,-

Ka3t

= Rp. 54 – Rp. 105

= Rp. -51,-

Ka i

ij

= Rp. 295,-

j

FOK k Kaij B t i

j

FOKk = Rp. 295 – Rp. 100 = Rp. 195,Keuntungan Rute Rs23t Pendapatan





Pa ij  M aij * T p * da ij  M a ij * Tk * da ij p

k



Pas2

= (30 * 2 * 4) + ( 14 * 4 * 4)

= 240 + 224

= Rp. 464,-

Pa23

= (30 * 2 * 2) + ( 14 * 4 * 2)

= 120 + 112

= Rp. 232,-


III-43


Pa3t

= (20 * 2 * 1) + ( 9 * 4 * 1)

= 40 + 36

= Rp. 76,-

Biaya


Cas2

= ( 30 * 4 ) + ( 75 * 1) = Rp. 195,-

Ca23

= ( 30 * 2 ) + ( 75 * 1) = Rp. 135,-

Ca3t

= ( 30 * 1 ) + ( 75 * 1) = Rp. 105,-


Kas2

= Rp. 464 – Rp. 195

= Rp. 269,-

Ka23

= Rp. 232 – Rp. 135

= Rp. 97,-

Ka3t

= Rp. 76 – Rp. 105

= Rp. -29,-

Ka i

ij

= Rp. 337,-

j

FOKk = Rp. 337 – Rp. 100 = Rp. 237,Keuntungan Rute Rs3t Pendapatan





Pa ij  M p a ij * T p * da ij  M k aij * T k * da ij



Pas3

= (15 * 2 * 6) + ( 7 * 4 * 6)

= 180 + 168

= Rp. 348,-

Pa3t

= (10 * 2 * 1) + ( 4 * 4 * 1)

= 20 + 16

= Rp. 36,-

Biaya Ca ij  B o * da ij   Bp * Np 

Cas3

= ( 30 * 6 ) + ( 75 * 1) = Rp. 255,-


III-44


Ca3t

= ( 30 * 1 ) + ( 75 * 1) = Rp. 105,-


Kas3

= 348 – 255

= Rp. 93,-

Ka3t

= 36 – 105

= Rp. -69,-

Ka i

ij

= Rp. 24,-

j

FOKk = Rp. 24 – Rp. 100 = Rp. -76,Dari ketiga rute diatas, hasil keuntungan yang didapat berbeda-beda seperti yang disajikan pada Tabel 3.26 berikut: Tabel 3. 26 Keuntungan Untuk Tiga Rute Terpendek FOK

1

Rute Rs13t

2

Rs23t

237

3

Rs3t

-76

No

195

Dan didapat rute Rs23t sebagai rute yang memiliki keuntungan terbesar dengan menggunakan metoda algoritma Djikstra.  Algoritma Genetika Untuk Maksimasi Keuntungan Untuk data yang dipakai adalah informasi jarak pada Tabel 3.1 serta keinginan pergerakan (T od) pada Tabel 3.11 untuk muatan penumpang dan Tabel 3.12 untuk muatan kendaraan juga informasi tambahan lainnya yang telah disajikan sebelumnya. Berikut merupakan tahapan yang dilakukan untuk mencapai solusi permasalahan dari maksimasi keuntungan:


III-45


1. Kodifikasi masalah dan Inisialisasi Populasi Pengisian set populasi dengan membangkitkan bilangan pada gen kromosom, yang disajikan pada Tabel 3.27. Tabel 3. 27 Inisialisasi Kasus Maksimasi Keuntungan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

2. Evaluasi kromosom Merupakan fungsi objektif dari masing-masing kromosom (rute/solusi) dengan menjumlahkan nilai keuntungan pada masing-masing ruas pada rute yang dipilih. Kemudian untuk nilai fitness (fk) digunakan dari fungsi objektif keuntungan (FOK k) pada persamaan (3.10) dan (3.12) karena merupakan fungsi maksimasi. Tetapi dalam pengerjaan fungsi objektif menggunakan angka bantuan sebesar 100 untuk membuat nilainya positif. Hal ini dilakukan karena ada nilai negatif yang dihindari agar dalam proses probabilitas P[k] nilainya positif dan bilangan acak masih dapat bekerja. Berikut contoh perhitungan fungsi objektif keuntungan (FOKk) pada kromosom 1 beserta semua kromosom di Tabel 3.28 dengan menggunakan informasi yang telah disajikan. Rute terbentuk Rs13t = as1 + a13 + a3t Pendapatan





Pa ij  M a ij * T p * da ij  M aij * T k * da ij p

k



Diketahui: Mpas1 = 35, Mpa13 = 30, Mp a3t = 15 dan Mkas1 = 17, Mka13 = 14, Mka3t = 6 sehingga Pas1 = Rp. 414,- ; Pa13 = Rp. 232,- ; Pa3t = Rp. 54,-. Biaya Ca ij  B o * daij   Bp *N p  Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-46


Diketahui: das1 = 3 km, da13 = 2 km, da3t = 1 km didapat Cas1 = Rp. 165,- , Ca13 = Rp. 135,- , Ca3t = Rp. 105,Keuntungan Ka ij Pa ij Ca ij

Kas1 = Rp. 249,- ; Ka13 = Rp. 97,- ; Ka3t = Rp. -51,-

Ka i

ij

= Rp. 295,- sehingga FOKk = Rp. 295 – Rp. 100 = Rp. 195,-

j

kemudian ditambahkan angka bantuan sebesar 100 menjadi FOKk = Rp. 295,Tabel 3. 28 Evaluasi Fungsi Objektif Kasus Maksimasi Keuntungan Nama\Node Kromosom Kromosom Kromosom Kromosom

1 2 3 4

s

1

2

3

t

FOKk = fk

1 1 1 1

1 1 1 0

0 1 0 0

1 0 0 1

1 1 1 1 Σfk

295 625 90 24 1034

3. Seleksi Kromosom Didapat dengan menghadapkan nilai random dengan kumulatif probabilitas. Kondisi yang berlaku adalah ketika R[k] < C[1] maka kromosom 1 dipilih sebagai induk, kromosom ke-k dipilih sebagai induk dengan syarat C[k-1] < R[k] < C[k]. Kromosom pada tahap ini diperlihatkan pada Tabel 3.29 sebagai berikut: Tabel 3. 29 Seleksi Kromosom Kasus Maksimasi Keuntungan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

P 0,29 0,60 0,09 0,02

C 0,285 0,890 0,977 1,000

R 0,095 0,442 0,138 0,595

Kromosom 1 ---> Kromosom 2 ---> Kromosom 3 ---> Kromosom 4 --->

Kromosom 1 Kromosom 2 Kromosom 1 Kromosom 2


s 1 1 1 1

1 1 1 1 1

2 0 1 0 1

3 1 0 1 0

t 1 1 1 1

III-47


4. Crossover (pindah silang) Jumlah kromosom yang mengalami crossover = Crossover rate x jumlah kromosom = 0.6 x 4 = 2.4 ≈ 2 kromosom. Lalu pasangan kromosom ditentukan dengan bilangan acak berupa kromosom crossover, seperti yang terlihat pada Tabel 3.30. Tabel 3. 30 Bilangan Acak Pasangan Crossover Kasus Maksimasi Keuntungan Kromos om 3 x Kromos om 4

Tahapan crossover dilakukan dengan menentukan letak cutting point yang juga melalui bilangan acak dan menukarkan gen yang terpotong tersebut. Proses crossover disajikan pada Tabel 3.31 dengan CP[1] = 3, berikut dengan hasil crossover pada Tabel 3.32. Tabel 3. 31 Proses Crossover Kasus Maksimasi Keuntungan Nama\Node Kromosom 3 INDUK Kromosom 4

s 1 2 3 t 1 1 0 1 1 1 1 1 0 1

Kromosom 3 Kromosom 4

1 1 0 0 1 1 1 1 1 1

ANAK

Tabel 3. 32 Hasil Crossover Kasus Maksimasi Keuntungan Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 1

2 0 1 0 1

3 1 0 0 1

t 1 1 1 1

FOMk 295 625 90 998



gen. Dengan bilangan acak, kromosom dan mutation point ditentukan (yaitu MP = 3 pada kromosom 1), maka hasil mutasi diperlihatkan pada Tabel 3.33. Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-48


Tabel 3. 33 Hasil Mutasi Kasus Maksimasi Keuntungan Node Kromosom Kromosom Kromosom Kromosom

s 1 1 1 1

1 2 3 4

1 1 1 1 1

2 1 1 0 1

3 1 0 0 1

t 1 1 1 1

FOKk Termutasi

998 625 90 998

Solusi

Hasil yang didapat dari algoritma genetika adalah rute R123t dengan nilai keuntungan FOK4 = Rp. 998,- dikurangi dengan angka bantuan 100 sehingga nilai keuntungannya menjadi = 998 – 100 = Rp. 898,Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.28 dibawah ini:

p

k

T BC dan T BC p k T BD dan T BD p k T BE dan T BE

Tp DE dan TkDE

3

1

d3t = 1

t

ds1 = 3

s p

d12 = 2

d23 = 2

k

T AB dan T AB p k T AC dan T AC p k T AD dan T AD p T AE dan T kAE

2

T pCD dan TkCD Tp CE dan TkCE

Gambar 3. 28. Hasil pengerjaan maksimasi keuntungan dengan algoritma genetika Dari kedua metoda diatas, hasil yang didapat dalam menyelesaikan masalah maksimasi keuntungan berbeda seperti yang disajikan pada Tabel 3.34 berikut: Tabel 3. 34 Hasil Perbandingan metoda untuk Maksimasi Keuntungan

Rute FOKk


898


III-49


Untuk hasil yang didapat berbeda antara algoritma Djikstra dan algoritma genetika. Algoritma genetika membentuk rute lebih maksimal dalam hal keuntungan daripada algoritma Djikstra. Sedangkan pengaruh antara pendapatan penumpang dan kendaraan, keduanya mempunyai kontribusi yang berbeda terhadap nilai keuntungan. Nilai keuntungan mendapat kontribusi besar dari pendapatan penumpang dibandingkan dengan kendaraan. 3.3.6 Maksimasi Muatan Dengan Batasan Kapasitas (Uaij) Tiap Ruas Permasalahan yang sama dengan subbab 3.3.4 tentang maksimasi muatan akan dicoba diselesaikan dengan menggunakan kedua metoda, algoritma Djikstra dan algoritma genetika. Tetapi pada permasalahan ini ikut mempertimbangkan batasan kapasitas (Uaij) moda yang berlaku pada tiap ruas aij . Konsep pengerjaannya tidak jauh berbeda dengan subbab sebelumnya. Informasi yang dipakai juga sama yaitu pada Gambar 3.13 untuk ilustrasi dalam graph, Tabel 3.11, dan Tabel 3.12 tentang data keinginan pergerakan, Tod, baik untuk penumpang (Tpod) maupun kendaraan (Tkod). Untuk menyelesaikan permasalahan jaringan diatas akan digunakan dua metoda yaitu metoda algoritma Djikstra dan metoda algoritma genetika, yang akan dijelaskan dibawah ini:  Metoda Algoritma Djikstra untuk Maksimasi Muatan dengan Batasan Kapasitas Penjelasan dari subbab sebelumnya tentang keterbatasan pada metoda algoritma, maka dipakai beberapa tahapan berikut: a. Menentukan 3 rute terbaik dari permasalahan minimasi jarak dengan algoritma Djikstra diatas. b. Membebankan keinginan pergerakan (Tod) pada masing-masing rute diatas. c. Dari ketiga rute diatas, dipilih rute yang mempunyai nilai muatan terbanyak dan sesuai dengan batasan kapasitas pada tiap ruasnya aij.


III-50


Dengan menggunakan metoda algoritma Djikstra pada permasalahan menentukan rute dengan fungsi tujuan meminimasi jarak, didapat tiga alternatif rute terpendek yaitu pada Tabel 3.12: b. Pembebanan Keinginan Pergerakan (Tod ) pada Tiga Rute Terbaik Rute-rute terbaik yang didapat dari algoritma Djikstra pada Tabel 3.12 digunakan untuk dibebani dengan keinginan pergerakan yang terlibat pada rute yang bersangkutan. Kemudian keinginan pergerakan (Tod) baik penumpang (T pod) maupun kendaraan (Tkod) dibebankan ke dalam ruas. Karena perhitungan pembebanan keinginan pergerakan yang dipakai tidak berbeda dengan subbab 3.3.4 tentang maksimasi muatan maka pada subbab ini hanya menerapkan batasan kapasitas untuk tiap ruas aij . Prosedur perhitungan yang dipakai adalah apabila ada muatan aij (Mpaij dan Mkaij) yang melebihi kapasitas maka muatan yang dipakai adalah sama dengan kapasitas, Mpaij > Upaij maka Mpaij = Upaij atau Mkaij > Uk aij maka M kaij = U kaij, jika Mpaij < Upaij dan Mkaij < Uk aij maka nilai Mpaij dan Mkaij yang dipakai sebagai muatan di ruas aij. Berikut adalah perhitungan dari permasalahan maksimasi muatan dengan batasan kapasitas memakai persamaan (3.1), (3.2), dan (3.3): Diketahui: - Kapasitas moda transportasi untuk penumpang (Upaij ) = 25 orang - Kapasitas moda transportasi untuk kendaraan (Ukaij ) = 12 kendaraan Muatan Penumpang - Rute Rs13t

= as1 + a13 + a3t

Mpas1 = Tp AB + TpAD + TpAE

= 20 + 10 + 5

= 35 > 25 = 25 orang

Mpa13 = Tp AD + TpAE + TpBD + TpBE = 10 + 5 + 10 + 5

= 30 > 25 = 25 orang

Mpa3t = TpAE + TpBE + TpDE

= 15 < 25 = 15 orang

=5+5+5


= 25 x 3 = 75 orang-km


III-51



= 25 x 2 = 50 orang-km


= 15 x 1 = 15 orang-km


= as2 + a23 + a3t

Mpas2 = T pAC + TpAD + TpAE

= 30 orang > 25 = 25 orang

Mpa23 = Tp AD + TpAE + TpCD + TpCE

= 30 orang > 25 = 25 orang

Mpa3t = TpAE + TpCE + TpDE

= 20 orang < 25 = 20 orang


= 25 x 4 = 100 orang-km


= 25 x 2 = 50 orang-km


= 20 x 1 = 20 orang-km


= as3 + a3t

Mpas3 = Tp AD + TpAE = 15 orang < 25 = 15 orang Mpa3t = TpAE + TpDE = 10 orang < 25 = 10 orang Sedangkan untuk muatan penumpang-km, yaitu sebagai berikut MDpas2 = Mp as2 x das2

= 15 x 6 = 90 orang-km


= 10 x 1 = 10 orang-km

untuk muatan penumpang-km total dari rute Rs23t = 90 + 10 = 100 orang-km Selain itu hasil pembebanan dari tiga rute diatas dapat dilihat pada Tabel 3.35 berikut:


III-52


Tabel 3. 35 Rute Terbaik Kasus Maksimasi Penumpang dengan Batasan Kapasitas No 1

Rute

Total (orang-km) 140

Rs13t Rs23t Rs3t

2 3

170 100

Dari hasil pembebanan diatas dengan mempertimbangkan kapasitas, maka dapat disimpulkan rute terbentuk adalah Rs23t , didapat jumlah muatan penumpang-km sebesar yaitu 170 orang-km, seperti pada Gambar 3.29.

3 p

M a3 t = 20 s

M pas2 = 100

Mpa23 = 50

t

2

Gambar 3. 29 Rute algoritma Djikstra maksimasi penumpang dengan batasan kapasitas

Muatan Kendaraan - Rute Rs13t

= as1 + a13 + a3t

Mkas1 = Tk AB + TkAD + TkAE = 10 + 5 + 2

= 17 knd > 12 = 12 knd

Mka13 = Tk AD + TkAE + TkBD + TkBE = 5 + 2 + 5 + 2= 14 knd > 12 = 12 knd Mka3t = TkAE + TkBE + TkDE = 2 + 2 + 2

= 6 knd < 12 = 6 knd


= 12 x 3 = 36 knd-km


= 12 x 2 = 24 knd-km


= 6 x 1 = 6 knd-km

untuk muatan kendaraan-km total dari rute Rs13t = 36 + 24 + 6 = 66 knd-km - Rute Rs23t

= as2 + a23 + a3t


III-53


Mkas2 = T kAC + TkAD + TkAE

=7+5+2

Mka23 = Tk AD + TkAE + TkCD + TkCE

= 14 knd > 12 = 12 knd

= 5 + 2 + 2 + 5 = 14 knd > 12 = 12 knd

Mka3t = TkAE + TkCE + TkDE = 2 + 5 + 2

= 9 knd < 12 = 9 knd


= 12 x 4 = 48 knd-km


= 12 x 2 = 24 knd-km


= 9 x 1 = 9 knd-km

untuk muatan kendaraan-km total dari rute Rs 23t = 48 + 24 + 9 = 81 knd-km - Rute Rs3t

= as3 + a3t

Mkas3 = Tk AD + TkAE = 5 + 2

= 7 knd < 12 = 7 knd

Mka3t = TkAE + TkDE = 2 + 2

= 4 knd < 12 = 4 knd


= 7 x 6 = 42 knd-km


= 4 x 1 = 4 knd-km

untuk muatan kendaraan-km total dari rute Rs 23t = 42 + 4 = 46 knd-km Selain itu hasil pembebanan dari tiga rute diatas dapat dilihat pada Tabel 3.36 berikut: Tabel 3. 36 Rute Terbaik Muatan Kendaraan dengan Batasan Kapasitas

No 1 2 3

Rute

Rs13t Rs23t Rs3t

Total (knd-km) 66 81 46


III-54


Dari hasil pembebanan diatas, maka dapat disimpulkan rute terbentuk Rs23t didapat dengan jumlah muatan yang besar yaitu 81 kendaraan-km, seperti pada Gambar 3.30. 3 k

M a3 t = 9 s

k

M as2 = 48

Mka23 = 24

t

2

Gambar 3. 30 Hasil maksimasi kendaraan algoritma Djikstra dengan batasan kapasitas

 Algoritma Genetika Untuk Maksimasi Muatan dengan Batasan Kapasitas Untuk data yang dipakai adalah informasi keinginan pergerakan (Tod) pada Tabel 3.11 untuk muatan penumpang dan Tabel 3.12 untuk muatan kendaraan serta batasan kapasitas yang telah dijelaskan diatas. Berikut merupakan tahapan yang dilakukan untuk mencapai solusi permasalahan dari maksimasi muatan: Muatan Penumpang 1. Kodifikasi masalah dan Inisialisasi Populasi Pengisian set populasi dengan membangkitkan bilangan pada gen kromosom, pada Tabel 3.37. 2. Evaluasi kromosom Berikut contoh perhitungan fungsi objektif (FOMk) pada kromosom 2, menggunakan persamaan (3.9) dan (3.12) yang disajikan di Tabel 3.37. Rute terbentuk Rs13t = as1 + a13 + a3t Mpas1 = Tp AB+TpAD+TpAE = 20 + 10 + 5

= 35 orang > 25 = 25 orang

Mpa13 = Tp AD+ TpAE+TpBD+TpBE = 10 + 5 + 10 + 5 = 30 orang > 25 = 25 orang Mpa3t = T pAE+TpBE +TpDE = 5 + 5 + 5

= 15 orang < 25 = 15 orang


III-55


Sedangkan untuk muatan penumpang-km, yaitu sebagai berikut MDpas1 = Mp as1 x das1 = 25 x 3 = 75 orang-km MDpa13 = Mp a13 x da13 = 25 x 2 = 50 orang-km MDpa3t = M pa3t x da3t = 15 x 1 = 15 orang-km Sehingga untuk FOM rute Rs13t = MDp as1 + MDpa13 + MDpa3t = 75 + 50 + 15 = 140 orang-km. Tabel 3. 37 Evaluasi Fungsi Objektif Maksimasi Muatan dengan Batasan Kapasitas

Nama\Node

s

1

2

3

t

FOMk = fk

Kromos om 1 Kromos om 2 Kromos om 3 Kromos om 4

1 1 1 1

1 1 1 0

1 0 0 0

0 1 0 1

1 1 1 1 Σfk

205 140 135 100 580

3. Seleksi Kromosom Didapat dengan menghadapkan nilai random dengan kumulatif probabilitas. Kondisi yang berlaku adalah ketika R[k] < C[1] maka kromosom 1 dipilih sebagai induk, kromosom ke-k dipilih sebagai induk dengan syarat C[k-1] < R[k] < C[k]. Kromosom pada tahap ini diperlihatkan pada Tabel 3.38 sebagai berikut: Tabel 3. 38 Seleksi Kromosom Maksimasi Muatan dengan Batasan Kapasitas

Nama\Node Kromos om 1 Kromos om 2 Kromos om 3 Kromos om 4

s 1 1 1 1

1 1 1 1 0

2 1 0 0 0

3 0 1 0 1

t 1 1 1 1

P 0,35 0,24 0,23 0,17

C 0,353 0,595 0,828 1,000

R 0,095 0,442 0,137 0,585



s 1 1 1 1

1 1 1 1 1

2 1 0 1 0

3 0 1 0 1

III-56

t 1 1 1 1


4. Crossover (pindah silang) Diawali dengan penentuan pasangan crossover melalui bilangan acak, seperti pada Tabel 3.39. Tabel 3. 39 Bilangan Acak Pasangan Crossover dengan Batasan Kapasitas Kromos om 1 x Kromos om 2

Tahapan crossover dilakukan dengan menentukan letak cutting point yang juga melalui bilangan acak dan menukarkan gen yang terpotong tersebut. Proses crossover dilakukan dengan CP[1] = 2, berikut dengan hasil crossover pada Tabel 3.40. Tabel 3. 40 Hasil Crossover Maksimasi Muatan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

FOMk 140 205 135 100



gen. Dengan bilangan acak, kromosom dan mutation point ditentukan (yaitu MP = 3 pada kromosom 1), maka hasil mutasi diperlihatkan pada Tabel 3.41. Tabel 3. 41 Hasil Mutasi Maksimasi Muatan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 1 1 0 0

3 1 0 0 1

t 1 1 1 1

FOMk 200 205 135 100

Termutasi Solusi

Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.31 dibawah ini: Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-57


p

M as1=25

s

1 t

p

M a12 =25 p

M a2t=20

2

Gambar 3. 31. Hasil maksimasi muatan penumpang-km dengan algoritma genetika

Muatan Kendaraan Untuk muatan kendaraan, cara pengerjaannya tidak jauh berbeda dengan muatan penumpang, hanya pada nilai muatan ditiap ruas yang berbeda. Oleh karena itu, untuk muatan kendaraan disajikan hasil akhir dari proses algoritma genetika seperti pada Tabel 3.42 dibawah ini: Tabel 3. 42 Hasil Crossover Maksimasi Muatan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

FOMk 66 96 60 46

Tabel 3. 43 Hasil Mutasi untuk Muatan Kendaraan dengan Batasan Kapasitas

Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 1 1 0 0

3 1 0 0 1

t 1 1 1 1

FOMk 95 96 60 46

Termutasi Solusi

Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.32 dibawah ini:


III-58


k

1

M as1=12

s

t

k

M a12=12

k

M a2t=9

2

Gambar 3. 32. Hasil maksimasi muatan kendaraan-km dengan algoritma genetika Dari kedua metoda diatas, hasil yang didapat berbeda seperti yang disajikan pada Tabel 3.44 dan Tabel 3.45 berikut, baik untuk kasus muatan penumpang maupun kendaraan. Tabel 3. 44 Hasil Perbandingan metoda untuk Muatan Penumpang

Rute FOM k

Algoritma Djikstra Algoritma Genetika R s23t R s12t 170 205

Tabel 3. 45 Hasil Perbandingan metoda untuk Muatan Kendaraan

Rute FOMk

Algoritma Djikstra Algoritma Genetika R s13t Rs12t 81 96

Kesimpulan yang bisa diambil adalah metoda algoritma genetika masih menghasilkan rute maksimal dari sisi muatan-km dengan mempertimbangkan batasan kapasitas

dibandingkan

dengan

algoritma

Djikstra.

Selain

itu,

dengan

mempertimbangkan batasan kapasitas, hasil yang didapat antara algoritma genetika dan algoritma Djikstra tidak jauh berbeda. Tetapi rute yang terbentuk berbeda antara permasalahan maksimasi muatan dengan dan tanpa batasan kapasitas. Hal tersebut dipengaruhi oleh muatan dan jarak yang ada diruas aij akibat batasan kapasitas.


III-59


3.3.7 Maksimasi Keuntungan dengan Batasan Kapasitas Tiap Ruas Untuk permasalahan maksimasi keuntungan dengan memperhitungkan faktor kapasitas pada tiap ruas aij, akan mengubah perhitungan pada pendapatan (Paij). Karena pada rumusan pendapatan terdapat variabel muatan yang dipengaruhi oleh batasan kapasitas, sehingga variabel lainnya tidak mengalami perubahan dari batasan tersebut. Ilustrasi graph yang dipakai pada Gambar 3.27, sedangkan data yang dipakai adalah informasi keinginan pergerakan (Tod) pada Tabel 3.11 untuk muatan penumpang dan Tabel 3.12 untuk muatan kendaraan. Dari penjelasan terminologi pada subbab sebelumnya, telah dijelaskan informasiinformasi yang dibutuhkan, yaitu: Tp

: 2 (rp/org/km)

Bo

: 30 (rp/km)

Tk

: 4 (rp/knd/km)

Bt

: 100 (rp/kapal)

Bp

: 75 (rp)

Hubungan rumusan biaya, pendapatan, dan keuntungan yang didapat dari rute terbentuk dihitung menggunakan persamaan (3.4), (3.5), dan (3.6). Dengan batasan, kapasitas moda transportasi untuk penumpang (Upaij ) = 25 orang dan kapasitas moda transportasi untuk kendaraan (Ukaij) = 12 kendaraan. Untuk menyelesaikan permasalahan jaringan diatas akan digunakan dua metoda yaitu metoda algoritma Djikstra dan metoda algoritma genetika.  Metoda Algoritma Djikstra Untuk Maksimasi Keuntungan dengan Batasan Kapasitas Penjelasan diatas mengenai maksimasi muatan dengan algoritma Djikstra, maka begitu

juga

dengan

maksimasi

keuntungan,

mengalami

kesulitan

dalam

penyelesaiannya. Dengan keterbatasan tersebut, maka dipakai beberapa tahapan seperti dalam kasus maksimasi muatan dengan memperhitungkan batasan kapasitas, sebagai berikut:


III-60


a. Menentukan 3 rute terbaik dari permasalahan minimasi jarak pada subbab sebelumnya. b. Kemudian pendapatan dan biaya dihitung pada masing-masing rute diatas berdasarkan informasi jarak dan muatan setelah disesuaikan dengan batasan kapasitas. c. Dari ketiga rute diatas, dipilih rute yang mempunyai nilai keuntungan terbesar. Dari rute terbaik pada Tabel 3.14 dan informasi jarak dan muatan dari subbab sebelumnya maka dapat dihitung keuntungan tiap rute, yang disajikan sebagai berikut: Keuntungan Rute Rs13t Pendapatan






k



Pas1

= (25 * 2 * 3) + ( 12 * 4 * 3)

= 150 + 144

= Rp. 294,-

Pa13

= (25 * 2 * 2) + ( 12 * 4 * 2)

= 100 + 96

= Rp. 196,-

Pa3t

= (15 * 2 * 1) + ( 6 * 4 * 1)

= 30 + 24

= Rp. 54,-

Biaya


Cas1

= ( 30 * 3 ) + ( 75 * 1) = Rp. 165,-

Ca13

= ( 30 * 2 ) + ( 75 * 1) = Rp. 135,-

Ca3t

= ( 30 * 1 ) + ( 75 * 1) = Rp. 105,-


Kas1

= Rp. 294 – Rp. 165

= Rp. 129,-


III-61


Ka13

= Rp. 196 – Rp. 135

= Rp. 61,-

Ka3t

= Rp. 54 – Rp. 105

= Rp. -51,-

Ka i

ij

= Rp. 139,- , sehingga FOKk = Rp. 139 – Rp. 100 = Rp. 39,-

j

Keuntungan Rute Rs23t Pendapatan





Pa ij  M aij * T p * da ij  M a ij * Tk * da ij p

k



Pas2

= (25 * 2 * 4) + ( 12 * 4 * 4)

= Rp. 392,-

Pa23

= (25 * 2 * 2) + ( 12 * 4 * 2)

= Rp. 196,-

Pa3t

= (20 * 2 * 1) + ( 9 * 4 * 1)

= Rp. 76,-

Biaya


Cas2

= ( 30 * 4 ) + ( 75 * 1) = Rp. 195,-

Ca23

= ( 30 * 2 ) + ( 75 * 1) = Rp. 135,-

Ca3t

= ( 30 * 1 ) + ( 75 * 1) = Rp. 105,-


Kas2

= Rp. 392 – Rp. 195

= Rp. 197,-

Ka23

= Rp. 196 – Rp. 135

= Rp. 61,-

Ka3t

= Rp. 76 – Rp. 105

= Rp. -29,-

Ka i

ij

= Rp. 229,- , sehingga FOKk = Rp. 229 – Rp. 100 = Rp. 129,-

j

Keuntungan Rute Rs3t Tugas Akhir Optimasi Rute Penyeberangan Feri di Provinsi Maluku Menggunakan Algoritma Genetika

III-62


Pendapatan





Pa ij  M p aij * T p * da ij  M k a ij * Tk * da ij



Pas3

= (15 * 2 * 6) + ( 7 * 4 * 6)

= 180 + 168

= Rp. 348,-

Pa3t

= (10 * 2 * 1) + ( 4 * 4 * 1)

= 20 + 16

= Rp. 36,-

Biaya Ca ij  B o * da ij   Bp * Np 

Cas3

= ( 30 * 6 ) + ( 75 * 1) = Rp. 255,-

Ca3t

= ( 30 * 1 ) + ( 75 * 1) = Rp. 105,-


Kas3

= 348 – 255

= Rp. 93,-

Ka3t

= 36 – 105

= Rp. -69,-

Ka i

ij

= Rp. 24,-, sehingga FOKk = Rp. 24 – Rp. 100 = Rp. -76,-

j

Dari ketiga rute diatas, hasil keuntungan yang didapat berbeda-beda seperti yang disajikan pada Tabel 3.46 berikut: Tabel 3. 46 Keuntungan untuk Tiga Rute Terpendek dengan Batasan Kapasitas No 1 2 3

Rute Rs13t Rs23t Rs3t

FOKk 39 129 -76

Keuntungan terbesar dari pengerjaan dengan algoritma Djikstra adalah rute Rs23t.


III-63


 Algoritma Genetika untuk Maksimasi Keuntungan dengan Batasan Kapasitas Untuk data yang dipakai adalah informasi jarak pada Tabel 3.1 serta keinginan pergerakan (Tod) pada Tabel 3.11 untuk muatan penumpang dan Tabel 3.12 untuk muatan kendaraan juga informasi tambahan lainnya yang telah disajikan sebelumnya. Berikut merupakan tahapan yang dilakukan untuk mencapai solusi permasalahan dari maksimasi keuntungan: 1. Kodifikasi masalah dan Inisialisasi populasi Pengisian set populasi dengan membangkitkan bilangan pada gen kromosom, pada Tabel 3.47. 2. Evaluasi kromosom Berikut contoh perhitungan fungsi objektif keuntungan (FOKk) pada kromosom 2 menggunakan persamaan (3.10) dan (3.12) yang diperlihatkan di Tabel 3.47. Perhitungan fungsi objektif tersebut menggunakan informasi yang telah disajikan dan memperhitungkan batasan kapasitas. Rute terbentuk Rs13t = as1 + a13 + a3t Pendapatan






k



Diketahui: Mpas1 = 25, Mpa13 = 25, Mp a3t = 15 dan Mkas1 = 12, Mka13 = 12, Mka3t = 6 sehingga Pas1 = Rp. 294,- ; Pa13 = Rp. 196,- ; Pa3t = Rp. 54,-. Biaya Ca ij  B o * daij   Bp *N p 

Diketahui: das1 = 3 km, da13 = 2 km, da3t = 1 km didapat Cas1 = Rp. 165,- , Ca13 = Rp. 135,- , Ca3t = Rp. 105,Keuntungan Ka ij Pa ij Ca ij


III-64


Kas1 = Rp. 129,- ; Ka13 = Rp. 61,- ; Ka3t = Rp. -51,-

Ka i

ij

= Rp. 139,- sehingga FOKk = Rp. 139 – Rp. 100 = Rp. 39,-

j

kemudian ditambahkan angka bantuan sebesar 100 menjadi FOKk = Rp. 139,Tabel 3. 47 Evaluasi Fungsi Objektif Keuntungan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 1 0 0 0

3 0 1 0 1

t FOKk = f k 1 299 1 239 1 90 1 24 Σfk 652

3. Seleksi Kromosom Didapat dengan menghadapkan nilai random dengan kumulatif probabilitas. Kondisi yang berlaku adalah ketika R[k] < C[1] maka kromosom 1 dipilih sebagai induk, kromosom ke-k dipilih sebagai induk dengan syarat C[k-1] < R[k] < C[k]. Kromosom pada tahap ini diperlihatkan pada Tabel 3.48 sebagai berikut: Tabel 3. 48 Seleksi Kromosom Kasus Keuntungan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 1 0 0 0

3 0 1 0 1

t 1 1 1 1

P C R 0,46 0,459 0,095 0,37 0,825 0,542 0,14 0,963 0,138 0,04 1 0,595

Seleksi Kromosom 1 Kromosom 2 Kromosom 1 Kromosom 2

s 1 1 1 1

1 1 1 1 1

2 1 0 1 0

3 0 1 0 1

t 1 1 1 1

4. Crossover (pindah silang) Jumlah kromosom yang mengalami crossover = Crossover rate x jumlah kromosom = 0.6 x 4 = 2.4 ≈ 2 kromosom. Lalu pasangan kromosom ditentukan dengan bilangan acak berupa kromosom crossover, seperti yang terlihat pada Tabel 3.49 dengan menggunakan CP[1] = 2..


III-65


Tabel 3. 49 Hasil Crossover Kasus Keuntungan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 0 1 0 0

3 1 0 0 1

t 1 1 1 1

FOKk 239 299 90 24



gen. Dengan bilangan acak, kromosom dan mutation point ditentukan (yaitu MP = 3 pada kromosom 1), maka hasil mutasi diperlihatkan pada Tabel 3.50. Tabel 3. 50 Hasil Mutasi Kasus Keuntungan dengan Batasan Kapasitas Nama\Node Kromosom 1 Kromosom 2 Kromosom 3 Kromosom 4

s 1 1 1 1

1 1 1 1 0

2 1 1 0 0

3 1 0 0 1

t 1 1 1 1

FOKk 240 299 90 24

Termutasi

Solusi

Hasil yang didapat dari algoritma genetika adalah rute R12t dengan nilai keuntungan FOKk = Rp. 299,- dikurangi dengan angka bantuan 100 sehingga nilai keuntungannya menjadi = 299 – 100 = Rp. 199,Dari hasil pengerjaan dengan metoda algoritma genetika didapatkan rute yang terbentuk pada Gambar 3.33 dibawah. Sedangkan dari kedua metoda diatas, hasil yang didapat dalam menyelesaikan masalah maksimasi keuntungan berbeda seperti yang disajikan pada Tabel 3.51 berikut: Tabel 3. 51 Perbandingan Metoda Maksimasi Keuntungan dengan Batasan Kapasitas

Rute FOK

Algoritma Djikstra Algoritma Genetika R s23t Rs12t 129 199


III-66


T pBC dan T kBC p k T BD dan T BD p k T BE dan T BE

1

t

das1 = 3

s

da12 = 2 da2t = 2

T pAB dan T kAB p k T AC dan T AC p k T AD dan T AD p k T AE dan T AE

p

2

k

T CD dan T CD Tp CE dan TkCE

Gambar 3. 33. Hasil pengerjaan maksimasi keuntungan dengan algoritma genetika Kesimpulan yang bisa diambil adalah metoda algoritma genetika masih menghasilkan rute maksimal dari sisi keuntungan dengan mempertimbangkan batasan kapasitas dibandingkan dengan algoritma Djikstra. Tetapi rute yang terbentuk berbeda antara permasalahan maksimasi keuntungan dengan dan tanpa batasan kapasitas. Hal tersebut dipengaruhi oleh muatan dan jarak yang ada diruas aij akibat batasan kapasitas. Selain itu, dengan mempertimbangkan batasan kapasitas, hasil yang didapat antara algoritma genetika dan algoritma Djikstra tidak jauh berbeda dibandingkan dengan tanpa memperhitungkan kapasitas. 3.4

RESUME PERBANDINGAN METODA Dengan contoh kasus permasalahan diatas baik minimasi maupun maksimasi, beserta penyelesaian dengan menggunakan metoda algoritma Djikstra dan algoritma genetika, maka dapat disimpulkan bahwa perbedaannya sebagai berikut:  Kedua algoritma menghasilkan rute yang sama dari permasalahan jaringan dengan tujuan meminimasi jarak.  Untuk permasalahan jaringan dengan tujuan memaksimasi muatan dan keuntungan, kedua algoritma menghasilkan rute yang berbeda. Algoritma genetika menghasilkan rute yang lebih baik daripada algoritma Djikstra.


III-67


 Algoritma Djikstra bekerja dengan cara menelusuri setiap node dan ruas. Setiap ruas dan node terbaik akan diberi tanda sebagai kondisi update. Rute terbaik terbentuk dari sekumpulan ruas yang menghubungkan node s ke t dengan node yang diberi tanda.  Algoritma Djikstra memerlukan penetapan point awal-akhir pada jaringan. Sedangkan Algoritma Genetika dapat bekerja pada kasus jaringan tanpa penetapan node awal-akhir.  Algoritma Djikstra banyak bekerja pada kasus optimasi dengan rumusan minimasi jarak/biaya. Kecenderungan solusi yang terbentuk merupakan rute yang terpendek. Hal tersebut berbeda dengan algoritma genetika yang dapat bekerja dengan dua permasalahan optimasi.  Algoritma genetika bekerja dengan menggunakan sekumpulan rute yang dibangkitkan. Rute terbaik didapatkan setelah melalui proses operasi genetika dengan nilai fungsi objektif paling baik.  Algoritma genetika menggunakan aturan-aturan pencarian probabilistik.  Algoritma genetika lebih tepat digunakan pada permasalahan jaringan yang lebih kompleks.  Asumsi arah pergerakan moda transportasi yang dipakai adalah satu arah. Dimana pergerakan yang terjadi adalah berurutan ke depan dari kodifikasi yang diberikan. Dari penjelasan diatas, maka untuk menyelesaikan permasalahan jaringan pada kasus selanjutnya digunakan metoda algoritma genetika.


III-68

BAB III METODOLOGI DAN PERBANDINGAN METODA

Recommend Documents