Penelitian ini dilakukan di salah satu perusahaan yang bergerak di industri semen yang mendistribusikan produknya ke seluruh Indonesia. Berdasarkan hasil audit yang telah dilakukan, maka dapat diketahui bahwa kondisi pendistribusian produk di wilayah Jawa Tengah masih kurang baik karena masih terdapat sejumlah status minor dan mayor di dalam perspektif manajemen pergudangannya dan persentase komponen biaya pergudangan pada gudang yang disewa kepada pihak distributor terhadap total biaya distribusi melebihi dari batas maksimum yang telah ditetapkan. Oleh karena itu, perlu untuk menentukan lokasi gudang distribusi baru yang dimiliki oleh perusahaan dengan mempertimbangkan aspek kualitatif dan kuantitatif, kemudian menghentikan pengoperasian gudang yang diewa kepada pihak distributor karena tingginya biaya subsidi yang ditetapkan oleh pihak ketiga tersebut. Metode yang digunakan dalam penelitian ini adalah analisis kelayakan investasi menggunakan perhitungan Net Present Value dan Benefit Cost Ratio, penentuan lokasi optimal menggunakan metode P-Median, dan penentuan lokasi berdasarkan multi-kriteria menggunakan metode Analytical Network Process. Hasil penelitian menunjukkan bahwa lokasi dengan bobot tertinggi berdasarkan pengambilan keputusan multi-kriteria dan dinyatakan layak berdasarkan analisis kelayakan investasinya, yaitu terletak di Kabupaten Cilacap dengan lokasi optimal di Kabupaten Cilacap Utara. Jika keputusan ini dilakukan, perusahaan dapat mengurangi total biaya distribusi yang harus dikeluarkan oleh perusahaan.