Districting for Micro Financial Institutions: A Matheuristic Framework for Large Scale Instances

Abstract: In this paper, we study a districting problem arising in microfinancial institutions, where one seeks to identify potential branch offices and allocate customers to their respective office, balancing several constraints while minimizing the distance of the customers to their assigned branch. We present an integer programming model and propose a hybrid metaheuristic for this problem. The proposed matheuristic is comprised of three phases, namely, (i) construction, where an at- tempt is made to build a feasible solution from scratch following a location-allocation strategy; (ii) constraint repair, where possible solution infeasibility is handled; and (iii) local search, where an at- tempt to improve the solution is made by means of a variable neighborhood descent procedure. Five different branch location procedures are developed and tested for the construction phase. Three different local move operators are designed and tested for the local search phase. The proposed matheuristic and each of its components are empirically assessed over a variety of instances. The computational results show the effectiveness and robustness of the proposed method and each of its components. When compared to an existing commercial solver, the proposed method was observed to obtain solutions of better quality significantly faster.