Research On Offshore Platform Supply Vessel Planning Based On Column Generation Algorithm

With limited storage space for offshore oil and gas production installations,offshore platform supply vessels provide periodic supplies to each installation from the onshore supply base to ensure continuity of production activities.Generally,oil and gas producers operating offshore need to charter vessels from other ship brokers and shipowners.The total operating cost of the supply vessel includes chartering cost and sailing cost.Chartering cost is the main factor affecting the total operating cost of the supply vessel.Therefore,in order to reduce the total operating cost of logistics distribution for oil and gas producers,it is necessary to formulate a reasonable planning plan for supply vessels.Supply vessel planning issues include determining the optimal fleet composition,periodic routes to service offshore oil and gas production installations,and scheduling.In order to formulate a supply vessel planning scheme in line with the actual situation,a new integer supply vessel planning model is designed in this thesis.On the basis of voyage model,restrictions such as hard time window,uniform departure of ships,non-overlapping voyage and voyage cycle are added to make the model more realistic.In order to solve the large-scale supply vessel planning problem accurately,the Column Generation(CG)Algorithm is adopted in this thesis,which breaks the limitation that heuristic algorithm can’t ensure the quality of solution and can only find approximately satisfactory solution.In the framework of column generation algorithm,the integer supply vessel planning model is decomposed into a path-based master problem and a shortest-path subproblem with resource constraints by using D-W decomposition principle.In order to improve the solving efficiency of the subproblem,this thesis designs a new Modified Label Correcting Algorithm(MLC),and a variety of pruning strategies are used to reduce the computational scale of subproblem.CG+MLC algorithm is used to iterate the qualified variables between the master problem and the subproblem until the global optimal exact solution is obtained.Based on all the pre-generated voyages obtained,this thesis designs a generation scheme of shipping schedule,which makes the planning more consistent with the reality.To verify the feasibility and effectiveness of the model and algorithm,under different scales of offshore installations,CG+MLC algorithm,NS algorithm and direct use of CPLEX solution are compared in efficiency.The traditional point-to-point distribution scheme and multi-point distribution scheme are compared by taking the distribution status of offshore oil and gas production installations in Bohai Sea of China as an example.It is found that the multipoint distribution scheme using CG+MLC algorithm can generate the best fleet combination(quantity and type),periodic sailing routes and shipping schedule with less storage space,shorter time and lower cost.Through the cost sensitivity analysis,it can be seen that the chartering cost has always been a major component of the total operating cost of the supply vessel,and with the continuous increase of the scale of offshore installations,the proportion of sailing cost is also increasing.The results show that the column generation algorithm has obvious advantages in the accuracy and speed of solving the large-scale offshore platform supply vessel planning problem.