In this paper, we introduce a novel variant of the Vehicle Routing Problem (VRP), the Rechargeable Rover Routing Problem (RRRP), which addresses the routing of energy-constrained autonomous electric rovers for Martian missions. We formulate a graph- based representation of the problem and propose an initial formulation as a mixed-integer non-linear program (MINLP). To enhance computational efficiency, we demonstrate how the model can be linearized. The resulting mixed integer linear model is evaluated on small-scale test cases, and its computational complexity is analyzed for larger problems with up to 30 Points of Interest (PoIs). Our experiments show that the problem can be solved to optimality for problem sizes anticipated in upcoming Mars expeditions. However, for future missions involving swarms of rovers, the development of more efficient heuristic or approximation algorithms will be necessary.