An evolutionary algorithm for the capacitated p-median problem

Abstract In the capacitated p -median problem there is a set of demand locations (customers) and a set of facility sites (medians). We have to select locations for p- facilities and select for every facility a disjunct subset of customers together with the facility so that the sum of service demands of customers do not exceed the service capacity of their facility and every customer belongs to exactly one facility. The aim is to minimize the total transportation costs while satisfying the demands of the customers from the facilities. In this paper a new hybrid evolutionary algorithm is described for the problem. It uses two techniques to generate the descendants: either estimation of distribution algorithm and sampling the resulting probability models, or applying the usual operators of evolutionary algorithms (selection, mutation). The estimation of distribution algorithm uses two probability models to generate a solution: one for generation of the set of medians and another for subset generation to every median. The algorithm can use two mutation operators, too, and improves the solution with local searches. We tested our algorithm on benchmark problems and it belongs to the best metaheuristics for the small and medium size capacitated p -median problems. For large-size problems, an island model improves the quality and runtime of the results. Our algorithm is a new method for large-size CPMP if it used our island model together with mathematical programming as post-processing technique as other authors did, we would expect similar results to theirs.