Generalization of capacitated p-median location problem: Modeling and resolution

摘要

The capacitated p-median location problem (CPMP) is very famous in literature and widely used within industry scope. However, in some cases, this location problem variant has poor management of capacity resources. In fact, the capacity used by facilities is fixed and not dependent on customers' demands. The budget constraint Multi-Capacitated Location Problem (MCLP), considered in that paper, is a generalization of the CPMP problem, it is characterized by allowing each facility to be open with different capacities. In this paper, we will discuss the mathematical modeling of the MCLP problem, then we suggest adapted solving methods. To do this, we propose to solve the MCLP problem using Branch and Cut method. This exact solving method well-known, will serve us to test and validate our new problem formulation. Then we will build one heuristic algorithm, well adapted to our problem, it will be called GCDF (Greatest Customer Demand First). For improving solution quality, the LNS method will complete the GCDF. 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 GCDF (GCDF improved) algorithm is fast and provides good results for most degree of difficulty instances, but it is unreliable for very specific cases. To remedy this problem, the method must start with a basic feasible solution determined by one of the reliable method such as Branch and Bound.