(61d) Global Optimization Algorithm for Capacitated Multi-Facility Continuous Location-Allocation Problems

In this paper, we address the design of networks that involves the selection and location of facilities in the continuous 2-dimensional space. The problem is formulated as a version of the continuous facility location and allocation problem with limited capacity, also known as the Capacitated Multi-facility Weber Problem (CMWP) [1]. The objective of this type of problem is to determine locations in continuous 2-dimensional space for opening new facilities based on their maximum capacity and the given coordinates of the suppliers or customers. Cooper [2] was the first to attempt solving this type of location-allocation problem in 1972. He proposed exact and approximate solution methods based on the property that an optimal allocation occurs at the extreme point of the transportation polytope, while the optimal set of locations lies on the convex hull of the locations of the existing facilities. Sherali and Shetty [3] develop a cutting plane algorithm for the rectilinear distance location-allocation problem. Sherali and Tuncbilek [4] propose a branch-and-bound algorithm for the squared-Euclidean distance location-allocation problem. Sherali, Al-Loughani, Subramanian [5] developed a branch-and-bound algorithm based on the partitioning of the allocation space that finitely converges to a global optimum within a tolerance.

We propose an extension of the original CMWP that considers fixed cost for opening new facilities, fixed transportation costs, and two sets of fixed-location points: suppliers i and customers j [6]. The latter goes back to the original Weber problem, in which the location of the facility had to be determined in relation to 2 suppliers and 1 customer. The model is a nonlinear Generalized Disjunctive Programming (GDP), reformulated as a nonconvex Mixed-Integer Nonlinear Programming (MINLP). This is, to the best of our knowledge, an original problem not reported before that has high practical applicability.

We develop a bilevel decomposition algorithm that consists of decomposing the problem into a master problem and a subproblem. The master problem is based on a relaxation of the nonconvex MINLP, which yields an MILP that predicts the selection of facilities and their links to suppliers and customers, as well as a lower bound on the cost of problem. The subproblem corresponds to a nonconvex NLP of reduced dimensionality that results from fixing the binary variables in the MINLP problem, according to the binary variables predicted in the MILP master problem. Based on the bounding properties of their subproblems, ε-convergence is proved for this algorithm.

We apply the proposed method to random instances varying from 2 suppliers and 2 customers to 40 suppliers and 40 customers, from one type of facility to 3 different types, and from 2 to 32 potential facilities. The results show that the algorithm is more effective at finding global optimal solutions than general purpose global optimization solvers tested.

[1] Brimberg, J., Hansen, P., Mladonovic, N., Salhi, S.: A survey of solution methods for the continuous location allocation problem. International Journal of Operational Research 5(1), 1–12 (2008).

[2] Cooper, L.: The transportation-location problem. Operations Research 20(1), 94-108 (1972).

[3] Sherali, A.D., Shetty, C.M.: The rectilinear distance location-allocation problem. A I I E Transactions 9(2), 136-143 (1977).

[4] Sherali, H.D., Tuncbilek, C.H.: A squared-euclidean distance location-allocation problem. Naval Research Logistics (NRL) 39(4), 447-469 (1992).

[5] Sherali, H.D., Al-Loughani, I., Subramanian, S.: Global optimization procedures for the capacitated Euclidean and l_p distance multifacility location-allocation problems. Operations Research 50(3), 433-448 (2002).