Previous studies have shown that machining error in 5-axis flank milling can be systematically reduced by optimization of tool path planning. However, the solution quality of the optimization methods adopted by those studies was not satisfactory, due to the constraint that the cutter must contact the boundary curves of the ruled surface to be machined. This work proposes an improved tool path planning method based on Particle Swarm Optimization (PSO) algorithms without this constraint. The method enlarges the feasible region in the optimization by allowing cutter location to deviate the boundary curves along the normal, tangent, and bi-normal directions. Design of experiment techniques are applied to determine better parameter setting in the PSO. A new objective function is formulated as the weighted sum of the errors induced by overcut and undercut. We can choose to minimize the total machining error, the overcut, or the undercut by properly adjusting the weight value. Compared to previous methods, the improved path planning method produces smaller machining error and offers better planning flexibility.