V. Blanco, S. García-Quiles

The Maximal Covering Location Problem (MCLP) consists of locating a fixed number of facilities so that the covered demand is maximized. As Euclidean distances on the plane are used in the MCLP, the geometric shape used to cover the demand point is a circle. A much less studied variant of this problem is to use not circles but ellipses to cover the points, which has applications to wireless telecommunications networks. Now, a number of ellipses from a given set is to be selected, and their centers are to be located anywhere on the plane, and the goal is to maximize the profit of covering the demand points. The existing methodologies for the problem are based on nonlinear mixed integer programming formulations and sophisticated heuristics (Cambolat and Von Massow, 2009; Andretta and Birgin, 2013). We use some geometric properties of this problem to
give a different integer linear formulation able to solve much larger instances, as it will be shown with in our computational study.

Keywords: Covering Location, Integer Programming


GT1-1 Location
September 3, 2019  3:30 PM
I3L8. Georgina Blanes building

Other papers in the same session

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.