Network- and Demand-Driven Initialization Strategy for Enhanced Heuristic in Uncapacitated Facility Location Problem

Jayson Lin, Shuo Yang (), Kai Huang (), Kun Wang and Sunghoon Jang
Additional contact information
Jayson Lin: School of Civil Engineering, Anhui JianZhu University, Hefei 230601, China
Shuo Yang: School of Civil Engineering, Anhui JianZhu University, Hefei 230601, China
Kai Huang: School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China
Kun Wang: School of Civil Engineering, Anhui JianZhu University, Hefei 230601, China
Sunghoon Jang: Department of Civil and Environmental Engineering, The Hong Kong Polytechnic University, Hong Kong 999077, China

Mathematics, 2025, vol. 13, issue 13, 1-31

Abstract: 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.

Keywords: stochastic optimization; heuristic algorithm; network-based uncapacitated facility location problem; constructive method; demand intensity; network topology (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/13/2138/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/13/2138/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:13:p:2138-:d:1691154

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().