In this paper, a two-phase algorithm, namely IVNS, is proposed for solvingnonlinear optimal control problems. In each phase of the algorithm, we use avariable neighborhood search (VNS), which performs a uniform distributionin the shaking step and the successive quadratic programming, as the localsearch step. In the rst phase, VNS starts with a completely random initialsolution of control input values. To increase the accuracy of the solutionobtained from the phase 1, some new time nodes are added and the valuesof the new control inputs are estimated by spline interpolation. Next, inthe second phase, VNS restarts by the solution constructed by the phase1. The proposed algorithm is implemented on more than 20 well-knownbenchmarks and real world problems, then the results are compared withsome recently proposed algorithms. The numerical results show that IVNScan nd the best solution on 84% of test problems. Also, to compare theIVNS with a common VNS (when the number of time nodes is same in bothphases), a computational study is done. This study shows that IVNS needsless computational time with respect to common VNS, when the quality ofsolutions are not di erent signi cantly.