: Offshore oil and gas installations to carry out their production and avtivities need a reliable and effective logistical support network. The needs of this facilities are provided by one or a few onshore depot and support services done by a fleet of supply vessels. The supply vessel planning problem consists of determining the optimal fleet composition of offshore supply vessels and the weekly routes and schedules for these vessels to service a given number of offshore installations from one or more onshore depot. In this study, the objective is to minimize the total costs while at the same time, maintaining a reliable supply service. The costs that are to be minimized are primarily the time charter costs for the supply vessels, then the sailing costs of the voyages. The aim of this thesis is planning offshore supply vessels consist of determining routs and time of voyages and assigning vessels to each voyage during planning horizon using a mixed integer programming model. The concept of consistency as a managerial constraints was added to the problem using an objective function and some constraints. Goal programming is used to consider two divergent objectives, simultaneously. Also, robust optimization approach was used to overcome the complexity of uncertainty due to impact of weather conditions. Since the proposed model is a NP-Hard problem, a variable neighborhood search algorithm was used to solve large-scale problems and to verify the results of this problems, compared by a variable neighborhood descent algorithm. Comparing the results of proposed VNS algorithm with GAMS software for small and medium-sized problems and with VND algorithm for large-sized problems was shown that VNS algorithm has a good performance in a short operating time.