Facility Location Problem with Minimum Capacity Constraints

摘要

Facility location, which is encountered in many fields such as network design, transportation and distribution logistics, is a strategic issue for almost every company. The capacitated p-median problem (CPMP) is one of the well-studied topics in facility location problems. It is to locate p facilities, each having a given maximum capacity to serve a given set of clients at the minimum transportation cost, where every client must be served by one facility. In this paper, we present a different but realistic CPMP model. In the new model, in order to guarantee the profitability, each potential plant has a minimum demand that must be satisfied by assigning clients (suppliers) to it. Different from traditional CPMP model, the fixed operating cost of facilities is also considered. A Lagrangian relaxation approach is adopted to decompose our model into 0-1 knapsack problems, which are solved by Martello and Toth’s algorithm. Two heuristics are proposed to construct a feasible solution based on the solution of the relaxed problem obtained in each iteration of the corresponding dual optimization. Their performances are compared in this paper. Numerical experiments indicate that the proposed approach can find near-optimal solutions for randomly generated instances with the average gap 0.7% between upper bound and lower bound.