We propose and demonstrate two methodologies for weight minimization of Type 4 (plastic lined, fiber wrapped) compressed hydrogen pressure vessels: genetic algorithms and simulated annealing. We consider 70 MPa vessels with a safety factor of 2.25, and analyze the vessels with classical laminate theory. We propose an objective function based on Tsai-Wu criterion, composite thickness, a safety factor, and a penalization factor. The optimum results are analyzed and compared by a high resolution finite element model. Computer simulations show that the proposed methodology produces more efficient designs by reducing the weight by up to 9.8% and 11.2% when compared to previously published vessel optimization research. (C) 2017 Hydrogen Energy Publications LLC. Published by Elsevier Ltd. All rights reserved.