Groupe d’études et de recherche en analyse des décisions

G-2019-29

Heuristics for the dynamic facility location problem with modular capacities

, , et

This paper studies the Dynamic Facility Location Problem with Modular Capacities (DFLPM). We propose a linear relaxation based heuristic (LRH) and an evolutionary heuristic that hybridizes a genetic algorithm with a variable neighborhood descent (GA+VND) to solve it. The problem is a generalization of several facility location problems and consists in determining locations and sizes of facilities to minimize location and demand allocation costs with decisions taken periodically over a planning horizon. The DFLPM is solved using two heuristics tailored for different network configurations and cost structures. Experiments are reported comparing them to a state-of-the-art mixed integer programming (MIP) formulation for the problem from the literature solved by CPLEX. For the existing benchmark instances, the solution generated by LRH improved by VND finds solutions within 0.03% of the optimal ones in less than half of the computation time of the state-of-the-art method from the literature. In order to yield a better representation of real-life scenarios, we introduce a new set of instances for which GA+VND proved to be an effective approach to solve the problem, outperforming both CPLEX and LRH methods.

, 27 pages