spopt.locate.KNearestPMedian¶
- class spopt.locate.KNearestPMedian(name: str, ai_sum: int | float, clients: array, facilities: array, weights: array, k_array: array, p_facilities: int, capacities: array = None, distance_metric: str = 'euclidean')[source]¶
Implement the P-Median Model with Near-Far Cost Allocation and solve it. The model is adapted from [Chu18], and can be formulated as:
\[\begin{split}\begin{array}{lllll} \displaystyle \textbf{Minimize} & \displaystyle \sum_{i \in I}\sum_{k \in k_{i}}{a_i d_{ik} X_{ik}} + \sum_{i \in I}{g_i (d_{i{k_i}} + 1)} && & (1) \\ \displaystyle \textbf{Subject To} & \sum_{k \in k_{i}}{X_{ik} + g_i = 1} && \forall i \in I & (2) \\ & \sum_{j \in J}{Y_j} = p && & (3) \\ & \sum_{i \in I}{a_i X_{ik}} \leq {Y_{k} c_{k}} && \forall k \in k_{i} & (4) \\ & X_{ij} \leq Y_{j} && \forall i \in I \quad \forall j \in J & (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} \\ && a_i & = & \textrm{service load or population demand at client location } i \\ && k_{i} & = & \textrm{the } k \textrm{nearest facilities of client location } i \\ && c_{j} & = & \textrm{the capacity of facility} j \\ && 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} \\ && g_i & = & \begin{cases} 1, \textrm{if the client } i \textrm{ needs to be served by non-k-nearest facilities} \\ 0, \textrm{otherwise} \\ \end{cases} \\ \end{array}\end{split}\]- Parameters:
- name
str The problem name.
- ai_sum
Union[int,float] The sum of weights representing the service loads of the clients.
- clients
np.array An array of coordinates of clients.
- facilities
np.array An array of coordinates of facilities.
- weights
np.array An array of weights representing the service loads of the clients.
- k_array
np.array An array of k values representing the number of nearest facilities for each client.
- p_facilities: int
The number of facilities to be located.
- capacities
np.arrayorNone An array of facility capacities. None if capacity constraints are not considered.
- distance_metric
str The distance metric used for computing distances between clients and facilities.
- name
- Attributes:
- sparse_matrix
CompressedSparseRowmatrix A cost matrix in the form of a compressed sparse row matrix between origins and destinations.
- aij
CompressedSparseRowmatrix A weighted cost matrix in the form of a compressed sparse row matrix between origins and destinations.
- problem
pulp.LpProblem A
pulpinstance 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
fac2cliwhere client to facility relationships are shown.
- sparse_matrix
- __init__(name: str, ai_sum: int | float, clients: array, facilities: array, weights: array, k_array: array, p_facilities: int, capacities: array = None, distance_metric: str = 'euclidean')[source]¶
Initialize.
- Parameters:
- name
str The desired name for the model.
- name
Methods
__init__(name, ai_sum, clients, facilities, ...)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(*args, **kwargs)Warning: This method is not supported in the KNearestPMedian subclass.
from_geodataframe(gdf_demand, gdf_fac, ...)Create the object of KNearestPMedian class using input data.
get_mean_distance()Calculate the mean distance.
solve(solver[, results])Solve the k-nearest p-median 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:
- classmethod from_cost_matrix(*args, **kwargs)[source]¶
Warning: This method is not supported in the KNearestPMedian subclass.
- 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, k_array: array = None, distance_metric: str = 'euclidean', name: str = 'k-nearest-p-median')[source]¶
Create the object of KNearestPMedian class using input data.
- Parameters:
- gdf_demand
GeoDataFrame A GeoDataFrame containing demand points with their associated attributes.
- gdf_fac
GeoDataFrame A GeoDataFrame containing facility points with their associated attributes.
- demand_col
str The column name in gdf_demand representing the coordinate of each client.
- facility_col
str The column name in gdf_fac representing the coordinate of each facility.
- weights_cols
str The column name in gdf_demand representing the weights for each client.
- p_facilities: int
The number of facilities to be located.
- facility_capacity_col
str, optional The column name in gdf_fac representing the capacity of each facility, by default None.
- k_array
np.array, optional An array of integers representing the k values for each client. If not provided, a default value of 5 or the number of facilities, whichever is smaller, will be used.
- distance_metric
str, optional The distance metric to be used in calculating distances between clients and facilities, by default “euclidean”.
- name
str, optional The name of the problem, by default “k-nearest-p-median”.
- gdf_demand
- Returns:
Examples
>>> from spopt.locate import KNearestPMedian >>> import geopandas
Create the input data and attributes.
>>> k = np.array([1, 1]) >>> demand_data = { ... 'ID': [1, 2], ... 'geometry': [Point(0.5, 1), Point(1.5, 1)], ... 'demand': [1, 1]} >>> facility_data = { ... 'ID': [101, 102], ... 'geometry': [Point(1,1), Point(0, 2), Point(2, 0)], ... 'capacity': [1, 1, 1]} >>> gdf_demand = geopandas.GeoDataFrame(demand_data, crs='EPSG:4326') >>> gdf_fac = geopandas.GeoDataFrame(facility_data, crs='EPSG:4326')
Create and solve a
KNearestPMedianinstance from the geodataframe.>>> k_nearest_pmedian = KNearestPMedian.from_geodataframe( ... gdf_demand, gdf_fac,'geometry','geometry', weights_cols='demand', ... 2, facility_capacity_col='capacity', k_array = k) >>> k_nearest_pmedian = k_nearest_pmedian.solve(pulp.PULP_CBC_CMD(msg=False))
Get the facility-client associations.
>>> for fac, cli in enumerate(k_nearest_pmedian.fac2cli): ... print(f"facility {fac} serving {len(cli)} clients") facility 0 serving 1 clients facility 1 serving 1 clients facility 2 serving 0 clients
Get the total and average weighted travel cost.
>>> round(k_nearest_pmedian.problem.objective.value(), 3) 1.618 >>> round(k_nearest_pmedian.mean_dist, 3) 0.809
Get the k values for the last iteration.
>>> print(k_nearest_pmedian.k_array) [2, 1]
- solve(solver: LpSolver, results: bool = True)[source]¶
Solve the k-nearest p-median model.
This method iteratively solves the
KNearestPMedianmodel using a specified solver until no more clients need to be assigned to placeholder facilities. Thekvalues for clients are increased dynamically based on the presence of clients not assigned toknearest facilities.- Parameters:
- Returns: