Lagrangean Relaxation Based Approximate Approach to the Capacitated Location Problem

Abstract

When a distribution system is to be designed, limits on terminal capability often must be taken into account. These capacity constraints in this and other facility location problems constitute severe obstacles in exact solving processes. Within this paper, we focused on study of approximate methods based on Lagrangean relaxation of the capacity constraints, which has several advantageous properties. The first of them is that the relaxed problem, known as the uncapacitated location problem, can be solved exactly even for real sized instances [6], [4]. The second useful property of the Lagrangean relaxation is that the objective function value of the optimal solution of the relaxed problem provides lower bound of the optimal solution of the original problem. We present two methods for obtaining suitable values of Lagrangean multipliers. The classical one is based on a sub-gradient method applied on capacity constraints after their special adjustment. The second method is designed as an adaptive method with random experiments for determination of candidates for move from the current solution to the next one. These two methods were tested, compared and the associated results are reported in the concluding part of this paper.