spopt.locate.LSCP

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

Implement the Location Set Covering Problem (LSCP) optimization model and solve it. A capacitated version, the Capacitated Location Set Covering Problem – System Optimal (CLSCP-SO), can also be solved by passing in client client demand and facility capacities.

The standard LSCP, as adapted from [CM18], can be formulated as:

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{j \in J}{Y_j} && & (1) \\ \displaystyle \textbf{Subject To} & \displaystyle \sum_{j \in N_i}{Y_j} \geq 1 && \forall i \in I & (2) \\ & Y_j \in \{0,1\} && \forall j \in J & (3) \\ & && & \\ \displaystyle \textbf{Where} && i & = & \textrm{index of demand points/areas/objects in set } I \\ && j & = & \textrm{index of potential facility sites in set } J \\ && 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\} \\ && Y_j & = & \begin{cases} 1, \textrm{if a facility is sited at location } j \\ 0, \textrm{otherwise} \\ \end{cases} \end{array}\end{split}\]

The CLSCP-SO, as adapted from [CM18] (see also [CS88]), can be formulated as:

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{j \in J}{Y_j} && & (1) \\ \displaystyle \textbf{Subject to} & \displaystyle \sum_{j \in N_i}{z_{ij}} = 1 && \forall i \in I & (2) \\ & \displaystyle \sum_{i \in I} a_i z_{ij} \leq C_jx_j && \forall j \in J & (3) \\ & Y_j \in {0,1} && \forall j \in J & (4) \\ & z_{ij} \geq 0 && \forall i \in I \quad \forall j \in N_i & (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 \\ && S & = & \textrm{maximal acceptable service distance or time standard} \\ && d_{ij} & = & \textrm{shortest distance or travel time between nodes } i \textrm{ and } j \\ && N_i & = & \{j | d_{ij} < S\} \\ && a_i & = & \textrm{amount of demand at } i \\ && C_j & = & \textrm{capacity of potential facility } j \\ && z_{ij} & = & \textrm{fraction of demand } i \textrm{ that is assigned to facility } j \\ && Y_j & = & \begin{cases} 1, \text{if a facility is located at node } j \\ 0, \text{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.

__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, service_radius)

Create an LSCP object based on a cost matrix.

from_geodataframe(gdf_demand, gdf_fac, ...)

Create an LSCP object from geopandas.GeoDataFrame objects.

solve(solver[, results])

Solve the LSCP 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, predefined_facilities_arr: array = None, demand_quantity_arr: array = None, facility_capacity_arr: array = None, name: str = 'lscp')[source]

Create an LSCP object based on a cost matrix. A capacitated version of the LSCP (the CLSCP-SO) can be solved by passing in the demand_quantity_arr and facility_capacity_arr keyword arguments.

Parameters:
cost_matrixnumpy.array

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

service_radiusfloat

Maximum acceptable service distance.

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].

demand_quantity_arrnumpy.array (default None)

Amount of demand at each client location.

facility_capacity_arrnumpy.array (default None)

Capacity for service at each facility location.

namestr, (default ‘lscp’)

The name of the problem.

Returns:
spopt.locate.coverage.LSCP

Examples

>>> from spopt.locate import LSCP
>>> 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 LSCP instance from the cost matrix.

>>> lscp_from_cost_matrix = LSCP.from_cost_matrix(
...     cost_matrix, service_radius=8
... )
>>> lscp_from_cost_matrix = lscp_from_cost_matrix.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Get the facility lookup demand coverage array.

>>> for fac, cli in enumerate(lscp_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 0 clients
facility 4 serving 58 clients
classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, service_radius: float, predefined_facility_col: str = None, demand_quantity_col: str = None, facility_capacity_col: str = None, distance_metric: str = 'euclidean', name: str = 'lscp')[source]

Create an LSCP object from geopandas.GeoDataFrame objects. Calculate the cost matrix between demand and facility locations before building the problem within the from_cost_matrix() method. A capacitated version of the LSCP (the CLSCP-SO) can be solved by passing in the demand_quantity_col and facility_capacity_col keyword arguments.

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.

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].

demand_quantity_colstr

Column name representing amount of demand at each client location.

facility_capacity_arrstr

Column name representing capacity for service at each facility location.

distance_metricstr (default ‘euclidean’)

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

namestr (default ‘lscp’)

The name of the problem.

Returns:
spopt.locate.coverage.LSCP

Examples

>>> from spopt.locate import LSCP
>>> 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 LSCP instance from the GeoDataFrame objects.

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

Get the facility lookup demand coverage array.

>>> for fac, cli in enumerate(lscp_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
solve(solver: LpSolver, results: bool = True)[source]

Solve the LSCP model.

Parameters:
solverpulp.apis.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.LSCP