A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars
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 graphbased representation of the problem and propose an i...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2025-09-01
|
| Series: | Foundations of Computing and Decision Sciences |
| Subjects: | |
| Online Access: | https://doi.org/10.2478/fcds-2025-0012 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849225013039726592 |
|---|---|
| author | Burzyński Wojciech Kaleta Mariusz |
| author_facet | Burzyński Wojciech Kaleta Mariusz |
| author_sort | Burzyński Wojciech |
| collection | DOAJ |
| description | 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 graphbased 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. |
| format | Article |
| id | doaj-art-3348c5a5c12d4048b273b377b01d0576 |
| institution | Kabale University |
| issn | 2300-3405 |
| language | English |
| publishDate | 2025-09-01 |
| publisher | Sciendo |
| record_format | Article |
| series | Foundations of Computing and Decision Sciences |
| spelling | doaj-art-3348c5a5c12d4048b273b377b01d05762025-08-25T06:11:49ZengSciendoFoundations of Computing and Decision Sciences2300-34052025-09-0150332534610.2478/fcds-2025-0012A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on MarsBurzyński Wojciech0Kaleta Mariusz11Warsaw University of Technology, Doctoral School, Pl. Politechniki 1, 00-661Warsaw, Poland2Warsaw University of Technology, Faculty of Electronics and Information Technology, Nowowiejska 15/19, 00-665Warsaw, PolandIn 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 graphbased 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.https://doi.org/10.2478/fcds-2025-0012task schedulingelectric vrpvrp with profitsrover routing problemmars explorationmilp |
| spellingShingle | Burzyński Wojciech Kaleta Mariusz A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars Foundations of Computing and Decision Sciences task scheduling electric vrp vrp with profits rover routing problem mars exploration milp |
| title | A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars |
| title_full | A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars |
| title_fullStr | A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars |
| title_full_unstemmed | A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars |
| title_short | A Mixed Integer Programming Approach to the Rechargeable Rover Routing Problem on Mars |
| title_sort | mixed integer programming approach to the rechargeable rover routing problem on mars |
| topic | task scheduling electric vrp vrp with profits rover routing problem mars exploration milp |
| url | https://doi.org/10.2478/fcds-2025-0012 |
| work_keys_str_mv | AT burzynskiwojciech amixedintegerprogrammingapproachtotherechargeableroverroutingproblemonmars AT kaletamariusz amixedintegerprogrammingapproachtotherechargeableroverroutingproblemonmars AT burzynskiwojciech mixedintegerprogrammingapproachtotherechargeableroverroutingproblemonmars AT kaletamariusz mixedintegerprogrammingapproachtotherechargeableroverroutingproblemonmars |