VRP (Vehicle Routing Problem)

VRP (Vehicle Routing Problem)

              VRP merupakan program non-linear yang mencari sebuah solusi pemecahan masalah. Program ini pertama kali ditemukan oleh Dantzig and Ramser pada tahun 1959. VRP terdiri dari penentuan rute kendaraan yang melayani beberapa pelanggan. Setiap kendaraan memiliki kapasitas angkut, dan setiap pelanggan memiliki demand. Tiap pelanggan dikunjungi tepat satu kali dan total demand tiap rute tidak boleh melebihi kapasitas angkut kendaraan. Dalam VRP sendiri dikenal pula istilah depot, dimana tiap kendaraan harus berangkat dan kembali ke depot itu. Hal tersebutlah yang menyebabkan VRP sering disebut sebagai permasalahan n-TSP.

                Faktor yang sering muncul pada VRP adalah masalah kapasitas yang dikenal dengan nama Capacitated Vehicle Routing Problem (CVRP) dan juga masalah batasan waktu yang dikenal sebagai Vehicle Routing Problem with Time Windows (VRPTW). Kedua permasalahan ini dapat digabungkan dengan prioritas utama yaitu semua permintaan terpenuhi batas waktunya.