Source-linked AI summary
Distributionally Robust Facility Location Problem under Decision-dependent Stochastic Demand
Beste Basciftci, Shabbir Ahmed, Siqian Shen
TL;DR
The paper addresses facility location under uncertain demand whose distribution changes with location decisions. It models decision-dependent demand moments with a distributionally robust formulation and derives an exact mixed-integer linear reformulation with strengthening inequalities. Computational results report higher profit and lower unmet demand than decision-independent stochastic and robust approaches.
Problem
Facility location planning must account for uncertain customer demand whose distribution depends on facility-location decisions.
Method
The paper models demand mean and variance as piecewise linear functions of facility decisions and derives an exact mixed-integer linear reformulation strengthened by valid inequalities.
Results
18% and 12% improvement in profit and 99% and 96% reduction in unmet demand are reported against SP and DR for instances with 10 facilities.
Takeaways & Limitations
Considering location-driven demand uncertainty improves profit and quality of service relative to decision-independent approaches across the reported computational tests.
Takeaways & Limitations
The model assumes unmet-demand penalties exceed transportation costs and uses capacity predivided among customer sites, with equal site allocations as a simplification.
Abstract
from arXiv · showhide
Facility location decisions significantly impact customer behavior and consequently the resulting demand in a wide range of businesses. Furthermore, sequentially realized uncertain demand enforces strategically determining locations under partial information. To address these issues, we study a facility location problem where the distribution of customer demand is dependent on location decisions. We represent moment information of stochastic demand as a piecewise linear function of facility-location decisions. Then, we propose a decision-dependent distributionally robust optimization model, and develop its exact mixed-integer linear programming reformulation. We further derive valid inequalities to strengthen the formulation. We conduct an extensive computational study, in which we compare our model with the existing (decision-independent) stochastic and robust models. Our results demonstrate superior performance of the proposed approach with remarkable improvement in profit and quality of service by extensively testing problem characteristics, in addition to computational speed-ups due to the formulation enhancements. These results draw attention to the need of considering the impact of location decisions on customer demand within this strategic-level planning problem.
1 Introduction
Facility location decisions influence customer demand, while demand is uncertain during planning. The paper models this dependency through a decision-dependent distributionally robust facility-location framework and evaluates its performance against decision-independent approaches.
- Nearby facilities can boost customer demand, making demand a strategic input to facility-location planning.
- Demand forecasts alone may produce inaccurate facility-location decisions because they do not fully capture underlying uncertainty.
- The paper proposes a distributionally robust facility-location problem in which demand uncertainty depends on facility-location decisions.
- Mean and variance information for random demand are represented as piecewise linear functions of facility-location decisions.
- The model has an exact mixed-integer linear reformulation and valid inequalities that strengthen its formulation.
2 Literature Review
Prior facility-location and uncertainty-optimization research addresses applications, stochastic or robust uncertainty, and decision-dependent uncertainty in related settings. The paper identifies a gap in formally modeling location-driven demand uncertainty within facility location and deriving tractable decision-dependent DRO reformulations.
- Facility-location research covers warehouses, distribution centers, emergency medical services, and connected-city infrastructure.
- Stochastic programming uses known distributional information or sampled demand scenarios, while DRO addresses uncertainty through ambiguity sets.
- Existing studies use moment-based ambiguity sets but do not capture the possible impact of location decisions on uncertain parameters.
- DRO ambiguity sets include statistical distance measures such as φ-divergence, Wasserstein distance, and the Levy-Prokhorov metric.
- Decision-dependent uncertainty research distinguishes decisions that change information timing from decisions that change the uncertainty distribution.
- Robust optimization incorporates decision-dependent uncertainty sets across applications including software partitioning, radiotherapy, and offshore oil planning.
- The paper addresses the unstudied combination of facility-location demand dependency and tractable decision-dependent DRO reformulation.
3 Problem Formulation
The formulation makes demand moments depend on facility-opening decisions, constructs a moment-based ambiguity set, and reformulates the resulting DRO model as a strengthened mixed-integer linear program.
- 3 Problem Formulation: The model represents demand distributions as functions of facility-location decisions and introduces a decision-dependent DRO formulation.
- 3.1 Ambiguity set formulation: Demand support is finite, with customer-site demand probabilities defined over a common support set of possible demand values.
- 3.1 Ambiguity set formulation: The ambiguity set constrains probabilities, mean deviations, and second moments around decision-dependent mean and variance information.
- 3.1 Ambiguity set formulation: Mean demand increases with nearby facility openings, while variance decreases with neighborhood facilities but remains bounded below by inherent market uncertainty.
- 3.1 Ambiguity set formulation: Distance-weight parameters allow closer facilities to have greater effects on demand moments, with cases ranging from no impact to closest-facility-only impact.
- 3.2 DRO model and reformulation: The objective minimizes facility, transportation, and unmet-demand costs net of revenue, subject to demand assignment and facility-capacity constraints.
- 3.2 DRO model and reformulation: The formulation assumes capacity is predivided among customer sites and simplifies to equal customer-site capacity allocations.
- 3.2 DRO model and reformulation: A closed-form inner solution and duality-based reformulation produce an exact mixed-integer linear program by linearizing bilinear and trilinear terms with auxiliary variables and McCormick constraints.
4 Computational Studies
The computational studies compare the decision-dependent DRO approach with decision-independent DR and stochastic programming approaches. They evaluate solutions through out-of-sample demand scenarios across multiple demand and modeling conditions.
- The study compares decision-dependent DRO solutions with facility-location plans from DR and stochastic programming models that neglect decision dependency.
- Out-of-sample evaluation uses Monte Carlo sampling and Sample Average Approximation to generate demand realizations from each location plan’s moment information.
- The evaluation model assigns scenario demand to facilities or records it as unsatisfied while enforcing facility-capacity limits.
- Experiments vary demand variability, unmet-demand penalties, robustness levels, facility-count limits, and decision-dependent distribution models.
4.1 Experimental Setup
The experiments use randomly generated facility and customer locations, with demand moments and decision-dependency parameters calibrated from location distances. The study evaluates the proposed framework across varied model parameters and demand distributions using multiple optimization approaches.
- Instance generation: Facility and customer locations are randomly generated, with Euclidean distances determining transportation-cost parameters c_ij.The default parameter settings remain fixed across numerical studies unless otherwise stated.
- Demand specification: Demand means are sampled from U(20, 40), with standard deviations set equal to means, yielding a coefficient of variation of 1.The demand support size is K = 100, with demand values ranging from 1 to 100.
- Decision-dependent demand: Decision dependency is modeled using distance-based parameters proportional to exp(−c_ij/25), so closer facilities exert greater effects on customer demand.The parameter vectors are normalized for each customer site.
- Benchmark formulation: Setting all λ^μ_ji values to zero reduces the model to a decision-independent, traditional distributionally robust optimization formulation.
- Computational study: The numerical study varies model parameters and underlying demand distributions while comparing the proposed and existing optimization approaches.All models are implemented in Python with Gurobi 7.5.2 and run on an Intel i5-3470T 2.90 GHz machine with 8 GB RAM.
4.2 Numerical Results and Analyses
The study evaluates stochastic, robust, and decision-dependent distributionally robust facility-location approaches across demand variability, distributional misspecification, penalty settings, robustness levels, and facility-opening limits. Across these tests, DDDR generally provides stronger profit and service outcomes, with its advantage depending on the demand and capacity setting.
- DDDR improves profit by 18% and 12% and reduces unmet demand by 99% and 96% versus SP and DR, respectively, for instances with 10 facilities.The comparison evaluates average optimal objective and unmet demand across test scenarios.
- DDDR achieves the best optimal-objective and unmet-demand results in the specific-instance comparison, while DR outperforms SP on percentile values.The evaluation reports averages, standard deviations, and percentiles over 1000 test scenarios.
- Effect of variability in demand: As demand variability increases, DR and DDDR become more suitable than SP, whose solution performance worsens monotonically.Variability is represented by the coefficient of variation while empirical mean demand remains fixed.
- Distributional misspecification: Under Gamma-distributed test demand, percentile results worsen for all approaches, but DDDR remains best across average, standard-deviation, and percentile measures.SP cannot capture changes in the underlying distribution, whereas DR and DDDR are less affected.
- Effect of unit penalty setting: Increasing the unmet-demand penalty decreases unmet demand for all approaches, while DDDR outperforms DR and SP in objective value and unmet demand across settings.At small penalties, DR opens fewer facilities and overlooks demand increases caused by opening facilities.
- Robustness and facility-opening limits: Higher robustness increases variability and worsens percentile outcomes, but DDDR and DR retain the same location plans across several robustness levels.DDDR is less affected by increased robustness than the default setting, and its advantage grows when the facility-opening limit is relaxed.
4.3 Results of computational time
The distributionally robust approaches require more computation than stochastic programming, while DDDR is especially sensitive to instance size. Adding valid inequalities produces measurable computational speed-ups.
- SP is the fastest approach, while DR and DDDR require more computational time.DDDR runtime is more sensitive to instance size despite better cost and demand-satisfaction performance.
- DDDR runtime depends on the upper bounds of its dual variables, set to 100 in all experiments.
- 3%–19% speed-ups result from adding the proposed valid inequalities across different instance sizes.The comparison uses 10 randomly generated instances for each size against the formulation without the inequalities and associated variables and constraints.
5 Conclusion
The paper develops a distributionally robust facility-location framework in which demand distributions depend on facility decisions. Its exact reformulation and valid inequalities support computationally tractable evaluation, with consistently higher profit and less unmet demand than existing stochastic approaches.
- The framework models demand moments as piecewise linear functions of facility-location decisions within a moment-based ambiguity set.
- Duality and convex envelopes yield an exact mixed-integer linear reformulation, strengthened by valid inequalities.
- The proposed approach consistently achieves higher profit and less unmet demand than existing stochastic programming approaches across tested instances.