Skip to content

A Python library for solving maximum coverage location problem

License

Notifications You must be signed in to change notification settings

cyang-kth/maximum-coverage-location

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

3 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Maximum coverage location problem (MCLP)

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.

  • Example 1: Select 20 circles with radius of 0.1 to cover 300 points (uniform distribution)

example1

(M is the number of candidate sites and C is the number of points covered)

  • Example 2: Select 20 circles with radius of 0.2 to cover 300 points (moon distribution)

example2

Problem formulation

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:

math

Demo and usage

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

jupyter-notebook

Requirements

  • Python 2.7
  • Scipy, Numpy (available as part of Anaconda)
  • Shapely
  • Gurobi, commercial software (free for academic usage)

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

Contact

Can Yang, Ph.D. student at KTH, Royal Institute of Technology in Sweden

Email: cyang(at)kth.se

Homepage: https://people.kth.se/~cyang/

Reference

Releases

No releases published

Packages

No packages published