An Opportunity Cost-Based Genetic Algorithm for a Modified Capacitated p-Median Problem

Abstract

Median problems are combinatorial problems of searching for p facility locations (medians) that will serve a network of n demand nodes at a minimum cost. A Capacitated p-Median Problem (CPMP) allocates the demand of all nodes to the p facilities subject to the service capacity of each facility. In view of a future increase in demand of the network, this study presented a modified CPMP, called the CPkMP, which incorporates the network’s existing number of k facilities in search of new and
additional p−k facility locations. This study evaluated the performance and applicability of a recently developed genetic algorithm (GA) that was used for a non-capacitated p-Median Problem (PMP) in order to solve the CPkMP. The proposed GA completes a combination of the needed p − k medians
by implementing a child generation procedure that is based on opportunity costs. When the closest facility location that can satisfy the demand of a node is removed from the list of candidate locations, the demand is reassigned to another facility farther from the node, and the lost opportunity of not choosing the closest facility to minimize the distance traveled is called the opportunity cost (OC). The opportunity cost genetic algorithm (OC-GA) removes from the set of candidate locations a candidate with the lowest total opportunity costs arising from the additional distance of reassigning the network demands to farther candidate facilities. Computational tests of the OC-GA on ten CPMP problems from literature with known optimal solutions showed a 4.5% relative error from the known optimal solution. When the locations for the k existing facilities are selected from the optimal solution of CPMP, the needed additional p−k facilities in the CPkMP tend to converge to the remaining members of this optimal solution. More so, when the k existing facilities are different from the medians in the optimal CPMP solution, 50 to 70 percent of the searched p−k locations are part of the CPMP optimal solution.