spopt.locate.PMedian¶

class spopt.locate.PMedian(name: str, problem: LpProblem, aij: array, weights_sum: int | float)[source]¶

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

\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{i \in I}\sum_{j \in J}{a_i d_{ij} X_{ij}} && & (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) \\ & X_{ij} \in \{0, 1\} && \forall i \in I \quad \forall j \in J & (5) \\ & Y_j \in \{0, 1\} && \forall j \in J & (6) \\ & && & \\ \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} \\ && a_i & = & \textrm{service load or population demand at client location } i \\ && 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} \\ \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, weights_sum: int | float)[source]¶

Initialize.

Parameters:

namestr: The desired name for the model.

Methods

`__init__`(name, problem, aij, weights_sum)	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 `PMedian` object based on a cost matrix.
`from_geodataframe`(gdf_demand, gdf_fac, ...)	Create an `PMedian` object from `geopandas.GeoDataFrame` objects.
`get_mean_distance`()	Calculate the mean distance.
`solve`(solver[, results])	Solve the `PMedian` 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, weights: array, p_facilities: int, predefined_facilities_arr: array = None, facility_capacities: array = None, fulfill_predefined_fac: bool = False, name: str = 'p-median')[source]¶

Create a PMedian object based on a 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.
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].
facility_capacitynumpy.array (default None): The capacity of each facility.
fulfill_predefined_facbool (default False): If the predefined facilities need to be fulfilled.
namestr (default ‘p-median’): The problem name.

Returns:

spopt.locate.p_median.PMedian

Examples

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

>>> pmedian_from_cost_matrix = PMedian.from_cost_matrix(
...     cost_matrix, ai, p_facilities=4
... )
>>> pmedian_from_cost_matrix = pmedian_from_cost_matrix.solve(
...     pulp.PULP_CBC_CMD(msg=False)
... )

Get the facility-client associations.

>>> for fac, cli in enumerate(pmedian_from_cost_matrix.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 14 clients
facility 1 serving 29 clients
facility 2 serving 31 clients
facility 3 serving 0 clients
facility 4 serving 26 clients

Get the total and average weighted travel cost.

>>> round(pmedian_from_cost_matrix.problem.objective.value(), 3)
1870.747
>>> round(pmedian_from_cost_matrix.mean_dist, 3)
3.027

classmethod from_geodataframe(gdf_demand: GeoDataFrame, gdf_fac: GeoDataFrame, demand_col: str, facility_col: str, weights_cols: str, p_facilities: int, facility_capacity_col: str = None, predefined_facility_col: str = None, fulfill_predefined_fac: bool = False, distance_metric: str = 'euclidean', name: str = 'p-median')[source]¶

Create an PMedian 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.
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].
facility_capacities_col: str (default None): Column name representing the capacities of each facility.
fulfill_predefined_facbool (default False): If the predefined facilities need to be fulfilled.
distance_metricstr (default ‘euclidean’): A metric used for the distance calculations supported by scipy.spatial.distance.cdist.
namestr (default ‘p-median’): The name of the problem.

Returns:

spopt.locate.p_median.PMedian

Examples

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

Simulate demand weights from 1 to 12.

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

Create and solve a PMedian instance from the GeoDataFrame object.

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

Get the facility-client associations.

>>> for fac, cli in enumerate(pmedian_from_geodataframe.fac2cli):
...     print(f"facility {fac} serving {len(cli)} clients")
facility 0 serving 13 clients
facility 1 serving 29 clients
facility 2 serving 31 clients
facility 3 serving 0 clients
facility 4 serving 27 clients

solve(solver: LpSolver, results: bool = True)[source]¶

Solve the PMedian 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_median.PMedian