## Sistem optimasi pendistribusian bahan makanan dan snack dengan algoritma Ant Colony Optimization (ACO)
Lutfi Erik Prasetyo 1) , Istiadi 2) , Fitri Marisa 3) 1,2,3) Universitas Widyagama Malang Jl. Borobudur No.35, Mojolangu, Kec. Lowokwaru, Kota Malang Email : 1 lutfierikprasetyo@gmail.com, 2 istiadi@widyagama.ac.id, 3 Fitrimarisa@gmail.com Riwayat artikel: Recieved: 01-05-2021 Revised: 01-10-2021 Accepted: 11-10-2021

## Abstract
Distribution activities are activities of distributing goods and services made from producers to consumers so that news is famous. That's what the company CV. Landahur, this company is responsible for implementing food and snack ingredients from the principal to the customer. This is done so that it makes it easier for customers and producers to buy and sell. In the distribution process, a salesman will make visits to customers with the aim of selling these food ingredients and snacks, but with so many customers who need to be visited, the best route recommendation is recommended. In this study, using the Ant Colony Optimization (ACO) algorithm. ACO is used because it is able to show the best route with parameters. In this study, 2 trials were carried out, the first trial using 5 data obtained a distance of 20.3 km and the second trial using 10 data obtained the best route distance of 22.96 km with the parameter that the number of ants is 3, 2iter ations, α = 1, β = 0 , 5, ρ = 0.5194, the initial Pheromone = 0.1. With this system, it is hoped that it can help sellers get the best route information precisely and accurately. Keywords: Ant Colony Optimization (ACO) Algorithm, Distribution, Travelling Salesman Problem (TSP).

## Abstrak
Kegiatan distribusi merupakan kegiatan penyaluran barang dan jasa yang dibuat dari produsen ke konsumen agar tersebar luas. Begitulah yang dilakukan oleh perusahaan CV. Landahur , perusahaan ini bertanggung jawab untuk mendistribusikan bahan makanan dan snack dari prinsipal menuju ke customer. Hal tersebut dilakukan supaya memudahkan customer dan produsen baik untuk membeli dan menjual. Dalam prosesnya pendistribusian seorang salesman akan melakukan kunjungan ke customer dengan tujuan untuk menjual bahan makanan dan snack tersebut, Namun dengan banyaknya customer yang perlu dikunjungi maka diperlukan rekomendasi rute terbaik. Dalam penelitian ini menggunakan algoritma Ant Colony Optimization (ACO). ACO digunakan karena mampu menunjukan rute terbaik dengan menetapkan parameter-parameter. Pada penelitian ini telah melakukan 2 ujicoba, ujicoba pertama dengan menggunakan 5 data didapatkan jarak 20,3 km dan ujicoba kedua menggunakan 10 data didapatkan jarak rute terbaik 22,96 km dengan parameter yang jumlah semut 3, 2iterasi, α = 1, β = 0,5, ρ = 0,5194, Pheromone awal = 0,1. Dengan adanya sistem tersebut diharapkan dapat membantu salesman  mendapatkan informasi rute terbaik dengan tepat dan akurat Kata kunci: Algoritma Ant Colony Optimization (ACO), Distribusi, Travelling Salesman Probelm (TSP)

