Mixed integer programming based nested partition algorithm for facility location optimization problems

Abstract

Facility location optimization is very important for many retail industries, such as banking network, chain stores, and so on. Maximal covering location problem (MCLP) is one of the well-known models for these facility location optimization problems, which has earned extensive research interests. However,various practical requirements limit the application of the traditional formulation of MCLP, and the NP-hard characteristic makes effective approaches for large scale problems extremely difficult. This paper focuses on a facility location problem motivated by a practical project of bank branching. The traditional MCLP formulation is generalized as a mixed integer programming (MIP) with considerations of various costs and revenues, multi-type of facilities, and flexible coverage functions. A CPLEX-based hybrid nested partition algorithm is developed for large scale problems, and heuristic-based extensions are introduced to deal with extremely large problems. Our formulation and algorithm are embedded into an asset called IFAO-SIMO. Numerical results demonstrate the effectiveness and efficiency of our approach. ©2008 IEEE.