Background Applicator displacement during brachytherapy treatment for cervical cancer leads to a drastic change in dose distribution. Hence, applicator displacement uncertainty is of significant relevance within the distribution of dose prescription. To minimize applicator displacement from patient movement during cervical cancer brachytherapy treatment, a multi-objective genetic algorithm was combined with a median absolute deviation (MAD) constrained robust optimization concept. Materials and methods To evaluate the feasibility of the robust optimization algorithm on applicator displacements, the clinically applied treatment plans of six tandem and ring (T&R) applicator cases for cervical cancer were included. All patients underwent magnetic resonance imaging (MRI) after the placement of the T&R applicator. The method considered multiple random scenarios reflecting the uncertainties in the dose delivered. For simplicity, the uncertainties in this proof-of-concept study were limited to potential applicator displacements. This problem is optimized by MAD-constrained robust optimization using a patient-specific multi-objective genetic algorithm. The proposed approach is then compared against the nominal (manual) plan strategies. Results All generated plans fulfilled EMBRACE protocol guidelines for all targets and organs at risk (OAR). MAD-constrained robust optimization provided not only excellent target coverage but also minimized doses to OAR. The nominal and robust plan equivalent dose in 2 Gy fractions (EQD2) of D98 for high-risk clinical target volume (HR-CTV) and rectum were 88.59, 55.29, and 84.84, 54.09, respectively. Furthermore, each standard deviation of D98 for HR-CTV and rectum reduced from ±1.0177 to ±0.9085 and ±0.4927 to ±0.4052, respectively. Conclusions Definitive dwell times and positions by the use of robust planned external beam radiation therapy plus brachytherapy (EBRT-BT) boost for cervical cancer were well tolerated. Using this robust strategy, the generated plans showed an increase in target coverage and minimized applicator displacement impact uncertainty on dose delivery.