In this paper, a numerical method for solving bounded continuous-time nonlinear optimal control problems (NOCPs) that based on variable neigh-borhood descent (VND) algorithm is proposed. First, the genetic algorithm (GA) is combined with an improved VND that uses efficient neighborhood interchange. Then, to improve the efficiency of the algorithm for practical and large-scale problems, the parallel processing approach is implemented for discrete form of NOCP. It performs the required complex computations in parallel. The resulting parallel algorithm is applied to a benchmark of nine practical problems such as Van Der Pol problem and chemical reactor problem. For large-scale problems, the parallel hybrid variable neighbor-hood descent algorithm (PHVND) is capable of obtaining optimal control values effectively. Our experimentation shows that PHVND outperforms the best-known heuristics in terms of both solution quality and computa-tional efficiency. In addition, computational results indicate that PHVND produces superior results compared to sequential quadratic programming or GA.