This paper discusses a multi-heuristics based Genetic Algorithm (GA) to solve maritime inventory routing problems (mIRP). The problem is to transport multiple oil products from a production facility to some consumption ports by using several heterogeneous ships with undedicated compartments. The objective of the problem is to find a minimum cost solution, while satisfying a number of technical and physical constraints, within a given planning horizon. The strategies to assign a ship are transformed to a set of heuristic combinations represented by a chromosome. At every iteration a number of chromosomes are evaluated and evolved within a GA framework. The approach has been applied on several test cases. The multi-heuristic results show that the best optimum values of the case problems are not different from the ones from a MILP method solved using Lingo, but they do so with a significant decrease in computation time.