An Investigation into Exact Methods for the Continuous p?Centre Problem and its Related Problems

This thesis will analyse, investigate and develop new and interesting ideas to optimally solve a location problem called the continuous p?centre problem. This problem wishes to locate p facilities in a plane or network of n demand points such that the maximum distance or travel time between each demand point and its closest facility is minimised. Several difficulties are identified which are to be overcome to solve the continuous p?centre problem optimally. These relate to producing a finite set of potential facility locations or decreasing the problem size so that less computational time and effort is required. This thesis will examine several schemes that can be applied to this location problem and its related version with the aim to optimally solve large problems that were previously unsolved.

This thesis contains eight chapters. The first three chapters provide an introduction into location problems, with a focus on the p?centre problem. Chapter 1 begins with a brief history of location problems, followed by the various classifications and methodologies used to solve them. Chapter 2 provides a review of the methods that have been used to solve the p?centre problem, with a focus on the continuous p?centre problem. An overview of the location models used in this research is given in Chapter 3, alongside an initial investigative work.

The next two chapters enhance two well-known optimal algorithms for the continuous p?centre problem. Chapter 4 develops an interesting exact algorithm that was first proposed over 30 years ago. The original algorithm is reexamined and efficient neighbourhood reductions which are mathematically supported are proposed to improve its overall computational performance. The enhanced algorithm shows a substantial reduction of up to 96% of required computational time compared to the original algorithm, and optimal solutions are found for large data sets that were previously unsolved. Chapter 5 develops a relatively new relaxation-based optimal method. Four mathematically supported enhancements are added to the algorithm to improve its efficiency and its overall computational time. The revised reverse relaxation algorithm yields a vast reduction of up to 87% of computational time required, which is then used to solve larger data sets where n ? 1323 optimally.

Chapter 6 creates a new relaxation-based matheuristic, called the relaxed p' matheuristic, by combining a well-known heuristic and the optimal method developed in Chapter 5. The unique property of the matheuristic is that it deals with the relaxation of facilities rather than demand points to establish a sub-problem. The matheuristic yields a good, but not necessarily optimal, solution in a reasonable time. To guarantee optimality, the results found from the matheuristic are embedded into the optimal algorithms developed in Chapters 4 and 5.

Chapter 7 adapts the optimal algorithm developed in Chapter 5 to solve two related location problems, namely the ??neighbour p?centre problem and the conditional p?centre problem. The ??neighbour p?centre problem is investigated and solved where ? = 2 & 3. A scenario analysis is also conducted for managerial insights by exploring changes in the number of facilities required to cover each demand point. Furthermore, an existing algorithm for the conditional p?centre problem is enhanced by incorporating the optimal algorithm proposed in Chapter 5, and it is used to solve large data sets where the number of preexisting facilities is 20. This chapter therefore demonstrates that an algorithm developed in this research can be adapted or used to enhance existing algorithms to optimally solve more practical and challenging related location problems.

Finally, Chapter 8 summarises the findings and main achievements of this research, and outlines any further work that could be worthwhile exploring in the future.