Iterated Local Search Heuristic for The Seating Arrangement Layout Problem

This work introduces the Seating Arrangement Layout Problem (SALP), an optimization challenge that seeks to allocate students to classroom seats while minimizing interpersonal conflicts. A mathematical model has been developed to formalize the problem, incorporating key constraints such as minimum spacing between students and predefined seating preferences. The objective is to maximize the distance between students with potential conflicts while fully respecting all restrictions. Since traditional optimization methods work well for small instances but become impractical as problem size increases, we propose an Iterated Local Search (ILS) heuristic to solve SALP. The ILS builds an initial solution based on a weight matrix that reflects undesired proximities and iteratively refines it throudh pertubation and local search phases. Computacional experiments using real-world scenarios demonstrate that the heuristic efficiently produces high-quality solutions. Notably, in highly conflicted classrooms, multiple ILS runs improved feasibility and significantly reduced proximity among conflicting students. Future work includes refining local search strategies and making the heuristic available as user-friendly software to assist teachers in a task typically done manually.