Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif

Abstract

Pendistribusian barang atau jasa merupakan salah satu bagian penting dari kegiatan sebuah instansi pemerintah ataupun perusahaan tertentu, yang sering mengadakan pengambilan keputusan mengenai rute yang dapat mengoptimalkan biaya, waktu dan sumberdaya lain yang tersedia. Masalah ini dapat diformulasikan secara matematis sebagai sebuah Vehicle Routing Problem (VRP). VRP merupakan salah satu aplikasi dari teori graf dan optimasi kombinatorial yang mencakup penentuan sejumlah rute angkutan yang diawali dan diakhiri di suatu tempat yang disebut depot untuk mengantarkan barang kepada sekumpulan pelanggan sesuai permintaannya masing-masing. Rute yang terbentuk harus mengunjungi setiap pelanggan tepat satu kali dan menghabiskan biaya atau jarak tempuh seminimal mungkin. Salah satu variasi dari VRP adalah VRP time windows (VRPTW) yang menambahkan kendala batasan selang waktu tertentu (time windows) dalam melayani pelanggan.