penjadwalan dan penentuan rute kendaraan pada...

PENJADWALAN DAN PENENTUAN RUTE KENDARAAN PADA INDUSTRI BAHAN KIMIA MENGGUNAKAN KOMBINASI METODE ALGORITMA GENETIKA DAN ALGORITMA PENCARIAN TABUOleh :Maya Sagita W.5208 100 106

Dosen Pembimbing :Prof. Ir. Arif Djunaidy, M.Sc., Ph.D

PRESENTASI TUGAS AKHIR – KS091336

20 Juli 2012 1Tugas Akhir - KS09-1336

PENDAHULUAN

20 Juli 2012 Tugas Akhir - KS09-1336

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


Perumusan Masalah

Permasalahan yang muncul dari latar belakang :• Bagaimana melakukan penjadwalan dan penentuan

rute kendaraan agar dapat mengoptimalkanpenggunaan kendaraan dan memenuhi permintaankonsumen menggunakan gabungan dari algoritmagenetik dan algoritma pencarian tabu.

• Bagaimana penjadwalan dan penentuan rutekendaraan yang menggunakan gabungan algoritmagenetik dan algoritma pencarian tabu dapatmemuaskan batasan yang berhubungan dengankondisi dan karakteristik transportasi, permintaankonsumen dan waktu layanan yang diberikan.


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.


Batasan Tugas Akhir

• Batasan tambahan yang disesuaikan : Dalam satu rute, Setiap konsumen hanya

dikunjungi dan dilayani oleh satu kendaraan dankendaraan yang sama.

Semua konsumen pada hari layanan harusdilayani.

Tambahan waktu yang diperhitungkan dalamestimasi waktu layanan adalah waktu tungguantrian kendaraan pada konsumen.


Tujuan Tugas Akhir

• Mengoptimalkan penggunaan kendaraan danmemenuhi target permintaan konsumen.

• Membuat penjadwalan dan penentuan rute yang dapat : Meminimalkan jarak Meminimalkan biaya transportasi Mengupayakan ketepatan waktu pengiriman

15 Juni 2012 6Tugas Akhir - KS09-1336

Manfaat Tugas Akhir

• Dapat membuat pelaksanaan proses distribusimenjadi efisien dan optimal berdasarkankondisi dan karakteristik distribusi kendaraan.


Metode PengerjaanTugas Akhir



MODEL DAN IMPLEMENTASI

Model dan Implementasi

9

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.


Model dan ImplementasiFormulasi 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 10Tugas Akhir - KS09-1336


11

Pemodelan Kromosom dan Individu

20 Juli 2012

Trip Object (T) Waktu kirimID PelangganJumlah permintaan (kg)Waktu kirimJenis produkID ArmadaID KendaraanKapasitas Kendaraan (kg)

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

Tugas Akhir - KS09-1336


12

• Fungsi Fitness



13

Alur Gabungan Algoritma Genetika dan Pencarian Tabu pada Program



14

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.



15

Praproses Data

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

20 Juli 2012

Nama Tabel Atribut Tambahan

Data pelanggan - Koor_x- Koor_y

Data kendaraan - Kecepatan_rata- Status_kendaraan

Data permintaan - Waktu_servis



1620 Juli 2012

Hasil Keluaran



UJI COBA DAN ANALISIS HASIL

Uji Coba dan Analisis Hasil

1720 Juli 2012

Verifikasi ProgramNo. Fungsionalitas Keterangan1 Memasukkan Data (Menyimpan Data

Pelanggan, Kendaraan, Permintaan Pengiriman)Dapat dijalankan

2 Merubah Data (Data Pelanggan, Kendaraan,Permintaan Pengiriman)

Dapat dijalankan

3 Menghapus Data (Data Pelanggan, Kendaraan,Permintaan Pengiriman)

Dapat dijalankan

4 Membentuk Jadwal dan Rute Dapat dijalankan



1820 Juli 2012

Validasi Hasil ProgramJadwal Biaya

(Program)NilaiFitness (Program)

Biaya (Manual)

Nilai Fitness (Manua)

Selisih Biaya (%)

Selisih Fitness (%)

1 (17 Pelanggan)

