Limits of the Multiplier Adjustment Approach to Capacitated Location Problem

Abstract

This contribution deals with a distribution system design problem, in which the located facilities satisfy all customer demands under limited abilities. The objective is to minimize the total costs, including both fixed charges and service costs. A special approach based on Lagrangean relaxation will be discussed here for its ability to cope with limited capacities of located facilities. Using the Lagrangean relaxation, the model of the original problem is rearranged to a model, which can be solved by exact algorithms for considerably large size. The capacities of the located facilities bring serious difficulties concerning solving technique, in the cases, where real-sized facility location problems are solved. In contrast to an uncapacitated facility location problem, which can be solved exactly in reasonable time for real-sized case containing hundreds of possible locations and thousands of customers.
In this paper, we shall discuss a transformation of the capacitated location problem into the uncapacitated location problem by means of Lagrangean relaxation of capacity constraints. To demonstrate the efficiency of the studied approach, numerical experiments were performed and their results are reported in the concluding part of this paper.