In a recent study, researchers investigated a class of vessel routing problem and a benchmark suite based on real shipping segments considering incompatibility constraints. These constraints same as pickups and deliveries, cargoes selections, travel times and costs and time windows state considerable challenges for researchers. Considering the literature review on the subject and the frequent resolving of this problem with Adaptive Large Neighborhood Search (ALNS), we proposed a Greedy Randomized Adaptive Search Procedure (GRASP) to solve this problem. The algorithm was tested on 240 available benchmarks. As shown in our experimental results the GRASP outperforms all previous heuristics and generates near-optimal solutions within minutes. These results are noteworthy since we have succeeded to improved 35 large instances of this set.