Penerapan Algoritma Simulated Annealing untuk menyelesaikan permasalahan Multitrip Location Routing Problem

Abstract

Multi-Trip Location Routing Problem (MTLRP) merupakan suatu pengembangan permasalahan dari Vehicle Routing Problem (VRP). Dalam MTLRP akan ditentukan depot yang akan digunakan dan rute perjalanan setiap kendaraan, di mana fungsi objektif dari MTLRP adalah meminimasi biaya. Setiap kendaraan pada MTLRP ini bersifat heterogen dan dapat melakukan beberapa kali perjalanan. Dalam penelitian ini, MTLRP akan diselesaikan dengan menggunakan algoritma Simulated Annealing (SA). SA merupakan salah satu algoritma metaheuristik yang dapat menghindari lokal optimal. Terdapat 4 parameter SA yang digunakan yaitu suhu maksimum (Tmax), suhu minimum (Tmin), cooling rate (CR), dan jumlah replikasi maksimum (Nmax). Selain itu, terdapat solusi tetangga yang akan selalu dibangkitkan pada iterasi dan replikasi tertentu. Pembangkitan solusi tetangga ini akan menggunakan metode neighborhood moves, yaitu insert, swap, dan reverse. Algoritma SA diimplementasikan ke dalam 5 kasus hipotetik, dengan 3 parameter yaitu Tmax, Tmin, dan CR, di mana setiap parameter memilki 2 level. Dari pengolahan data yang ada, didapatkan bahwa CR memiliki pengaruh terhadap performansi algoritma SA. Kemudian, dari 5 kasus tersebut, didapatkan 1 kasus mencapai solusi optimal sedangkan sisanya memiliki selisih penyimpangan maksimum sebesar 2,828%.