Solution approaches for single-source capacitated multi facility weber problem

Damgacıoğlu, Haluk
Single Source Capacitated Multi Facility Location Problem (SSCMFLP) is a continuous location-allocation problem such that determining the locations of p facilities in the plane and allocations of n demand points to only one facility by considering the capacity restriction of each facility so as to minimize total transportation cost to satisfy n demand points from p facilities. In addition to Mixed Integer Non-Linear Programming formulation of the problem in the literature, we give a new formulation for the problem using Second Order Cone Programming. Since the problem is a variant of MWP well-known NP-hard planar location-allocation problem and it is easily reducible to MWP, SSCMWP is hard to solve and it can be classified in NPhard. Therefore, these two formulations do not solve the problem optimally even for small and medium size problems. Moreover, in this study, we propose three heuristics based on two phase location allocation algorithm iteratively to tackle the problem effectively and efficiently. We first find the initial locations of facilities by using Pdistance clustering algorithm. We solve allocation part with given locations by solving generalized assignment problem (GAP) and then by using new assignments we determine each facility location by using P-distance clustering algorithm iteratively. Our heuristics differ in solution approaches for GAP. we solve the problem optimally by using CPLEX. Since CPLEX is an exponential time solver, we give two alternative heuristics for CPLEX which are branch and bound heuristic and Very Large Scale Neighborhood Search (VLNS). We tested our heuristics’ performance by comparing results with each other and other heuristics in the literature on well-known test data for continuous location problems.
Citation Formats
H. Damgacıoğlu, “Solution approaches for single-source capacitated multi facility weber problem,” M.S. - Master of Science, Middle East Technical University, 2014.