The continuous p centre problem: formulation and solution techniques

对于政府或地方政府的公共部门决策者来说，确定警察局、救护站或消防站的位置是一项复杂的任务。这是运筹学和计算机科学中的一个复杂决策问题。问题是最大限度地减少从选定地点到最远客户或用户的最大距离或旅行时间（换句话说，我们需要在为时已晚之前到达犯罪现场）。当潜在的网站是已知的手的问题成为顶点p中心的问题（其中p是指需要找到设施的数量）。在某些情况下，由于收集所有必要数据所涉及的成本，很难评估和列举大量可能的地点。我们的目标是研究连续的情况下，而不是其解决方案将为我们提供一个最佳的，但“理想”的位置，可能是不可行的（位于现有的学校！）。然而，这些宝贵的信息可以用来指导用户收集那些有希望的潜在网站，这些网站不会那么多，因此将花费更少。当解决离散的情况下，这也可以减少可行域时，最佳解决问题。此外，最优解也可以用于基准测试目的作为下限。我们打算通过开发新的近似方法来研究这个组合问题，这些方法被称为启发式搜索，可以在一定的计算时间内提供良好的解决方案。这将基于完善的可变邻域搜索和GRASP及其与精确数学公式的集成。由于搜索空间是连续的，即。在平面上，需要发展适应性办法，以界定邻里。所提出的方法将扩展到满足双目标问题，即同时考虑两个相互冲突的目标，即最小和最小最大。

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.