## Pendahuluan
Pendistribusian atau penjualan barang merupakan nyawa bagi setiap perusahaan karena jika penjualan berkurang maka perusahaan tersebut akan terganggu dalam melakukan aktvitas perusahaan terutama membayar beban gaji karyawan dan beban-beban lainnya. Manajemen pemasaran sangatlah penting untuk dilakukan terutama dalam melakukan kunjungan ke customer atau pelanggan. Pada perusahaan Landahur kunjungan ke setiap customer paling cepat dikunjungi setiap minggu sekali dan paling lambat tiga  minggu oleh salesman. Kunjungan tersebut terjadwal berdasarkan area atau wilayah sehingga kunjungan dapat dilakukan secara terukur dan terarah. Dengan banyaknya customer yang perlu dikunjungi setiap harinya, maka perlu dikembangkan sistem optimasi pendistribusian bahan makanan dan snack dengan algoritma Ant Colony Optimization (ACO) .  Dengan demikian, perjalanan pendistribusian akan mendapatkan rute optimum atau jalur terpendek sehingga dapat menekan waktu kunjungan dan beban biaya.
Permasalahan pendistribusian tersebut termasuk dalam sebuah Travelling Salesman Problem (TSP). Travelling Salesman Problem (TSP) adalah pencarian rute terpendek atau jarak minimum oleh seorang salesman dari suatu kota ke n-kota tepat satu kali dan kembali ke kota awal keberangkatan[1]. Dalam mendistribusikan barang seorang salesman akan mendatangi atau menentukan tempat yang harus di kunjungi pertama kali sampai ke tempat terakhir dan kembali ke tempat pertama pemberangkatan, dimana setiap tempat hanya boleh di kunjungi satu kali dalam satu perjalanan dengan memperhitungkan jarak dan waktu tempuh yang paling kecil. Travelling Salesman Problem dapat diterapkan pada graph komplit berbobot yang memiliki total bobot sisi minimum, dimana bobot pada sisi adalah jarak. Rute TSP ini memuat semua titik pada graph tersebut tepat satu kali. Dalam penyelesaian masalah TSP ada berbagai macam metode optimasi yang dapat di gunakan, diantaranya Ant Colony Optimization (ACO), Campbell Dudeck Smith (CDS), Greedy Algorithm, Particle Swarm Optimization (PSO), dan Genetic Algorithm (Algoritma Genetika) [2].
Algoritma Ant Colony Optimizatio (ACO) merupakan algoritma pencarian berdasarkan probabilistik dan  merupakan salah satu algoritma yang bersifat heuristik dalam menyelesaikan masalah optimasi.  ACO diadopsi dari perilaku semut yang dikenal dengan System Semut. Dalam mencari makanan koloni semut mampu menemukan rute terpendek dengan alamiah dari lokasi sarang menuju lokasi sumber makanan. Semut memiliki zat pheromone dimana di gunakan untuk menandai jalur yang dilalui. Semakin banyak semut yang melaui jalur tersebut maka semakin pekat aroma pheromone sehingga akan banyak semut yang melewati jalur tersebut.
Berdasarkan  masalah yang ada pada perusahaan tersebut,  penulis membangun sistem optimasi pendistribusian bahan makanan dan snack yang diaplikasikan  dengan  algoritma Ant Colony Opmization (ACO) . Dengan tujuan untuk menemukan jalur terpendek yang dilalui oleh salesman dalam melakukan kunjungan ke pelanggan. Nilai perhitungan yang digunakan adalah jarak antar titik lokasi customer yang dimana dari setiap lokasi customer diambil latitude dan longitude dan kecepatan diambil berdasarkan kecepatan rata – rata yang dilalui oleh salesman. Harapannya dengan penelitian ini dapat membantu perusahaan dalam menghemat waktu dan biaya akomodasi.

