spopt.locate.MCLP

class spopt.locate.MCLP(name: str, problem: LpProblem)[source]

Implement the Maximal Coverage Location Problem (MCLP) optimization model and solve it. The MCLP, as adapted from [CM18], can be formulated as:

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Maximize} & \displaystyle \sum_{i \in I}{a_iX_i} && & (1) \\ \displaystyle \textbf{Subject To} & \displaystyle \sum_{j \in N_i}{Y_j \geq X_i} && \forall i \in I & (2) \\ & \displaystyle \sum_{j \in J}{Y_j} = p && & (3) \\ & X_i \in \{0, 1\} && \forall i \in I & (4) \\ & Y_j \in \{0, 1\} && \forall j \in J & (5) \\ & && & \\ \displaystyle \textbf{Where} && i & = & \textrm{index of demand points/areas/objects in set } I \\ && j & = & \textrm{index of potential facility sites in set } J \\ && p & = & \textrm{the number of facilities to be sited} \\ && S & = & \textrm{maximum acceptable service distance or time standard} \\ && d_{ij} & = & \textrm{shortest distance or travel time between locations } i \textrm{ and } j \\ && N_i & = & \{j | d_{ij} < S\} \\ && X_i & = & \begin{cases} 1, \textrm{if client location } i \textrm{ is covered within service standard } S \\ 0, \textrm{otherwise} \\ \end{cases} \\ && Y_j & = & \begin{cases} 1, \textrm{if a facility is sited at location } j \\ 0, \textrm{otherwise} \\ \end{cases} \end{array}\end{split}\]
Parameters:
namestr

The problem name.

problempulp.LpProblem

A pulp instance of an optimization model that contains constraints, variables, and an objective function.

Attributes:
namestr

The problem name.

problempulp.LpProblem

A pulp instance of an optimization model that contains constraints, variables, and an objective function.

fac2clinumpy.array

A 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated. An empty client array indicates the facility is associated with no clients.

cli2facnumpy.array

The inverse of fac2cli where client to facility relationships are shown.

aijnumpy.array

A cost matrix in the form of a 2D array between origins and destinations.

n_cli_uncovint

The number of uncovered client locations.

__init__(name: str, problem: LpProblem)[source]

Initialize.

Parameters:
namestr

The desired name for the model.

Methods

__init__(name, problem)

Initialize.

check_status()

Ensure a model is solved.

client_facility_array()

Create a 2D array storing client to facility relationships where each row represents a client and contains an array of facility indices with which it is associated.

facility_client_array()

Create a 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated.

from_cost_matrix(cost_matrix, weights, ...)

Create a MCLP object based on cost matrix.

from_geodataframe(gdf_demand, gdf_fac, ...)

Create an MCLP object from geopandas.GeoDataFrame objects.

get_percentage()

Calculate the percentage of covered clients.

solve(solver[, results])

Solve the MCLP model

uncovered_clients()

Calculate how many clients points are not covered.

facility_client_array() None[source]

Create a 2D array storing facility to client relationships where each row represents a facility and contains an array of client indices with which it is associated. An empty client array indicates the facility is associated with no clients.

Returns:
None
classmethod from_cost_matrix(cost_matrix: array, weights: array, service_radius: float, p_facilities: int, predefined_facilities_arr: array = None, name: str = 'mclp')[source]

Create a MCLP object based on cost matrix.

Parameters:
cost_matrixnumpy.array

A cost matrix in the form of a 2D array between origins and destinations.

weightsnumpy.array

A 1D array of service load or population demand.

service_radiusfloat

Maximum acceptable service distance.

p_facilitiesint

The number of facilities to be located.

predefined_facilities_arrnumpy.array (default None)

A binary 1D array of service facilities that must appear in the solution. For example, consider 3 facilites ['A', 'B', 'C']. If facility 'B' must be in the model solution, then the passed in array should be [0, 1, 0].

namestr (default ‘mclp’)

The problem name.

Returns:
spopt.locate.coverage.MCLP

Examples

>>> from spopt.locate import MCLP
>>> from spopt.locate.util import simulated_geo_points
>>> import geopandas
>>> import numpy
>>> import pulp
>>> import spaghetti

Create a regular lattice.

>>> lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
>>> ntw = spaghetti.Network(in_data=lattice)
>>> streets = spaghetti.element_as_gdf(ntw, arcs=True)
>>> streets_buffered = geopandas.GeoDataFrame(
...     geopandas.GeoSeries(streets["geometry"].buffer(0.2).unary_union),
...     crs=streets.crs,
...     columns=["geometry"]
... )

Simulate points about the lattice.

>>> demand_points = simulated_geo_points(streets_buffered, needed=100, seed=5)
>>> facility_points = simulated_geo_points(streets_buffered, needed=5, seed=6)

Snap the points to the network of lattice edges.

>>> ntw.snapobservations(demand_points, "clients", attribute=True)
>>> clients_snapped = spaghetti.element_as_gdf(
...     ntw, pp_name="clients", snapped=True
... )
>>> ntw.snapobservations(facility_points, "facilities", attribute=True)
>>> facilities_snapped = spaghetti.element_as_gdf(
...     ntw, pp_name="facilities", snapped=True
... )

