PENJADWALAN DAN PENENTUAN RUTE KENDARAAN PADA INDUSTRI BAHAN KIMIA MENGGUNAKAN KOMBINASI METODE ALGORITMA GENETIKA DAN ALGORITMA PENCARIAN TABU

PRESENTASI TUGAS AKHIR – KS091336

PENJADWALAN DAN PENENTUAN RUTE KENDARAAN PADA INDUSTRI BAHAN KIMIA MENGGUNAKAN KOMBINASI METODE ALGORITMA GENETIKA DAN ALGORITMA PENCARIAN TABU Oleh : Maya Sagita W. 5208 100 106 Dosen Pembimbing : Prof. Ir. Arif Djunaidy, M.Sc., Ph.D

20 Juli 2012

Tugas Akhir - KS09-1336

1

PENDAHULUAN

20 Juli 2012


Latar Belakang Kendala yang dihadapi saat melakukan pengiriman barang : • Keterlambatan dan waktu tunggu akibat dari estimasi waktu layanan pengiriman yang kurang tepat • Permasalahan pada ketersediaan dan kesiapan kendaraan yang akan melakukan pengiriman

20 Juli 2012


2

Perumusan Masalah Permasalahan yang muncul dari latar belakang : • Bagaimana melakukan penjadwalan dan penentuan rute kendaraan agar dapat mengoptimalkan penggunaan kendaraan dan memenuhi permintaan konsumen menggunakan gabungan dari algoritma genetik dan algoritma pencarian tabu. • Bagaimana penjadwalan dan penentuan rute kendaraan yang menggunakan gabungan algoritma genetik dan algoritma pencarian tabu dapat memuaskan batasan yang berhubungan dengan kondisi dan karakteristik transportasi, permintaan konsumen dan waktu layanan yang diberikan. 20 Juli 2012


3

Batasan Tugas Akhir Batasan yang dikenakan pada proses penjadwalan dan penentuan rute kendaraan : • Kendaraan memulai aktifitasnya dari titik awal yang sama, kemudian kembali ke titik awal yang sama pula. • Jumlah kendaraan terbatas dan tidak menentu karena disesuaikan dengan jumlah ketersediaan kendaraan. • Jumlah produk yang dimuat tidak melebihi kapasitas kendaraan. • Waktu layanan pada kendaraan yang melakukan pengiriman dibatasi dan harus memenuhi waktu kedatangan sampai batas waktu yang ditentukan di konsumen. 20 Juli 2012


4

Batasan Tugas Akhir • Batasan tambahan yang disesuaikan :  Dalam satu rute, Setiap konsumen hanya dikunjungi dan dilayani oleh satu kendaraan dan kendaraan yang sama.  Semua konsumen pada hari layanan harus dilayani.  Tambahan waktu yang diperhitungkan dalam estimasi waktu layanan adalah waktu tunggu antrian kendaraan pada konsumen. 20 Juli 2012


5

Tujuan Tugas Akhir • Mengoptimalkan penggunaan kendaraan dan memenuhi target permintaan konsumen. • Membuat penjadwalan dan penentuan rute yang dapat :  Meminimalkan jarak  Meminimalkan biaya transportasi  Mengupayakan ketepatan waktu pengiriman

15 Juni 2012


6

Manfaat Tugas Akhir • Dapat membuat pelaksanaan proses distribusi menjadi efisien dan optimal berdasarkan kondisi dan karakteristik distribusi kendaraan.

20 Juli 2012


7

Metode Pengerjaan Tugas Akhir

20 Juli 2012


8

MODEL DAN IMPLEMENTASI

20 Juli 2012


Model dan Implementasi Formulasi Model • Fungsi Tujuan Meminimalkan jarak dan waktu perjalanan.

• Fungsi Batasan •

Hard Constraint  Tidak ada pelanggan dalam satu armada yang tidak dilayani oleh kendaraan.

 Permintaan yang dimuat oleh satu kendaraan dalam suatu armada tidak boleh melebihi kapasitas muatan kendaraan tersebut.

