Vertical Total Electron Content (vTEC) is an ionospheric characteristic used to derive the signal delay imposed by the ionosphere on near-vertical trans-ionospheric links. The major aim of this paper is to design a prediction model based on the main factors that influence the variability of this parameter on a diurnal, seasonal and long-term time-scale. The model should be accurate and general (comprehensive) enough for efficiently approximating the high variations of vTEC. However, good approximation and generalization are conflicting objectives. For this reason a Genetic Programming (GP) with Multi-objective Evolutionary Algorithm based on Decomposition characteristics (GP-MOEA/D) is designed and proposed for modeling vTEC over Cyprus. Experimental results show that the Multi-Objective GP-model, considering real vTEC measurements obtained over a period of 11 years, has produced a good approximation of the modeled parameter and can be implemented as a local model to account for the ionospheric imposed error in positioning. Particulary, the GP-MOEA/D approach performs better than a Single Objective Optimization GP, a GP with Non-dominated Sorting Genetic Algorithm-II (NSGA-II) characteristics and the previously proposed Neural Network-based approach in most cases.