This paper addresses combinatorial optimization problems under uncertain and correlated data where the mean-covariance information of the random data is assumed to be known. Such a problem can be modeled as an integer non-linear program. We reformulate the problem using spectral decomposition and apply principal component analysis (PCA) to approximate the reformulation. The quality of the resulting approximate solutions is assessed by determining a worst-case optimality gap. We apply our results to the capacitated vehicle routing problem with uncertain and statistically correlated travel times (CVRP-SCT). The CVRP-SCT seeks vehicle routes whose observed travel times are not excessively dispersed with respect to their expected value. To solve the approximate models to optimality, we develop exact branch-price-and-cut algorithms. Our experimental results on a rich collection of instances show that good quality feasible solutions can be found using the proposed approximate models. In particular, solving the PCA-based model, even with a very small number of components, provides solutions that are optimal for all instances with known optimal values in less computational times than an exact method.