20 Juli 2012


9

Model dan Implementasi Formulasi Model

• Hard Constraint  Waktu kedatangan kendaraan pada pelanggan tidak boleh melebihi batas waktu akhir pengiriman yang ditentukan oleh pelanggan.

Untuk batasan ini, tjv dibentuk dari formulasi (tiv + wi + tli + tijv)xijv • SoftConstraint  Waktu kedatangan kendaraan boleh kurang dari waktu awal pengiriman yang ditentukan pelanggan.

20 Juli 2012


10

Model dan Implementasi Pemodelan Kromosom dan Individu

Trip Object (T) ID Pelanggan Jumlah permintaan (kg) Waktu kirim Jenis produk ID Armada ID Kendaraan Kapasitas Kendaraan (kg)

20 Juli 2012

Waktu kirim Waktu Awal kirim (menit) Waktu Akhir kirim (menit)


11

Model dan Implementasi • Fungsi Fitness

20 Juli 2012


12

Model dan Implementasi Alur Gabungan Algoritma Genetika dan Pencarian Tabu pada Program

20 Juli 2012


13

Model dan Implementasi Terminasi

• Jika jumlah generasi yang dihasilkan telah mencapai angka maksimum generasi yang ditentukan. • Solusi terbaik dalam populasi atau solusi terbaik dari individu baru terhadap solusi terbaik dari populasi sebelumnya tidak mengalami peningkatan sebanyak 500 kali iterasi atau mengalami penurunan pada jumlah generasi tertentu. • Solusi terbaik dari individu baru dibandingkan solusi terbaik dari populasi generasi sebelumnya memiliki persentase kurang dari error rate yang ditentukan. 20 Juli 2012


14

Model dan Implementasi Praproses Data Nama Tabel Data pelanggan Data kendaraan Data permintaan

Atribut Tambahan -

Koor_x Koor_y Kecepatan_rata Status_kendaraan Waktu_servis

Perubahan bentuk data pada Data permintaan dimana batas waktu pengiriman (Waktu_atas dan Waktu_bawah) diubah dari bentuk jam (hh:mm) ke menit untuk memudahkan proses perhitungan.

20 Juli 2012


15

Model dan Implementasi Hasil Keluaran

20 Juli 2012


16

UJI COBA DAN ANALISIS HASIL

20 Juli 2012


Uji Coba dan Analisis Hasil Verifikasi Program No. 1

Fungsionalitas Keterangan Memasukkan Data (Menyimpan Data Dapat dijalankan Pelanggan, Kendaraan, Permintaan Pengiriman)

2

Merubah Data (Data Pelanggan, Kendaraan, Dapat dijalankan Permintaan Pengiriman)

3

Menghapus Data (Data Pelanggan, Kendaraan, Dapat dijalankan Permintaan Pengiriman)

4

Membentuk Jadwal dan Rute

20 Juli 2012

Dapat dijalankan


17

Uji Coba dan Analisis Hasil Validasi Hasil Program Jadwal

Biaya (Program)

Nilai Fitness (Program)

Biaya (Manual)

Nilai Fitness (Manua)

Selisih Biaya (%)

Selisih Fitness (%)

1 (17 366,14285 Pelanggan) 71428571

0,0023214 98244245 0256

366,14285 7142857

0,0023214 98244245 02

0%

0%

2 (24 599,94285 Pelanggan) 71

0,0014287 07495952

599,94285 7142857

0,0014287 07495952

0%

0%

3 (27 564,9142 Pelanggan)

0,0015931 572,15866 620473396 8302665 7

0,0015222 48617711 67

1,2 %

4,4 %

20 Juli 2012


18

Uji Coba dan Analisis Hasil Lingkungan Uji Coba Uji coba dilakukan pada komputer personal dengan spesifikasi sebagai berikut : • Processor : Intel(R) Core(TM)2 Duo CPU T6600 2,20GHz • Memory : 1 GB • Sistem Operasi : Microsoft Windows 7 Ultimate • Compiler : Netbeans IDE 7.0.1

