Simulated Annealing for Antenna Placements
TL;DR
An approach that separates geometric visibility preprocessing from a portfolio of incremental combinatorial searches is described, complemented by exact discrete one-swap descent, ruin-and-recreate, and elite crossover.
Abstract
The 2026 ACM SIGSPATIAL GIS Cup posed the following geometric challenge: Given a set of simple, pair-wise disjoint polygons, compute $k$ antennas (points) on polygon boundaries, maximizing the number of polygons with at least a fraction $\tau$ of their perimeter visible from the antennas. Contestants had 24 hours to produce the best possible solutions. We describe an approach that separates geometric visibility preprocessing from a portfolio of incremental combinatorial searches. A construction pool provides initial solutions with antennas restricted to polygon vertices; simulated annealing explores one-for-one antenna swaps, complemented by exact discrete one-swap descent, ruin-and-recreate, and elite crossover. A secondary objective rewards progress toward the service threshold without overriding the primary score. Candidate antennas are later expanded to include points in polygon-edge interiors. Our submitted solutions cover between 261 and 16,273 buildings across the nine parameter combinations, and the team was invited to present as one of the top entries. The code is available at https://github.com/JacobusTheSecond/giscup.