Année
2012
Abstract
Given a set of customers, a set of potential facility locations and some inter-connection nodes, the goal of the Connected Facility Location problem (ConFL) is to find the minimum-cost way of assigning each customer to exactly one open facility, and connecting the open facilities via a Steiner tree. The sum of costs needed for building the Steiner tree, facility opening costs and the assignment costs needs to be minimized. If the number of edges between a pre-specified node (the so-called root) and each open facility is limited, we speak of the Hop Constrained Facility Location problem (HC ConFL). This problem is of importance in the design of data-management and telecommunication networks. In this article we provide the first theoretical and computational study for this new problem that has not been studied in the literature so far. We propose two disaggregation techniques that enable to model HC ConFL: i) as directed (asymmetric) ConFL on layered graphs, or ii) as the Steiner arborescence problem (SA) on layered graphs. This allows for usage of best-known MIP models for ConFL or SA to solve the corresponding hop constrained problem to optimality. In our polyhedral study, we compare the obtained models with respect to the quality of their LP lower bounds. These models are finally computationally compared in an extensive computational study on a set of publicly available benchmark instances. Optimal values are reported for instances with up to 1300 nodes and 115 000 edges.
LJUBIC, I. et GOLLOWITZER, S. (2012). Layered Graph Approaches to the Hop Constrained Connected Facility Location Problem. INFORMS Journal on Computing, 25(2), pp. 256-270.