Penerapan artificial immune system dalam M(max)-travelling salesman problem untuk meminimasi total biaya dengan memperhatikan due date

Abstract

Pengiriman barang (distribusi) merupakan salah satu faktor yang perlu diperhatikan dalam dunia industri. Kendala yang dihadapi dalam pengiriman barang adalah bagaimana mengirimkan barang sampai ke tangan konsumen tepat pada waktunya sekaligus menempuh rute perjalanan dengan jarak terpendek sehingga dapat menghemat biaya. Masalah penentuan rute perjalanan agar mendapatkan total jarak yang minimum dikenal dengan Travelling Salesman Problem (TSP). Dalam penelitian ini, masalah yang dibahas adalah mmax-TSP dengan ukuran performansi adalah total biaya. Pada mmax-TSP, jumlah salesman yang tersedia lebih dari satu orang dan merupakan jumlah salesman maksimum. Total biaya yang menjadi ukuran performansi mencakup biaya bahan bakar, biaya makan, biaya penginapan, dan biaya penalti per hari akibat keterlambatan. Algoritma yang digunakan dalam penelitian ini adalah Artificial Immune System (AIS). AIS merupakan metode metaheuristik yang dikembangkan untuk menyelesaikan permasalahan kombinatorial. Penyelesaian masalah pada AIS meniru cara kerja dari sistem kekebalan tubuh dalam hal mempertahankan kekebalan tubuh manusia terutama dalam hal produksi antibodi. Teori yang digunakan dalam AIS adalah Clonal Selection Principle. Clonal Selection Principle merupakan teori yang menjelaskan bagaimana B-Cells dalam tubuh memproduksi antibodi yang bervariasi melalui proses kloning untuk dimutasi. Antibodi dapat dianalogikan sebagai solusi bagi masalah yang dihadapi. Hasil mutasi kemudian menghasilkan antibodi-antibodi yang lebih baik dari antibodi sebelumnya. Proses tersebut dikenal dengan affinity maturation. Semakin baik suatu antibodi mengikat antigen, semakin baik solusi yang dihasilkan untuk menyelesaikan masalah. Dalam penelitian ini, AIS diimplementasikan pada 6 kasus hipotetik. Karakteristik kasus yang membedakan satu sama lain adalah jumlah kota, jumlah salesman maksimum, serta hubungan antar kota tujuan. Hasil penelitian menunjukkan bahwa algoritma AIS dapat menyelesaikan mmax-TSP dengan cukup baik. Nilai parameter yang diuji (langkah eliminasi (F), proporsi eliminasi (P), serta βmin mutasi dan βmax mutasi) memberikan pengaruh terhadap total biaya pada kasus yang cenderung lebih kompleks. Selain itu, dari perbandingan dengan Genetic Algorithm dengan Genetic Multi-step Searches (GA/GMS) pada kasus-kasus yang diuji dalam penelitian ini menunjukkan bahwa AIS memiliki performansi yang lebih baik dibandingkan GA/GMS pada kasus yang lebih kompleks.