We address the problem of high-dose-rate brachytherapy treatment planning for prostate cancer. The problem involves determining a treatment plan consisting of the so-called dwell times that a radiation source resides at different positions inside the patient such that the prostate volume and the seminal vesicles are covered by the prescribed radiation dose level as much as possible while the organs at risk, e.g., bladder, rectum, and urethra, are irradiated as little as possible. The problem is highly constrained, following clinical requirements for radiation dose distribution while the planning process for treatment planners to design a clinically-acceptable treatment plan is strictly time-limited. In this paper, we propose that the problem can be formulated as a bi-objective optimization problem that intuitively describes trade-offs between target volumes to be radiated and organs to be spared. We solve this problem with the recently-introduced Multi-Objective Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (MO-RV-GOMEA), which is a promising MOEA that is able to effectively exploit dependencies between problem variables to tackle complicated problems in the continuous domain. MO-RV-GOMEA also has the capability to perform partial evaluations if problem structures allow local variations in existing solutions to be efficiently computed, substantially accelerating the overall optimization performance. Experiments on real medical data and comparison with state-of-the-art MOEAs confirm our claims.