The continuous p centre problem: formulation and solution techniques

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

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.