20 Juli 2012


19

Uji Coba dan Analisis Hasil Uji Coba Dilakukan 2 skenario uji coba, antara lain : 1. Uji Kebenaran 2. Uji Kinerja

20 Juli 2012


20

Uji Coba dan Analisis Hasil Uji Kebenaran Solusi yang dihasilkan program disesuaikan dengan batasan yang dikenakan. - Solusi yang dihasilkan oleh program terbukti tidak menyalahi batasan (hardconstraint) yang dikenakan. - Hasil perhitungan program dan perhitungan secara manual mengenai batasan (hardconstraint) yang dikenakan sesuai

20 Juli 2012


21

Uji Coba dan Analisis Hasil Uji Kinerja Menguji kemampuan program dan algoritma yang digunakan dalam menghasilkan solusi. Dilakukan 2 jenis uji coba, antara lain : 1. Uji Kinerja Program 2. Uji Kinerja Metode

20 Juli 2012


22

Uji Coba dan Analisis Hasil Uji Kinerja Program Menguji kemampuan program dalam menghasilkan solusi yang optimal.

20 Juli 2012

Uji ke-

Jumlah Pelanggan

1.

17

2.

24

3

27

4

17

Biaya

Nilai Fitness

432,542857 0,00206855 1 07 0,00144204 616,4095 27 574,742857 0,00151540 1 42 0,00204172 462,571428 671

Nilai Fitness terakhir Individu baru 0,00206855 072 0,00144204 27 0,00151540 42 0.00204172 6717


Generasi terkhir

503 781 499 2101

23

Uji Coba dan Analisis Hasil Uji Kinerja Program 0,00225 0,002125 0,002 0,001875 0,00175 0,001625 0,0015 0,001375 0,00125 0,001125 0,001 0,000875 0,00075 0,000625 0,0005 0,000375 0,00025 0,000125 0

17 Pelanggan 27 Pelanggan 24 Pelanggan

1 25 49 73 97 121 145 169 193 217 241 265 289 313 337 361 385 409 433 457 481 505 529 553 577 601 625 649 673 697 721 745 769

Nilai

Grafik Perubahan Nilai Fitness

Generasi

20 Juli 2012


24

Uji Coba dan Analisis Hasil Uji Kinerja Program 0,00225 0,002125 0,002 0,001875 0,00175 0,001625 0,0015 0,001375 0,00125 0,001125 0,001 0,000875 0,00075 0,000625 0,0005 0,000375 0,00025 0,000125 0

Nilai Fitness

1 62 123 184 245 306 367 428 489 550 611 672 733 794 855 916 977 1038 1099 1160 1221 1282 1343 1404 1465 1526 1587 1648 1709 1770 1831 1892 1953 2014 2075

Nilai

Grafik Perubahan Nilai Fitness

Generasi

20 Juli 2012


25

Uji Coba dan Analisis Hasil Uji Kinerja Metode Menguji kinerja tiap-tiap algoritma acuan yang digunakan dengan membandingkan hasil yang dikeluarkan oleh tiap-tiap algoritma. Membandingkan algoritma yang digunakan dengan metode penjadwalan perusahaan.

20 Juli 2012


26

Uji Coba dan Analisis Hasil Uji Kinerja Metode Uji 1 :

Uji 2 :

20 Juli 2012

Metode

Rata-rata Biaya

Waktu Komputasi Rata-rata

Algoritma Genetika

526,256190

28 menit 40 detik

432,06667

0,001967288998611 33

Algoritma Pencarian Tabu

421,37809

8 menit 13 detik

386,49523

-

Algoritma Kombinasi

396,5381

28 menit 21 detik

366,14290

0,002321498244245 0256

Biaya Terbaik

Nilai Fitness Terbaik

Metode

Rata-rata Biaya


Algoritma Genetika

815,055238

39 menit 45 detik

746.67619

0,001147944541523 7047


647,629524

8 menit 58 detik

