Optimization of a Supply Vessel Scheduling and Fuel Type Allocation Problem for a Hellenic Oil Company

This master thesis is concerned with solving a combined fuel supply vessel scheduling and fuel type allocation problem. The problem is provided by a Hellenic oil company. The company has a small, fixed fleet of fuel supply vessels, which it uses to supply customer ships anchored in the broader area of Piraeus Port outside Athens. The supply vessels are loading multiple types of fuels at refineries before carrying the fuel out to the customer ships. The customers are either mandatory contract ships which must be served, or optional spot ships which may be served if the company has available capacity. The company must decide whether to accept a spot ship or not within only minutes after the inquiry. Based on the contract customers and the accepted spot customers, the company must generate schedules which specify which customers each supply vessel should supply, when this should be done and in what sequence. The planning horizon is three days. The customers specify a time for when they want to be served, something which must be accounted for in the generated schedules. A given customer ship can place orders of various fuel types to be delivered within the same time interval. All orders placed by a customer ship do not have to be operated by the same vessel, meaning customer splitting is possible. The fuels demanded must be allocated to compartments within the supply vessels, and fuels of different types cannot be loaded to the same compartment. Conversely, different orders of the same fuel type may be blended within a compartment, and large orders may be split between several compartments. The main objective of this thesis is to develop a detailed optimization model for the problem in order to really getting to know the problem and to study its complexity. This model is intended to serve as a starting point for additional research. Further, we want to utilize the model or variants of this to support the company in its decision making. The model is developed as a mixed-integer programming (MIP) problem and implemented by use of commercial optimization software. The test cases are generated based on real life information from the company. Due to the complexity of the problem, there is made considerable effort in reducing the numbers of variables and constraints in the implementation of the mathematical model. Valid inequalities and model simplifications are added to the basic model with the intention of further improving the model?s performance. The best solutions were obtained by a model which included both tested model simplifications; stowage elimination and no customer splitting. To get feasible solutions with respect to the real allocation problem, the vessels? total capacities had to be set as low as 50 % of the actual vessel capacities. The model with this capacity fraction performed well on test cases of smaller sizes, but in larger test cases this low capacity limits the possibility of obtaining solutions where all demand is met.The problem is very complex and consequently not easy to solve, but we have seen that simplifying complicating model aspects reduces the model?s complexity and makes the model better able to support the company in its decision making. Still, with regards to support the decision making, there is a need for further research