Heuristic and Metaheuristic Methods for One Sided Crossing Minimization in Bipartite Graphs.

The One-Sided Crossing Minimization (OSCM) Problem is a classic graph, NP-hard, and the subject of the PACE Challenge 2024. We propose an approach based on the Median constructive heuristic to generate initial solutions, combined with the Simulated Annealing (SA) metaheuristic for refinement. The SA is employed to explore the search space efficiently and avoid great locations. The experimental evaluation in 196 instances of PACE 2024 demonstrates that combining a simple startup with the exploratory power of AS produces solutions that are competitive in relation to the literature. With good computational performance, the approach shows its effectiveness in large instances. The present work was carried out with the support of the Coordination for the Improvement of Higher Education Personnel - Brazil (CAPES) - Financing Code 001, and the Federal University of Ouro Preto.