1
$\begingroup$

I'm currently working on a research project to optimize the recovery of space debris. We have to recover 50 pieces of space debris with the minimum number of missions possible. The missions are sent in parallel, so there are no planning problems to worry about. Obviously, a piece of debris has to be in a mission, and several missions can't contain the same piece of debris.

We have all the code needed to calculate the energy that a mission can produce, taking into account the positions of the debris at time T and its orbital drift. However, we must respect certain constraints for these missions, delta V_max and delta T_max, which are respectively the maximum speed a mission can travel in km/s and the number of days a mission can last.

I've implemented algorithms such as ACO, Genetic, NSGA-2 and 3. I've also optimized the function that gives the minimum energy a mission can produce, thanks to the Branch-and-bound algorithm, which permutes the debris list more efficiently to find the permutation with the minimum energy.

Since I'm looking for algorithms with constraints, I'd like to ask you if you know of any, or if you have any papers or articles on algorithms that have worked on this type of problem.

P.S : Here is an example of my problem but without scheduling : https://sophia.estec.esa.int/gtoc_portal/wp-content/uploads/2017/05/gtoc9_problem_stmt.pdf

$\endgroup$
5
  • $\begingroup$ Did you use a standard MIP-solver when you mention "Branch-and-Bound" algorithm? If yes, can't you include the relevant constraints in the mathematical model you pass to the solver? Concerning metaheuristics, most can deal with constraints. For example, in Genetic algorithms, you can penalize violations of your constraints. $\endgroup$
    – PeterD
    Commented Nov 14, 2023 at 11:00
  • $\begingroup$ Thank you for your answer, I don't see what a MIP-solver is. Yes for the penalties I had this idea however I don't see how to introduce it in my population. Should I make a part of my population which would be unacceptable solutions with penalties ? $\endgroup$
    – HunKhle
    Commented Nov 14, 2023 at 12:51
  • $\begingroup$ I can now see what a MIP problem is, I don't put the delta T max and delta V max constraints in the Branch-and-Bound algorithm because this algorithm is dedicated to finding the permutation that consumes the least energy in a given debris list. Once the permutation has been found, it returns its values such as delta V and delta T and I look to see if it respects the constraints. The function is used every time I make a mutation. $\endgroup$
    – HunKhle
    Commented Nov 14, 2023 at 13:01
  • $\begingroup$ Is it fair to say this is a Vehicle Routing Problem in space? With some extra constraints. Sounds like fun. $\endgroup$ Commented Nov 16, 2023 at 20:13
  • $\begingroup$ If you have a potential solution, say mission 1 collects items A, D and B (in that order), can you calculate delta V and delta T from that? If so, you can compare them with their max values in the score calculation of a metaheuristic. $\endgroup$ Commented Nov 16, 2023 at 20:16

1 Answer 1

1
$\begingroup$

ACO, genetic algorithms and other metaheuristics can be adapted to constrained problems by adding to the objective function penalties for constraint violations and then treating the problem as unconstrained (other than perhaps variable domains, e.g. $0 \le x \le U$ or $x\in \lbrace 0, 1\rbrace$). Also, there are versions of GAs called "random key" GAs, in which you choose a chromosome encoding and a function that maps each chromosome to a feasible solution.

For instance, the chromosome might be a permutation of the pieces of debris and the decoder function might scan the list in order and take as many pieces as the first mission can feasibly handle (skipping any that would "break" the mission), then scan the reduced list to fill the second mission and so on. I don't guarantee that approach would yield a feasible solution since I don't know all your constraints; it's just intended to give you an idea of the decoding process.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.