Variable neighborhood search for the p-next center problem with discount factor

Abstract

The p -next center problem (PNCP) is an extension of the well-known p-center problem, which captures the situation when one or more centers suddenly fail due to some technical problem. If a user is faced with the failure of its primary center, it is being redirected to its backup center - the center that is closest to the primary one. The goal of the PNCP is to minimize the maximum distance that a user must travel to its backup center via the primary center. In practice, the distance that the user travels is often expressed in travel cost or travel time, and the communication between the centers is cheaper or faster. In order to capture this real-world situation, we involve a discount factor for the travel cost or time between the centers in the objective function of the classical PNCP. A metaheuristic method based on variable neighborhood search is used as a solution method for the considered variant of the PNCP. The set of computational experiments on instances from the literature is performed to investigate the impact of the discount factor on the obtained solutions and the corresponding objective function values.