This paper presents a novel approach to the Maximum Coverage Location Problem, extended to include arbitrarily shaped objects, rotation, and center-specific restricted zones. We formulate the problem as a nonlinear optimization problem using a dynamically tuned penalty function via neural networks to enforce constraints. Particle Swarm Optimization and Memetic Algorithms are accelerated using a surrogate neural network approximating the computationally expensive objective function. The hybrid evaluation strategy combines the exact computation of Shapely with Monte Carlo approximations to improve efficiency. Numerical experiments on elliptical objects and circular restricted zones demonstrate the effectiveness of the method, achieving high coverage density in a limited time. The integration of neural network-based adaptive penalties and geometric optimization offers a scalable, robust solution for applications in telecommunications, healthcare, ecology, and urban planning, with the potential for further deployment in real-world settings.
In the modern world, placement problems for maximizing coverage of a given area find wide applications in various fields such as logistics, urban planning, telecommunications, ecology, and defense systems. The classical maximum coverage location problem (MCLP) involves placing a limited number of facilities (e.g., base stations, warehouses, or sensors) to maximize the covered area or the number of demand points served. However, real-world scenarios often introduce additional constraints, such as arbitrary shapes of the area and covering objects and restricted zones for facility centers.
In the considered problem, there is an area covered using a set of distinct covering objects of given shape and size that needs to be , each with fixed shape and size.
Placement parameters include the coordinates of the pole (center) for each object and the rotation angle . The goal is to maximize the covered area of , i.e., the area of the union of transformed objects
after positioning and rotation.
Additionally, constraints are imposed: poles cannot be located in intersections between covering objects and restricted zones are allowed, and restricted zones should also be covered if it contributes to maximizing the overall area.
The novelty of this formulation lies in the combination of continuous space, geometric transformations, and partial prohibitions (only for object centers). This distinguishes the problem from traditional discrete MCLP models, where facilities are placed at fixed points, and from simple geometric coverings without transformation flexibility. Such constraints reflect real scenarios: for example, in antenna placement for communications, centers cannot be in residential areas, but signals must cover them; in ecology, sensors for forest fire monitoring avoid restricted zones but cover them; or in crisis scenarios, mobile health units are placed in safe, accessible locations while maximizing service coverage. Solving such problems optimizes resources, minimizes costs, and enhances system efficiency.
In the literature, MCLP has evolved from discrete models of the 1970s to continuous and stochastic variants accounting for uncertainties and geometric aspects. However, the integration of restricted zones and neural network-assisted optimization remains underexplored, making this work timely. In the following sections, we conduct a literature review, describe the materials and methods, present numerical results, discuss their implications, and conclude with future directions.
The maximum coverage location problem (MCLP), introduced by Church and ReVelle [
Significant advancements in continuous coverage include the work of Cortés et al. [
Swarm intelligence and evolutionary algorithms are well-suited for the multi-extremal landscapes of MCLP. Kennedy and Eberhart [11] introduced Particle Swarm Optimization (PSO), valued for its simplicity and balanced exploration-exploitation dynamics, while Storn and Price [12] proposed Differential Evolution (DE) as a robust alternative with minimal hyperparameters. Ant Colony Optimization (ACO), developed by Dorigo and Stützle [13], excels in combinatorial subproblems, such as object ordering, and is often embedded in memetic schemes, as explored by Neri and Cotta [14]. Yang [15] provides a comprehensive synthesis of nature-inspired algorithms, emphasizing their adaptability to geometric optimization, while Mirjalili et al. [16] advance multiobjective PSO variants for complex problems. Memetic algorithms, combining global search with local refinement like BFGS, as detailed by Molina et al. [17], offer frameworks for hybrid optimization, particularly effective for geometry-heavy objectives. These methods underpin our approach, which hybridizes PSO and memetic algorithms with neural network surrogates to navigate high-dimensional spaces efficiently.
The computational cost of geometric operations, such as unions and intersections for area
computation, necessitates surrogate modeling. Traditional approaches, like Kriging and Radial
Basis Functions (Forrester et al. [18]), rely on adaptive sampling, but recent trends favor deep
learning models. Zaheer et al. [19] introduced Deep Sets for permutation-invariant inputs, ideal for
variable object sets in coverage problems. Active learning, as described by Jin et al. [20], enhances
surrogate robustness through periodic exact evaluations, while physics-informed neural networks
(Raissi et al. [21]) support multi-fidelity training for engineering applications. Goodfellow et al. [22]
provide a foundational framework for neural networks in optimization, and Zhang et al. [23]
highlight their integration with metaheuristics for global search. Papers [
Practical applications of MCLP span diverse domains. In wireless sensor networks (WSNs), continuous layout formulations optimize area, point, and barrier coverage under connectivity and lifetime constraints, as surveyed by Akyildiz et al. [24]. Unmanned vehicle (UAV/UGV/USV) coverage path planning, explored by Low et al. [25], improves path efficiency for 2D/3D terrains, while environmental monitoring and precision agriculture benefit from optimized sensor layouts over irregular parcels, as noted by Choset [26]. Industrial inspection, including painting and nondestructive testing, leverages robotics coverage for arbitrary shapes [27]. In the area of crisis management, [28] proposes a coverage model for mobile health units, using predictive analytics to optimize vaccination or testing center placement under safety and accessibility constraints, directly relevant to our focus on restricted zones. Similarly, [29] evaluates the reliability of a sensor network for wildfire monitoring, focusing on placement constraints and failure factors, which our model improves through flexible shape handling and fast optimization. Security, surveillance, and disaster response also rely on maximizing sensor redundancy in complex sites using reliabilityoriented strategies [29, 30].
Relative to Voronoi-based control [
To address the maximum coverage location problem (MCLP) with restricted zones, we developed a
comprehensive methodology that integrates nonlinear optimization, swarm and memetic
algorithms, and neural network-driven surrogate modeling to maximize coverage while adhering
to spatial constraints. The approach is designed to handle complex geometric configurations, such
as irregular polygonal areas and arbitrarily shaped covering objects, making it suitable for
realworld applications like mobile health unit placement and environmental monitoring. Our
formulation builds on prior work in continuous coverage optimization [
We consider a compact coverage area , typically an irregular polygon, to be covered by n compact objects
, each with a predefined shape, such as an ellipse. Each object undergoes a transformation defined by a shift to coordinates angle , yielding the transformed object and a rotation by where
encapsulates the placement variables.
A key constraint requires that the pole (center) of each object, , avoids restricted zones , ensuring
Notably, intersections between transformed objects Tᵢ and restricted zones Fⱼ are permitted, allowing coverage of these zones to contribute to the objective, which mirrors real-world scenarios like sensor placement in forest fire monitoring [29] or mobile health unit deployment in crisis zones [28].
The optimization problem is inherently multimodal and high-dimensional due to geometric operations and constraint enforcement, necessitating robust computational strategies. To transform the constrained problem into an unconstrained one, we employ a penalty function approach. The violation for each object's pole is defined as where is an indicator function returning 1 if and 0 otherwise.
For smoother formulations, particularly with circular restricted zones, we use where is the rotation matrix with elements The objective is to maximize the covered area, defined as and
The total violation is and the penalty term is with as a penalty coefficient. The resulting objective function is and the problem becomes
, and optimize
This self-adaptive penalty minimizes a composite loss, , trained on samples
, and or decreasing it if optimization stalls Following exterior penalty theory,
starts at 10 and increases dynamically via (c=10) until ensuring constraint satisfaction. To avoid manual tuning, we treat an additional variable, defining as enhancing robustness.
To tackle the multimodal landscape, we employ a hybrid optimization framework combining swarm intelligence and memetic algorithms, drawing on their proven efficacy in geometric and high-dimensional problems [11-15]. Particle Swarm Optimization (PSO), inspired by flock behavior [11], updates candidate solutions (particles) using velocities driven by personal and global best positions: ,
,
, , , and , where
(inertia) decreases from 0.9 to 0.4,
The swarm size ( = 50-100) and iterations ( = 500-1000) were tuned to balance exploration and computation efficiency within a time budget of 5-10 minutes, with initial speeds limited to 10% of the search range.
Given the computational intensity of geometric operations, such as area calculations for unions and intersections, we leverage neural network surrogate modeling to accelerate evaluations, a technique increasingly vital for optimization tasks [16, 20, 22]. A Deep Sets-style neural network, implemented in PyTorch (version 1.12), ensures permutation invariance for object sets, taking normalized as input and producing a scalar approximation .
The architecture features per-object embeddings through 3 fully-connected layers (128–256 neurons, ReLU activation), followed by mean pooling and concatenation with the number of restricted zones, and an output layer. Training uses 5000–10000 samples , generated via Latin Hypercube Sampling in , with exact computed using Monte Carlo or Shapely methods [9, 10]. The network is optimized with Adam (learning rate 0.001, decay 0.95) in Python 3.8, minimizing MSE + L1 loss over 1000 epochs, with batch size 64, dropout 0.2, and L2 regularization (weight decay 0.001).
Active learning updates the dataset every 50 iterations, selecting 5–10 points with high uncertainty or expected improvement, reducing MSE to approximately 0.005 and enabling 80–90% of evaluations to use fast surrogate predictions (inference ~1 ms) [19].
The objective function comprises the coverage area and violation penalty , evaluated using a hybrid approach combining exact and approximate methods. The Shapely library (version 2.0) facilitates precise 2D geometry operations, transforming objects via rotation and shift, computing unions with , intersecting with to obtain , and checking pole violations with . While accurate to
, Shapely is computationally costly, especially for complex shapes. To address this, Monte Carlo approximation samples points in
, estimating , with to for early iterations (1–5% error) and to for final precision (<0.1%). Violations are computed exactly, and a multi-fidelity strategy uses Monte Carlo for exploration and Shapely for top-10% candidates or validation, achieving 10–50x speedups. For the violation measure , representing uncovered areas, we employ Monte Carlo discretization with 2000–20000 points (adaptive grid), testing inclusion via ray-casting or distance functions, or exact Shapely computations for high-fidelity verification, ensuring robust evaluation across optimization stages.
The hybrid optimization architecture orchestrates these components seamlessly. It begins with greedy initialization to approximate coverage, followed by global exploration using DE or PSO with surrogate evaluations. Periodic exact verifications refine top candidates, which undergo local CMA-ES optimization, and the neural surrogate is updated with new data.
Using the hybrid optimization framework described in Section 3, we validated the neural networkdriven adaptive approach for the maximum coverage location problem (MCLP) with restricted zones through a numerical experiment involving 20 elliptical objects and 5 restricted zones. After multiple runs on similar MCLP instances, we selected optimized parameters to achieve the best coverage, demonstrating the method’s efficacy in handling complex geometric configurations, such as those encountered in mobile health unit placement [28] and forest fire monitoring [29]. The experiment was conducted on an 8-core CPU (Intel Core i7, 3.2 GHz, 16 GB RAM) with a 10-minute time budget, utilizing Python libraries NumPy (1.23), SciPy (1.9), PyTorch (1.12), Shapely (2.0), and pycma (3.2).
The coverage area is an irregular polygon with 10 vertices (Table 1) with a total area of 330.4013 units, which corresponds to the sum of the areas of 20 different ellipses, the semi-axes of which are given in Table 2. Six circular restriction zones are also defined, the coordinates of the centers and radii of which are presented in Table 3.
Table 1 Coordinates of Polygon Vertices
Vertex Index x y
The optimization variables were , with bounds , . The sum of ellipse areas equaled the area of , making full coverage theoretically possible but challenging due to overlaps and restricted zones. Based on preliminary experiments with similar tasks, we tuned the PSO and MA parameters (PSO: swarm size , iterations ; MA: population , generations , local search frequency ) to maximize coverage within the time constraint, as outlined in Section 3. The neural network surrogate (input size 61, four hidden layers: 512-256-128-64) was trained on 600 samples, achieving an RMSE of approximately 0.005. Monte Carlo approximation used 3000 initial and 15000 final points for area estimation (error <0.5%), with Shapely for top-10% candidate validation.
The best run, selected from 10 trials with coverage ranging from 88–92%, yielded (90.0%) for PSO and (94.0%) for MA, both with zero constraint violations ( ). The neural network provided an 80% reduction in computational evaluations, enabling efficient exploration [16]. Optimal placement parameters from MA are shown in Table 4.
The visualization of the resulting coverage (Figure 1) confirms correct pole placement outside
restricted zones, which are colored red. The uncovered part of the polygon is marked in yellow,
and the poles of the ellipses and circles are indicated by dots.
Preliminary tests on similar MCLP instances indicated that further parameter tuning (e.g., reducing
to 200 or to 500 for PSO, or using a pre-trained neural network with fewer epochs) could
potentially lower the computation time to 5 minutes or less while maintaining coverage above 90%.
These adjustments, tested in a subset of runs, suggested marginal coverage improvements of 1–2%,
confirming that the achieved 94.0% coverage is near-optimal given the geometric constraints and
restricted zones [
The numerical experiments demonstrate that our neural network-driven adaptive approach effectively addresses the MCLP with restricted zones, achieving coverage of 86.8–89.2% within constrained time limits (5–10 minutes). The memetic algorithm consistently outperformed PSO due to its hybrid global-local search mechanism, while the neural network surrogate provided 80–85% computational speedup, enabling practical deployment. The adaptive penalty mechanism ensured zero constraint violations ( ) without manual tuning, highlighting the robustness of the selfadaptive framework.
Despite the high coverage achieved, the results reveal inherent limitations due to the geometric complexity of the problem. Ellipses cannot perfectly tile an irregular polygon, leading to gaps or overlaps that restrict coverage to below the theoretical maximum of 100%. The restricted zones further constrain feasible placements, creating bottlenecks where minor adjustments yield diminishing returns. These findings align with the NP-hard nature of geometric covering problems and suggest that coverage rates above 85–90% may require significantly more computational resources or alternative object shapes.
This study was partly funded by the IMPRESS-U joint program of the National Science Foundation (project no. 2412914), the National Science Center of Poland (project no. 2023/05/Y/ST6/00263), and the Office of Naval Research of the US National Academy of Sciences (project no. 7136).
During the preparation of this work, the authors did not used Generative AI tools. [9] Yakovlev, S., Kartashov, O., & Mumrienko, A. (2022). Formalization and solution of the maximum area coverage problem using library Shapely for territory monitoring. Radioelectronic and Computer Systems, 2022(2), 35–48. http://nti.khai.edu/ojs/index.php/reks/article/view/reks.2022.2.03 [10] Yakovlev, S. V. (2023). The concept of modeling packing and covering problems using modern computational geometry software. Cybernetics and Systems Analysis, 59(1), 108–119. https://doi.org/10.1007/s10559-023-00547-5 [11] Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Proceedings of ICNN'95 International Conference on Neural Networks, 4, 1942–1948. https://doi.org/10.1109/ICNN.1995.488968 [12] Storn, R., & Price, K. (1997). Differential evolution – A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 11(4), 341–359. https://doi.org/10.1023/A:1008202821328 [13] Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
https://doi.org/10.7551/mitpress/4811.001.0001 [14] Neri, F., & Cotta, C. (2012). Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation, 2, 1–14. https://doi.org/10.1016/j.swevo.2011.11.003 [15] Yang, X.-S. (2018). Mathematical analysis of nature-inspired algorithms. Neural Computing and Applications, 30(1), 113–119. https://doi.org/10.1007/s00521-017-3156-1 [16] Mirjalili, S., Saremi, S., Mirjalili, S. M., & Coelho, L. S. (2016). Multi-objective grey wolf optimizer: A novel algorithm for multi-criterion optimization. Expert Systems with Applications, 47, 106–119. https://doi.org/10.1016/j.eswa.2015.10.039 [17] Molina, D., Lozano, M., & Herrera, F. (2015). Memetic algorithms for continuous optimisation based on local search chains. Evolutionary Computation, 23(1), 1–28. https://doi.org/10.1162/EVCO_a_00124 [18] Forrester, A., Sóbester, A., & Keane, A. (2008). Engineering design via surrogate modelling: A practical guide. John Wiley & Sons. https://doi.org/10.1002/9780470770801 [19] Zaheer, M., et al. (2017). Deep sets. Advances in Neural Information Processing Systems, 30, 3391–3401. https://arxiv.org/abs/1703.06114 [20] Jin, Y., Wang, H., Chugh, T., Guo, D., & Miettinen, K. (2019). Data-driven evolutionary optimization: An overview and case studies. IEEE Transactions on Evolutionary Computation, 23(3), 442–458. https://doi.org/10.1109/TEVC.2018.2869001 [21] Raissi, M., Perdikaris, P., & Karniadakis, G. E. (2019). Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. Journal of Computational Physics, 378, 686–707. https://doi.org/10.1016/j.jcp.2018.10.045 [22] Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep learning. MIT Press.
https://doi.org/10.7551/mitpress/9780262035613.001.0001 [23] Zhang, J., Xiao, M., Gao, L., & Pan, Q. (2018). Queuing search algorithm: A novel metaheuristic algorithm for solving global optimization problems. Applied Soft Computing, 67, 136–148. https://doi.org/10.1016/j.asoc.2018.02.038 [24] Akyildiz, I. F., Su, W., Sankarasubramaniam, Y., & Cayirci, E. (2002). Wireless sensor networks:
A survey. Computer Networks, 38(4), 393–422. https://doi.org/10.1016/S1389-1286(01)00302-4 [25] Low, K. H., Dolan, J. M., & Khosla, P. (2009). Adaptive multi-robot wide-area exploration and mapping. Autonomous Robots, 27(2), 129–148. https://doi.org/10.1007/s10514-009-9126-5 [26] Choset, H. (2001). Coverage for robotics – A survey of recent results. Annals of Mathematics and Artificial Intelligence, 31(1–4), 113–126. https://doi.org/10.1023/A:1016639210559 [27] Yakovlev, S., Kiseleva, O., Chumachenko, D., & Podzeha, D. (2023). Maximum service coverage in business site selection using computer geometry software. Electronics, 12(10), 2329. https://doi.org/10.3390/electronics12102329 [28] Yakovlev, S., et al. (2025). Optimization of mobile medical service locations based on predictive analytics in crisis scenarios. Proceedings of the International Conferences IADIS Information Systems 2025 and E-Society 2025, 538–541. [29] Leichenko, K., et al. (2025). Assessment of the reliability of wireless sensor networks for forest fire monitoring systems considering fatal combinations of multiple sensor failures.
Cybernetics and Systems Analysis, 61(1), 137–147. https://doi.org/10.1007/s10559-025-00722-w [30] Skorobohatko, S., et al. (2024). Architecture and reliability models of hybrid sensor networks for environmental and emergency monitoring systems. Cybernetics and Systems Analysis, 60(2), 293–304. https://doi.org/10.1007/s10559-024-00670-x