Undersampled trajectories were optimized for parallel imaging with explicit consideration of the RF coil sensitivities in order to complement the RF coil elements. A second-order approximation of pixel variance was used as a metric to evaluate encoding trajectories and also serves as the cost function in the optimization problem, solved using Simulated Annealing. The metric was implemented on a Graphical Processing Unit (GPU) to accelerate computations. The developed method was evaluated on two test cases with Cartesian and radial sampling for isotropic and anisotropic fields-of-view. Resulting optimized trajectories led to improved image quality, more uniform SNR and reduced g-factors.