| dc.description.abstract | In this thesis we examine how Logistics in Petrobras may improve their decision making with regard to routing and scheduling of platform supply vessels (PSV). Petrobras are aiming to double their current production level by 2020. The expansion requires an increase in capacity on all levels of the organization. This includes Logistics, which will have to cope with the future expansion in addition to facing some underlying issues that already exist in their supply chain.The logistics base for Campos basin is located in the city Macaé. Currently the port in Macaé is operating at maximum capacity and struggles to cope with increasing demand inquiries. We argue that an operational planning tool for routing and scheduling may contribute to more efficient order handling.The thesis introduces the platform supply vessel routing and scheduling problem with refueling tankers (PSVRSP-RT), which consists of identifying optimal routes and schedules for the daily departures of PSVs servicing a set of offshore installations. The problem considered is formulated as a deterministic cost minimization problem and solved as a mixed integer linear programming problem (MILP). For a given planning horizon the model intends to properly allocate a set of pickup and delivery orders to a fleet of PSVs that has one available departure per day. Among other tasks, the model solves the optimal choice of vessel type for each departure, delivery sequence of orders and optimal deployment locations for refueling tankers. The objective function minimizes fixed and variable sailing costs, in addition to minimizing the penalty costs of delay and express delivery of orders.Friedberg and Uglane (2012b) provided an arc-flow formulation of the original PSVRSP. In the Master's thesis the same model is expanded by including the aspect of refueling tankers. According to the reviewed literature, there seems to be a clear trend towards the use of column generation to solve maritime ship routing problems. The arc-flow model is therefore decomposed using the Dantzig-Wolfe decomposition (DWD) approach, which results in a path-flow model. In the decomposed model, a subproblem (SP) is solved for each combination of departures and vessels, whereas the restricted master problem (RMP) incorporates the common constraints and the pool of columns generated in the subproblems. Column generation is used to solve the linear programming relaxation of the MILP problem. Furthermore, Branch and Price (B&P) is implemented to close the MILP gap and provide an optimal integer solution. A computational study tests a set of different approaches to column generation and other aspects of the B&P tree to speed up the solution process for the path-flow model. Testing reveals that the break-first-then-optimum (BFO) procedure is the most promising column generation approach. After implementing a satisfactory B&P scheme, the path-flow model is compared with the arc-flow model for several problem instances. Results indicate that the arc-flow model performs better for small problem instances, but as the size of the problems increases the path-flow model becomes superior. An advantage of column generation is that the model is able to provide decent bounds within a reasonable time frame, despite experiencing a tail-off effect in the B&P tree. The model is applied to a base case from Campos basin to evaluate the problem from an economical perspective. In terms of economical value, knowing how the model is affected by variations in input parameters adds value on a strategic level. With regard to the PSV fleet size and mix it is evident that a balanced composition is important in terms of cost minimization. The results reveal that a scenario involving excess capacity, i.e. a majority of PSV 3000 vessels, causes a significant increase in direct costs. In contrast, the instances involving a capacity deficit reveal a potential increase in indirect costs related to delay and express delivery costs. When we alter parameters for the offshore refueling operations, the results present only small deviations in total costs. In fact, the results indicate that the buoys for anchoring refueling tankers are properly positioned. Changing the deployment locations of refueling tankers to non-optimal buoys make little difference in terms of direct costs. With regard to the order prioritization system, the analysis provides an important intuition about the sensitivity of the delay penalty. The direct costs, which consist of sailing distance and fixed leasing rates for PSVs, are not significantly influenced by large alterations in delay penalty.Logistics face some issues that must be addressed before the model may be implemented in practice. Internal uncertainty factors arise due to lack of transparency, capacity restrictions and stakeholders? mistrust in logistics operations. To increase trust in the system by more reliability in order handling, Logistics have introduced fixed routes and schedules for PSVs. In relation to the Petrobras 2020 vision and the development in Santos basin, the future state of Logistics may become more adaptable to a dynamic planning environment. As Santos basin is under development, drilling rigs and other non-stationary installations will be the main source for demand. Fixed routes would therefore have to be reset frequently. Furthermore, as distances from the depot increase, refueling offshore might in fact become a necessity to increase the range of the PSVs. | nb_NO |