## Kajian Pustaka
Sebagai bahan perbandingan maka diperlukan beberaa kajian tentang penelitian terdahulu yang terkait dengan optimasi yang menggunakan algoritma Ant Colony Optimization (ACO). Pada penelitian sebelumnya yang berjudul ”Penerapan Algoritma Ant Colony Optimization Pada Aplikasi Pemandu Wisata Provinsi Sumatera Utara Berbasis Android” bertujuan untuk memudahkan seorang wisatawan dalam mencari rute terpendek menuju tempat pariwisata. Penelitian ini melakukan perhitungan bobot terkecil dari semua rute yang dihubungkan dari satu tempat ke tempat lainnya dalam rangka kunjungan ke area wisata tertentu [3].
Penelitian berikutnya dilakukan Nurlaelasari  [4] menggunakan Algoritma Ant Colony Optimization untuk mencari nilai optimal dalam memilih objek wisata di Karawang. Dalam penelitian tersebut jarak bukanlah satu satunya tolak ukur yang dapat di perhitungkan saat melakukan perjalanan, sehingga harus menambahkan variabel lain yaitu biaya pada sebuah jarak. Sehingga mampu meminimalkan biaya transportasi dalam menuju tempat wisata.
Semut memiliki sifat sosial dan hidup didalam koloninya serta mempunyai sifat atau karakter yang menarik yaitu berkoordinasi dalam mengumpulkan makanan. Semut akan mencari makanan secara acak ketika sumber makanan di temukan semut tersebut, akan membawa makanan kembali ke sarangnya. Dengan sebuah mekanisme tertentu, semut – semut yang lain akan mengetahui jalur untuk menuju ke sumber makanan tersebut,  kemudian mengangkut makanan ke sarangnya. Bahkan ketika jalur yang sudah tercipta diberi penghalang, semut tersebut akan menemukan jalur baru yang menghubungkan ke tujuannya [6]. Hal
ini terjadi karena pada saat semut berjalan mereka meninggalkan jejak berupa pheromone . Pheromone digunakan untuk mencari solusi optimal dari suatu perjalanan semut sehingga proses dari sarang menuju ke tujuan sumbermakanan lebih cepat [7]. Formulasi lengkap algoritma semut adalah sebagai berikut [8]:
1. Inisialiasi parameter (jumlah semut, intensitas jejak semut antar kota, jumlah kota, tetapan siklus semut, jumlah siklus maksimum, intensitas jejak semut, pengendalian visibilitas, dan penguapan jejak semut).
2. Penyusunan rute kunjungan dengan menggunakan persamaan
𝑝𝑝 𝑎𝑎𝑎𝑎 = 𝜏𝜏 𝑎𝑎 , 𝑎𝑎 𝛼𝛼 x η a , b 𝛽𝛽 ∑𝑘𝑘𝑘𝑘𝑘𝑘 𝜏𝜏 𝑎𝑎 , 𝑎𝑎 𝛽𝛽 x η a , b 𝛽𝛽 ∀ 𝑏𝑏 ∈ 𝑘𝑘
3. setelah itu dicari probabilitas kumulatifnya dengan membangkitkan bilangan random (r) untuk di bandingan dengan probabilitas kumulatif sehingga customer ke n akan terpilih jika nilai  r > q n-1 dan  r  ≥  q n, Kemudian kota selanjutnya di pilih dan dimasukan ke tabulist(memori tiap semut). Selanjutnya mengulangi proses ini sampai semua kota telah dikunjungi.
4. Perhitungan panjang rute setiap semut
5. Mengecek kondisi berhenti apabila belum mencapai kondisi berhenti:
a. Menghitung matriks perubahan intensitas feromone pada tiap semut, jika jalur (a ,b ) atau ( b,a ) terdapat pada memori:
∆𝜏𝜏 𝑎𝑎𝑎𝑎 𝑘𝑘 = � 1 𝐶𝐶𝐶𝐶𝐶𝐶𝑡𝑡 𝑘𝑘
Untuk (a,b) ϵ tour yang dilakukan semut k  0. Untuk sebaliknya.
Keterangan:
∆𝜏𝜏 𝑎𝑎𝑎𝑎 𝑘𝑘 = Perubahan intensitas feromon semut ke – k dari titik i ke j Cost k = Total jarak terpendek yang di perlukan oleh semut
b. Menghitung matriks perubahan intensitas feromon global untuk setiap semut.
∆𝜏𝜏 𝑎𝑎𝑎𝑎 = � ∆𝜏𝜏 𝑎𝑎𝑎𝑎 𝑘𝑘 𝑚𝑚
Keterangan : Δ ꚍ ab = Perubahan intensitas feromon global
Δ ꚍ kab = Perubahan intensitas feromon semut ke – k dari titik a ke titik b
c. Menghitung update feromone dengan persamaan 𝜏𝜏 𝑎𝑎𝑎𝑎 = (1 − 𝜌𝜌 ) 𝜏𝜏 𝑎𝑎𝑎𝑎 , ∀𝑎𝑎 , 𝑏𝑏 ∈ [1, 𝑛𝑛 ]
d. Mengosongkan kembali tabel jalur pada kunjungan yang di lewati oleh semut.
e. Mengulangi langkah 2 sampai mencapai siklus maksimum.
Gambar 1 . Flowcart algoritma Ant Colony Optimization ACO

