Distribusi merupakan sebuah aktivitas yang harus dilakukan oleh semua perusahaan untuk mengirimkan produknya kepada konsumen. Produk harus dikirimkan kepada konsumen dengan kondisi yang baik, tepat waktu dan dengan biaya pengiriman yang minimum. Pertamina TBBM Boyolali merupakan salah satu distribution center (DC) bahan bakar minyak pada area sebagian Jawa Tengah dan Jawa Timur. Konsumen dari TBBM Boyolali merupakann SPBU yang jumlahnya ada sekitar 224 titik. TBBM Boyolali dalam mendistribusikan produknya mempertimbangkan beberapa hal, yaitu multi-products dan multi-compartments yang mana jenis produk yang dikirimkan dan kendaraan yang dipakai untuk mengirim produk memiliki kompartemen lebih dari satu, time window yang mana adanya mekanisme jam buka dan jam tutup konsumen (SPBU) sesuai dengan pelanggan yang lebih dari satu dalam periode perencanaan, dan mempertimbangkan waktu loading- unloading. Permasalahan yang sering dialami oleh TBBM Boyolali dalam mendistribusikan produknya adalah tidak optimalnya rute yang dipilih sehingga dapat menghasilkan pemborosan biaya pengiriman dan waktu kirim yang lebih lama. Untuk mengurangi permasalahan yang dialami, maka diperlukan penentuan rute distribusi yang sering dikenal sebagai Petrol Station Replenishment Problem (PSRP). PSRP dapat menyelesaikan permasalahan spesifik untuk distribusi bahan bakar minyak dengan mempertimbangkan kompartment kendaraan, jenis produk dan batas waktu pengiriman yang berbeda untuk setiap konsumen. Hasil penelitian diwujudkan dalam model matematis dengan menggunakan Ilog CPLEX dengan metode exact dan algoritma branch and cut. Model yang dibangun mampu menghasilkan rute pengiriman bbm dengan biaya paling optimal berdasarkan dengan permintaan dalam waktu satu hari. Sehingga dari model dapat menghasilkan penghematan biaya sewa kendaraan sebesar 56% dengan total biaya pengiriman sebesar Rp 5.397.897.440 dalam waktu satu bulan.

Kata Kunci: Petrol Station Replenishment Problem (PSRP), multi-compartment, multi- product, time windows.<!--[if gte mso 9]><xml> Normal 0 false false false EN-US X-NONE X-NONE </xml><![endif]--><!--[if gte mso 9]><xml> </xml><![endif]--><!--[if gte mso 10]> <style> /* Style Definitions */ table.MsoNormalTable {mso-style-name:"Table Normal"; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-qformat:yes; mso-style-parent:""; mso-padding-alt:0mm 5.4pt 0mm 5.4pt; mso-para-margin:0mm; mso-para-margin-bottom:.0001pt; mso-pagination:none; text-autospace:none; font-size:11.0pt; font-family:"Calibri","sans-serif"; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:"Times New Roman"; mso-fareast-theme-font:minor-fareast; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:"Times New Roman"; mso-bidi-theme-font:minor-bidi;} </style> <![endif]-->