BAB IV PEMBAHASAN. Tabel 4.1 Menyajikan data permintaan daging ayam di PT Ciomas Adisatwa pada hari Senin

BAB IV PEMBAHASAN Pada bab ini akan dijelaskan mengenai penggunaan metode Clarke and Wright Saving dan Algoritma Genetika pada pendistribusian daging ayam di PT Ciomas Adisatwa 4.1. Pendistribusian Ayam di PT Ciomas Adisatwa PT

Ciomas

Adisatwa

merupakan

perusahaan

yang

bergerak

pada

pendistribusian ayam di Jawa Tengah. PT Ciomas Adisatwa setiap harinya mendistribusikan ayam yang tersebar di seluruh kabupaten/ kota di Jawa Tengah. dalam pendistribusian daging ayam pada hari Senin disediakan 2 kendaraan angkut berupa truk L300 yang dapat mengangkut sebesar 1 ton daging ayam, namun agar daging ayam yang didistribusikan tetap terjaga mutunya, sehingga hanya dapat mengangkut maksimal 900 kg setiap angkut. Proses pendistribusian dimulai pukul 08.00 WIB dengan pengecekan kendaraan dan jumlah daging ayam yang akan didistribusikan. Pukul 08.30 WIB sales mulai berangkat untuk mendistribusikan ayam tersebut. Penelitian ini akan mengambil studi kasus pada PT Ciomas Adisatwa karena belum adanya rute tetap dari perusahaan. Data yang digunakan adalah data pendistribusian daging ayam di PT Ciomas Adisatwa. Data yang digunakan ada 21 pelanggan. Berikut ini disajikan data permintaan daging ayam di PT Ciomas Adisatwa pada hari Senin. Tabel 4.1 Menyajikan data permintaan daging ayam di PT Ciomas Adisatwa pada hari Senin

No

1

Nama Pelanggan

Ayam Krezy

Alamat

Jumlah Permintaan (Kg)

Jl. Nalula Sadewa No.9, Kembangarum, Dukuh, Sidomukti, Kota Salatiga, Jawa Tengah 50722

150

1

No

Nama Pelanggan

Alamat

Jumlah Permintaan (Kg)

2

D’Saji Crispy

Jl. Jend. Sudirman No.265a, Gendongan, Tingkir, Salatiga City, Central Java

120

3

Wahid Hotel

Jl. Jendral Sudirman No. 2, Salatiga, Sidorejo, Salatiga, Sidorejo, Kota Salatiga, Jawa Tengah 50711

60

4

LA Crispy

Jalan Plongkowati, Tegalrejo, Argomulyo, Tegalrejo, Salatiga, Kota Salatiga, Jawa Tengah 50733

55

5

Chicken Day

Sidoharjo, Susukan, Semarang, Jawa Tengah 50777

80

6

Balemong Resort

Jl. Patimura No. 1B, Sisemut, Ungaran, Jawa Tengah 50511

100

7

The Wujil Resort & Conventions

Ungaran - Semarang, Jl. SoekarnoHatta km 25,5 Ungaran, Semarang, Jawa Tengah 50552

40

8

Semesta Bilingual Boarding School

Jl. Raya Gn. Pati, Nongkosawit, Gunung Pati, Semarang City, Central Java 50519

60

9

Ada Swalayan

Jalan Setiabudi No. 221 - 225, Srondol Wetan, Banyumanik, Srondol Kulon, Semarang, Kota Semarang, Jawa Tengah 50263

40

10

PT. Carrefour Indonesia

Jl. Jenderal Anton Sujarwo No.119, Srondol Wetan, Banyumanik, Kota Semarang, Jawa Tengah 50263

40

11

A&W Restaurants, Duta Pertiwi Mall Semarang,

Jl. Pemuda No. 150, Sekayu, Semarang Tengah, Kota Semarang, Jawa Tengah 50132

40

12

A&W Restaurants Srondol

Jl. Setiabudi No. 127, Srondol Kulon, Banyumanik, Kota Semarang, Jawa Tengah 50263

40

2

No

Nama Pelanggan

Alamat

Jumlah Permintaan (Kg)

13

Richeese Factory

Jl. S. Parman No.48, Gajahmungkur, Kota Semarang, Jawa Tengah 50232

40

14

Noormans Hotel Semarang

Jalan Teuku Umar No. 27, Kel. Jatingaleh, Kec. Gajahmungkur, Karangrejo, Gajahmungkur, Kota Semarang, Jawa Tengah 50231

100

15

Hotel ibis Semarang Simpang Lima

Jl. Gajahmada No.172, Pekunden, Semarang Tengah, Kota Semarang, Jawa Tengah 50134

65

16

Rumah Sakit Permata Medika

Jl. Raya Mr. Moch Ichsan No. 93-97 Ngaliyan, Ngaliyan, Kota Semarang, Jawa Tengah 50181

45

17

Pop Chicken

Ruko Permata Karanggeneng Kav.D, Jl. Mr. Wurjanto, Sumurejo, Gunung Pati, Sumurrejo, Gn. Pati, Kota Semarang, Jawa Tengah 50226

45

18

Family Fried Chicken

