Facility Location

The facility location problem is a classical optimisation problem that can be solved using a technique called Benders’ decomposition. Similar to the Column Generation approach, Benders’ decomposition considers only a reduced version of the problem. In this case, the reduced version is to identify the where to open facilities without considering the customer demand. This problem is called the first stage problem. Once the first stage problem is solved and the decision to open facilities has been made, then it is checked whether the customer demands can be satisfied. This checking process is called the second stage. Using the information gained from this checking process (the second stage), the first stage is then resolved to find an alternative set of facilities to open. The algorithm for Benders’ decomposition alternates between the first and second stages until it is determined that the selected facilities can be used to best satisfy the customer demand.

The facility location problem has been repeatedly used in practice for many different applications. In addition to determining docking station locations, the facility location problem can be used to determine where to place telecomunication exchanges, health care services, such as hospitals and GP surgeries, and warehouses for large online delivery stores, such as Amazon.