366,1428571428571

0,0023214982442450256

366,142857142857

0,00232149824424502

0 % 0 %

2 (24 Pelanggan)

599,9428571

0,001428707495952

599,942857142857

0,001428707495952

0 % 0 %

3 (27 Pelanggan)

564,9142 0,00159316204733967

572,158668302665

0,00152224861771167

1,2 % 4,4 %



1920 Juli 2012

Lingkungan Uji CobaUji 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



2020 Juli 2012

Uji Coba Dilakukan 2 skenario uji coba, antara lain :1. Uji Kebenaran2. Uji Kinerja



2120 Juli 2012

Uji KebenaranSolusi 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



2220 Juli 2012

Uji KinerjaMenguji kemampuan program dan algoritma yang digunakan dalam menghasilkan solusi.Dilakukan 2 jenis uji coba, antara lain :1. Uji Kinerja Program2. Uji Kinerja Metode



2320 Juli 2012

Uji Kinerja ProgramMenguji kemampuan program dalam menghasilkan solusi yang optimal.

Uji ke- Jumlah Pelanggan Biaya Nilai

Fitness

Nilai Fitness terakhir Individu

baru

Generasi terkhir

1. 17 432,5428571

0,0020685507

0,00206855072 503

2. 24 616,4095 0,0014420427

0,0014420427 781

3 27 574,7428571

0,0015154042

0,0015154042 499

4 17 462,571428 0,00204172671

0.002041726717 2101



2420 Juli 2012

Uji Kinerja Program

00,000125

0,000250,000375

0,00050,000625

0,000750,000875

0,0010,001125

0,001250,001375

0,00150,001625

0,001750,001875

0,0020,002125

0,00225

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

Nila

i

Generasi

Grafik Perubahan Nilai Fitness

17 Pelanggan

27 Pelanggan

24 Pelanggan



2520 Juli 2012

Uji Kinerja Program

00,000125

0,000250,000375

0,00050,000625

0,000750,000875

0,0010,001125

0,001250,001375

0,00150,001625

0,001750,001875

0,0020,002125

0,00225

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

Nila

i

Generasi

Grafik Perubahan Nilai Fitness

Nilai Fitness



2620 Juli 2012

Uji Kinerja MetodeMenguji kinerja tiap-tiap algoritma acuan yang digunakan dengan membandingkan hasil yang dikeluarkan oleh tiap-tiap algoritma.Membandingkan algoritma yang digunakan dengan metode penjadwalan perusahaan.



2720 Juli 2012

Uji Kinerja MetodeUji 1 :

Uji 2 :

Metode Rata-rata Biaya Waktu Komputasi Rata-rata Biaya Terbaik Nilai Fitness Terbaik

Algoritma Genetika 526,256190 28 menit 40 detik 432,06667 0,00196728899861133

Algoritma Pencarian Tabu 421,37809 8 menit 13 detik 386,49523 -

Algoritma Kombinasi 396,5381 28 menit 21 detik 366,14290 0,002321498244245

0256


Algoritma Genetika 815,055238 39 menit 45 detik 746.67619 0,0011479445415237047

Algoritma Pencarian Tabu 647,629524 8 menit 58 detik 625.33333 -

Algoritma Kombinasi 646,395237 53 menit 33 detik 610.10476 0,001404910944256

26



2820 Juli 2012

Uji Kinerja MetodeUji 3 :

Uji 4 :





6727





4667



2920 Juli 2012

Uji Kinerja MetodeUji 5 : Metode Rata-rata Biaya Waktu Komputasi

Rata-rata Biaya Terbaik Nilai Fitness Terbaik


Algoritma Pencarian Tabu 467,934187 11 menit 13 detik 423.1904761904 -

Algoritma Kombinasi 461,14029 60 menit 20 detik 427.057142857 0,020361800099481

94



3320 Juli 2012

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.



KESIMPULAN DAN SARAN

Kesimpulan dan Saran

3420 Juli 2012

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.


Kesimpulan dan Saran

3520 Juli 2012

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.


36

Sekian dan Terima Kasih


penjadwalan dan penentuan rute kendaraan pada...

Documents