The Multi-objective Supply Vessel Planning Problem - A Hybrid Genetic Search Approach
MetadataVis full innførsel
The supply vessel planning problem (SVPP) is a problem faced by Statoil, the largest operator on the Norwegian continental shelf. Offshore installations need supplies from an onshore supply depot in order to operate, and the supplies are transported by platform supply vessels (PSVs). The objective of the SVPP is to minimize the costs related to the chartering and operation of PSVs, while maintaining a reliable supply service. In addition to minimal costs, the decision makers at Statoil have requested solutions that are persistent and robust. Persistent solutions are solutions that have few changes from the previous solution, while robust solutions are solutions that are capable of handling unforeseen events, such as delays. The SVPP with multiple objectives is referred to as the multi-objective supply vessel planning problem (MSVPP), and this thesis considers the MSVPP with cost, persistence and robustness as objectives. A mathematical formulation for the SVPP is presented, as well as formulations of how to measure persistence and robustness. Exact methods are unable to solve real-size instances of the SVPP and the MSVPP due to the complexity of the problem. A hybrid genetic search heuristic with adaptive diversity control (HGSADC) is therefore developed for the SVPP. The heuristic is extended to solve the MSVPP, generating Pareto fronts that illustrate the trade-off between cost, persistence and robustness. The heuristic is tested on problem instances provided by Statoil. The results from solving the instances with cost as the only objective show that the heuristic is able to find the optimal solution to the SVPP for all problem instances where exact methods can prove optimality, and that it seems to find high-quality solutions for real-size problem instances. The heuristic has stable performance for all problem instances, and the running time increases linearly with the size of the problem instance. For the MSVPP, three different sets of objectives were used: cost and persistence, cost and robustness and finally cost, persistence and robustness. The results show that the heuristic finds Pareto fronts that are identical or close to the optimal fronts for problem instances that can be solved by exact methods. The cost of all the solutions found for the real-size problem instances are less than 1% higher than the cost of the solutions found by the single-objective heuristic, indicating that adding additional objectives does not impair the quality of solutions much. The heuristic has stable performance for the MSVPP, and in the tests, the running time increases linearly with the number of objectives. Pareto fronts generated for real-size problem instances show that the persistence and robustness of the solutions can be improved to optimal or near-optimal values for a cost increase of less than 1% from the lowest known cost. The Pareto fronts also illustrate the trade-off between cost and the other objectives, improving the decision makers insights of how the objectives are related. Decision support tools that implement the solution methods presented in this thesis are therefore expected to improve the supply service by reducing costs and improving reliability.