as the population in Indonesia grows, the need of energy in forms of fuel, electricity, asphalt, or wax which were distilled through the refinery process of crude oil, has been consistently increasing for the past several years. In addition, with the continuous entrance of foreign companies penetrating the Indonesia gas market, increases the stringent of the competition. In order to be able to stay competitive, PT. PERTAMINA, an Indonesian state-owned oil and natural gas corporation, is required to be able to support such continuously increasing needs. The Shipping Division in the firm is expected to be able to deliver crude oil from the load port crude to refinery unit by using available owned and chartered vessels. In the current crude oil distribution system, every day the company assigned total of 49 vessels where three of them are owned and the remaining are chartered. Due to the archipelagic nature of Indonesia in addition to the variety of the sea and strait depths, some refinery areas are remote and reachable on by selected types of vessels. Integer programming model combined with CDS algorithm for m-machine are used to provide better crude distribution system for the company. As a result, the company can save up to 51% on the number of vessels needed to be used to transport the crude oil.

Keywords—crude oil, integer programming, CDS algorithm, load port crude, refinery unit, archipelago