: Many oil and gas producers operate offshore installations that need regular supplies of commodities from land. Specialized offshore supply vessels are used to bring supplies from onshore supply depots out to offshore installations. To achieve a cost efficient supply service, good planning of supply vessels is required. The supply vessel planning problem is a maritime traortation problem consisting of determining the optimal fleet composition of offshore supply vessels and their corresponding weekly voyages and schedules. Iran is recognized as one of largest producers of oil and gas in the world possessing a large number of installation set in Persian Gulf and The Sea of Oman which undertake exploration, drilling and production operations. The optimal fleet composition of offshore supply vessels and their corresponding weekly voyages and schedules can result in considerable cost saving for upstream oil and gas logistics. In this thesis in order to reach an optimal supply vessel planning and propose an efficient model which is well adapted to the real life situations, some additional properties such as backhaul and pickup and delivery between installation set are considered. An exact method consisting of two phases is also proposed. The exact method is able to solve medium sized instances. In order to solve large sized problems a meta heuristic algorithm based on taboo search method is proposed. In order to improve the proposed meta heuristic algorithm, it was combined with an exact method; the results show the high efficiency of this approach. The proposed model was tested on instances based on a real supply vessel planning problem faced by Iranian Offshore Oil Company (IOOC) and the results were analyzed.