Métodos Heurísticos e Metaheurísticos para o One Sided Crossing Minimization em grafos bipartidos.

O Problema de Minimização de Cruzamentos Unilaterais (One-Sided Crossing Minimization – OSCM) é clássico em grafos, NP-difícil e tema do PACE Challenge 2024. Propomos uma abordagem baseada na heurística construtiva da Mediana para gerar soluções iniciais, combinada à metaheurística Simulated Annealing (SA) para refinamento. O SA é empregado para explorar o espaço de busca eficientemente e evitar ótimos locais. A avaliação experimental em 196 instâncias do PACE 2024 demonstra que aliar uma inicialização simples ao poder exploratório do SA produz soluções competitivas em relação à literatura. Com bom desempenho computacional, a abordagem evidencia sua eficácia em instâncias de grande porte. O presente trabalho foi realizado com apoio da Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) - Código de Financiamento 001, e da Universidade Federal de Ouro Preto.