## Metode Penelitian
Alur penelitian ini diawali dengan mengidentifikasi masalah dengan observasi ke perusahaan Landahur baik berupa wawancara atau mengetahui secara langsung aktivitas yang dilakukan.dari hasil pendalalaman pendalaman objek yang terdiri dari berbagai permasalahan,selanjutnya dirumuskan kembali yakni disimpulkan atau di kerucutkan kendala apa yang menjadi inti masalah.
Selanjut tahapan studi pustaka dilakukan sebagai referensi serta mengkaji teori dari penelitian terdahulu yang sudah dilakukan yang berhubungan dengan masalah yang sedang diteliti. Referensi tersebut berupa jurnal ilimiah, buku, artikel yang lainnya. Setelah proses perumusan masalah dan studi pustaka maka akan didapatkan garis besar penelitian yang akan dilakukan. Dari hal tersebut dilakukan sebuah analisa sehingga masalah akan ditangani secara terukur dan dapat dipilih solusi yang paling optimal.
Dalam  penelitian ini penyelesaiannya algoritma yang digunakan harus mematuhi dua batasan yaitu titik keberangkatan harus menjadi titik pemberhentian dan semua titik selain titik keberangkatan hanya dikunjungi sekali. Dalam Observasi yang telah dilakukan oleh peneliti,  diketahui permasalahan yang ada dimana belum mengetahui jarak tempuh minimal yang harus dilalui oleh salesman lewat aplikasi secara menyeluruh dan hanya berdasarkan data manual. Data yang diambil dalam penelitian ini adalah data customer sebanyak 10 yang berupa nama customer , alamat, kordinat, dan jarak antar customer .

## Hasil dan Pembahasan
Dari perancangan yang sudah disusun dengan uji coba data dengan perhitungan aplikasi sehingga diketahui hasil yang akurat dan tidak akurat. Dalam percobaan ini dilakukan dengan sample data sejumlah 5 dan 10 customer. Adapun parameter yang digunakan yakni Jumlah semut sebanyak 3, α = 1, β = 0,5, ρ = 0,5194, Pheromone awal = 0,1, dan Iterasi sebanyak 2. Berikut adalah tampilan halaman distribusi setelah dilakukan generate algoritma ACO pada aplikasi .

