Minimizing the downtime due to refueling is a crucial economic problem in Pressurized Water Nuclear Reactors. Among the unloaded nuclear fuel bundles, some remain in the cooling pool and are replaced by fresh ones when the reactor is reloaded. The fuel bundles are covered by so-called "clusters" which serve different roles during the nuclear reaction: some help regulate the reaction, some are emergency stopping systems, others allow monitoring and some are simple plugs covering the bundle. When the reactor is emptied, bundles are manipulated together with their clusters, but since bundles do not return to the same position in the core after refueling, many clusters need to be swapped between bundles in order to move to their correct position when the core is reloaded. This swapping operation uses different tools to handle the clusters but only one tool at a time can be used on the manipulation crane. Finally, some clusters are interchangeable, making some permutations operations equivalent overall. The global number of cluster permutations leads to a dramatically combinatorial problem when trying to minimize the global operation time, which is a crucial issue since this operation is part of the refueling process' critical path.

We approach this problem as a graph-based shortest path problem between an initial situation and one of the multiple possible desired allocations of clusters on bundles. Our contribution is three-fold. First we analyze the problem symmetries and define an abstract state which groups together equivalent states, making the goal state unique. This first step uses the equivalence between interchangeable clusters and the equivalence between non-reloaded bundles. It allows to reason in terms of equivalent sets rather than in terms of bundles and clusters, and hence reduces the number of equivalent search paths. Secondly, we define an on-the-fly child node generation procedure, that only generates a subgraph of the search graph, which is guaranteed to contain at least one optimal path to the goal state. This pruning procedure exploits the equivalence between sequences of operations. Finally, we experimented a heuristic A* search algorithm in this pruned abstract subgraph and a stochastic depth first search (DFS). The best admissible heuristic for the A* search turned out to be a simple weighted Hamming distance with the goal state. We observed that only the DFS approach was able to tackle industrial size instances of the Optimal Swapping Problem and conjectured that the solution quality was close to optimal, based on comparisons between both approaches on smaller instances.

Overall, this study provides insight into a difficult combinatorial problem and introduces efficient methods to address the full planning problem as well as on-the-fly replanning issues.