Air merupakan kebutuhan primer bagi makhluk hidup, khususnya manusia, karena di dalam tubuh manusia didominasi oleh air. Untuk dapat terus hidup manusia membutuhkan air yang diperlukan bagi metabolisme tubuh. Pesatnya perkembangan teknologi dan informasi membawa dampak terhadap tatanan kehidupan di masyarakat yang menginginkan sesuatu hal cepat dan praktis. Di Kabupaten Rembang khususnya, kebutuhan akan air minum bersih, meningkat seiring bertambahnya jumlah penduduk, cadangan air dalam tanah tiap daerah di Kabupaten Rembang ini sangat beragam, kondisinya pun beragam, ada yang bagus layak untuk dikonsumsi, ada yang hanya layak untuk mencuci, bahka ada ang tidak layak untuk dikonsumsi. PT. Sekar Sari Sejahtera Abadi merupakan salah satu perusahaan yang memproduksi dan menjual air dalam kemasan yang berada di Desa Leran, Kecamatan Sluke, Kabupaten Rembang, Jawa Tengah,jalan raya Semarang - Surabaya KM 137 dengan nama dagang "sarine". Jumlah total agen bulan April 2017 yang dilayani adalah 103 Agen/Customer. Pendistribusian awal perusahaan menggunakan Daihatsu GranMax Box dengan jumlah 3 mobil yang membentuk 3 rute distribusi. Sistem pendistribusian "sarine" ini dimodelkan sebagai salah satu varian dari permasalahan penentuan rute kendaraan (vehicle routing problem) dengan adanya batasan kapasitas angkut kendaraan (capacitated) dengan menggunakan algoritma sweep. Batas maksimal angkut kendaraan adalah 1680 kg, yang setiap hari Selasa mendistribusikan "sarine" ke 22 agen/customer. Implemantasi CVRP dengan Algorita Sweep pada pendistribusian AMDK "sarine" mengasilkan 4 rute dengan masing-masing rute menggunakan 1 kendaraan. Terjadi perbedaan jarak tempuh antara rute awal dengan rute usulan sebesar 29.67%. Perbedaan waktu tempuh kendaraan sebesar 29.87%, biaya bahan bakar 29.67%.

Kata kunci : AMDK, "sarine", CVRP, Sweep