IMPLEMENTASI ALGORITMA FLOYD WARSHALL DAN NEAREST NEIGHBOUR DALAM PENGOPTIMALAN RUTE CAPACITATED VEHICLE ROUTING PROBLEM WITH TIME WINDOWS (CVRPTW)

Abstract

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) merupakan masalah penentuan rute
tercepat kendaraan untuk memenuhi permintaan konsumen yang terdiri dari pelayanan antar dengan kendala
kapasitas kendaraan, time windows, dan kecepatan pada tiap jalur berdasarkan waktu per jam. Dalam
menyelesaikan masalah CVRPTW akan digunakan dua algoritma, yakni algoritma Floyd Warshall dan
Nearest Neighbour. Pada penelitian ini, dijelaskan mengenai penggunaan algoritma Floyd Warshall dan
Nearest Neighbour dalam penyelesaian masalah CVRPTW yang diimplementasikan pada data simulasi
secara manual dan menggunakan perangkat lunak MatLab. Selanjutnya akan dibandingkan efektifitas kedua
algoritma tersebut yang diukur berdasarkan waktu penyelesaian dan hasil pembentukan rute. Berdasarkan
hasil penelitian, diperoleh bahwa algoritma Floyd Warshall dapat membentuk rute dengan total waktu
tempuh 939 menit, yang lebih efektif dibandingkan dengan algoritma Nearest Neighbor dengan total waktu
tempuh 1.006 menit. Namun dalam proses penerapannya, algoritma Nearest Neighbour jauh lebih cepat dan
praktis dibandingkan dengan algoritma Floyd Warshall.
Kata kunci: Capacitated Vehicle Routing Problem With Time Windows (CVRPTW), Floyd Warshall,
Nearest Neighbour