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.
Facility location Capacitated p-median problems Transportation Lagrangian relaxation Knapsack problems
Zhen YANG Haoxun CHEN Feng CHU
Institute Charles Delaunay (ICD,FRE CNRS 2848) Industrial systems optimization laboratory,LOSI University of Technology of Troyes 12 rue Marie Curie,BP 2060,Troyes,10010,France
国际会议
北京
英文
2007-05-30（万方平台首次上网日期，不代表论文的发表时间）