Educators increasingly rely on e-learning to supplement traditional classroom learning. Personalized learning paths (PLPs) have emerged as one type of supplement. A PLP is a sequence of learning materials (LMs) and activities that are selected according to LM fitness for the learner’s preferences and ordered according to prerequisite relationships. A problem that consistently emerges in PLP research is the use of pseudo-scientific learning theories to inform PLP design. This research presents LM and PLP rubrics, derived from the Cognitive Theory of Multimedia Learning (an experimentally validated learning theory) as a foundation that informs the PLP design process. The LM and PLP rubrics are decomposed into two problem domains, which include selecting and sequencing LMs to create PLPs. These problem domains are supported by proofs of NP-completeness. Next, real-world data are presented and used to derive instances of these multi-objective problems, which are then solved using the Non-Dominated Sorting Genetic Algorithm, a simulated annealing algorithm, and a Random Hill Climber algorithm. These metaheuristics produce satisfactory results, with the rubric scores of 12 student profiles ranging from $3.19$ to $3.54$ on a four-point scale. The rubrics, data, and algorithms used in this paper are publicly available.