Heuristics for a facility location problem with a quadratic objective function

Heuristics for a facility location problem with a quadratic objective function

Schmidt, Malena (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Delft Institute of Applied Mathematics; TU Delft Discrete Mathematics and Optimization)

van Essen, J.T. (mentor)
Singh, Bismark (graduation committee)
Fokkink, R.J. (graduation committee)

Delft University of Technology

Applied Mathematics

2023-07-11

Facility location problems are an important set of problems within the field of optimisation. These problems consider which facilities to open out of a set of possible facilities and how to assign users to the open facilities. Most of the facility location problems studied have a linear objective. In this thesis, we consider a facility location problem with a quadratic objective, the Balanced Facility Location Problem (BFLP). This problem, and facility location problems in general, quickly becomes difficult to solve for standard MIP solvers as the input size increases. The difficulty of this problem is further supported by it being a NP-hard problem.

Hence, we develop three heuristics for the BFLP: two greedy heuristics and one local search heuristic. These heuristics are adapted from heuristics used for the standard Capacitated Facility Location Problem (CFLP).

The idea behind the first greedy heuristic is to close one facility at a time, starting with all facilities being open, until we have as many facilities open as the budget constraint of the BFLP dictates. At each step, the best facility to close is closed. Apart from adapting this heuristic to accommodate the slightly different constraints of the BFLP, we also make some further adjustments in order to reduce the running time.

The second heuristic that we adapt is a heuristic that instead of closing facilities one at a time, opens facilities one by one, until we reach the budget of open facilities that the BFLP allows. These simple heuristics perform very well in practice on both small and large instances of the BFLP.

Lastly, we discuss a local search heuristic, which attempts to improve a solution to the BFLP by opening one facility and closing another facility at each iteration. The local search only improves marginally upon the results of the greedy algorithms.

For use within the heuristics for the BFLP, we require fast heuristics to solve a subproblem of the BFLP, the problem of assigning users to facilities where the set of open facilities is fixed. Hence, we develop three heuristics for this subproblem and also adapt a previously developed heuristic to be optimised for its use within the BFLP heuristics.

Our heuristics achieve results that are similar or better than what a MIP solver achieves and find a good solution in significantly less time. Especially when the MIP solver struggles, due to the size or limited capacity of the BFLP instance, our heuristics are able to outperform the MIP solver.

Facility location problem
MIP
Heuristics
Optimisation

http://resolver.tudelft.nl/uuid:7186c978-1f4f-4207-a391-1541a3f8dfd3

Student theses

master thesis

© 2023 Malena Schmidt