Solving the rectilinear distance location-allocation problem using lagrangean relaxation and subgradient optimization

Abstract

This thesis is concerned with the rectilinear distance location-allocation problem, which seeks the location of capacitated facilities along with the allocation of their products to customers, so as to minimize total cost proportional to the rectilinear distance and the amount shipped. Knowing each customer’s coordinates, unit cost from each facility to that customer, the customer’s demand, and the supply at each facility, we determine each facility’s optimal location and allocation simultaneously. This is a non-convex optimization problem and difficult to solve exactly. However, there has been research concerning with the application on the development of accurate and efficient heuristic methods. In this work we continue this line of research and propose new Lagrangean relaxation based heuristics by using the new semi-Lagrangean relaxation approach. The subproblems solved in the semi-Lagrangean relaxation are almost as in- tractable as the original one although the solution quality is very high. We there- fore propose a subgradient algorithm to solve them approximately in order to increase efficiency. This new approach is implemented and computational results based on extensive experiments are also provided.