The automotive industry is shifting from hardware-centric to software-centric with the emergence of various intelligent features powered by software. This poses a new challenge for software testers to ensure software reliability by designing test plans that satisfy the test objectives while abiding by the constraints like scope, time, as well as various automotive safety standards. This paper proposed an automatic test plan generation framework built on the evolutionary algorithm. A novel encoding mechanism is proposed to represent the multi-dimensional test plan, while a belief model is proposed to reveal the underlying correlations between the relevant test attributes. Experiments conducted on an actual automotive software in production environment developed by our industry partner show that our method can achieve around 50% improvements in finding defects and covering high-priority test cases as compared to typical evolutionary algorithms while abiding by multiple constraints such as the total run time and custom objectives set by users.