Mixed integer optimization for the combined capacitated facility location-routing problem

This paper combines the multi-product variant of the capacitated facility location problem with multicommodity flow routing. This problem shares many similarities with the digital content placement and retrieval problem when minimizing the cost of installing a set of servers for storing multiple sets of data objects (files) and connecting clients to them in order to satisfy their demands while accounting for the induced arc load. However, the regular formulation of the facility location problem models the cost of allocating the demand originated by individual clients independently of the others. The combination of this problem with flow routing removes the demand allocation independence property, leading to strongly interrelated facility location and routing decisions. Moreover, involving multiple types of data objects yields facility capacity constraints with a more complex structure than the simple superposition of per-product constraints. This paper proposes a mixed integer programming formulation for this combined problem and evaluate the computational performance for solving it. Experimental results obtained with this combined formulation are provided and compared with those obtained when solving these two problems sequentially. With the latter, the routing cost increases (up to doubling) or the facility installation cost increases (up to requiring more than twice the number of facilities) compared to the cost values obtained by solving the combined problem. This paper also extends the combined model with demand rerouting to evaluate its cost gain compared to demand protection as provided by the reliable facility location model. The results obtained with the combined formulation indicate that when subject to representative failure probabilities, demand rerouting can significantly outperform demand protection up to a factor four