Facility Location

The facility location problem chooses where to open facilities, such as warehouses or clinics, to serve a set of demand points at minimum total cost, balancing facility opening costs against customer service distances. Most variants, including k-median and k-center, are NP-hard.

How it works

Practical solvers combine several ideas. Greedy algorithms open the facility with the best cost-per-covered-demand ratio and achieve provable approximation guarantees. Local search swaps open and closed facilities while improvement is possible. Exact solutions for moderate sizes use mixed integer programming, and large instances use Lagrangian relaxation or clustering-based heuristics such as k-means to seed candidate sites.

Applications

Facility location decides warehouse and distribution center placement in supply chains, cell tower and EV charging coverage, hospital and fire station siting for emergency response, and content delivery server placement. It is a flagship problem of operations research and logistics analytics.