## Gambar 2. Tampilan halaman distribusi setelah generate ACO
Percobaan pertama dengan menggunakan 5 data yang terdiri dari data pelanggan yang berjumlah 4 buah dan data pemberangkatan (cabang perusahaan) 1 buah. Jarak antar lokasi diperoleh secara manual dari sistem aplikasi dengan cara mencari satu persatu jarak antar titik customer. Data tersebut di susun secara matrix untuk mempermudah  pembacaan dengan menggunakan  satuan jarak km  seperti yang dapat dilihat pada tabel 1 berikut ini.
Tabel 1 Data jarak antar titik KODE  Nama Customer 0 1 2 3 4 0 SOTO AYAM PAK JA'I 0 1,7 5,9 4 2,2 1 KOPERASI SEHAT /RSUD BJN 1,7 0 4,7 5,7 2,4 2 TANJUNG DRAJAT 5,9 4,7 0 5,5 7,1 3 CV.Landahur 4 5,7 5,5 0 6,2 4 LANGGENG 2,2 2,4 7,1 6,2 0
Dari data tersebut, selanjutnya dilakukan  uji coba pertama dan didapatkan rute yang dilalui memiliki jarak tempuh 20,3 km dengan waktu tempuh rata rata adalah 30,45 menit. Hasil perhitungannya daat dilihat ada tabel berikut ini.
Tabel 2 Hasil data uji pertama Percobaan Rute Jarak tempuh Waktu 1 3-4-0-1-2-3 20,3 km 30,45 Menit
Percobaan kedua dilakukan dengan menggunakan 10 data yang terdiri dari data  pelanggan  yang berjumlah 9  buah dan data pemberangkatan (cabang perusahaan) 1 buah,  jarak antar lokasi didapat kan secara manual dari sistem aplikasi dengan cara mencari satu persatu dari antar titik customer sehingga didapatkan data jarak. Data tersebut di susun secara matrix supaya mudah dalam pembacaan dengan satuan jarak km.
Tabel 3 Data jarak antar titik Nama Customer 0 1 2 3 4 7 8 9 10 11 0 SOTO AYAM PAK JA'I 0  1,7  5,9  4  2,2  1,5  1,7  3,2 3,2 3,2 1 KOPERASI SEHAT/RSUD BJN  1,7  0  4,7  5,7  2,4  1,3  1,7  2,5 2,4 2,3 2 TANJUNG DRAJAT 5,9  4,7  0  5,5  7,1  6  6,4  6,1 6 5,9 3 CV.Landahur 4  5,7  5,5  0  6,2  5,4  5,7  7,6 7,1 7,2 4 LANGGENG 2,2  2,4  7,1  6,2  0  1,4  0,8  1,0 1,1 1,1 7 NURUL ,BU 1,5  1,3  6,0  5,4  1,4  0  0,7 2 1,9 1,9 8 KUSUMA ,BU 1,7  1,7  6,4  5,7  0,8  0,7  0,0  1,6 1,5 1,6 9 PT. TOP BUKU GROSIR 3,2  2,5  6,1  7,6  1,0  2  1,6 0 0,070  0,2 10 SENTRAL MANDIRI LISTRIK  3,2  2,4  6,0  7,1  1,1  1,9  1,5  0,07 0 0,09 11 BTPN BOJONEGORO 3,2  2,3  5,9  7,2  1,1  1,9  1,5  0,20  0,09 0
Dari data tersebut pada uji coba kedua didapatkan hasil rute terbaik  dengan catatan waktu diambil dari kecepatan mengemudi salesman berkisar antara 30 – 50 km/jam. Adapun hasil perhitungan adalah sebagai berikut :
Tabel 4 Hasil perhitungan manual excel dengan 10 data. Percobaan Rute Jarak tempuh Waktu 2 3-8-4-9-10-11-7-0-1-2-3 22,96 km 34,44 Menit
Pada tabel di atas dalam percobaan pertama didapatkan rute atau customer yang dilalui dengan jarak tempuh 22,96 km dengan waktu rata rata yang didapatkan 34,44 Menit.
Dari hasil dua percobaan yang sudah dilakukan, selanjutnya dilakukan pengujian akurasi hasil perhitungan dengan cara membandingkan hasil perhitungan alpikasi dengan hasil perhitungan manual. Fokus perhitungan adalah pada  waktu tempuh dan jarak tempuh. Pengujian dilakukan dengan menggunakan parameter yang sama dan diperoleh hasil sebagai berikut.
Tabel 5 Data perbandingan jarak tempuh
Jumlah data Rute kunjungan Jarak (km) Aplikasi algoritma ACO Manual Algoritma ACO Aplikasi algoritma ACO Manual Algoritma ACO Selisih 5 3-2-1-0-4-3  3-4-0-1-2-3 20,3 km 20,3 km 0 km 10 3-2-1-0-7- 11-10-9-4-8- 3 3-2-1-0-7- 11-10-9-4- 8-3 22,96 Km 22,96 Km 0 km
Dari tabel 5 dapat dilihat bahwa jarak rute dari perhitungan manual dengan aplikasi sejumlah tidak terdapat selisih. Dengan demikian bisa dikatakan bahwa perhitungan yang dilakukan oleh aplikasi sudah benar dan sesuai dengan yang sebenarnya.