Calculate the cost matrix from origins to destinations.

>>> cost_matrix = ntw.allneighbordistances(
...    sourcepattern=ntw.pointpatterns["clients"],
...    destpattern=ntw.pointpatterns["facilities"]
... )

Simulate demand weights from 1 to 12.

>>> ai = numpy.random.randint(1, 12, 100)

Create and solve an MCLP instance from the cost matrix.

>>> mclp_from_cost_matrix = MCLP.from_cost_matrix(
...     cost_matrix, ai, service_radius=7, p_facilities=4
... )
>>> mclp_from_cost_matrix = mclp_from_cost_matrix.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Get the facility lookup demand coverage array.

>>> for fac, cli in enumerate(mclp_from_cost_matrix.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 44 clients
facility 1 serving 54 clients
facility 2 serving 75 clients
facility 3 serving 77 clients
facility 4 serving 0 clients

Get the number of clients uncovered and percentage covered.

>>> mclp_from_cost_matrix.n_cli_uncov
1
>>> mclp_from_cost_matrix.perc_cov
99.0
classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, weights_cols: str, service_radius: float, p_facilities: int, predefined_facility_col: str = None, distance_metric: str = 'euclidean', name: str = 'mclp')[source]

Create an MCLP object from geopandas.GeoDataFrame objects. Calculate the cost matrix between demand and facility locations before building the problem within the from_cost_matrix() method.

Parameters:
gdf_demandgeopandas.GeoDataFrame

Demand locations.

gdf_facgeopandas.GeoDataFrame

Facility locations.

demand_colstr

Demand sites geometry column name.

facility_colstr

Facility candidate sites geometry column name.

weights_colsstr

The weight column name representing service load or demand.

service_radiusfloat

Maximum acceptable service distance.

p_facilities: int

The number of facilities to be located.

predefined_facility_colstr (default None)

Column name representing facilities are already defined. This a binary assignment per facility. For example, consider 3 facilites ['A', 'B', 'C']. If facility 'B' must be in the model solution, then the column should be [0, 1, 0].

distance_metricstr (default ‘euclidean’)

A metric used for the distance calculations supported by scipy.spatial.distance.cdist.

namestr (default ‘mclp’)

The name of the problem.

Returns:
spopt.locate.coverage.MCLP

Examples

>>> from spopt.locate import MCLP
>>> from spopt.locate.util import simulated_geo_points
>>> import geopandas
>>> import pulp
>>> import numpy
>>> import spaghetti

Create a regular lattice.

>>> lattice = spaghetti.regular_lattice((0, 0, 10, 10), 9, exterior=True)
>>> ntw = spaghetti.Network(in_data=lattice)
>>> streets = spaghetti.element_as_gdf(ntw, arcs=True)
>>> streets_buffered = geopandas.GeoDataFrame(
...     geopandas.GeoSeries(streets["geometry"].buffer(0.2).unary_union),
...     crs=streets.crs,
...     columns=["geometry"]
... )

Simulate points about the lattice.

>>> demand_points = simulated_geo_points(streets_buffered, needed=100, seed=5)
>>> facility_points = simulated_geo_points(streets_buffered, needed=5, seed=6)

Snap the points to the network of lattice edges and extract as GeoDataFrame objects.

>>> ntw.snapobservations(demand_points, "clients", attribute=True)
>>> clients_snapped = spaghetti.element_as_gdf(
...     ntw, pp_name="clients", snapped=True
... )
>>> ntw.snapobservations(facility_points, "facilities", attribute=True)
>>> facilities_snapped = spaghetti.element_as_gdf(
...     ntw, pp_name="facilities", snapped=True
... )

Simulate demand weights from 1 to 12.

>>> ai = numpy.random.randint(1, 12, 100)
>>> clients_snapped['weights'] = ai

Create and solve an MCLP instance from the GeoDataFrame objects.

>>> mclp_from_geodataframe = MCLP.from_geodataframe(
...     clients_snapped,
...     facilities_snapped,
...     "geometry",
...     "geometry",
...     "weights",
...     service_radius=7,
...     p_facilities=4,
...     distance_metric="euclidean"
... )
>>> mclp_from_geodataframe = mclp_from_geodataframe.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Get the facility lookup demand coverage array.

>>> for fac, cli in enumerate(mclp_from_geodataframe.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 63 clients
facility 1 serving 80 clients
facility 2 serving 96 clients
facility 3 serving 0 clients
facility 4 serving 58 clients

Get the number of clients uncovered and percentage covered.

>>> mclp_from_geodataframe.n_cli_uncov
0
>>> mclp_from_geodataframe.perc_cov
100.0
solve(solver: LpSolver, results: bool = True)[source]

Solve the MCLP model

Parameters:
solverpulp.LpSolver

A solver supported by pulp.

resultsbool (default True)

If True it will create metainfo (which facilities cover which demand) and vice-versa, and the uncovered demand.

Returns:
spopt.locate.coverage.MCLP