A biased-randomised algorithm for the capacitated facility location problem with soft constraints

Abstract

This paper analyzes the single-source capacitated facility location problem (SSCFLP) with soft capacity constraints. Hence, the maximum capacity at each facility can be potentially exceed by incurring in a penalty cost, which increases with the constraint-violation gap. In some realistic scenarios, this penalty cost can be modelled as a piecewise function. As a result, the traditional cost-minimization objective becomes a non-smooth function that is difficult to optimise using exact methods. A mathematical model of this non-smooth SSCFLP is provided, and a biased-randomized iterated local search metaheuristic is proposed as a solving method. A set of computational experiments is run to illustrate our algorithm and test its efficiency.