This paper addresses the maximum coverage location problem in a generalized setting, where both facilities (service areas) and regional demand are modeled as continuous entities. Unlike traditional formulations, our approach allows for arbitrary shapes for both service areas and demand regions, with additional constraints on facility placement. The key novelty of this work is its ability to handle complex, irregularly shaped service areas, including approximating them as unions of centrally symmetric shapes. This enables the use of an analytical approach based on spatial symmetry, which allows for efficient estimation of the covered area. The problem is formulated as a nonlinear optimization task. We analyze the properties of the objective function and leverage the Shapely library in Python 3.13.3 for efficient geometric computations. To improve computational efficiency, we develop an extended elastic model that significantly reduces processing time. This model generalizes the well-known quasi-physical, quasi-human algorithm for circle packing, extending its applicability to more complex spatial configurations. The effectiveness of the proposed approach is validated through test cases in which service areas take the form of circles, ellipses, and irregular polygons. Our method provides a robust and adaptable solution for various settings of practically interesting continuous maximum coverage location problems involving irregular regional demand and service areas.
29 December 2022 in Cybernetics and Computer Technologies
NEOS server provides free access to the library of necessary software for solving optimization problems. The effective numerical methods developed can be used for a specific application or for solving a wide range of mathematical programming problems. The article is devoted to researching the possibilities of solving optimization problems using NEOS server on the example of two mathematical programming problems: a linear Boolean programming problem for the well-known m-traveler problem and nonlinear programming problem for a special multiextremal problem on the Stiefel’s manifold. The material of the work is presented in 4 sections. Chapter 1 describes general information about using NEOS server for solving optimization problems and focuses on AMPL mathematical programming language as its component. Comparison of the frequency of use of AMPL, GAMS and other input data formats available on the server was conducted. The second section describes the principle of solving optimization problems using NEOS and provides a list of AMPL-supporting solvers available on the server. Statistics of use frequency of the solvers CPLEX, Gurobi and BARON in comparison with other solvers available on the server, as well as general statistics of the number of solved problems on the server in 2021 are given. Chapter 3 describes linear Boolean programming problems for the m-travelers problem, which is equivalent to the well-known traveling salesman problem. Performance indicators for solving these problems using CPLEX and Gurobi solvers are given. In Chapter 4 a study of nonlinear programming problem for a special multiextremal problem on the Stiefel’s manifold is conducted. General formulation of the problem and the formulation of its partial cases depending on the constraints imposed on vector components are given. The efficiency of solving test cases using BARON solver was investigated depending on the number of vectors and their dimensions.