JL. Meranti Barat I 335 RT 006/16, Semarang, 50235, Srondol Wetan, Banyumanik, Semarang City, Central Java 50263

35

19

Sarana Medika

Jl. Kh Ahmad Dahlan, Pekunden, Semarang Tengah, Kota Semarang, Jawa Tengah 50134

45

20

CV Jaya Mandiri

Jl. Pedurungan Kidul I No.3, Pedurungan Kidul, Pedurungan, Kota Semarang, Jawa Tengah 50192

50

21

Quick Chicken

Jl. Pandanaran No.197, Banaran, Boyolali Sub-District, Boyolali Regency, Central Java 57313

35

3

4.2. Pembentukan Model CVRP pada Pendistribusian Ayam di PT Ciomas Adisatwa Permasalahan CVRP pada pendistribusian daging ayam dapat didefinisikan sebagai suatu graf G=(V,E), dimana V = {0,1,2,...,22} dengan 0 sampai 22 adalah gabungan dari konsumen C dan depot, C = {1,2,...,21} adalah konsumen 1 sampai dengan 21, dengan depot dinyatakan dengan 0 dan 22. Jalan yang dilalui oleh kendaraan dinyatakan sebagai himpunan rusuk berarah 𝐸 yaitu penghubung antar konsumen, 𝐸 = {(𝑖, 𝑗)|𝑖, 𝑗 ∈ 𝑉, 𝑖 ≠ 𝑗}. Setiap simpul memiliki permintaan (demand) sebesar 𝑑𝑖 , dengan 𝑑𝑖 adalah integer positif. Setiap konsumen dipasok dari depot 0. Himpunan dari k kendaraan mempunyai kapasitas yang sama q ditempatkan di depot 0 dan digunakan untuk melayani konsumen. Sebuah rute didefinisikan sebagai biaya siklus dari graf G melewati depot 0 sehingga total permintaan dari simpul yang dikunjungi tidak melebihi kapasitas kendaraan. Asumsi yang digunakan dalam permasalahan ini adalah: 1. Tiap simpul (konsumen) dikunjungi hanya satu kali 2. Setiap konsumen terhubung satu sama lain dan jarak antar konsumen simetrik, yang artinya 𝑐𝑖𝑗 = 𝑐𝑗𝑖 3. Jumlah simpul pendistribusian yaitu 22 simpul dengan 1 depot dan 21 konsumen. Dengan indeks yang digunakan : 𝑖 : indeks untuk konsumen awal, 𝑖 = 0,1,2, … , 21 𝑗 : indeks untuk konsumen tujuan, 𝑗 = 1,2, … , 22 𝑘 : indeks untuk kendaraan, 𝑘 = 1,2 Dengan parameter 𝑐𝑖𝑗 adalah jarak antar konsumen, selanjutnya didefinisikan 𝑘 variabel keputusan 𝑥𝑖𝑗 yang memodelkan ada tidaknya perjalanan dari simpul 𝑖 ke

