Two-phase heuristics for a multi-period capacitated facility location problem with service-differentiated customers

We investigate a recently introduced extension of the multi-period facility location problem that considers service-differentiated customer segments. Accordingly, some customers require their demands to be met on time, whereas the remaining customers accept delayed deliveries as long as lateness does not exceed a pre-specified threshold. In this case, late shipments can occur at most once over the delivery lead time, i.e. an order cannot be split over several time periods. At the beginning of the multi-period planning horizon, a number of facilities are in place with given capacities. A finite set of potential facility sites with multiple capacity levels is also available. The objective is to find the optimal locations and the opening, resp. closing, schedule for new, resp. existing, facilities that provide sufficient capacity to satisfy all customer demands at minimum cost. In this paper, we propose four heuristics that construct initial solutions to this problem and subsequently explore their neighborhoods via different local improvement mechanisms. Computational results with randomly generated instances demonstrate the effectiveness of the proposed heuristics. While a general-purpose mixed-integer programming solver fails to find feasible solutions to some instances within a given time limit, the heuristics provide good solutions to all instances already during the constructive phase and in significantly shorter computing times. During the improvement phase, the solution quality is further enhanced. For nearly one-fifth of the instances, the heuristic solutions outperform the best solutions identified by the solver.