EeP operations in the Santos Basin have always been left in second plan when compared to the Campos Basin, the cradle of the gigantic oil discoveries of the last 40 years. However, with the discovery of the pre-salt, more present in the Santos Basin, this hegemony of the Campos Basin is gradually diminishing, with the production of the pre-salt having surpassed for the first time the one of the postsalt in June of 2017. With this, it is essential to improve the operation to meet this new demand. Along with this new discovery, the severe crisis that the oil industry has experienced since 2014 with the sharp fall in the price of the barrel, more intensified in Brazil due to the increase of the dollar, brought a new focus in reducing the cost of extraction, including the reduction of logistics costs. At Petrobras, most of the oil production comes from deep water and the maritime units need supplies in considerable volume and on time to carry out their operations. The final link of the logistics chain to serve this maritime units are vessels and they represent about 70 percent of logistics costs. In this study, the different maritime service policies for deck cargo transport used in recent years, both in the Campos Basin and Santos Basin, were analyzed empirically and some improvement points were found. The feasibility of reducing the fleet was identified and a methodology to accomplish this reduction was proposed. The methodology is based on a new form of clusters formation, reducing the total vessels navigation time, and a new berth scheduling, in such a way that the same vessel can perform more services during the week, thus generating less need of fleet. The complete new methodology was implemented in January 2018, initially generating a 20 percent decrease in the cargo transport fleet in the Santos Basin.