Solving Location Problems by Heuristics and Exact Algorithms

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

Facility location theory studies the placement of new facilities relative to a set of existing facilities. Of the several well-studied problems in the literature, the most popular one is probably the classical p-median problem. The objective here is to locate a given number, p, of new facilites in order to minimize a sum of weighted distances to the existing facilities. The new facilities could represent, for example, warehouses, the existing facilities - customers (or market areas), and the weights - anticipated demand or flow of goods or services to each customer. The sum of weighted distances between the customers and their "closest" new facility would be a useful performance measure for the total cost of satisfying the requirements of the customers. The p-centre problem, where the objective would be to minimize the maximum distance between the customers and their closest facilities would be an example of another performance measure that might be more pertinent to, say, the location of emergency facilities. The new facilities may be restricted to candidate sites giving rise to discrete (or network) models, or they may be located anywhere in continuous space. Irrespective of the type of solution space, most facility location models, including the two mentionned above, are very difficult to solve. Although exact algorithms exist, these are generally restricted to smaller problem instances. Heuristic (or approximate) solution methods are needed to solve larger instances that may arise in real-life problems where customers number in the thousands and several facilities are required. Location problems are not restricted to physical facilities either. In the areas of cluster analysis, regression analysis and data mining, for example, very large scale problems numbering in the millions of data points may be encountered, which may also be classified as location problems. The proposed research will develop and study new heuristics for solving continuous location problems such as the p-median problem. One new idea we wish to investigate will use discrete approximations of the continuous model within the solution approach. That is, any continuous model may be approximated by a network where specified nodes are identified as candidate sites for the new facilities and the distance between any pair of nodes (e.g., customer- facility pair) is measured by the specified distance function. In this way we may combine algorithms (exact or approximate) for discrete models with those used in the continuous space. However, to do this effectively, we need to better understand the relation between the two types of models. This in itself raises an interesting area of research that has hardly been touched in the literature. In the process we will have to investigate several basic questions. For example, how do we select an appropriate set of candidate sites to represent the continuous model? Can we provide good bounds on the solution quality obtained from a discrete approximation? What is the best way of combining the discrete and continuous components of the search? Other ideas and questions will also be investigated. For example, we are currently studying new ways of generating "good" starting solutions, and their impact on the quality of the final solution. Decomposition-based approaches with different neighbourhood structures will also be investigated. Another objective will be to incorporate the new local searches that we develop into higher-level algorithms. These various ideas will hopefully improve our understanding of the structure of continuous location models. For practitioners, we hope to develop more efficient solution approaches that will be capable of finding higher-quality solutions in reasonable computing time.