Solving the capacitated multifacility Weber problem approximately

Abstract

In this study, we consider the capacitated multifacility Weber problem which is concerned with locating m facilities in the plane, and allocating their limited capacities to n customers at minimum total cost. In this group of location-allocation problems, the only cost dealt with is the transportation cost that is proportional to the distance between the facility and the customer. The capacities of each facility and the demands and the locations of each customer are predetermined and given as parameters. This problem is an intractable non-convex optimization problem and difficult to solve. Therefore, using approximation strategies to compute efficient and accurate lower and upper bounds for the capacitated multifacility Weber problem can be a good approach. We first concentrate on the alternating location allocation heuristics. Then we continue with the discretization strategies and the Lagrangean relaxations of the approximating models. Some specific lower bounding algorithms are also defined by using the special properties of some of the distance functions. In addition to them, the relaxation of the main model is investigated and a Lagrangean heuristic is devised. In this heuristic, either a linear relaxation or exact solution of the Lagrangean subproblem is found by using column generation and branch and price algorithms combined with concave minimization. Although an exact solution methodology is not found, the approximation methods give accurate results. The tight bounds calculated by using these algorithms can be convenient in searching the exact solutions for this group of problems.