Phase Change Materials (PCMs) are gaining importance in energy storage applications. However, many PCMs are poor thermal conductors and thus can benefit from the optimal use of appropriate fins. This work introduces a PCM-fin structure optimization framework. Typically, the non-linear solidification process increases the complexity associated with solving the mathematical equations for the PCM-fin structure optimization problem, making it computationally expensive. In this paper a modeling approach called Layered Thermal Resistance (LTR) model is extended and developed in 2D cylindrical geometry in order to enable efficient PCM-fin structure optimization. The finned LTR model represents the nonlinear transient solidification process by analytic equations. This significantly reduces the computational cost associated with optimization. A finned heat pipe structure modeled by the finned LTR approach is optimized based on minimizing cost while meeting operational requirements. The optimal results imply that thinner fins result in lower system cost and that there is a thickness limit for the fins to be economically welded on a heat pipe. The finned LTR model also gives the optimal cost of material usage for a large scale latent thermal energy storage system in terms of dollars per kilowatt and it was found that the system cost is slightly lower by using carbon-steel as the construction material for the heat pipes and fins than by using Al 6061.