TY - JOUR
T1 - Heuristics for a multi-period facility location problem with delayed demand satisfaction
AU - Sauvey, Christophe
AU - Melo, Teresa
AU - Correia, Isabel
N1 - UID/MAT/00297/2019
Sem PDF conforme despacho.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - 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 other 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 more than one-fourth of the instances, the heuristic solutions outperform the best feasible solutions identified by the solver.
AB - 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 other 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 more than one-fourth of the instances, the heuristic solutions outperform the best feasible solutions identified by the solver.
KW - Constructive heuristics
KW - Delivery lateness
KW - Facility location
KW - Local improvements
KW - Multi-period
UR - http://www.scopus.com/inward/record.url?scp=85076552138&partnerID=8YFLogxK
U2 - 10.1016/j.cie.2019.106171
DO - 10.1016/j.cie.2019.106171
M3 - Article
AN - SCOPUS:85076552138
SN - 0360-8352
VL - 139
JO - Computers & Industrial Engineering
JF - Computers & Industrial Engineering
M1 - 106171
ER -