Mathematical Models and Nonlinear Optimization in Continuous Maximum Coverage Location Problem

Abstract

This paper considers the maximum coverage location problem (MCLP) in a continuous formulation. It is assumed that the coverage domain and the family of geometric objects of arbitrary shape are specified. It is necessary to find such a location of geometric objects to cover the greatest possible amount of the domain. A mathematical model of MCLP is proposed in the form of an unconstrained nonlinear optimization problem. Python computational geometry packages were used to calculate the area of partial coverage domain. Many experiments were carried out which made it possible to describe the statistical dependence of the area calculation time of coverage domain on the number of covering objects. To obtain a local solution, the BFGS method with first-order differences was used. An approach to the numerical estimation of the objective function gradient is proposed, which significantly reduces computational costs, which is confirmed experimentally. The proposed approach is shown to solve the maximum coverage problem of a rectangular area by a family of ellipses.

Keywords

• geometric object
• coverage
• optimization
• computational geometry software
• Python