<p>Limited budget optimization scenarios typically arise in two situations: when evaluating the objective function is computationally expensive, or in mission-critical contexts where a solution must be obtained within a short timeframe. In this work, we focus on the limited budget optimization of permutation problems, a class of combinatorial optimization problems where the objective function is defined over the space of permutations. As a use case, we examine the Asteroid Routing Problem (ARP), which aims to determine the optimal sequence of asteroids to be visited by a spacecraft departing from Earth’s orbit, while minimizing both energy consumption and visit time. The ARP is a recently proposed computationally expensive benchmark permutation problem that may also be relevant in time-critical mission planning scenarios. In particular, we propose the application of two iterative optimization algorithms: FAT-RLS and FAT-EA. These algorithms differ in their search strategies, with FAT-RLS using randomized local search and FAT-EA following a trajectory based evolutionary approach. However, both incorporate a tabu mechanism and a perturbation strength regulation strategy to enhance search effectiveness while ensuring low computational overhead. To evaluate their performance, we conducted extensive experiments on well-established ARP instances, comparing FAT-RLS and FAT-EA with two recognized metaheuristics for limited budget optimization of permutation problems. The results clearly show that our approaches outperform the competitors.</p>