Algoritma hybrid genetika pada capacitated vehicle routing problem (CVRP) dan implementasinya

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan varian dari permasalahan VRP yaitu mengenai masalah pencarian sejumlah rute kendaraan dengan jarak minimum untuk memenuhi permintaan sejumlah customer yang hanya dikunjungi tepat satu kali dan tidak melebihi kapasitas kendaraan dengan perluasan setiap kendaraan memiliki kapasitas yang sama. Dan rute kendaraan berawal dan berakhir di depot yang sama. Algoritma genetika merupakan teknik optimasi yang didasarkan pada proses evolusi makhluk hidup, dimana dalam evolusi tersebut makhluk hidup mengalami mekanisme seleksi alam (diantaranya pindah silang dan mutasi) untuk bertahan hidup. Algoritma genetika merupakan suatu algoritma yang dapat diaplikasikan dalam berbagai jenis permasalahan optimasi. Algoritma best improvement local search adalah salah satu keluarga local search yang memperhitungkan semua perubahan di lingkungan sekitarnya berdasarkan permutasi, ditinjau dari semua kemungkinan keadaan yang didapat untuk menghasilkan nilai optimal. Algoritma pengembangan untuk permasalahan CVRP tersebut adalah algoritma genetika hybrid. Algoritma genetika hybrid merupakan gabungan dari algoritma genetika dan local search (best improvement local search). Dalam menyelesaikan permasalahan CVRP dengan menggunakan algoritma genetika hybrid dibutuhkan proses yang panjang. Oleh sebab itu, untuk mempermudah pencarian rute, diimplementasikan ke dalam program menggunakan Borland Delphi 7.