# An Iterative Optimization Algorithm for Planning Spacecraft Pathways Through Asteroids
## 2 Permutation Optimization Problems
For instance, the Linear Ordering Problem (LOP) [27; 28] and the Permutation Flowshop Scheduling Problem (PFSP) [29] are classic examples of ordering problems. On the other hand, the Assignment Problem, which can be solved in polynomial time [30], and its more complex NP-hard variant, the Quadratic Assignment Problem (QAP) [31], are typical examples of assignment problems. Additionally, the well-known Traveling Salesman Problem (TSP) [32], although focused on finding an optimal circular tour through a set of cities, is usually considered an ordering problem (simply designating a start/end city in the tour allows the solutions of the TSP to be represented as orderings over the remaining cities). It is worth noting that the categorization ordering/assignment problems is not always clear-cut. Indeed, both LOP and TSP have been shown to be special cases of the QAP [31]. This indicates that the boundary between the ordering and assignment nature of permutation problems is not yet fully understood. Two commonly employed methods for representing solutions to permutation problems are the traditional linear representation and the use of permutation matrices. The linear representation is based on the single-line notation of Equation (1), while the permutation matrix encoding represents a permutation as a binary matrix, where each row and column are one-hot vectors (i.e., they have one 1-entry and \(n-1\) 0-entries). While the linear representation is applicable to both kinds of permutation problems, the matrix representation does not inherently encode any ordering information; rather, it only reflects the pairings between row and column indices. Therefore, in this work, we utilize the linear genotypic representation for permutation solutions. However, as described in [21], two equivalent linear representations exist in ordering problems: the _ordering representation_ and the _ranking representation_. As previously discussed, an ordering problem aims to optimally arrange a set \(A\) of \(n\) items based on a given objective function. The ordering representation maps positions to items in \(A\), whereas the ranking representation maps items of \(A\) to their respective positions. Since the items in \(A\) are denoted by identification numbers in \([n]\), it is easy to confuse the two representations. However, both representations convey the same information and can be interconverted through a simple permutation inversion. In light of this, it is essential to specify which representation is being used when defining both the objective function and the algorithmic components used to tackle permutation problems. Using the wrong representation without the necessary conversion can lead to subtle errors that are difficult to detect but may significantly hinder the effectiveness of the algorithm. In this work, we adopt the ordering representation. Furthermore, it is important to mention that within the permutation space, there exist various definitions of elementary moves which can be utilized to develop local search strategies or genetic operators. The most classical ones are swapping two adjacent elements (_adjacent swaps_), swapping two arbitrary elements (_exchanges_), and shifting an element to a new position (_insertions_). Exchanges are typically effective in assignment problems, while adjacent swaps and insertions are more suited for problems related to ordering sequences. Additionally, it easy to see that (i) adjacent swaps are special cases of insertions, and (ii) a single insertion can be expressed as a sequence of multiple adjacent swaps. As a result, insertion moves are frequently preferred when designing algorithms aimed at solving ordering problems.