Web pages of Lars Relund Nielsen

PhD thesis: Discrete Location Problems – Theory, Algorithms, and Extensions to Multiple Objectives

Sune one of my PhD students has just finished his defense of his thesis titled “Discrete Location Problems – Theory, Algorithms, and Extensions to Multiple Objectives“. I would like to congratulate Sune with his PhD title and for a good presentation at the defense. I have included the thesis summary below.

Summary

This PhD–dissertation proposes a number of solution procedures for discrete facility location problems. In the literature of operations research, location problems are mathematical models describing optimization problems where one or more facilities need to be placed in relation to a given set of customers or demand points. An example is the location of hospitals which needs to be performed in such a way as to take into account capacity limits and the sizes of nearby towns and cities.

The dissertation particularly focuses on the so–called single–source capacitated facility location problem (SSCFLP). The problem consists in opening a set of facilities and allocating the customers’ demands to these open facilities in such a way that the capacity of each facility is respected and such that each customer is serviced from exactly one open facility. An optimal solution to the SSCFLP is a solution in which the total cost of opening facilities and servicing customers is minimized. In this problem, it is assumed that all costs and the customers’ demand and the capacity of the facilities are fixed and known. The dissertation proposes new solution procedures for both single objective as well as bi– objective versions of the SSCFLP. The dissertation considers exact methods that guarantee an optimal solution. When two objective functions are optimized simultaneously, an optimal solution consists of a set of solutions which maps into the entire set of non–dominated outcome vectors.

The first chapter of the dissertation provides a historic overview of location problems and a short survey of the literature on discrete multi–objective facility location.

The second chapter proposes an improved cut–and–solve based algorithm for the SSCFLP. The algorithm is effective and turns out to be up to 40 times faster compared to state–of–the–art algorithms from the literature.

The third chapter describes two algorithms that integrates the cut–and–solve framework with a semi–Lagrangean dual ascent algorithm in order to solve large instances of the SSCFLP. The first algorithm uses a variant of the cut–and–solve algorithm proposed in Chapter 2 to solve subproblems arising in the dual ascent algorithm whereas the second solves the sparse problems of the cut–and–solve algorithm using a semi–Lagrangean based dual ascent algorithm.

In the last two chapters (Chapter 4 and Chapter 5) of the dissertation, bi–objective location problems are considered. In Chapter 4, a so–called bi–objective “cost–bottleneck” location problems is studied. The problem minimizes two objective functions simultaneously. The first minimizes the total cost while the second minimizes the maximal transportation time from a customer to a nearest open facility. An “$\epsilon$–constrained algorithm is proposed which preserves the structure of the underlying location problem. In the last chapter of the dissertation, Chapter 5, branch-and-cut algorithms for bi-objective optimization are developed. The proposed algorithms rely on explicitly and implicitly given lower bound sets and compute all rational compromises between the cost of opening facilities and the cost incurred by servicing the customers.

Leave a Reply