Network- and Demand-Driven Initialization Strategy for Enhanced Heuristic in Uncapacitated Facility Location Problem
As network scale and demand rise, the Uncapacitated Facility Location Problem (UFLP), a classical NP-hard problem widely studied in operations research, becomes increasingly challenging for traditional methods confined to formulation, construction, and benchmarking. This work generalizes the UFLP to...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/13/2138 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | As network scale and demand rise, the Uncapacitated Facility Location Problem (UFLP), a classical NP-hard problem widely studied in operations research, becomes increasingly challenging for traditional methods confined to formulation, construction, and benchmarking. This work generalizes the UFLP to network setting in light of demand intensity and network topology. A new initialization technique called Network- and Demand-Weighted Roulette Wheel Initialization (NDWRWI) has been introduced and proved to be a competitive alternative to random (RI) and greedy initializations (GI). Experiments were carried out based on the TRB dataset and compared eight state-of-the-art methods. For instance, in the ultra-large-scale Gold Coast network, the NDWRWI-based Neighborhood Search (NS) achieved a competitive optimal total cost (9,372,502), closely comparable to the best-performing baseline (RI-based: 9,189,353), while delivering superior clustering quality (Silhouette: 0.3859 vs. 0.3833 and 0.3752 for RI- and GI-based NS, respectively) and reducing computational time by nearly an order of magnitude relative to the GI-based baseline. Similarly, NDWRWI-based Variable Neighborhood Search (VNS) improved upon RI-based baseline by reducing the overall cost by approximately 3.67%, increasing clustering quality and achieving a 27% faster runtime. It is found that NDWRWI prioritizes high-demand and centrally located nodes, fostering high-quality initial solutions and robust performance across large-scale and heterogeneous networks. |
|---|---|
| ISSN: | 2227-7390 |