Penyelesaian Vehicle Routing Problem Menggunakan Algoritme Genetika

Abstract

Vehicle routing problem (VRP) adalah masalah penentuan rute terpendek sekelompok kendaraan yang harus mengunjungi beberapa kota. Penyelesaian VRP berukuran besar dengan metode eksak akan memerlukan waktu komputasi yang lama, sehingga pada umumnya VRP berukuran besar diselesaikan dengan metode pendekatan (heuristik). Algoritme genetika adalah salah satu metode pendekatan untuk masalah optimasi seperti VRP. Secara umum, tahapan algoritme genetika adalah pengodean, pembangkitan populasi awal, seleksi induk, kawin silang, mutasi, dan penggantian generasi. Banyak pilihan metode yang dapat digunakan dalam tahapan-tahapan algoritme genetika tersebut. Tujuan penelitian ini adalah mendeskripsikan cara kerja algoritme genetika untuk menyelesaikan VRP. Dalam penelitian ini, VRP dengan 9 kota diselesaikan dengan algoritme genetika menggunakan metode stochastic universal sampling untuk seleksi induk, order crossover untuk kawin silang, dan insertion untuk mutasi dengan bantuan software MATLAB R2008b. Algoritme genetika menghasilkan rute terpendek 29 km, sedangkan hasil dengan metode eksak diperoleh rute terpendek 27 km.