PT. Sabina Tirta Utama merupakan produsen air minum dalam kemasan yang berlokasi di Jalan Mas Penghulu, Kota Samarinda. Selain menghasilkan Air Minum Dalam Kemasan (AMDK) perusahaan ini juga mendistribusikan hasil produknya kepada agen dan pelanggan akhir. Perusahaan ini memiliki kendaraan dengan jenis Daihatsu Gran Max Pick Up sebanyak 4 unit yang digunakan dalam pendistribusian AMDK dengan kapasitas maksimal sebanyak 200 dus. Pelanggan terbanyak perusahaan terdapat pada Kota Samarinda. Karena Perusahaan ini mendistribusikan hasil produknya maka harus menentukan rute yang dilalui untuk memenuhi permintaan dari pelanggan. Salah satu solusi untuk mengatasi permasalahan di PT. Sabina Tirta Utama Samarinda adalah dengan menggunakan Vehicle Routing Problem (VRP) yaitu metode penyelesaian persoalan distribusi dengan mempertimbangkan keterbatasan daya angkut (kapasitas) kendaraan. Dalam penyelesaian VRP digunakan beberapa metode yaitu metode Saving Matrix, Nearest Neighbour, dan Insertion. Berdasarkan hasil penelitian total jarak distribusi awal yaitu sebesar 117,53 km dengan rute awal sebanyak 10 rute dan biaya distribusi yaitu Rp979.417/bulan. Pada metode Saving Matrix total jarak dapat dioptimalkan menjadi 107,55 km dengan rute sebanyak 7. Setelah dilakukan pengurutan pelanggan menggunakan Nearest Neighbour didapatkan total jarak sebesar 103,13 km, sedangkan pada metode Insertion didapatkan total jarak sebesar 90,24 km. Dari ketiga metode tersebut didapatkan total jarak paling optimal yaitu sebesar 90,24 km yaitu dengan penggunaan metode Insertion. Sehingga perusahaan dapat menghemat jarak sebesar 23% dari jarak awal perusahaan. Oleh karena itu, perusahaan dapat menghemat biaya bahan bakar bensin yang awalnya Rp979.417 menjadi Rp752.000 dengan selisih Rp227.417/bulan.