Algoritma ant colony optimizaion (ACO) pada multi depot vehicle routing problem

Abstract

Permasalahan Multi Depot Vehicle Routing Problem (MDVRP) merupakan permasalahan perluasan dari Vehicle Routing Problem (VRP) dengan kondisi dimana depot yang digunakan sebagai pusat distribusi barang lebih dari satu. Kaur, M., dan Goyal, S., (2013) dalam jurnalnya menuliskan bahwa ada beberapa tahap algoritma dalam menyelesaikan masalah MDVRP dengan menggunakan algoritma Ant Colony Optimization, yaitu dengan aturan transisi status, tahap pembaharuan jejak pheromone, pembaharuan jejak lokal dan daftar calon rute baru. Sedangkan MDVRP sendiri mempunyai tiga tahapan dalam menyelesaikan masalah. Sebelum masuk pada tahap transisi status, beberapa customer dikelompokkan berdasarkan depot terdekat. Aturan transisi status dan pembaharuan jejak pheromone dimasukkan pada tahap pembentukan rute. Pada tahap terakhir, urutan pengiriman dipilih dengan menggunakan pembaharuan jejak lokal dan perhitungan rute akhir.
Pada algoritma Ant Colony Optimization digunakan parameter yang mengontrol bobot relatif pheromone yaitu α dan parameter pengendali jarak atau β. Parameter α dan β digunakan untuk menghitung nilai probabilitas P_ij^k dari semut k pada titik i yang memilih untuk menuju titik j. Nilai ρ (parameter tingkat evaporasi pheromone) yang besar mengakibatkan nilai pembaruan pheromone juga besar sedangkan jika nilai ρ kecil maka nilai pembaruan pheromone juga kecil.