A dry bulk shipping company is operating its fleet on a number of trade routes and is committed to sail a given number of voyages on these trade routes during the planning period, while trying to derive additional revenue from chartering out ships on short term contracts if possible. The shipping company has agreed with the cargo owners that the voyages of a trade should be fairly evenly spread. This leads to a maritime fleet deployment problem with voyage separation requirements. Two formulations for this problem are presented, one arc flow formulation and one path flow formulation. The voyage separation requirements are modeled either as hard constraints or as soft constraints. Computational results show that the path flow model can be solved for problems of realistic size, and that including voyage separation requirements gives solutions with much better spread of voyages. Solving a real life problem and comparing the solution with a plan made manually by experienced fleet schedulers shows that using the proposed optimization method can both generate increased profit and save the schedulers a lot of work.