ABSTRAK CV dua prima lestari merupakan distributor minuman adant. Lokasi pemasaran yang dilakukan oleh perusahaan ini ialah Meulaboh, Mereubo, Jeuram, Seumayam, Lamno, Teunom, Blangpidie, Susoh, Sawang, Meukek, dan Tapak Tuan di Propinsi Aceh. Perusahaan ini perlu memperhatikan segala aspek-aspek yang menguntungkan pihak perusahaan antara lain tepatnya lokasi gudang wilayah baru dengan tempat lokasi pengsuplaian ke konsumen-konsumen, pemanfaatan kendaraan dan meminimalisir jumlah pengantaran produksi dalam hal tersebut berhubungan dengan rute pendistribusian. Oleh karena itu untuk mengoptimalkan keuntungan perusahaan, diperlukan untuk mengaplikasikan suatu model optimisasi. Penelitian ini menggunakan model optimisasi binary integer programming yang diselesaikan dengan menggunakan software LINGO 11.0. Penelitian ini ditinjau berdasarkan jarak, jumlah permintaan, kapasitas gudang, biaya pendistribusian, kendaraan, dan kapasitas kendaraan. Menentukan penempatan lokasi gudang baru dengan asumsi rencana gudang sebanyak 3 gudang dengan beberapa jenis kapasitas gudang dan rute penditribusian dengan asumsi biaya perjalanan setiap kendaraan per km adalah sama. Gudang yang akan dibangun ialah gudang di lokasi 2 kapasitas besar, lokasi 3 kapasitas besar dan dilokasi 4 kapasitas besar. Total biaya yang dibutuhkan untuk proses pendistribusian adalah Rp 40.842.380. Total biaya minimum untuk mendapatkan rute yang optimal pada gudang 2, 3 dan 4 adalah Rp 29.125.080, Rp 36.117.000, dan Rp 26.212.220. Kata kunci : binary integer programming, CV Dua Prima Lestari, software LINGO 11.0