The continuous p centre problem: formulation and solution techniques

点击翻译按钮获取中文摘要

Locating police stations, ambulance stations or fire stations is a complex task for public sector decision makers either in government or local government. This is a complex decision problem in operational research and computer science. The problem is to minimise the maximum distance or travel time to the furthest customer or user from the selecetd sites (in other words, we need to reach the crime scene before it is too late). When the potential sites are known before hand the problem becomes the vertex p center problem (where p refers to the number of facilites that need to be found). In some situations it is difficult to evaluate and enumerate a large number of possible sites due to the cost involved to gather all the necessary data. We aim to study the continuous case instead whose solution will provides us with an optimal but 'ideal' locations that could be infeasible (locating on top of an existing school!). However this invaluable information can then be used to guide the user in the gathering of those promising potential sites which will not be as many and hence will cost less. When sloving the discrete case, this could also reduce the feasible region when solving the problem optimally. In addition, the optimal solution could also be used for benchmarking purposes as lower bounds. We intent to study this combinatorial problem by developing new approximative methods known as heuristic search that provide good solutions within a certain amount of computing time. This will be based on the well established variable neighbourhood search and GRASP and their integration with an exact mathematical formulation. As the search space is continuous, ie. on the plane, adaptations to defining the neighbourhoods need to be developed. The proposed approach will be extended to cater for the bi-objective problem where both conflicting objectives namely the minisum and the minimax are considered simultaneously.