Vehicle routing problem (VRP) merupakan aplikasi dari optimasi kombinatorial untuk menentukan sejumlah rute yang diawali dan diakhiri di suatu tempat. Permasalahan pengelolaan pengangkutan sampah merupakan bagian yang sangat penting dalam menjaga estetika dan kenyamanan suatu kota maupun wilayah. Provinsi Sumatera Utara sendiri merupakan salah satu provinsi di Indonesia penghasil timbunan sampah, dimana wilayah pada provinsi tersebut yang memiliki rasio produksi sampah harian per penduduk tertinggi adalah di Kota Pematangsiantar sebanyak 0,83 kg/hari per penduduk yang tentunya akan mengakibatkan tingginya angka timbunan sampah harian. Tingginya angka timbunan sampah tentunya harus di imbangi dengan baiknya pelayanan pengangkutan keseluruhan sampah yang ada di suatu wilayah. Penelitian ini bertujuan untuk mendapatkan rute kendaraan untuk distribusi pengangkutan sampah dengan meminimalkan waktu tempuh yang optimal untuk distribusi tersebut. Dengan menggunakan vehicle routing problem diperoleh 43 rute untuk 34 unit kendaraan pengangkut sampah, dengan total timbunan sampah 183,1 m3/hari dan total waktu operasional 4608 menit

---

The Vehicle Routing Problem is an application of combinatorial optimization to determine a number of routes that start and end at one place. The problem of managing waste transportation is a very important part in maintaining the aesthetics and comfort of a city or region. North Sumatra Province itself is one of the provinces in Indonesia that produces waste piles, where the area in the province that has the highest daily waste production ratio per resident is Pematangsiantar City as much as 0.83 kg/day per resident which of course will result in high daily waste accumulation rates. The high number of landfills must of course be balanced with good transportation services for the entire waste in an area. This study aims to obtain vehicle routes for the distribution of waste transportation by minimizing the optimal travel time for the distribution. By using the Vehicle Routing Problem, 43 routes were obtained for 34 units of garbage transporting vehicles, with a total waste pile of 183.1 m3/day and a total operational time of 4608 minutes