625.33333

-

Algoritma Kombinasi

646,395237

53 menit 33 detik

610.10476

0,001404910944256 26

Biaya Terbaik



27


Uji 4 :

20 Juli 2012

Metode

Rata-rata Biaya


Algoritma Genetika

865,992399

97 menit 31 detik

838,54285

0,001192544890796 96


623,5018081

20 menit 30 detik

576,09523

-

Algoritma Kombinasi

612,78852

70 menit 27 detik

Biaya Terbaik

564,9142


0,001593162047339 6727

Metode

Rata-rata Biaya


Biaya Terbaik


Algoritma Genetika

793,411719

93 menit 43 detik

779,352380

0,001191465441392 1202


608,408345

21 menit 53 detik

Algoritma Kombinasi

584,469125

88 menit 38 detik

552,9142857 544,723809


0,001704664661864 4667

28


20 Juli 2012

Metode

Rata-rata Biaya


Biaya Terbaik


Algoritma Genetika

542,9839487

50 menit 46 detik

525,447619047

0,001903139273544 5512


467,934187

11 menit 13 detik

Algoritma Kombinasi

461,14029

60 menit 20 detik

423.1904761904 427.057142857


0,020361800099481 94

29

Uji Coba dan Analisis Hasil Analisis Hasil Uji Coba : • Program menjalankan proses perhitungan sesuai dengan batasan yang diberikan. Program terbukti tidak menyalahi batasan yang merupakan hardconstraint. • Program masih belum memberikan kinerja terbaiknya dalam membentuk jadwal dan rute kendaraan. • Kombinasi algoritma terbukti menghasilkan solusi yang paling baik. Namun kombinasi metode ini memiliki kekurangan pada waktu komputasi dimana waktu komputasi yang dihasilkan lebih lama. • Kombinasi algoritma maupun dua algoritma acuan belum bisa menghasilkan solusi yang lebih minimum • Biaya yang paling mendekati biaya yang dihasilkan oleh metode penjadwalan perusahaan adalah yang dihasilkan oleh program yang menggunakan kombinasi algoritma. 20 Juli 2012


33

KESIMPULAN DAN SARAN

20 Juli 2012


Kesimpulan dan Saran Kesimpulan yang dapat diambil dari analisis solusi yang dilakukan : •

•

•

Program terbukti dapat menjalankan semua fungsional yang diberikan dan solusi yang dihasilkan oleh program sesuai dengan perhitungan manual terhadap solusi yang dihasilkan. Aplikasi yang dibuat berdasarkan algoritma genetika dan pencarian tabu yang dibuat mampu memenuhi batasan-batasan yang ditentukan dalam pembentukan jadwal dan rute kendaraan dari perusahaan. Aplikasi yang dibuat berdasarkan kombinasi algoritma genetika dan pencarian tabu berpeluang memberikan biaya lebih minimum dari pada biaya yang dikeluarkan menggunakan metode penjadwalan perusahaan.

20 Juli 2012


34

Kesimpulan dan Saran Berikut ini beberapa saran yang diberikan untuk pengembangan aplikasi untuk masa mendatang : •

Dibutuhkan penyesuaian kembali pada aplikasi terhadap kondisi nyata proses penjadwalan dan penentuan rute kendaraan, dimana biaya yang dihitung bukan jarak dan waktu tapi biaya pengiriman produk seperti biaya bahan bakar, biaya sopir dan biaya lain yang bersatuan mata uang. Dalam penentuan rute, rute yang dibentuk didapatkan dari jarak yang didapat dari sistem peta geografis, bukan didapat dari koordinat tambahan yang diberikan.

20 Juli 2012


35

Sekian dan Terima Kasih

20 Juli 2012


36

PENJADWALAN DAN PENENTUAN RUTE KENDARAAN PADA INDUSTRI BAHAN KIMIA MENGGUNAKAN KOMBINASI METODE ALGORITMA GENETIKA DAN ALGORITMA PENCARIAN TABU

Recommend Documents