Penerapan algoritma Multi-Verse Optimizer pada penyelesaian Capacitated Vehicle Routing Problem with Time Windows

Abstract

Salah satu permasalahan yang sering terjadi dalam dunia perindustrian adalah permasalahan yang terkait dengan distribusi. Distribusi akan berdampak pada biaya yang harus dikeluarkan. Biaya distribusi meliputi biaya jarak tempuh kendaraan dan jumlah kendaraan yang digunakan yang harus diminimasi. Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) merupakan suatu permasalahan yang terkait dengan pencarian rute terpendek yang dapat ditempuh oleh sejumlah kendaraan dalam melayani pelanggan dalam ruang waktu tertentu. CVRPTW merupakan permasalahan bersifat nondeterministic polynomial-time hard (NP-Hard). Hal ini dikarenakan semakin banyak jumlah pelanggan yang dilayani, maka waktu yang dibutuhkan semakin lama, sehingga metode eksak tidak cukup efisien dalam segi waktu komputasi untuk menyelesaikan permasalahan ini. Oleh karena itu, perlunya metode lain untuk dapat menyelesaikan permasalahan CVRPTW. Salah satu metode yang dapat menyelesaikan permasalahan dengan np-hard adalah dengan menggunakan metode metaheuristik. Pada penelitian ini, permasalahan CVRPTW akan diselesaikan dengan algoritma Multi-Verse Optimizer (MVO). MVO merupakan algoritma metaheuristik yang terinspirasi dari hipotesis multiverse dimana terdapat beberapa alam semesta (universe) yang memiliki beberapa objek di dalamnya dan dapat saling berinteraksi. Dalam pencarian universe terbaik, ada dua jenis perpindahan objek yang dilakukan, yaitu perpindahan dengan melewati Black/White Hole (eksplorasi) dan perpindahan dengan melewati Wormhole (eksploitasi). Pada penelitian ini, MVO diimplementasikan pada enam benchmark problems CVRPTW. Hasil implementasi yang dilakukan akan dibandingkan dengan dua algoritma pembanding, yaitu Grey Wolf Optimizer (GWO) dan Bat Algorithm (BAT). Secara keseluruhan, dapat dikatakan bahwa MVO memiliki peformansi yang lebih baik dari GWO. Algoritma MVO juga dapat mendapatkan hasil yang lebih dengan BAT pada tiga kasus benchmark danmemberikan hasil yang serupa pada tiga kasus yang lain. Algoritma MVO mempunyai tiga parameter yang diuji pengaruhnya terhadap performansi yang dihasilkan, yaitu variabel max, min dan p. Hasil pengujian menunjukkan adanya pengaruh parameter max dan p terhadap nilai fungsi objektif yang dihasilkan MVO untuk satu kasus benchmark.