This repository provides a Python implementation of solving a classical instance of the maximum coverage location problem described in Church 1974.
The problem is defined as: given N points, find K circles with radius of r to cover as many points as possible.
(M is the number of candidate sites and C is the number of points covered)
The method randomly generates a set of candidate sites within the region of the input points. The problem is then solved by integer programming.
The mathematical formulation is given below:
from mclp import *
import numpy as np
Npoints = 300
from sklearn.datasets import make_moons
points,_ = make_moons(Npoints,noise=0.15)
# Number of sites to select
K = 20
# Service radius of each site
radius = 0.2
# Candidate site size (random sites generated)
M = 100
# Run mclp
# opt_sites is the location of optimal sites
# f is the number of points covered
opt_sites,f = mclp(points,K,radius,M)
# Plot the result
plot_result(points,opt_sites,radius)
Check the jupyter-notebook demo.ipynb.
To run the example interactively, inside the project directory type the command
It is recommended to use Anaconda directly, where the packages can be installed with pip or conda.
pip install shapely
conda config --add channels http://conda.anaconda.org/gurobi
conda install gurobi
Can Yang, Ph.D. student at KTH, Royal Institute of Technology in Sweden
Email: cyang(at)kth.se
Homepage: https://people.kth.se/~cyang/
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4