Abstract:
This thesis focuses on an extension of the capacitated facility location problem. Every demand point consists of multiple customer classes whose demands are satisfied by facilities having different capacities and costs for each facility class. We give integer and mixed-integer linear programming formulations respectively for single-source and multi-source versions of this problem. Then we propose exact and heuristic solution procedures. Capacitated facility location problems are difficult to solve exactly. However, many accurate and efficient heuristic methods have been introduced for these problems. In the light of these researches, we develop Lagrangean heuristics in order to find near optimal solutions for our problems. The Lagrangean dual problems are solved using three different subgradient optimization methods, namely classical subgradient optimization, deflected subgradient optimization and volume algorithm. The Lagrangean heuristics with the mentioned subgradient optimization methods are implemented and computational results based on extensive experiments are also provided. Furthermore, an exact solution technique based on Benders’ decomposition is developed and implemented for the multi-source problem. Although optimal solutions are found for some small test problems, this exact solution algorithm converges very slowly.