𝑗 dengan kendaraan 𝑘. 𝑘 𝑥𝑖𝑗 ={

1, jika terdapat perjalanan dari 𝑖 ke 𝑗 dengan kendaraan 𝑘 0, jika tidak ada perjalanan dari 𝑖 ke 𝑗 dengan kendaraan 𝑘

4

(3.1)

𝑘 Variabel keputusan yang digunakan dalam pendistribusian 𝑥𝑖𝑗 akan bernilai

1 jika terdapat perjalanan oleh kendaraan 𝑘 dari konsumen 𝑖 langsung ke j, dan bernilai 0 jika tidak demikian. Adapun 𝑑𝑖 menyatakan total demand (permintaan) setiap konsumen i langsung ke j. Menurut Kara, dkk (2004) VRP dapat diformulasikan dalam bentuk pemograman linear dengan meminimalkan total biaya atau total jarak tempuh dari rute perjalanan pendistribusian barang/jasa seperti berikut : Untuk meminimumkan: 2

21 22

𝑍 = ∑ ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗𝑘

( 3.2)

𝑘=1 𝑖=0 𝑗=1

dengan kendala: 1. Memastikan bahwa setiap konsumen dikunjungi tepat satu kali 2

22

𝑘 ∑ ∑ 𝑥𝑖𝑗 = 1,

∀ 𝑗 ∈ {1, … ,22},

(3.3)

𝑘=1 𝑗=1

2. Menjamin rute tetap tiap kendaraan, sehingga kendaraan yang mengunjungi suatu simpul, setelah melayani akan meninggalkan simpul tersebut 21

22

𝑘 ∑ 𝑥𝑖𝑗 𝑖=0

𝑘 − ∑ 𝑥𝑖𝑗 = 0,

∀𝑘 ∈ {1, … , 𝐾}

(3.4)

𝑗=1

3. Batas kapasitas kendaraan sehingga tidak ada kendaraan yang melebihi kapasitas 22 𝑘 ∑ 𝑑𝑖 𝑥𝑖𝑗 ≤ 900,

∀𝑖 ∈ {0, … ,21} 𝑘 ∈ {1, … , 𝐾}

(3.5)

𝑗=1

4. Setiap rute perjalanan kendaraan berawal dari depot 0 22 𝑘 ∑ 𝑥0𝑗 = 1,

𝑘 ∈ {1, … , 𝐾},

𝑗=1

5. Setiap rute perjalanan kendaraan berakhir di depot 22

5

(3.6)

22 𝑘 ∑ 𝑥𝑖22 = 1,

𝑘 ∈ {1, … , 𝐾},

( 3.7)

𝑖=0 𝑘 6. 𝑥𝑖𝑗 merupakan variabel binner 𝑘 𝑥𝑖𝑗 ∈ {0,1} ,

∀ 𝑖, 𝑗 ∈ {1, … , 𝑁}, 𝑘 ∈ {1, … , 𝐾}

(3.8)

Pada Gambar 4.1 digambarkan sebagai graf kosong untuk lokasi depot dan konsumen sebagai simpul.

Gambar 4.1 Graf pendistribusian di PT Ciomas Adisatwa

Pada Gambar 4.2 diberikan graf lengkap pendistribusian di PT Ciomas Adisatwa

Gambar Gambar 3.2 4.2 Graf Graf Lengkap lengkap pendistribusian Pendistribusian di di PT PT Ciomas Ciomas Adisatwa Adisatwa

6

Jarak antara simpul yang sama selalu nol dan jarak antara simpul adalah bersifat simetrik atau jarak simpul A ke B sama dengan jarak simpul B ke A. Penentuan rute distribusi model CVRP adalah dengan mengunjungi setiap simpul tanpa adanya pengulangan atau setiap simpul hanya dikunjungi satu kali. Selanjutnya, dibuat tabel jarak depot ke konsumen dan antar konsumen dengan menggunakan google maps. Dalam penentuan jarak menggunakan google maps, terdapat berbagai pilihan rute, rute yang dipilih adalah rute dengan jarak terpendek dan tidak satu jalur, sehingga asumsi 𝑐𝑖𝑗 = 𝑐𝑗𝑖 berlaku. Tabel matriks jarak terlampir pada Lampiran 1 halaman 62. Setelah diketahui tabel jarak, maka dapat dilakukan penyelesaian model menggunakan metode Clarke and Wright Savings dan Algoritma Genetika dengan bantuan software Matlab. 4.3. Penyelesaian dengan Clarke and Wright Saving Penyelesaian dengan Clarke and Wright Saving yaitu membuat matriks jarak dengan entri-entrinya adalah jarak depot dengan konsumen dan antar konsumen. Tabel 4.2 Matriks jarak asal-tujuan (km) hari Senin

Menurut Persamaan (2.9) akan dibuat matriks penghematan. Berikut ini adalah salah satu contoh perhitungan nilai penghematan untuk pangkalan di D’Saji Crispy, Jl. Jend. Sudirman No.265a, Gendongan, Tingkir, Salatiga City, Central Java, dan Ayam Krezy, Jl. Nalula Sadewa No.9, Kembangarum, Dukuh, Sidomukti, Kota Salatiga, Jawa Tengah 50722 dengan menggunakan persamaan (2.9), dimasukkan nilai jarak, maka didapatkan nilai penghematan.

7

𝑆21 = 𝐶20 + 𝐶01 − 𝐶21 = 7,7 + 9,5 − 1,5 = 15,7 Menggunakan cara yang sama diperoleh matriks penghematan untuk semua simpul yang disajikan pada Tabel 4.3 Tabel 4.3 Matriks Penghematan

Setelah matriks penghematan terbentuk, selanjutnya menentukan kelompok rute bedasarkan nilai penghematan yang terbesar sampai yang terkecil dari matriks penghematan. Langkah ini merupakan iterasi dari matriks penghematan, dimana jika nilai penghematan terbesar terdapat pada simpul i dan j maka baris i dan kolom j dicoret, lalu i dan j digabungkan dalam satu kelompok rute, demikian seterusnya sampai iterasi yang terakhir. Selanjutnya pengelompokkan rute berdasarkan nilai penghematan diperoleh dari simpul gabungan hasil iterasi matriks penghematan. Kemudian mengurutkan daftar tujuan/pelanggan sesuai dengan kelompok rute yang berdasarkan nilai penghematan tersebut. Langkah-langkah untuk pembentukan kelompok rute: 1. Memilih nilai penghematan terbesar dalam matriks penghematan, yaitu 88,3 antara simpul 20 dan simpul 11. Menggabungkan keduanya menjadi satu rute, kemudian mencoret semua baris pada kolom 11 dan mencoret semua kolom pada baris 20. Rute yang terbentuk adalah: Rute 1 = 20 – 11. Untuk rute ini daging ayam yang dikirim adalah 50 + 40 = 90 kg, dan masih belum melampaui kapasitas dari kendaraan yaitu 900 kg. Pengelompokan ini disajikan pda Tabel 4.4 iterasi 1

8

Tabel 4.4 Iterasi 1 pengelompokan simpul bedasarkan matriks penghematan

2. Memilih nilai penghematan terbesar dalam matriks penghematan, yaitu 87,5 antara simpul 19 dan simpul 15. Menggabungkan simpul 19 dan simpul 15 menjadi satu rute dalam rute 2. Kemudian mencoret semua baris pada kolom 19 dan mencoret semua kolom pada baris 15. Rute terbentuk adalah: Rute 2 = 20 – 11 – 19 – 15. Untuk rute ini daging ayam yang dikirimkan adalah 90 + 45 + 65 = 200 kg. Total tersebut belum melaumpaui kapasitas yang disediakan. Pengelompokan ini disajikan pada Tabel 4.5 iterasi 2.

Tabel 4.5 Iterasi 2 pengelompokan simpul bedasarkan matriks penghematan

3. Memilih nilai terbesar berikutnya dalam matriks penghematan, kemudian lakukan langkah seperti pada iterasi 1 dan 2, apabila sudah melampaui kapasitas maka membuat rute baru. Dari iterasi yang disajikan pada lampiran 1 halaman 62 diperoleh:

9

Rute 1 = 0 – 20 – 11 – 19 – 15 – 20 - 13 – 16 – 14 – 8 – 9 -12 – 10 – 18 – 6 – 17 – 7 – 0 = 50 + 40 + 45 + 65 + 40 + 45 + 100 + 60 +40 + 40 + 40 + 35 + 100 + 45 + 40 = 785 Rute 2 = 0 – 1 – 5 – 21 – 4 - 2 – 3 – 0 = 150 + 80 + 35 + 55 + 120 + 60 = 500 Dapat disajikan dengan tabel untuk pendistribusian daging ayam untuk hari senin sebagai berikut: Tabel 4.6 Rute Hari Senin

Kendaraan

1

Rute

0 – 20 – 11 – 19 – 15 –

Permintaan

Jarak Tempuh

(kg)

(Km)

785

165.3

500

86.8

1285

252.11

20 - 13 – 16 – 14 – 8 – 9 -12 – 10 – 18 – 6 – 17 – 7–0 2

0 – 1 – 5 – 21 – 4 - 2 – 3 –0 Total

Bedasarkan tabel 4.6 dapat diketahui solusi dari model CVRP pada pendistribusian daging ayam di PT Ciomas Adisatwa yaitu: Rute 1 : 0 20 11 19 15 20 13 16 14 8 9 12 10 18 6 17 7 0 Depot - CV Jaya Mandiri - A&W Restaurants, Duta Pertiwi Mall Semarang - Sarana Medika - Hotel ibis Semarang Simpang Lima - Richeese Factory - Rumah Sakit Permata Medika - Noormans Hotel Semarang - Semesta Bilingual Boarding School - Ada Swalayan - A&W Restaurants Srondol - PT. Carrefour Indonesia - Family Fried Chicken - Balemong Resort - Pop Chicken - The Wujil Resort & Conventions – Depot Rute 2 : 0 1 5 21 4 2 3 0

10

Depot - Ayam Krezy - Chicken Day - Quick Chicken - LA Crispy - D’Saji Crispy - Wahid Hotel – depot Dapat dituliskan sebagai suatu graf untuk pendistribusian daging ayam menggunakan metode Clarke and Wright Savings sebagai berikut:

Gambar 4.3 Rute pendistribusi dengan metode Clarke and Wright Savings

Keterangan:

: Rute 1 : Rute 2

4.4. Penyelesaian masalah CVRP dengan menggunakan Algoritma Genetika Sebelum memulai untuk menyelesaikan model dengan Algoritma Genetika, akan diberikan beberapa contoh dari istilah penting dalam membangun penyelesaian masalah menggunakan Algoritma Genetika, yaitu sebagi berikut: 1.

Gen, dipresentasikan dengan bilangan real yang masing-masing bilangan menunjukan depot dan konsumen Contoh:

Gen 0 = Depot Gen 1 = Konsumen 1

2.

Kromosom, dipresentasikan dengan gabungan beberapa gen yaitu dalam masalah CVRP adalah membentuk rute namun belum melibatkan depot. Contoh:

Kromosom 1 = 5 7 4 1 2 3 6

11

3.

Individu, merupakan kromosom yang membentuk suatu perjalanan kendaraan dalam CVRP adalah rute yang terbentuk yang dimulai dari depot dan kembali ke depot Contoh:

4.

Individu 1 = 0 1 2 4 6 5 3 7 0

Nilai fitness, jika x menyatakan total jarak dalam rute, maka nilai fitness 1

dapat didefinisikan 𝑥. Oleh karena total jarak yang diinginkan adalah yang kecil, maka nilai fitness yang dipilih adalah yang paling besar. 1

Invers total jarak dari rute yang didapatkan atau 𝑥, dengan x adalah total jarak dalam suatu rute. Contoh : terdapat rute: 0 1 2 4 6 5 3 7 0 1

Total jarak dari rute diatas adalah 60 km, maka nilai fitnessnya adalah 60. 5.

Populasi, dipresentasikan dengan sekumpulan individu yaitu gabungan beberapa perjalanan kendaraan. Contoh:

Individu 1 = 0 1 2 4 6 5 3 7 0 Individu 2 = 0 1 3 4 5 6 2 7 0 Individu 3 = 0 1 4 5 3 2 6 7 0 Individu 4 = 0 1 3 5 7 6 2 4 0

6.

Induk, bedasarkan no 3, nilai fitness terbaik adalah nilai fitness yang besar, dan bedasarkan seleksi nilai fitness terpilih 2 rute dengan kemungkinan terbaik. Masing-masing rute terbaik tersebut disebut dengan induk. Contoh:

Individu 1 = 0 1 2 4 6 5 3 7 0 Didapat : Induk 1 = 0 2 3 4 5 1 6 7 0 Induk 2 = 0 1 3 2 7 6 5 4 0

7.

Anak, rute baru yang terbentuk bedasarkan induk yang diperoleh dari no 6 disebut anak. Cara untuk membentuk rute baru tersebut yaitu dengan menentukan bagian dari induk 1 untuk disisipkan ke induk 2. Contoh :

Induk 1 = 0 2 3 4 5 1 6 7 0 Induk 2 = 0 1 5 2 7 6 3 4 0

12

Diperoleh : Anak 1 = 0 6 7 6 2 3 4 5 0 Anak 2 = 0 3 4 5 1 2 7 6 0 Setelah mengetahui bebrapa istilah yang akan digunakan dalam Algoritma Genetika, langkah selanjutnya adalah menyelesaikan CVRP dengan menggunakan algoritma genetika sebagai berikut: 1. Penyandian Gen (pengkodean) Gen merupakan bagian dari kromosom. Masing-masing kromosom berisi sejumlah gen yang menyandikan informasi yang disimpan di dalam kromosom. Gen juga dapat ditulis sebagai suatu graf. Berikut ini merupakan representasi gen yang ditunjukan oleh tabel 4.7 Tabel 4.7 Representasi gen Gen

Nama Pelanggan

0

Depot PT Ciomas Adisatwa

1

Ayam Krezy

2

D’Saji Crispy

3

Wahid Hotel

4

LA Crispy

5

Chicken Day

6

Balemong Resort

7

The Wujil Resort & Conventions

8

Semesta Bilingual Boarding School

9

Ada Swalayan

10

PT. Carrefour Indonesia

11

A&W Restaurants, Duta Pertiwi Mall Semarang,

12

A&W Restaurants Srondol

13

Gen

Nama Pelanggan

13

Richeese Factory

14

Noormans Hotel Semarang

15

Hotel ibis Semarang Simpang Lima

16

Rumah Sakit Permata Medika

17

Pop Chicken

18

Family Fried Chicken

19

Sarana Medika

20

CV Jaya Mandiri

21

Quick Chicken

2. Membangkitkan Populasi Awal Langkah

ini

membangkitkan

sejumlah

individu

atau

membangkitkan rute awal secara acak sehingga membentuk suatu populasi. Satu individu dalam penulisan ini adalah 21 gen yang berisi gen 1 sampai gen 21 yang membentuk rute pendistribusian daging ayam. Teknik dalam pembangkitan populasi awal ini ada beberapa macam yaitu, random generator, pendekatan tertentu, permutasi gen. Pada penulisan ini digunakan teknik membangkitkan populasi berupa random generator, yaitu dengan melibatkan pembangkitan bilangan random untuk nilai setiap gen sesuai dengan representasi kromosom yang digunakan. Dengan bantuan software Matlab akan dibangkitkan beberapa rute acak sesuai dengan ukuran populasi. Script prosedur pembangkitkan populasi awal terdapat pada lampiran 3 halaman 68. Hasil dari pembangkitkan secara acak rute pendistribusian yang membentuk populasi pada generasi awal adalah sebagai berikut dan selengkapnya pada Lampiran 4 halaman 75.

14

Individu 3 = 21 4

20 10

15 8

14

18

16

19

12 7

11

3 5

9

13

6

17

2

1

3. Menghitung Nilai Fitness Langkah selanjutnya yaitu menghitung nilai fitness dari setiap individu yang akan digunakan untuk menentukan rute terpendek. Setiap individu dihitung jarak totalnya, kemudian dihitung nilai fitnesnya dengan menggunakan Persamaan 2.10. Dengan bantuan software matlab, ditentukan nilai fitness dari setiap individu dalam populasi. Script prosedur dan perhitungannya terdapat pada Lampiran 3 halaman 76. Berikut merupakan nilai fitness yang didapat dari generasi awal Tabel 4.8 Nilai fitness individu populasi awal Individu Nilai Fitness

Individu Nilai Fitness

1

0,0016

11

0,0022

2

0,0014

12

0,0014

3

0,0020

13

0,0016

4

0,0014

14

0,0015

5

0,0019

15

0,0016

6

0,0013

16

0,0017

7

0,0017

17

0,0016

8

0,0014

18

0,0017

9

0,0016

19

0,0015

10

0,0019

20

0,0016

Setelah dihitung nilai fitness dari setiap individu dengan bantuan software matlab, maka didapat nilai fitness terbaik yaitu fitness yang terbesar nilainya dari populasi awal yaitu pada individu ke-11 dengan nilai fitness sebesar 0,0022. Individu dengan nilai fitness terbaik dari populasi generasi pertama akan dipertahankan dan dibawa ke generasi selanjutnya

15

4. Seleksi Langkah berikutnya adalah melakukan seleksi, yaitu untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota pop ulasi yang terpilih. Seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana offspring terbentuk dari individu-individu terpilih tersebut. Pada kepenulisan ini digunakan seleksi rangking. Dalam 20 individu terpilih 10 individu yang mempunyai nilai fitness terbaik dan dari individu yang terpilih mempunyai dua alternatif solusi rute yang terbaik, kemudian dapat disebut induk 1 yaitu alternatif rute ke 1 dan induk 2 yaitu alternatif rute 2. Dengan bantuan software matlab, akan dipilih beberapa induk untuk dilakukan seleksi dengan metode seleksi rangking. Induk-induk yang terpilih selengkapnya dapat dilihat pada Lampiran 6 halaman 77 dan script prosedur seleksi terdapat pada Lampiran 3 halaman 68. Induk 1 = individu 7 = 10 1

11

16

15

Induk 2 = individu 9 = 9 17

7

13

13

18

20

14

12

2

5 3

3 11 20 15 12

4

6

14

17 2

18

6

7 9

4

19

21

8

8 19 10 21 16 5

1

5. Pindah Silang (Crossover) Setelah terpilih induk-induk dari proses seleksi, selanjutnya indukinduk tersebut akan dilakukan proses pindah silang. Pindah silang akan menghasilkan individu baru hasil dari dua induk yang disebut anak. Setiap pasang induk menghasilkan sepasang anak agar proses seleksi pada generasi selanjutnya mendapatkan jumlah populasi yang sama. Pindah silang ini dilakukan dengan skema ordercrossover. Proses pindah silang ditentukan oleh Probabilitas Crossover (Pc) antara 0,6 s/d 0,95 (Michalewicz, 1996: 35). Setiap pasang induk akan diberikan suatu bilangan acak [0,1], jika probabilitas pasangan induk kurang dari Pc maka dilakukan pindah silang dan berlaku sebaliknya. Apabila tidak

16

terjadi pindah silang maka anak untuk generasi berikutnya adalah induk tersebut. Berikut hasil pindah silang berupa keturunan (anak) yang selengkapnya bisa dilihat pada Lampiran 7 halaman 78 Induk 1 = individu 7 = 10 1

11

16

15

Induk 2 = individu 9 = 9 17

7

13

13

18

20

14

12

2

5 3

3 11 20 15 12

4

6

14

6 17

2

7 9

4

19

21

8

8 19 10 21 16

18

5

1

Dari persilangan antara rute 1 yaitu induk 1 dan rute 2 yaitu induk 2 diperoleh rute baru hasil persilangan, dengan cara posisi gen ditukar menurut hasil output dari Matlab. Setelah dilakukan pindah silang, diperoleh sepasang anak sebagai berikut: Anak 1 = 15

14 5

Anak 2 = 13

12

2

3

7

4

19 14

6 12

20

4 15

6 2

8

17

9

8

1

11

16

18

5

1

10

16

17

10

19

21

21

13

18

20

9

3

11

7

6. Mutasi Setelah dilakukannya proses pindah silang, anak yang dihasilkan dari proses tersebut selanjutnya akan diproses ke tahap mutasi. Terdapat beberapa teknik mutasi seperti swapping mutation, inversion mutation, reciprocal exchange mutation, dan uniform mutation. Teknik mutasi yang digunakan dalam skripsi ini adalah teknik swapping mutation, karena teknik mutasi ini sangat mudah dan sederhana untuk diimplementasikan. Teknik ini diawali dengan memilih dua bilangan acak kemudian gen yang berada pada posisi bilangan acak pertama ditukar dengan gen yang berada pada bilangan acak kedua dalam probabilitas tertentu (Suyanto, 2005:65). Berikut ini individu hasil mutasi yang diperoleh dan selengkapnya terdapat di Lampiran 8 halaman 80. Sebelum di mutasi:

17

Anak 1 = 15

14 5

Anak 2 = 13

12

2

3

7

4

19 14

6 12

20

4

6

15

2

8

17

9

8

1

11

16

18

5

1

10

16

10

17

21

19

21

13

18

20

9

3

11

13

18

20

9

3

11

7

Setelah dimutasi: Anak 1 = 15

14

12

5

6

7

Anak 2 = 13 19

12 15

2 4

4 2

3

17

19

6 8

8

11

16

1

9

20

18

5

10

16

17

10

1

21

14

21

7

7. Elitism Setelah langkah-langkah di atas dilakukan, maka langkah selanjutnya adalah membentuk populasi selanjutnya di generasi kedua, proses ini dinamakan sebagai elitism. Proses elitism mengulangi langkah 1 sampai dengan 6 sebanyak jumlah generasi 1100, karena dalam jumlah generasi 1100 terdapat nilai finess terbaik dan total jarak yang terpendek. Elitsm bertujuan untuk menjaga agar individu bernilai fitness tertinggi tersebut tidak hilang selama proses evolusi. Proses evolusi merupakan proses Algoritma Genetika mulai dari pembentukan populasi awal hingga evaluasi nilai fitness dari populasi baru yang terbentuk. Prosedur pembentukan populasi selanjutnya terdapat dalam lampiran 4 dan hasil pembentukkan populasi baru selengkapnya bisa dilihat pada lampiran 9 dengan bantuan software Matlab. Berikut merupakan hasil populasi baru di generasi selanjutnya: Individu 3 = 16 17 12 15 4 20 9 7 1

8 19 11 13 18 21 10 5

3 2

6

14

Setelah diperoleh generasi baru, maka langkah selanjutnya adalah mencari nilai fitness generasi baru dengan menggunakan software Matlab, hasil perhitungan fitness generasi baru selengkapnya dapat dilihat pada lampiran 8 halaman 80. Diperlukan beberapa kali percobaan dalam menerapkan Algoritma Genetika menggunakan

18

software Matlab hingga mendapatkan nilai fitness yang optimum dan konvergensi generasi tertentu, yaitu dengan mencoba beberapa nilai ukuran populasi dan jumlah generasi yang berbeda. Hal ini karena Algoritma Genetika akan selalu menghasilkan solusi yang berbeda dalam setiap proses seleksi. Berikut tabel percobaan dengan menggunakan beberapa nilai ukuran populasi dan jumlah generasi yang berbeda : Tabel 4.9 Hasil Percobaan Algoritma Genetika

Percobaan ke-

Ukuran Populasi

Jumlah Generasi

Fitness

Total Jarak

1

15

200

0.003795

263.50

2

20

0.004115

243.01

3

25

0.003660

273.25

4

30

0.004268

234.30

5

15

0.004066

245.95

6

20

0.004322

231.40

7

25

0.004153

240.80

8

30

0.003990

250.65

9

15

0.003569

280.20

10

20

0.004398

227.36

11

25

0.00390

256.40

12

30

0.005042

198.31

13

15

0.004135

241.86

14

20

0.004937

202.56

15

25

0.004692

213.15

16

30

0.004971

201.15

300

400

500

19

Percobaan ke-

Ukuran Populasi

17

15

18

20

19 20

Jumlah Generasi

Fitness

Total Jarak

0.004726

211.60

0.005442

183.75

25

0.004608

217.00

30

0.004502

222.10

1100

Tabel diatas merupakan hasil percobaan Algoritma Genetika dengan beberapa ukuran populasi random yaitu 15, 20, 25 dan 30. Jumlah iterasi yang digunakan adalah 200, 300, 400, 500, dan 1100. Parameter yang digunakan yaitu probablitias crossover 0.6 dan probablitias mutation 0.47. Probabilitas crossover sebesar 0.6 berarti peluang suatu individu akan dikenai proses crossover adalah sebesar 60%. Sedangkan probablitias mutation sebesar 0.47 berarti peluang suatu gen akan dimutasi adalah sebesar 47%. Bedasarkan Tabel 4.9 percobaan dengan ukuran 20 populasi menghasilkan nilai fitness terbaik yaitu sebesar 0.005442 pada iterasi ke-1100, dengan ukuran 15 populasi nilai fitness terbaik yang dihasilkan sebesar 0.004726 pada iterasi ke-1100, dengan ukuran 25 populasi nilai fitness terbaik yang dihasilkan sebesar 0.004692 pada iterasi ke-500, dengan ukuran 30 populasi nilai fitness terbaik yang dihasilkan sebesar 0.005042 pada iterasi ke-400. Jumlah iterasi tidak menjamin terhadap nilai fitness, hal ini ditunjukan oleh percobaan dengan jumlah populasi 30. Bedasarkan Tabel 4.9 percobaan dengan jumlah iterasi ke-200 memperoleh nilai fitness 0.004268 dan percobaan dengan jumlah iterasi ke-300 memperoleh nilai fitness sebesar 0.003990. Terjadi penurunan nilai fitness saat jumlah iterasi bertambah, tetapi percobaan dengan jumlah iterasi ke-400 diperoleh nilai fitness sebesar 0.005042. Jadi tidak dapat dikatakan bahwa semakin banyak jumlah iterasi maka semakin baik juga nilai fitnessnya.

20

Kemudian dapat dilihat juga dari percobaan diatas bahwa ukuran populasi yang besar tidak menjamin solusi yang dihasilkan akan semakin baik. Hal ini dapat ditunjukan dari tabel diatas untuk percobaan jumlah generasi sebanyak 1100 bahwa solusi yang dihasilkan paling kecil yaitu 20, lebih baik dari solusi dengan ukuran yang lebih besar. Namun pada percobaan untuk jumlah generasi 500, solusi yang dihasilkan dari ukuran populasi yang lebih besar yaitu 30 lebih baik daripada solusi yang dihasilkan dengan ukuran populasi yang lebih kecil lainya. Sehingga dibutuhkan ukuran populasi yang tepat pada setiap permasalahan untuk mendapat solusi yang optimal. Dapat disimpulkan bahwa solusi optimal yang dihasilkan oleh setiap iterasi dapat berubah. Hal ini disebabkan karena setiap generasi yang dibentuk dari generasi sebelumnya sangat dipengaruhi oleh populasi awal, seleksi, pindah silang, dan mutasi. Sehingga di setiap proses generasi akan selalu dihasilkan solusi optimal yang berbeda-beda. Proses tersebut akan selalu berulang-ulang hingga didapatkan individu dengan nilai fitness terbaik. Bedasarkan Tabel 4.9 pada percobaan ke-18 dengan ukuran populasi 20 dan jumlah iterasi 1100 didapatkan nilai fitness terbaik yang dihasilkan oleh Algoritma Genetika yaitu sebesar 0.005442 dengan total jarak tempuh kendaraan 183.75 km dan banyak kendaraan yang beroperasi sebanyak 2 kendaraan. Berikut ini grafik percobaan ke-18 seperti pada gambar 4.4.

21

Gambar 4.4 Grafik pergerakan nilai fitness

Kurva pada Gambar 4.4 merupakan pergerakan nilai fitness hingga generasi ke-1100. Dan kurva yang berada dibawah merupakan pergerakan nilai rata-rata fitness dari 1100 generasi. Dapat dilihat pada grafik bahwa terdapat 1100 generasi dengan nilai fitness dari 0 hingga 0.01. Rute-rute percobaan ke-18 seperti pada Tabel 4.10 Tabel 4.10 Pembagian rute percobaan ke-13 Kendaraan

Rute

Permintaan

Jarak Tempuh

(Kg)

(Km)

1

0-7-6-17-8-14-13-1611-20-15-19-9-12-1810-0

785

142.45

2

0-1-2-5-21-4-3-0

500

81.6

Total

1285

224.05

Bedasarkan Tabel 4.10 dapat diketahui solusi dari model CVRP pada pendistribusian daging ayam di PT Ciomas Adisatwa yaitu: Rute 1 : 0 7 6 17 8 14 13 16 11 20 15 19 9 12 18 10 0

22

Dengan rute pendistribusian daging ayam: Depot - The Wujil Resort & Conventions - Balemong Resort - Pop Chicken Semesta Bilingual Boarding School - Noormans Hotel Semarang - Richeese Factory - Rumah Sakit Permata Medika - A&W Restaurants, Duta Pertiwi Mall Semarang - CV Jaya Mandiri - Hotel ibis Semarang Simpang Lima - Sarana Medika - Ada Swalayan - A&W Restaurants Srondol - Family Fried Chicken - PT. Carrefour Indonesia - Depot Rute 2 : 0 1 2

5 21 4 30

Dengan rute pendistribusian daging ayam: Depot - Ayam Krezy - D’Saji Crispy - Chicken Day - Quick Chicken–LA Crispy Wahid Hotel–Depot Digambarkan graf untuk rute pendistribusian daging ayam pada gambar 3.5. Graf untuk penditribusian daging ayam dengan Algoritma Genetika sebagai berikut:

Gambar 4.5 Rute Pendistribusian dengan Algoritma Genetika

Keterangan:

: Kendaraan 1

23

: Kendaraan 2 4.5. Perbandingan Penyelesaian Model Menggunakan Metode Clarke and Wright Saving dan Algoritma Genetika Perbandingan penyelesaian model, dalam hal ini rute pendistribusian yang diperoleh menggunakan Metode Clarke and Wright Saving dan Algoritma Genetika ditunjukan dalam Tabel 4.11 berikut : Table 4. 11 Perbandingan rute yang diperoleh menggunakan Clarke and Wright Saving dan Algoritma Genetika

Metode

Rute

Metode Clarke and Wright Saving 0 20 11 19 15 20 13 16 14 Kendaraan 1 89 12 1018 6 17 7 0 Kendaraan 2

0 1 5 21 4 2 3 0 Total

Total Jarak Tempuh

Permintaan

165.31 km

785 kg

786.8 km

500 kg

252.11 km

1285 kg

142.45 km

785 kg

81.6 km

500 kg

224.05 km

1285 kg

Algoritma Genetika 0 7 6 17 8 14 Kendaraan 1

Kendaraa 2

13

16 11 20

15 19 9 12 18 10 0 0 1 2 5 21 4 3 0 Total

Pada Tabel 4.11 terlihat bahwa Algoritma Genetika menghasilkan total jarak tempuh yang lebih baik dibandingkan dengan metode Clarke and Wright Saving. Algoritma Genetika menghasilkan total jarak 224.05 km, sedangkan dengan metode Clarke and Wright Saving menghasilkan 252.11 km. Sehingga dapat disimpulkan penyelesaian dengan model Algoritma Genetika lebih baik dalam segi jarak jika dibandingkan dengan metode Clarke and Wright Saving dalam menyelesaikan Capacitated Vehicle Routing Problem (CVRP). Jika dilihat dari keefektifitasan kendaraan dalam memuat permintaan, kedua metode diatas

24

menghasilkan keefektifitasan yang sama yaitu pada kendaraan 1 memuat 785 kg daging ayam dan pada kendaraan 2 memuat 500 kg daging ayam. Jadi dapat disimpulkan Algoritma Genetika lebih optimum untuk pendistribusian daging ayam di PT Ciomas Adisatwa.

25