Chapter 7 Multi-capacitated Location Problem: A New Resolution Method Combining Exact and Heuristic Approaches Based on Set Partitioning

摘要

In this paper, we present one generalization of the famous capacitated p-median location problem, called budget constraint multi-capacitated location problem (MCLP). This new generalization is characterized by allowing each facility to be used with different capacity levels. The MCLP solution can be represented as a set of disjoint clusters (pair of one facility and a subset of customers). Creating these clusters satisfies implicitly some constraints of the problem. In this work, we present the new formulation of the MCLP based on set partitioning, then we suggest an adapted solving method, which will be called NFF (Nearest Facility First). This new method can be used in two ways: as a heuristic by taking only the first solution found or exact approach when waiting finished the execution. Computational results are presented at the end using instances that we have created under some criteria of difficulties or adapted from those of p-median problems available in literature. The NFF method provides very good results for low and medium difficulty instances, but it is less effective for the more complex ones. To remedy this problem, the method will be supplemented by column generation approach.