A number of parallel gradient-free local optimization methods are investigated in application to problems of voyage planning for maritime ships. Two optimization algorithms are investigated, a parallel version of the Nelder-Mead Simplex method and the Subplex method with Nelder-Mead Simplex as its inner solver. Additionally, two new formulations of the optimization problem are suggested which together with an improved implementation of the objective function increases the overall performance of the model. Numerical results show the efficiency of these methods in comparison with the earlier introduced Grid search method and solvers from an open-source optimization library.