Penelitian ini membahas mengenai kasus distribusi Premium, Kerosin dan Solar di perusahaan Migas yang mengalami masalah deviasi jumlah pendistribusian produk di beberapa depot utama (pelabuhan bongkar) yang disebabkan oleh keterlambatan kapal, keterbatasan draft pelabuhan dan fluktuasi permintaan. Pengoptimalan rute dan jadwal pendistribusian bahan bakar ini menggunakan Algoritma Tabu Search dengan mengintegrasikan 2 kapal yang berbeda jenis Medium Range (MR) dan General Purpose (GP), konsumsi harian di tiap pelabuhan bongkar berbeda akan tiap produk, stok pelabuhan muat tidak terbatas, keterbatasan draft pelabuhan sehingga menghasilkan sebuah solusi yang menjaga keberadaan persediaan pengaman dengan biaya transportasi yang minimum. Rute usulan dari penelitian ini dirancang dengan penjadwalan 30 hari menggunakan perangkat lunak Matlab versi 7 (R2000b). Hasil yang diperoleh memberikan performansi yang baik karena rute dan jadwal yang dihasilkan dapat menjaga keberadaan persediaan pengaman dengan total biaya sebesar Rp. 6,265,337,216 dengan pertimbangan Kapal MR digunakan dedicated untuk pelabuhan bongkar TTM.

---

This research discusses about case of fuel distribution (Premium, Kerosene and Solar) in an oil company which involved in quantity of product distribution problem in some main depot (unloading port) which are caused by ship lateness, limitation of draft and demand fluctuation. It is solved by using Tabu Search Algorithm which have model that integrate two different ships consist of Medium Range (MR) and General Purpose (GP), different daily consumption product of every unloading port, unlimited inventory loading port, and limited port draft for give a solution to maintain safety stock with low transportation cost. This routes were designed by planning horizon 30 days using Matlab 7th version (R2000b). The result prove that safety stock in each unloading port can be maintained with total cost is Rp. 6,265,337,216. MR (Medium Range) ship is dedicated to fulfill TTM port demand.