In maritime inventory routing, a fleet of vessels is employed to transport products that are produced and consumed in different ports with limited storage capacity. The tight coupling between inventory management and routing, and diverse constraints make this a challenging problem. We generate a routing plan using an iterative construction algorithm, starting from an empty plan. In each iteration, a constraint violation, e.g. a stockout, is identified. We generate a number of different journeys that can fix the violation and add the best one. This continues until the plan is feasible or no remaining violation can be fixed. The construction algorithm is reused in the optimization phase, where each iteration consists of removing and then rebuilding a part of the plan. We present results on real world cases.