An Opportunity Cost-Based Modified Genetic Algorithm for the P − k Median Problem

Abstract

Median problems are combinatorial problems that associate the allocation cost of demand points to the selection of different location sites for a number of facilities that satisfy the total demand. This study focuses on the P − k median problem of minimizing the total weighted distance between n demand points and these location sites when the number of existing facilities, k, on a given network is increased to P. Initial combinations of possible locations for the additional P − k facilities areiteratively improved using a proposed modified genetic algorithm. The algorithm implements a new opportunity cost-based child reproduction procedure for the generation of better solutions with biased parent selection probabilities. This creates the best possible offspring without affecting the locations of existing facilities while current information from having the existing k facilities simplifies the choice of locations for increasing the number of facilities from k to P. The generated combinations of facility locations are tested on the Galvao-100 median set deriving 30 P − k median problems from the Lagrangian relaxation solutions. Average percentage difference from the optimal solution found at 0.52% outperforms the neighborhood search improvement made on the myopic algorithm at higher values of P − k .

Keywords: facility location, genetic algorithm, median problems, opportunity cost