Stochastic Capacitated Facility Location Problem (SCFLP)
- Category
- Network Design & Location
- Formulation
- Stochastic
- Objective
- Minimize
- Time limit
- 60 s per instance
- Paper
- Strengthened Benders Cuts for Stochastic Integer Programs with Continuous RecourseMerve Bodur, Sanjeeb Dash, Oktay Günlük, James Luedtke · INFORMS Journal on Computing, 2016
Description
A logistics company must decide which facilities to open among a set of potential facility locations in order to serve a set of customers whose demands are uncertain. There are a given number of potential facilities and a given number of customers. Uncertainty in customer demands is captured through a finite set of scenarios, each occurring with a known probability (all scenarios are equally likely when the scenario set is generated by sampling). The company must commit to facility opening decisions before observing which demand scenario materializes; once a scenario is realized, the company allocates supply from open facilities to customers.
Each potential facility has a fixed opening cost and a maximum capacity. Each customer has a demand that varies across scenarios; the demand of each customer under each scenario is provided as input. For each facility-customer pair, a unit transportation cost is given, representing the cost of shipping one unit of product from that facility to that customer. The input data also includes the probability associated with each scenario.
The company must make two kinds of choices. First, for each potential facility, it must decide whether or not to open it. Second, for each scenario, it must determine how much of each customer's demand is served by each open facility. The facility opening decisions are made before the demand scenario is known, while the allocation decisions are made after the scenario is revealed.
Every customer's demand must be fully satisfied in every scenario: the total amount shipped to a customer from all facilities must be at least as large as that customer's demand under the given scenario. In each scenario, the total amount shipped from any facility across all customers may not exceed that facility's capacity if the facility is open, and must be zero if the facility is not open. Additionally, the total capacity of all opened facilities must be at least as large as the maximum total customer demand across all scenarios, ensuring that the company can always serve all customers regardless of which scenario occurs.
The goal is to minimize total expected cost, defined as the sum of the fixed opening costs of all opened facilities plus the expected (probability-weighted average over all scenarios) total transportation cost of shipping goods from facilities to customers.
Instance schema
{
"num_facilities": "<int> Number of candidate facility locations.",
"num_customers": "<int> Number of customers whose demand must be satisfied.",
"num_scenarios": "<int> Number of demand scenarios considered.",
"capacity_factor": "<float> Ratio of total facility capacity to total expected demand, controlling how tight capacity is.",
"variance_level": "<str> Level of demand variability across scenarios ('normal' or 'high').",
"facilities": [
{
"id": "<int> Zero-based index identifying the facility.",
"opening_cost": "<float> Fixed cost incurred if this facility is opened.",
"capacity": "<float> Maximum total units this facility can ship across all customers in any scenario.",
"location_x": "<float> X-coordinate of the facility location, used to compute transportation costs.",
"location_y": "<float> Y-coordinate of the facility location, used to compute transportation costs."
}
],
"customers": [
{
"id": "<int> Zero-based index identifying the customer.",
"deterministic_demand": "<float> Expected (mean) demand of this customer.",
"demand_std_fraction": "<float> Ratio of demand standard deviation to mean demand for this customer.",
"location_x": "<float> X-coordinate of the customer location, used to compute transportation costs.",
"location_y": "<float> Y-coordinate of the customer location, used to compute transportation costs."
}
],
"transportation_costs": "<list[list[float]], shape [num_facilities][num_customers]> Per-unit cost of shipping from each facility to each customer, equal to the Euclidean distance between them.",
"scenarios": [
{
"id": "<int> Zero-based index identifying the scenario.",
"probability": "<float> Probability of this scenario occurring.",
"demands": "<list[float], length num_customers> Realized demand of each customer under this scenario."
}
]
}Solution schema
{
"objective_value": "<float> Total expected cost combining facility opening costs and the probability-weighted transportation costs across all demand scenarios.",
"open_facilities": "<list[int]> Identifiers of the facilities selected to be opened.",
"x": "<dict, key: '{facility}'> Whether each facility is opened (1 = opened, 0 = closed).",
"y": "<dict, nested keys: '{scenario}' -> '{facility}' -> '{customer}'> Quantity shipped from each facility to each customer under each demand scenario."
}Public instances
For development. Scoring uses private instances, which are never published. Sign in to download them.
- large_instance_1.json60 s
- tiny_instance.json60 s
Checker
The checker our evaluation runs, from the FrontierOR benchmark (CC BY 4.0) with the recomputed objective added to its result. How to run it. Sign in to download it.
- feasibility_check.py