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:
- name
str
The problem name.
- problem
pulp.LpProblem
A
pulp
instance of an optimization model that contains constraints, variables, and an objective function.
- name
- Attributes:
- name
str
The problem name.
- problem
pulp.LpProblem
A
pulp
instance of an optimization model that contains constraints, variables, and an objective function.- fac2cli
numpy.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.
- cli2fac
numpy.array
The inverse of
fac2cli
where client to facility relationships are shown.- aij
numpy.array
A cost matrix in the form of a 2D array between origins and destinations.
- n_cli_uncov
int
The number of uncovered client locations.
- name
- __init__(name: str, problem: LpProblem)[source]¶
Initialize.
- Parameters:
- name
str
The desired name for the model.
- name
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.
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 fromgeopandas.GeoDataFrame
objects.get_percentage
()Calculate the percentage of covered clients.
solve
(solver[, results])Solve the
MCLP
modeluncovered_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:
- 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_matrix
numpy.array
A cost matrix in the form of a 2D array between origins and destinations.
- weights
numpy.array
A 1D array of service load or population demand.
- service_radius
float
Maximum acceptable service distance.
- p_facilities
int
The number of facilities to be located.
- predefined_facilities_arr
numpy.array
(defaultNone
) 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]
.- name
str
(default ‘mclp’) The problem name.
- cost_matrix
- Returns:
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
to12
.>>> 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 fromgeopandas.GeoDataFrame
objects. Calculate the cost matrix between demand and facility locations before building the problem within thefrom_cost_matrix()
method.- Parameters:
- gdf_demand
geopandas.GeoDataFrame
Demand locations.
- gdf_fac
geopandas.GeoDataFrame
Facility locations.
- demand_col
str
Demand sites geometry column name.
- facility_col
str
Facility candidate sites geometry column name.
- weights_cols
str
The weight column name representing service load or demand.
- service_radius
float
Maximum acceptable service distance.
- p_facilities: int
The number of facilities to be located.
- predefined_facility_col
str
(defaultNone
) 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_metric
str
(default ‘euclidean’) A metric used for the distance calculations supported by scipy.spatial.distance.cdist.
- name
str
(default ‘mclp’) The name of the problem.
- gdf_demand
- Returns:
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
to12
.>>> ai = numpy.random.randint(1, 12, 100) >>> clients_snapped['weights'] = ai
Create and solve an
MCLP
instance from theGeoDataFrame
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