A robust locating scheme design was provided under the circumstance that only parts of A surface or initial structure are known in the initial design phase of a new vehicle model. An optimization design model of locating scheme was established based on the deterministic locating for rigid parts and robust design principles. The optimal locators are searched by using genetic algorithms in feasible region; the sensitivity coefficient which provides an indicator of how sensitive the assembly quality are to variance of locator is extracted, and finally tolerance optimization is achieved while costs are reduced. An example of locating design of a new vehicle model’s head-lamp was demonstrated, which proves that the method is effective in the initial design phase.