ANALISIS CAPACITATED VEHICLE ROUTING PROBLEM (CVRP) PADA PRODUK AMDK AIRKU KEMASAN CUP 240ML DENGAN METODE MIXED INTEGER LINEAR PROGRAMMING (MILP) DAN ALGORITMA SWEEP-MILP (STUDI KASUS PADA PDAM TIRTA BINANGUN KULON PROGO)

Proses distribusi merupakan salah satu komponen penting yang mempengaruhi keunggulan kompetitif suatu perusahaan. Tidak optimalnya perencanaan sistem distribusi berdampak pada tingginya biaya distribusi. Perusahaan Daerah Air Minum (PDAM) Tirta Binangun Kulon Progo merupakan salah satu perusahaan yang memproduksi Air Minum Dalam Kemasan (AMDK) dengan nama produk AirKu. Tingginya permintaan produk AMDK AirKu kemasan cup 240 ml, terbatasnya kendaraan dengan kapasitas minim dan belum adanya standar rute distribusi yang jelas menyebabkan proses pendistribusian masih dilakukan secara acak. Tujuan dari penelitian ini adalah untuk membandingkan hasil rute pendistribusian yang diperoleh dengan rute perusahaan dan rute dari penelitan terdahulu guna memaksimalkan rute distribusi dan menambahkan opsi untuk perusahaan. Penelitian ini menggunakan pendekatan Capacitated Vehicle Routing Problem (CVRP) dimana penentuan rute dilakukan dengan adanya batasan kapasitas kendaraan. Penyelesaian permasalahan CVRP menggunakan metode eksak yaitu Mixed Integer Linear Programming (MILP) dan juga metode heuristik yaitu algoritma Sweep. MILP digunakan sebagai metode penyelesaian langsung dan juga sebagai metode lanjutan penentuan rute berdasarkan pembagian grup algoritma Sweep. Pada awal perusahaan jarak yang ditempuh adalah 403,16km. Berdasarkan penelitian diperoleh total jarak menggunakan MILP adalah 257,36km dan menggunakan Sweep-MILP adalah 309,4km. Sedangkan pada penelitian terdahulu, jarak yang didapatkan menggunakan metode Saving Matrix-Nearest Neighbor adalah 282,71km dan metode Sequential Insertion adalah 278km. Metode MILP menghasilkan rute distribusi terpendek dengan penghematan jarak sebesar 145,8km atau 36% lebih baik dari rute awal