The expansion of e-commerce has intensified the need for efficient last-mile delivery solutions, with parcel lockers emerging as a promising alternative to traditional home deliveries. This paper presents a spatially grounded optimization model for the design of cost-efficient parcel locker networks in urban areas. The model simultaneously considers locker installation, decommissioning, and customer assignment decisions, integrating behavioral preferences through a continuous attractiveness function based on distance. Due to the model’s nonlinear and combinatorial nature, a tailored genetic algorithm (GA) is developed to explore near-optimal solutions efficiently. The methodology is validated on a synthetic instance and applied to a large-scale real-world case study in Catania (Italy), involving 2,793 demand nodes. Results show that the proposed approach significantly reduces operational costs while ensuring high service coverage (above 98%). The study highlights the GA’s ability to provide scalable and effective decision support for logistics planners and outlines potential future developments involving dynamic demand, environmental objectives, and multi-operator scenarios.