This paper reports the use of two methods, simulated annealing (SA) and threshold accepting (TA), to determine a set of optimal terms (the structure) of the vapor pressure correlation for the R134a. The SA algorithm with the Lundy and Mees annealing schedule, and the TA algorithm with the Aarts and VanLaarhoven schedule gave the best performance, based on minimal computational time for a given performance. SA and TA appear to be versatile, powerful and computationally simple methods for determining the structure of empirical correlations of thermophysical property data.