Lagrangean heuristic fio the capacitated multi-facility location allocation problem

Abstract

In this study, we consider the capacitated multi-facility location-allocation problem, also called multi-facility Weber problem. It is concerned with the determination of the location of m new facilities having known capacities, as well as the allocation of their supplies, to satisfy the demand of customers, such that the total transportation cost proportional to the distance between customers and facilities is minimized. The demand and location of each customer are given. This problem has a nonconvex objective function and is very difficult and sometimes even impossible to solve exactly. Therefore, using a discrete approximation becomes a promising strategy to obtain good approximate solutions. We first present a mixed integer linear programming approximation of the capacitated multi-facility Weber problem. We apply Lagrangean relaxation and subgradient optimization-based heuristics on this approximation and then propose new heuristics for the continuous version of the problem which also make use of these Lagrangean heuristics. Computational results on the test instances indicate that these heuristics are efficient and accurate. We also study on exact solution procedures. We make use of the fact that the capacitated multi-facility Weber problem has a special transportation network structure and the optimal solution occurs at an extreme point of the feasible region. The procedures we work on range from branch-and-bound methods to affine scaling methods, to collapsing polytopes, and to send-and-split methods. Although we could not find an exact solution methodology by using these procedures, we were able to gain more insight about the problem and this can help us in the development of other heuristic methods in the future.