TL;DR
This paper tackles the complex problem of simultaneously deciding which new facilities to open and which existing ones to close, all while adhering to a budget and a target number of facilities. They introduce a novel mathematical model and develop three efficient heuristic algorithms (greedy interchange, tabu search, and Lagrangian relaxation) to find near-optimal solutions for this NP-hard problem, demonstrating their effectiveness on a real-world bank branch location scenario.
What Problem Does This Paper Address?
Businesses often face the challenge of optimizing their facility network in response to changing customer demand or market conditions. A common scenario involves deciding whether to open new locations or close underutilized existing ones. However, these decisions are rarely made in isolation. This paper addresses the "budget-constrained facility relocation problem," where a company must simultaneously decide which new facilities to open and which existing facilities to close, subject to a limited budget for these actions and a desired total number of open facilities. This is crucial for service industries like banking, where inefficient branch placement can lead to customer dissatisfaction and increased operational costs. The problem is particularly challenging because it combines aspects of both the p-median problem (finding optimal locations for a fixed number of facilities) and the uncapacitated facility location problem (deciding which facilities to open from a set of potential sites).
Methods
The authors formulate the problem as a mathematical program and then develop three heuristic algorithms to find approximate solutions, as the problem is NP-hard.
- Mathematical Formulation: They define binary variables for opening/closing facilities and assigning customers to facilities. The objective is to minimize total weighted travel distance, subject to budget constraints for opening/closing and a constraint on the total number of open facilities.
- Greedy-Interchange (GI) Heuristic: This algorithm operates in two phases. The first phase greedily adds or removes facilities to reach the target number of open facilities, prioritizing cost-effectiveness. The second phase then attempts to improve the solution by swapping an open facility with a closed one if it leads to a better objective function value and stays within budget.
- Tabu Search (TS) Approach: This method builds upon the GI heuristic's interchange phase. Instead of stopping at the first local optimum, it uses a tabu list to explore other potential solutions, preventing the algorithm from revisiting recently explored swaps and allowing it to escape local optima.
- Lagrangian Relaxation (LR) Approximation: This approach relaxes the constraints on the number of open facilities and the budget. By solving the relaxed problem and using a subgradient algorithm, it generates an $\epsilon$-optimal solution, meaning the solution is guaranteed to be within a certain percentage of the true optimum.
Datasets
The study uses a realistic network derived from the Town of Amherst, New York, for computational testing. This dataset includes:
- 459 customer nodes with weights derived from 1991 US Census data.
- 84 potential facility sites.
- Ten weighted distance matrices generated by perturbing Euclidean distances.
- Randomly generated opening and closing costs.
The authors also mention testing on four randomly generated large-scale problems.
Key Insights and Ideas
- Simultaneous Opening and Closing is Crucial: The paper highlights that in many real-world scenarios, opening new facilities and closing existing ones cannot be treated independently. A holistic approach is necessary for effective network optimization.
- Heuristics Offer a Practical Trade-off: For NP-hard problems like this, exact methods can be computationally prohibitive. The developed heuristics (GI, TS, LR) provide a practical way to obtain good quality solutions in a reasonable amount of time.
- Lagrangian Relaxation Guarantees Quality: While GI and TS are faster, LR offers a valuable guarantee on solution quality (within 2% of optimal), making it suitable when precision is paramount.
- Budget and Facility Count are Key Drivers: The study shows that the interplay between the budget and the desired number of facilities significantly influences the problem's complexity and the potential for simultaneous opening and closing.
Key Results
- High Performance of Heuristics: All three heuristics performed very well, with average errors across all tested problems being:
- GI heuristic: 0.46%
- TS approach: 0.25%
- LR approximation: 0.27%
- Efficiency: The GI heuristic was the fastest, followed by TS, and then LR. For large-scale problems, the heuristics were significantly faster than CPLEX and could solve problems that CPLEX could not due to memory limitations.
- Solution Quality Trade-off: The TS approach generally provided better solutions than the GI heuristic, while the LR approximation offered a guarantee on solution quality.
- Consolidation vs. Expansion: The GI and TS approaches were particularly effective in scenarios where the number of open facilities was decreasing (p ≤ q), indicating their suitability for consolidation strategies.
Limitations and Future Work
- Unlimited Capacity Assumption: The current model assumes facilities have unlimited capacity, which is not realistic. Future research should explore versions of the problem with capacity constraints.
- Probabilistic Demand and Queueing: The paper suggests examining probabilistic versions of the problem, especially when queue capacity is a concern.
- Negative Closing Costs: Investigating scenarios with negative closing costs (where savings are accrued annually) could be relevant.
- Variable Operating Costs: Extending the model to handle facility-specific operating costs per unit of customer demand is a promising area for future research, potentially requiring branch-and-bound approaches.
Summary updated