spopt.locate.LSCPB

class spopt.locate.LSCPB(name: str, problem: LpProblem, solver: LpSolver)[source]

Implement the Location Set Covering Problem - Backup (LSCP-B) optimization model and solve it. The LSCP-B, as adapted from [CM18], can be formulated as:

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Maximize} & \displaystyle \sum_{i \in I}{U_i} && & (1) \\ \displaystyle \textbf{Subject To} & \displaystyle \sum_{j \in J}{a_{ij}}{Y_j} \geq 1 + U_i && \forall i \in I & (2) \\ & \displaystyle \sum_{j \in J}{Y_j} = p && & (3) \\ & U_i \leq 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{objective value identified by using the } LSCP \\ && U_i & = & \begin{cases} 1, \textrm{if demand location is covered twice} \\ 0, \textrm{if demand location is covered once} \\ \end{cases} \\ && a_{ij} & = & \begin{cases} 1, \textrm{if facility location } j \textrm{ covers demand location } i \\ 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.

solverpulp.LpSolver

A solver supported by pulp.

Attributes:
namestr

The problem name.

problempulp.LpProblem

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

solverpulp.LpSolver

A solver supported by pulp.

lscp_obj_valuefloat

The objective value returned from a solved LSCP instance.

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.

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

Initialize.

Parameters:
namestr

The desired name for the model.

Methods

__init__(name, problem, solver)

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, ...[, ...])

Create an LSCPB object based on a cost matrix.

from_geodataframe(gdf_demand, gdf_fac, ...)

Create an LSCPB object from geopandas.GeoDataFrame objects.

get_percentage()

Calculate the percentage of clients with backup.

solve([results])

Solve the LSCPB model.

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, service_radius: float, solver: LpSolver, predefined_facilities_arr: array = None, name: str = 'lscp-b')[source]

Create an LSCPB object based on a cost matrix.

Parameters:
cost_matrixnumpy.array

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

service_radiusfloat

Maximum acceptable service distance.

solverpulp.LpSolver

A solver supported by pulp.

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 ‘lscp-b’)

The problem name.

Returns:
spopt.locate.coverage.LSCPB

Examples

>>> from spopt.locate import LSCPB
>>> 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"]
... )

Create and solve an LSCPB instance from the cost matrix.

>>> lscpb_from_cost_matrix = LSCPB.from_cost_matrix(
...     cost_matrix, service_radius=8, solver=pulp.PULP_CBC_CMD(msg=False)
... )
>>> lscpb_from_cost_matrix = lscpb_from_cost_matrix.solve()

Get the facility lookup demand coverage array.

>>> for fac, cli in enumerate(lscpb_from_cost_matrix.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 0 clients
facility 1 serving 63 clients
facility 2 serving 85 clients
facility 3 serving 92 clients
facility 4 serving 0 clients

Get the percentage of clients covered by more than one facility.

>>> round(lscpb_from_cost_matrix.backup_perc, 3)
88.0

88% of clients are covered by more than 1 facility

classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, service_radius: float, solver: LpSolver, predefined_facility_col: str = None, distance_metric: str = 'euclidean', name: str = 'lscp-b')[source]

Create an LSCPB 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.

service_radiusfloat

Maximum acceptable service distance.

solverpulp.LpSolver

A solver supported by pulp.

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 ‘lscp-b’)

The name of the problem.

Returns:
spopt.locate.coverage.LSCPB

Examples

>>> from spopt.locate import LSCPB
>>> 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 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
... )

Create and solve an LSCPB instance from the GeoDataFrame objects.

>>> lscpb_from_geodataframe = LSCPB.from_geodataframe(
...     clients_snapped,
...     facilities_snapped,
...     "geometry",
...     "geometry",
...     service_radius=8,
...     solver=pulp.PULP_CBC_CMD(msg=False),
...     distance_metric="euclidean"
... )
>>> lscpb_from_geodataframe = lscpb_from_geodataframe.solve()

Get the facility lookup demand coverage array.

>>> for fac, cli in enumerate(lscpb_from_geodataframe.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 0 clients
facility 1 serving 0 clients
facility 2 serving 100 clients
facility 3 serving 0 clients
facility 4 serving 0 clients

Get the percentage of clients covered by more than one facility.

>>> round(lscpb_from_geodataframe.backup_perc, 3)
0.0

All clients are covered by 1 facility because only one facility is needed to solve the LSCP.

solve(results: bool = True)[source]

Solve the LSCPB model.

Parameters:
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.LSCPB