PENYELESAIAN SPLIT DELIVERY VEHICLE ROUTING PROBLEM MENGGUNAKAN INTEGER LINEAR PROGRAMMING DAN ALGORITME TABU SEARCH

Abstract

Suatu masalah penentuan rute pendistribusian barang ke para pelanggan yang dimulai dan diakhiri di suatu depot disebut sebagai Split Delivery Vehicle Routing Problems (SDVRP). Setiap pelanggan dapat dikunjungi lebih dari satu kali. Model SDVRP merupakan kasus NP-Hard Problem yang dapat diselesaikan menggunakan metode eksak, heuristic maupun metaheuristic. Pada karya ilmiah ini, SDVRP diselesaikan menggunakan metode eksak Integer Linear Programming (ILP) dan metode metaheuristic algoritme Tabu Search 2-opt. Hasil uji coba memperlihatkan bahwa waktu eksekusi menggunakan algoritme Tabu Search 2-opt 61,240 kali lebih cepat dibandingkan dengan metode ILP. Akan tetapi, algoritme Tabu Search 2-opt hanya menghasilkan solusi pendekatan dengan selisih jarak sebesar 15.55% dari hasil optimal yang diperoleh dengan metode ILP.