## Simpulan
Berdasarkan percobaan yang dilakukan, algoritma Ant Colony Optimization (ACO) dapat digunakan dalam membantu pencarian rute terpendek dalam pendistribusian bahan makanan dan snack. Percobaan dengan 5 dan 10 data lokasi
antar pelanggan dengan parameter yang sama yakni Semut 3 ekor, 2 iterasi, α = 1, β = 0,5, ρ = 0,5194, Pheromone awal = 0,1 aplikasi dapat menunjukan jarak rute minimum yang akan dilewati oleh salesman 20,3 km untuk 5 data. Serta 22,16 km untuk pengujian 10 data.  Sehingga dapat disimpulkan bahwa perhitungan pada aplikasi dapat menunjukan rute terpendek. Durasi waktu dalam perncarian rute pada aplikasi terukur cepat karena mengingat jumlah yang digunakan 5 semut dan 10 semut, serta iterasi yang digunakan sebanyak 3.
Sistem optimasi pengiriman distribusi makanan dan snack dengan algoritma Ant Colony Optimization (ACO) yang diimplementasikan masih jauh dari kesempurnaan untuk itu diperlukan pengembangan pada penelitian selanjutnya. Dengan  kriteria perhitungan dan algoritma yang lain supaya diketahui perbedaan tingkat keakurasiannya tentunya lebih baik lagi.

## Daftar Pustaka
[1]  Yumalia, A. (2017) ‘Minimasi Biaya Distribusi Dengan Menggunakan Metode Traveling Salesman Problem ( TSP )’, Jurnal UMJ , (November 2017), pp. 1–8. Available at: jurnal.umj.ac.id/index.php/semnastek.
[2]  Yuliastuti, G. E., Mahmudy, W. F. and Rizki, A. M. (2017) ‘Penanganan Fuzzy Time Window pada Travelling Salesman Problem (TSP) dengan Penerapan Algoritma Genetika’, Matics , 9(1), p. 38. doi: 10.18860/mat.v9i1.4072.
[3]  Anshory, Z. (2020) ‘Penerapan Algoritma Ant Colony Optimization Pada Aplikasi Pemandu Wisata Provinsi Sumatera Utara Berbasis Android’, 1(2), pp. 61–67.Available at: https://ejurnal.seminard.com/index.php/josyc/article/view/106
[4] Nurlaelasari, E., Supriyadi, S. and Lenggana, U. T. (2018) ‘Penerapan Algoritma Ant Colony Optimization Menentukan Nilai Optimal Dalam Memilih Objek Wisata Berbasis Android’, Simetris: Jurnal Teknik Mesin, Elektro dan Ilmu Komputer , 9(1), pp. 287–298. doi: 10.24176/simet.v9i1.1914.
[5] Purnomo, R. G., Maylawati, D. S., & Alam, C. N. (2018). Implementas Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP) . JOIN (Jurnal Online Informatika) .
[6] Soesanto, O., Affandi, P. and Astuti, N. D. (2019) ‘Algoritma Ant Colony Optimization pada Quadratic Assignment Problem’, Jambura Journal of Mathematics , 1(2), pp. 104– 110. doi: 10.34312/jjom.v1i2.2353
[7]   Sihaloho, I. and Cholissodin, I. (2019) ‘Optimasi Travelling Salesman Problem Pada Angkutan Sekolah Menggunakan Algoritme Genetika ( Studi Kasus : Sekolah MI Salafiyah Kasim Blitar )’, Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer (J-PTIIK) Universitas Brawijaya , 3(1), pp. 454–461.