spopt.locate.PCenter

class spopt.locate.PCenter(name: str, problem: LpProblem, aij: array)[source]

Implement the \(p\)-center optimization model and solve it. The \(p\)-center problem, as adapted from [Das13], can be formulated as:

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle W && & (1) \\ \displaystyle \textbf{Subject To} & \displaystyle \sum_{j \in J}{X_{ij} = 1} && \forall i \in I & (2) \\ & \displaystyle \sum_{j \in J}{Y_j} = p && & (3) \\ & X_{ij} \leq Y_{j} && \forall i \in I \quad \forall j \in J & (4) \\ & W \geq \displaystyle \sum_{j \in J}{d_{ij}X_{ij}} && \forall i \in I & (5) \\ & X_{ij} \in \{0, 1\} && \forall i \in I \quad \forall j \in J & (6) \\ & Y_j \in \{0, 1\} && \forall j \in J & (7) \\ & && & \\ \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} \\ && d_{ij} & = & \textrm{shortest distance or travel time between locations } i \textrm{ and } j \\ && X_{ij} & = & \begin{cases} 1, \textrm{if client location } i \textrm{ is served by facility } j \\ 0, \textrm{otherwise} \\ \end{cases} \\ && Y_j & = & \begin{cases} 1, \textrm{if a facility is sited at location } j \\ 0, \textrm{otherwise} \\ \end{cases} \\ && W & = & \textrm{maximum distance between any demand site and its associated facility} \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.

aijnumpy.array

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

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, aij: array)[source]

Initialize.

Parameters:
namestr

The desired name for the model.

Methods

__init__(name, problem, aij)

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, p_facilities)

Create a PCenter object based on a cost matrix.

from_geodataframe(gdf_demand, gdf_fac, ...)

Create an PCenter object from geopandas.GeoDataFrame objects.

solve(solver[, results])

Solve the PCenter 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, p_facilities: int, predefined_facilities_arr: array = None, name: str = 'p-center')[source]

Create a PCenter object based on a cost matrix.

Parameters:
cost_matrix: numpy.array

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

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 ‘p-center’)

The problem name.

Returns:
spopt.locate.p_center.PCenter

Examples

>>> from spopt.locate import PCenter
>>> from spopt.locate.util import simulated_geo_points
>>> import geopandas
>>> 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 a PCenter instance from the cost matrix.

>>> pcenter_from_cost_matrix = PCenter.from_cost_matrix(
...     cost_matrix, p_facilities=4
... )
>>> pcenter_from_cost_matrix = pcenter_from_cost_matrix.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Get the facility-client associations.

>>> for fac, cli in enumerate(pcenter_from_cost_matrix.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 15 clients
facility 1 serving 24 clients
facility 2 serving 33 clients
facility 3 serving 0 clients
facility 4 serving 28 clients
classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, p_facilities: int, predefined_facility_col: str = None, distance_metric: str = 'euclidean', name: str = 'p-center')[source]

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

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 ‘p-center’)

The name of the problem.

Returns:
spopt.locate.p_center.PCenter

Examples

>>> from spopt.locate import PCenter
>>> from spopt.locate.util import simulated_geo_points
>>> import geopandas
>>> 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 a PCenter instance from the GeoDataFrame objects.

>>> pcenter_from_geodataframe = PCenter.from_geodataframe(
...     clients_snapped,
...     facilities_snapped,
...     "geometry",
...     "geometry",
...     p_facilities=4,
...     distance_metric="euclidean"
... )
>>> pcenter_from_geodataframe = pcenter_from_geodataframe.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Get the facility-client associations.

>>> for fac, cli in enumerate(pcenter_from_geodataframe.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 14 clients
facility 1 serving 26 clients
facility 2 serving 34 clients
facility 3 serving 0 clients
facility 4 serving 26 clients
solve(solver: LpSolver, results: bool = True)[source]

Solve the PCenter 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.p_center.PCenter